Micromass' big July Challenge

[mfb]

Then something is wrong with your simulation. Edit: Sorry, misread the post, the result is fine.

I did it the long way: make a huge 365x2016 matrix, keep track of the probability that N days are birthdays for M persons. The result: 0.230987
Directly between my the estimates in my previous post. For reference, here are the other relevant options for k days that are not birthdays:
>5 days: 0.0031978085
5 days: 0.0115619723
4 days: 0.0419113291
3 days: 0.1193038793
2 days: 0.2500413533
1 days: 0.3429964758
0 days: 0.2309871816

 

[Clever Penguin]

I think 6. may have something to with combinations, permutations, and factorials?

 

[micromass]

Since $SO_3(ℝ)$ is the covering group of $SU_2(ℂ)$

Isn't it the other way around? $SU_2(\mathbb{C})$ is the universal covering group of $SO_3(\mathbb{R})$.

 

[fluidistic]

Then something is wrong with your simulation.
(...)
0 days: 0.2309871816

This is not that much different from the result I obtained. I don't understand why my simulation is wrong, I only did 10k trials. Had I done more, it would have converged toward the real ratio. My ratio is 0.2327 and you got 0.2310.

 

[fresh_42]

Isn't it the other way around? $SU_2(\mathbb{C})$ is the universal covering group of $SO_3(\mathbb{R})$.

As I saw my mistake it had been too late to edit it. But the quotient is $\{± I\}$ so it was not that important.

 

[mfb]

This is not that much different from the result I obtained. I don't understand why my simulation is wrong, I only did 10k trials. Had I done more, it would have converged toward the real ratio. My ratio is 0.2327 and you got 0.2310.

Sorry, I misinterpreted your post, I read it as "in all of 2327 simulations all days were birthdays".
2327 out of 10000 is perfectly reasonable.

 

[PeroK]

This is not that much different from the result I obtained. I don't understand why my simulation is wrong, I only did 10k trials. Had I done more, it would have converged toward the real ratio. My ratio is 0.2327 and you got 0.2310.

My knowledge of statistics is a bit shaky, but I think the standard deviation of a binomial distribution with probability 0.2310 and 10k trials is about 42. So, you would expect 2310 successes, plus or minus 42. The 2327 is, therefore, well within one standard deviation.

 

[andrewkirk]

Here is my proposed solution to problem 1. I have found the mode and median. The mean is left for somebody else, because it would be messy. It would be easy enough to compute numerically though.
Let the two points have coordinates (X_1,Y_1),\ (X_2,Y_2), where the coordinates are pairwise independent and each is drawn from a uniform distribution on [0,1]. Then the squared length L^2 of the connecting line segment is given by:
$$L^2=(X_2-X_1)^2+(Y_2-Y_1)^2$$
Let us write X=X_2-X_1,\ Y=Y_2-Y_1 so that L^2=X^2+Y^2. Then X,Y are mutually independent and the cdf of X is F_X(c)=Pr(X<c)=Pr(X_2<X_1+c) which is the area of the region of the unit square in the number plane above the line y=x+c. A little geometry shows that F_X(c) is equal to \frac12 (1+2c+c^2) if c\in[-1,0] and \frac12 (1+2c-c^2) if c\in[0.1], The pdf is f_X(c)=1+c if c\in[-1,0] and 1-c if c\in[0.1], F_Y and f_Y have the same form. Note that the pdfs are even functions.

