Probability that Santa will give $N$ different presents to exactly $N-1$ kids

Question

Santa is randomly giving $N$ different presents to $N$ different kids.

1. what is the probability that Samuel doesn't get a present?

2. what is the probability that every kid got a present?

3. what is the probability that there exists a kid who didn't get a present

4. what is the probability that exactly one kid didn't get a present?

My Attempt:

The first three sections I managed to do. For the fourth section - I'm lost.

1. calculating the Complementary event: Probability that Samuel didn't get the first present: $1 - \frac{1}{N}$ repeating this process $N$ times: $$P(A) = \left(1 - \frac{1}{N}\right)^N$$

2.$ \ P(B) = \frac{N!}{N^N}$ where $N!$ is the number of different ways to give away $N$ presents

3.$\ P(C) = 1 - \frac{N!}{N^N}$

4.$ \ \Omega = N^N$.

For the numerator: if exactly one kid did not get a present, then there exists exactly one kid who got $2$ presents. There exists $N-1$ kids who did get a present, which means there's $N-1!$ (that's a guess) to give $N$ presents to $N-1$ kids?

Answer 1

Your answers to the first three questions are correct.

If $N$ different presents are distributed randomly to $N$ children, what is the probability that exactly one child does not receive a present?

There are $N^N$ ways to distribute the presents.

If exactly one child does not receive a present, exactly one child must receive two presents. There are $N$ ways to choose the unlucky child who does not receive a present. That leaves $N - 1$ ways to select the lucky child who receives two presents. There are $\binom{N}{2}$ ways to select which two presents that child receives. There are $(N - 2)!$ ways to distribute the remaining $N - 2$ presents to the remaining $N - 2$ children. Hence, the number of favorable cases is $$\binom{N}{1}\binom{N - 1}{1}\binom{N}{2}(N - 2)! = N!\binom{N}{2}$$

Hence, the probability that exactly one child does not receive a present is $$\frac{N!\binom{N}{2}}{N^N}$$

Answer 2

Your approach starts out good, but we would have N-2 children with exactly one present, 1 with no presents, and 1 with two presents. If the children and presents are distinguishable, then then are N ways to choose who doesn't get a present, and once we choose that child, there are N-1 options left for who gets two presents.

There are ${N \choose 2}$ ways to pick what presents the child with two presents gets, and (N-2)! ways to distribute the remaining presents. Alternatively, there are N! ways to distribute the presents, but the order that the double presents get chosen doesn't matter, so we should divide by 2!=2.

That is, we can think of there being N buckets. There are N(N-1) ways to give one child two buckets and one child none. There are N! ways to put presents in the buckets. Since the child who gets two presents doesn't care which of their two buckets gets which of their two presents, we should divide by 2. So the numerator should be N(N-1)N!/2.

Answer 3

Probability is $0$ because there is no Santa Claus.

Okay....

I think one subtle trick is not to thing in terms of which kid gets which present but thinking instead which present goes to which kid.

There are $N$ presents and each present can can go to one of $N$ kids so there are $N^N$ outcomes.

1) if Samuel didn't get a present then each present could have gone to any of the $N-1$ other children. So there are are $(N-1)^N$ ways this could occur. So the probability that Samuel didn't get a present is

$\frac {(N-1)^N}{N^N} = (\frac {N-1}{N})^N = (1 - \frac 1N)^N$.

2) For every kid to get a present there are $N$ kids that could get the first, $N-1$ kids that could get the second and so on. There are $N!$ ways to distribute so the probability is:

$\frac {N!}{N^N}$.

3) Well, that'd be $1$ minus the probability every kid got a present:

$1 - \frac{N!}{N^N}$.

4) Well, I'd do it this way. You are correct is one kid who go two presents. There are $N$ choices for the kid who didn't get a present. There are $N-1$ choices for the kid who got two presents. There are ${N\choose 2}$ choices for which two presents that snot-nosed kid got. If the remaining $N-2$ kids and $N-2$ presents there are $(N-2)!$ ways to arrange them.

So there are $N*(N-1)*{N\choose 2}*(N-2)!= \frac {N^2(N-1)^2}2(N-2)!$ ways for exactly one kid to have his entire life ruined and be bitter and resentful forever. So the probability is

$\frac {N^2(N-1)^2(N-2)!}{2N^N} =\frac {(N-1)(N-1)!}{2N^{N-1}}$

...

By the way.

Q: Why can't Santa Claus and Mae West fit into the same phone booth?

A: When was the last time you saw a phone booth?

(When the joke was first told the answer was "There is no Santa Claus" -- and a good thing too if he's just going to give out presents randomly and not care if some poor kids don't get any and let others get more than one.... what a jerk.)