Definition:Hat-Check Distribution

From ProofWiki
Jump to navigation Jump to search

Definition

Let $X$ be a discrete random variable on a probability space $\struct {\Omega, \Sigma, \Pr}$.

Let $\Img X = \set {0, 2, 3, \ldots, n}$

Let $X$ represent the number of elements in a a totally ordered set with $n$ elements that are not in the correct order.

Then $X$ has the hat-check distribution with parameter $n$ (where $n > 0$) if and only if:

Definition 1

$X$ has the hat-check distribution with parameter $n$ if and only if:

$\ds \map \Pr {X = k} = \dfrac 1 {\paren {n - k }!} \sum_{s \mathop = 0}^k \dfrac {\paren {-1}^s} {s!}$


Definition 2

$X$ has the hat-check distribution with parameter $n$ if and only if:

$\ds \map \Pr {X = k} = \dfrac {!k} {n! } \dbinom n k$

where:

$!k$ is the subfactorial of $k$
$\dbinom n k$ is the binomial coefficient.


Hat-Check Triangle

$\begin{array}{r|rrrrrrrrrr} n & !0 \binom n 0 & !1 \binom n 1 & !2 \binom n 2 & !3 \binom n 3 & !4 \binom n 4 & !5 \binom n 5 & !6 \binom n 6 & !7 \binom n 7 & !8 \binom n 8 & !9 \binom n 9 \\ \hline 0 & 1 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 \\ 1 & 1 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 \\ 2 & 1 & 0 & 1 & 0 & 0 & 0 & 0 & 0 & 0 & 0 \\ 3 & 1 & 0 & 3 & 2 & 0 & 0 & 0 & 0 & 0 & 0 \\ 4 & 1 & 0 & 6 & 8 & 9 & 0 & 0 & 0 & 0 & 0 \\ 5 & 1 & 0 & 10 & 20 & 45 & 44 & 0 & 0 & 0 & 0 \\ 6 & 1 & 0 & 15 & 40 & 135 & 264 & 265 & 0 & 0 & 0 \\ 7 & 1 & 0 & 21 & 70 & 315 & 924 & 1855 & 1854 & 0 & 0 \\ 8 & 1 & 0 & 28 & 112 & 630 & 2464 & 7420 & 14832 & 14833 & 0 \\ 9 & 1 & 0 & 36 & 168 & 1134 & 5544 & 22260 & 66744 & 133497 & 133496 \\ \end{array}$


Also see

  • Results about the hat-check distribution can be found here.