Then the cdf of L is F_L(l) which is the integral over the origin-centred circle of radius l of f_X(x)f_Y(y), excluding parts of the circle that lie outside the square S\equiv[-1,1]\times[-1,1]. If we restrict to l<1, the whole circle lies inside S so we can calculate the integral without having to break it into sections. It is simplest as a polar integral. Since both the pdfs are even, the full integral is equal to four times the integral in the first quadrant, which is
$$4\int_0^l \int_0^{\frac\pi2} f_X(r\cos \theta)f_Y(r\sin\theta)\,r\,d\theta\,dr$$
Hence we have
\begin{eqnarray*}
F_L(l)&=4\int_0^l \int_0^{\frac\pi2} (1-r\cos \theta)(1-r\sin\theta)\,r\,d\theta\,dr\\
&=4\int_0^l \int_0^{\frac\pi2} (1-r\cos \theta-r\sin\theta+r^2\cos\theta\sin\theta)\,r\,d\theta\,dr\\
&=4\int_0^l \left[ \theta-r\sin \theta+r\cos\theta+\frac12r^2\sin^2\theta)\right]_0^{\frac\pi2}\,r\,dr\\
&=4\int_0^l \left( \frac\pi2-r-r+\frac12r^2\right)\,r\,dr\\
&=4 \left[ \frac\pi2\cdot\frac12r^2-\frac23r^3+\frac18r^4\right]_0^l\\
&=\pi l^2-\frac83 l^3+\frac12l^4
\end{eqnarray*}

The pdf is
$$f_L(l)=\frac d{dl}F_L(l)=2\pi l-8l^2+2l^3$$

The mode will occur when \frac d{dl}f_L(l)=0, that is:
$$0=2\pi-16l+6l^2$$
This has roots at \frac13(4-\sqrt{16-3\pi}) of which only the lower one is in the admissible range, giving a value of about 0.48.

Hence the mode is approx 0.48.

To find the median we solve the equation F_L(x)=0.5. That is
$$\pi l^2-\frac83 l^3+\frac12l^4=0.5$$
Numerically solving this, we find it has four real roots, of which the second is at approx 0.51. The LHS of the equation is increasing at that point, so we know that is the median.

Hence the median is approx 0.51.

Finding the mean would be trickier, because it would require integrating over the entire admissible region, which will involve breaking the integral into parts to allow for excluding the areas that lie outside the square S. That is a task for somebody with more patience than me.

 

[andrewkirk]

I did a numerical calc and estimated the mean at about 0.52. Here is the code, in R:

n=1000
wt=1/(n*n)
cumexp=0
for (j in 1:n){
  x=j/n
  for (k in 1:n){
  y=k/n
  cumexp=cumexp+wt*(1-x)*(1-y)*sqrt(x^2+y^2)
  }
}
4*cumexp

 

[TheDemx27]

Seeing all this group theory is really exciting, although the problems shown here are quite a bit beyond my reach. I can only do simple proofs I guess.
For #1, I believe I found the average distance. Considering only 1 dimension, we have a line upon which we consider a certain point, $\tau$. The distance from $\tau$ to every other point is $abs(x-\tau)$. The average distance of all points from the point in question is $\int_0^1 abs(x-\tau) \,dx$. Iterating over all points $\tau$ (and essentially taking the average of all the averages), we have $\int_0^1 \int_0^1 abs(x-\tau) \, dx \, d\tau$. Wolfram alpha tells us that the double integral evaluates to $1/3$. Then we just pythagorize that with itself because the other dimension is symmetrical and we get $\frac{\sqrt{2}}{3}$.

I feel like I did this wrong after seeing andrewkirk's solution ho boy

 

[andrewkirk]

I've been looking at number 4. I don't understand the question.

It says 'containing all continuous functions and closed under pointswise limits'

If we were talking about sequences of functions I could understand the ref to pointswise limits, but not for an unstructured set that contains a bunch of continuous functions.

What does 'closed under pointswise limits' mean here? Since the functions are all continuous, they are trivially equal to the limit at every point. Since there are no sequences defined, we can't talk about limits of sequences of functions, so I don't know what 'limits' can be referring to.

I doubt I'll be able to answer the question anyway, as I'm exceedingly rusty on measurability. But I'd at least like to understand the question.

 

[Infrared]

I think the meaning is that if (f_n) is a sequence of functions in B that converges pointwise to a function f, then f is also in B. Micro, please correct me if this isn't the right interpretation.

I've been meaning to look at this problem but I've been busy these past few days.

 

[micromass]

I've been looking at number 4. I don't understand the question.

It says 'containing all continuous functions and closed under pointswise limits'

If we were talking about sequences of functions I could understand the ref to pointswise limits, but not for an unstructured set that contains a bunch of continuous functions.

