# Prob 27. Discrete distributions - Blitzstein and Hwang Ch. 3

I would like someone to verify my line of thoughts on this problem. This is based de Montmort's matching problem.

1. Recall de Montmort's matching problem from chapter 1: in a deck of $n$ cards labeled $1$ through $n$, a match occurs when the number on the card matches the card's position in the deck. Let $X$ be the number of matching cards. Is $X$ binomial? Is $X$ hypergeometric?

Solution.

Suppose we are interested in the probability that there is $X=1$ matching card.

The matching card can be $1$ of $n$ cards in the deck. There are $(n-2)!$ ways to assign different non-matching card numbers to the remaining $n-1$ cards.

$P(X=1)=\frac{{n\choose1}(n-2)!}{n!}=\frac{1}{n-1}$

On the same lines,

$P(X=k)=\frac{{n\choose{k}}(n-(k-1))!}{n!}=\frac{n!}{(n-k)!k!}\cdot\frac{(n-(k-1))!}{n!}=\frac{1}{k!(n-k)}$

Perhaps, the above formulation for the PMF of $X$ is correct. I know, that we are sampling without replacement. However, I am having difficulty expressing this as a hypergeometric story proof.

Example. An urn contains $w$ white balls, and $b$ black balls, and $n$ balls are drawn at random, without replacement. The number of white balls in the sample follows $HGeom(w,b,n)$.

Your pmf is incorrect. Note that $\{X=k\}$ means that "precisely" $k$ cards are in correct position, and NO OTHER card is in correct position. When you are doing things like $(n-k)!$ you ARE allowing the remaining cards to be in correct positions.
Instead, look at $P[X\geq k]=\dfrac{{n\choose k}(n-k)!}{n!}$. You select the $k$ cards that are always in position, and then you allow the other $n-k$ cards to permute among themselves. Since you have selected $k$ cards in position, this guarantees $X\geq k$. Simplification yields $P(X\geq k)=\dfrac{1}{k!}$
Now use the fact that $P(X=k)=P(X\geq k)-P(X\geq k+1)$.