What does 'closed under pointswise limits' mean here? Since the functions are all continuous, they are trivially equal to the limit at every point. Since there are no sequences defined, we can't talk about limits of sequences of functions, so I don't know what 'limits' can be referring to.

I doubt I'll be able to answer the question anyway, as I'm exceedingly rusty on measurability. But I'd at least like to understand the question.

The functions in $\mathcal{B}$ are not all continuous. All I'm saying is that every continuous function is in $\mathcal{B}$, but there might be more. The limit condition says that if $f_n\in \mathcal{B}$, then so is $\lim_n f_n\in \mathcal{B}$.

 

[micromass]

Here is my proposed solution to problem 1. I have found the mode and median. The mean is left for somebody else, because it would be messy. It would be easy enough to compute numerically though.
Let the two points have coordinates (X_1,Y_1),\ (X_2,Y_2), where the coordinates are pairwise independent and each is drawn from a uniform distribution on [0,1]. Then the squared length L^2 of the connecting line segment is given by:
$$L^2=(X_2-X_1)^2+(Y_2-Y_1)^2$$
Let us write X=X_2-X_1,\ Y=Y_2-Y_1 so that L^2=X^2+Y^2. Then X,Y are mutually independent and the cdf of X is F_X(c)=Pr(X<c)=Pr(X_2<X_1+c) which is the area of the region of the unit square in the number plane above the line y=x+c. A little geometry shows that F_X(c) is equal to \frac12 (1+2c+c^2) if c\in[-1,0] and \frac12 (1+2c-c^2) if c\in[0.1], The pdf is f_X(c)=1+c if c\in[-1,0] and 1-c if c\in[0.1], F_Y and f_Y have the same form. Note that the pdfs are even functions.

Then the cdf of L is F_L(l) which is the integral over the origin-centred circle of radius l of f_X(x)f_Y(y), excluding parts of the circle that lie outside the square S\equiv[-1,1]\times[-1,1]. If we restrict to l<1, the whole circle lies inside S so we can calculate the integral without having to break it into sections. It is simplest as a polar integral. Since both the pdfs are even, the full integral is equal to four times the integral in the first quadrant, which is
$$4\int_0^l \int_0^{\frac\pi2} f_X(r\cos \theta)f_Y(r\sin\theta)\,r\,d\theta\,dr$$
Hence we have
\begin{eqnarray*}
F_L(l)&=4\int_0^l \int_0^{\frac\pi2} (1-r\cos \theta)(1-r\sin\theta)\,r\,d\theta\,dr\\
&=4\int_0^l \int_0^{\frac\pi2} (1-r\cos \theta-r\sin\theta+r^2\cos\theta\sin\theta)\,r\,d\theta\,dr\\
&=4\int_0^l \left[ \theta-r\sin \theta+r\cos\theta+\frac12r^2\sin^2\theta)\right]_0^{\frac\pi2}\,r\,dr\\
&=4\int_0^l \left( \frac\pi2-r-r+\frac12r^2\right)\,r\,dr\\
&=4 \left[ \frac\pi2\cdot\frac12r^2-\frac23r^3+\frac18r^4\right]_0^l\\
&=\pi l^2-\frac83 l^3+\frac12l^4
\end{eqnarray*}

The pdf is
$$f_L(l)=\frac d{dl}F_L(l)=2\pi l-8l^2+2l^3$$

The mode will occur when \frac d{dl}f_L(l)=0, that is:
$$0=2\pi-16l+6l^2$$
This has roots at \frac13(4-\sqrt{16-3\pi}) of which only the lower one is in the admissible range, giving a value of about 0.48.

Hence the mode is approx 0.48.

To find the median we solve the equation F_L(x)=0.5. That is
$$\pi l^2-\frac83 l^3+\frac12l^4=0.5$$
Numerically solving this, we find it has four real roots, of which the second is at approx 0.51. The LHS of the equation is increasing at that point, so we know that is the median.

Hence the median is approx 0.51.

Finding the mean would be trickier, because it would require integrating over the entire admissible region, which will involve breaking the integral into parts to allow for excluding the areas that lie outside the square S. That is a task for somebody with more patience than me.

Very neat. I will credit you after somebody found the mean.

 

[micromass]

Seeing all this group theory is really exciting, although the problems shown here are quite a bit beyond my reach. I can only do simple proofs I guess.
For #1, I believe I found the average distance. Considering only 1 dimension, we have a line upon which we consider a certain point, $\tau$. The distance from $\tau$ to every other point is $abs(x-\tau)$. The average distance of all points from the point in question is $\int_0^1 abs(x-\tau) \,dx$. Iterating over all points $\tau$ (and essentially taking the average of all the averages), we have $\int_0^1 \int_0^1 abs(x-\tau) \, dx \, d\tau$. Wolfram alpha tells us that the double integral evaluates to $1/3$. Then we just pythagorize that with itself because the other dimension is symmetrical and we get $\frac{\sqrt{2}}{3}$.

I feel like I did this wrong after seeing andrewkirk's solution ho boy

Sorry, that is the incorrect answer

 

[mfb]

Then we just pythagorize that with itself because the other dimension is symmetrical and we get $\frac{\sqrt{2}}{3}$

The Pythagoras is not linear, you can't "pull the average in/out" like that.

 

[PeroK]

I have a revised formula for number 6:

$$P = 1 - \sum_{i = 1}^{d-1} \binom{d}{i} \sum_{j=1}^{i} (-1)^{i+j} \binom{i}{j} (\frac{j}{d})^n$$

With $d = 365$ and $n = 2016$

I ran this calculation and got $P = 0.230987$ (which agrees with @mfb).

That's my final bid!

 

[andrewkirk]

The functions in $\mathcal{B}$ are not all continuous. All I'm saying is that every continuous function is in $\mathcal{B}$, but there might be more. The limit condition says that if $f_n\in \mathcal{B}$, then so is $\lim_n f_n\in \mathcal{B}$.

Is the following then an accurate representation of what the set $\mathcal B$ is intended to be in problem 4?

Let $C^0$ be the set of all continuous functions from $\mathbb R\to \mathbb R$.
Given a set $S$ of functions $\mathbb R\to\mathbb R$, we say $S$ is 'pointwise closed' if, for any countable subset $(f_n)_{n\in\mathbb N}$ of $S$ that converges pointwise to a function $f:\mathbb R\to\mathbb R$, the function $f$ is also in $S$.

Then $\mathcal B$ is defined to be the intersection of all sets of functions $S$ that contain $C^0$ and are pointwise closed.

 

[micromass]

Is the following then an accurate representation of what the set $\mathcal B$ is intended to be in problem 4?

Let $C^0$ be the set of all continuous functions from $\mathbb R\to \mathbb R$.
Given a set $S$ of functions $\mathbb R\to\mathbb R$, we say $S$ is 'pointwise closed' if, for any countable subset $(f_n)_{n\in\mathbb N}$ of $S$ that converges pointwise to a function $f:\mathbb R\to\mathbb R$, the function $f$ is also in $S$.

Then $\mathcal B$ is defined to be the intersection of all sets of functions $S$ that contain $C^0$ and are pointwise closed.

That is right.

 

[mfb]

I have a revised formula for number 6:

$$P = 1 - \sum_{i = 1}^{d-1} \binom{d}{i} \sum_{j=1}^{i} (-1)^{i+j} \binom{i}{j} (\frac{j}{d})^n$$

With $d = 365$ and $n = 2016$

I ran this calculation and got $P = 0.230987$ (which agrees with @mfb).

That's my final bid!

The inner sum should give the probability that people have birthdays on exactly d (specified) days, right? Why don't you directly extend it to 365 and consider that only? We don't need the double sum.
$$\sum_{j=1}^{d}(-1)^{j+1} \binom{d}{j} \left(\frac j d \right)^n$$
For d=365 and n=2016, it gives 0.230987.

That's the inclusion/exclusion I was looking for earlier.

 

[andrewkirk]

Well, I have waded through the mire of messy integration to solve the mean for problem four.

WARNING: it is not pretty. Avert your eyes if you are easily distressed.

To calculate the mean we want to use Cartesian rather than Polar integration so that we can include the corners of the square $[-1,1]\times[-1,1]$. Fortunately, we don't need to calculate the cdf of L in Cartesian coordinates, which might be very messy. Instead we calculate the mean directly using Cartesian integration over the first quadrant, using only the pdfs of X and Y.

\begin{align*}
E[L]&=4\int_0^1\int_0^1 f_X{x}f_Y(y)\sqrt{x^2+y^2}\,dy\,dx\\
&=4\int_0^1\int_0^1 (1-x)(1-y)\sqrt{x^2+y^2}\,dy\,dx\\
&=4\int_0^1(1-x)\left[-\frac13 (x^2+y^2)^\frac32+ \frac12\left(y\sqrt{x^2+y^2}+x^2\log\left(\sqrt{x^2+y^2}+y\right)\right)\right]_0^1\,dx\\
%
&=4\int_0^1(1-x)\Bigg(\left(-\frac13 (x^2+1^2)^\frac32+ \frac12\left(1\sqrt{x^2+1^2}+x^2\log\left(\sqrt{x^2+1^2}+1\right)\right)\right)\\
&\quad\quad\quad-\left(
-\frac13 (x^2+0)^\frac32+ \frac12\left(0+x^2\log\left(\sqrt{x^2+0}+0\right)\right)
\right)
\Bigg)\,dx\\
%
&=4\int_0^1(1-x)\Bigg(-\frac13 (x^2+1)^\frac32+ \frac12\sqrt{x^2+1}+\frac12 x^2\log\left(1+\sqrt{x^2+1}\right)\\
&\quad\quad\quad+\frac13 x^3-\frac12 x^2\log{x}\Bigg)dx\\
%
&=
4\left[\frac1{12}x^4-\frac1{15}x^5\right]_0^1+
%
4\int_0^1\Bigg(+\frac13 x(x^2+1)^\frac32 - \frac12 x\sqrt{x^2+1}\\
&\quad\quad\quad-\frac13 (x^2+1)^\frac32+\frac12 \sqrt{x^2+1}
+(1-x)\left(\frac12 x^2\log\left(1+\sqrt{x^2+1}\right)
-\frac12 x^2\log{x}\right)\Bigg)dx\\
%
&=\frac13-\frac4{15}
+4\left[
\frac1{15}(x^2+1)^\frac52
-\frac16(x^2+1)^\frac32
\right]_0^1\\
&\quad\quad\quad+4\int_0^1\Bigg(
-\frac13 (x^2+1)^\frac32+\frac12 \sqrt{x^2+1}
+(1-x)\left(\frac12 x^2\log\left(1+\sqrt{x^2+1}\right)
-\frac12 x^2\log{x}\right)\Bigg)dx\\
%
&=\frac1{15}+\frac1{15}\cdot 16\sqrt2-\frac16 8\sqrt2-\frac4{15}+\frac23\\
&\quad\quad\quad+4\int_0^1\Bigg(
-\frac13 (x^2+1)^\frac32+\frac12 \sqrt{x^2+1}
+(1-x)\left(\frac12 x^2\log\left(1+\sqrt{x^2+1}\right)
-\frac12 x^2\log{x}\right)\Bigg)dx\\
%
&=0.090
+4\int_0^1\Bigg(
-\frac13 (x^2+1)^\frac32+\frac12 \sqrt{x^2+1}
+\frac12 x^2\log\left(1+\sqrt{x^2+1}\right)
-\frac12 x^2\log{x}\\
&\quad\quad\quad-\frac12 x^3\log\left(1+\sqrt{x^2+1}\right)
+\frac12 x^3\log{x}
\Bigg)dx
%
\end{align*}

\begin{align*}
&=0.090
-\frac13\cdot\frac18\left[x\sqrt{x^2+1}(2x^2+5)+3\sinh^{-1}x\right]_0^1\\
&\quad\quad\quad+\frac12\cdot\frac12\left[x\sqrt{x^2+1}+\sinh^{-1}x\right]_0^1\\
&\quad\quad\quad+\frac12\cdot\frac1{18}\left[
-2x^3+3x\sqrt{x^2+1}+6x^3\log(1+\sqrt{x^2+1})-3\sinh^{-1} x\right]_0^1\\
&\quad\quad\quad-\frac12\cdot\frac19\left[
x^3(3\log x-1)\right]_0^1\\
&\quad\quad\quad-\frac12\cdot\frac1{48}\left[
-3x^4+4x^2\sqrt{x^2+1}-8\sqrt{x^2+1}+12x^4\log(1+\sqrt{x^2+1})
\right]_0^1\\
&\quad\quad\quad+\frac12\cdot\frac1{16}\left[x^4(4\log x - 1)\right]_0^1
\end{align*}
The alert reader will have noticed that in evaluating the fourth and sixth definite integrals here it appears I will have to perform an illegal operation in evaluating \log 0. However, we can validate such a step by observing that the formulas actually being evaluated are (x^4\log x) and (x^3\log x) in the fourth and six items respectively. We can show by l'Hopital's rule that the limit of these formulas as x goes to zero from above is 0. Hence we can use that, since it is only the limit, not the value of the antiderivative at 0, that determines the value of the definite integral.

Let us continue:
\begin{align*}
&=0.090
-\frac1{24}\left[1\cdot\sqrt{1+1}(2+5)+3\sinh^{-1}1-(0)\right]
+\frac14\left[\sqrt{2}+\sinh^{-1}1-(0)\right]\\
&\quad\quad\quad+\frac1{36}\left[-2+3\sqrt{2}+6\log(1+\sqrt{2})-3\sinh^{-1} 1-(0)\right]\\
&\quad\quad\quad-\frac1{18}\left[1(3\cdot 0-1)-(0)\right]\\
&\quad\quad\quad-\frac1{96}\left[
-3+4\sqrt{2}-8\sqrt{2}+12\log(1+\sqrt{2})-(-8)\right]\\
&\quad\quad\quad+\frac1{32}\left[1\cdot (4\cdot 0 - 1)-(0)\right]\\
%
&=0.52
\end{align*}
which matches the value calculated earlier by numerical integration. What a relief!

 

[mfb]

The calculation is much shorter if you use polar coordinates and make the radius depend on the angle.

 

[PeroK]

The inner sum should give the probability that people have birthdays on exactly d (specified) days, right? Why don't you directly extend it to 365 and consider that only? We don't need the double sum.
$$\sum_{j=1}^{d}(-1)^{j+1} \binom{d}{j} \left(\frac j d \right)^n$$
For d=365 and n=2016, it gives 0.230987.

That's the inclusion/exclusion I was looking for earlier.

I missed that!

 

[haruspex]

Problem 1.
(I assume it means average distance between two points, not two numbers.)
The obvious approach is a quadruple integral, $\int\int\int\int\sqrt{(x_1-x_2)^2+(y_1-y_2)^2}$. The first integral can be handled with a tan substitution, leading to integral of sec³, with a standard but messy result, or a sinh substitution, leading to a sinh^-1 term. Either way, the second integral looks very nasty.

We can do better by noting that lines in which the endpoints differ by a vector (x,y) have a relative frequency (1-x)(1-y). This leads to the double integral $\int\int(1-x)(1-y)\sqrt {x^2+y^2}.dxdy/\int\int(1-x)(1-y)dxdy=4\int\int(1-x)(1-y)\sqrt {x^2+y^2}.dxdy$.
Multiplying out, we get an xy term, an x term, a y term and a "1" term. The xy term can be integrated twice easily. The x and y terms can also be integrated twice, though it involves integrating sec⁵ (I think).
But for the "1" term we have the same horrendous second integral as before.

Any better ideas?

 

[mfb]

Go to polar coordinates for the "1" term.

 

[haruspex]

Go to polar coordinates for the "1" term.

Doh! I looked at that when I had the quadruple integral and it didn't help, but I didn't retry it with the simpler integral.
Thanks!

 

[rcgldr]

Following up on mfb's post for number 6, a similar formula I had from the early 1990's, for dropping n balls into a plinko like box, each ball with an equal probability of ending up in 1 of d slots (note a real plinko box (bean machine) would have a bell curve distribution, not a uniform distribution, this was being used as an analogy for comparing error rates at the bit level versus a block level on tape drives and hard drives).

correction - was (-1)^(j+1), corrected to (-1)^(j+d):

$\left( \sum_{j=1}^{d} (-1)^{j+d} \begin{pmatrix} d\\j\end{pmatrix} j^n \right) \ / \ (d^n)$

for d = 365, and n = 2016, the result is

~= 0.23098718155802874302697567890329631779588686618349968487

To explain this sum, note that there are $d^n$ total possible cases, each of n people can have one of d possible birthdays.

For all the birthdays to fall on a single day, there are ...
For all the birthdays to fall on exactly two days, there are ...
For all the birthdays to fall on exactly three days, there are ...
For all the birthdays to fall on exactly 365 days, there are

The probability of all the birthdays to fall on exactly 365 days = the number of cases for exactly 365 days divided by the total number of cases, $d^n$ .

 

[PeroK]

To explain this sum, note that there are $d^n$ total possible cases, each of n people can have one of d possible birthdays.

For all the birthdays to fall on a single day, there are
$\begin{pmatrix} d\\1\end{pmatrix} 1^n$ cases.

For all the birthdays to fall on exactly two days, there are
$\begin{pmatrix} d\\2\end{pmatrix} 2^n$ cases minus the number of single day cases.

For all the birthdays to fall on exactly three days, there are
$\begin{pmatrix} d\\3\end{pmatrix} 3^n$ cases minus the number of exactly two day cases.

For all the birthdays to fall on exactly 365 days, there are
$\begin{pmatrix} d\\365\end{pmatrix} 365^n$ cases minus the number of exactly 364 day cases.

I must confess, I don't see this argument. First, why is the final number the total number of cases minus the exactly 364 cases? What about all the 363, 362 etc cases? The same for the others: the number of exactly 3-day cases should be the total number of 3-day cases minus the number of exactly 2-days cases minus the number of exactly 1-day cases.

Second, that calculation for the number of 2-days cases (not exact) includes as separate 2-day cases day-1/day-2 and day-1/day-3, which counts the subcase of all day-1 twice.

 

[PeroK]

In fact, the probability that $n$ people have birthdays covering exactly any $x$ days is:

$$ \binom{d}{x} \sum_{j=1}^{x}(-1)^{j+x} \binom{x}{j} \left(\frac j d \right)^n$$

It's only when $x = d$ that the initial binomial term disappears.

Note also, a minor point, that it should be in general $(-1)^{j+x}$. It's only $(-1)^{j+1}$ when $x$ is odd.

 

[PeroK]

In fact, the probability that $n$ people have birthdays covering exactly any $x$ days is:

$$ \binom{d}{x} \sum_{j=1}^{x}(-1)^{j+x} \binom{x}{j} \left(\frac j d \right)^n$$

It's only when $x = d$ that the initial binomial term disappears.

Note also, a minor point, that it should be in general $(-1)^{j+x}$. It's only $(-1)^{j+1}$ when $x$ is odd.

Here's a counting argument that I think works:

Let $N_i$ be the number of ways that exactly any $i$ days can be birthdays:

$\binom{d}{2} 2^n = N_2 + 2\binom{d}{2}$

As all the $N_2$ cases are covered and every pair chosen generates $2$ cases where only 1 day is covered. Hence:

$N_2 = \binom{d}{2} (2^n - 2) = \binom{d}{2} \sum_{j=1}^{2} (-1)^{j+2} \binom{2}{j} j^n$

And:

$\binom{d}{3} 3^n = N_3 + \binom{d}{3}(3(2^n) - 3)$

All the $N_3$ cases are generated, plus for every triple there are 3 sets of $2^n$ cases where at most 2 days are covered, but this counts twice each of the three cases where only one day is covered. Hence:

$N_3 = \binom{d}{3}(3^n - 3(2^n) + 3)$

And, in general - or for the last day - we get the series of alternating inclusions and exclusions.