Skip to main content

Birthdays and Celebrations (Quick Notes)

Given N people, what is the number of birthday celebrations on average in a year?

Solution

The quick solution is: the probability of having a celebration in a particular day is 1 - (364/365)^N. So the average is 365(1 - (364/365)^N).  (Linearity if expectation)

I wonder if someone tries to solve this problem directly, i.e. compute the number of ways to assign birthdays to N people to have k celebrations, call this B(N, k), then the average number of celebrations = sum k B(N, k).

Turns out B(N, k) is very similar to something called Stirling number of second kind, which computes the number of ways to partition N labelled objects into k non-empty unlabelled groups. One can come up with the recurrence relation quite easily, but to directly compute it is interesting and relies on principle of exclusion and inclusion.

The PIE for B(N, k) goes like this: let A_d be the set containing all assignments of birthdays where birthday d is unused. Then the answer is k^N - | A_1 union A_2 union ... union A_k |, which can be computed by PIE.





Comments

Post a Comment

Popular posts from this blog

641 | 2^32 + 1

Problem: Show that \( 641 | 2^{32} + 1 \). Solution: (From Problem Solving Strategies, Arthur Engel) \( 641 = 625 + 16 = 5^4 + 2^4 \). So \( 641 | 2^{32} + 2^{28} \cdot 5^4 \). Also, \( 641 = 640 + 1 = 2^7 \cdot 5 + 1\). So \( 641 | (2^7 \cdot 5)^4 - 1 = 2^{28}\cdot 5^4 - 1 \). Hence \( 641 | 2^{32} + 2^{28} \cdot 5^4 -(2^{28}\cdot 5^4 - 1) \). QED
Post a Comment
Read more

Derive e

Prove that \( \left( 1 + \frac{1}{n} \right)^n \) converges. Solution Let \( G(n) =  \left( 1 + \frac{1}{n} \right)^n \). Binomial expansion, \( G(n) = \sum_{k = 0}^{n} \frac{ \binom{n}{k} }{n^k} \). By simple inequality argument, \( \frac{ \binom{n}{k} }{n^k} < \frac{1}{k!} \). So if we let \( F(n) = \sum_{k = 0}^{n} \frac{1}{k!} \), we have \( G(n) < F(n) \). By simple inequality argument, \( F(n) < 1 + \sum_{k = 1}^{n} \frac{1}{2^{k-1}} < 3 \). So G and F are bounded above. By AM-GM, \( \frac{G(n-1)}{G(n)} = \left( \frac{ n^2 }{ n^2 - 1} \right)^{(n-1)} \frac{ n}{n+1} < \left(  \frac{ \frac{ n^2 }{ n^2 - 1} (n-1) + \frac{ n}{n+1} }{n} \right)^n = 1 \). So \( G(n-1) < G(n) \). Since G is monotonic increasing and bounded above, G converges. Similarly F converges. Let's also prove that G and F converges to the same limit. By studying individual terms in \( F(n) - G(n) \) and making simple inequality arguments, we can show that for each \( \epsilon > 0 \) w...
Post a Comment
Read more

2n+1 3n+1 squares then 5n+3 not prime

Problem: Prove that if \( 2n+1 \) and \( 3n+1 \) are both squares, then \( 5n+3 \) is not a prime. Solution: Proof by contradiction. Suppose that there is n such that 5n+3 is prime. Note that \( 4(2n+1) - (3n+1) = 5n+3 \). Let \( 2n+1 = p^2 \) and \( 3n+1 = q^2 \), where \( p, q > 0 \). We have \( (2p-q)(2p+q) = 5n+3 \). Since RHS is a prime, we must have \(2p - q = 1 \) and \( 2p + q = 5n+3 \). Solving for \( q \) we get \( 2q = 5n + 2 \). Substituting, we get \( 2q = q^2 + 2n + 1 \), or \( -2n = (q-1)^2 \). Since RHS is \( \geq 0 \), we can only have equality when \( n= 0 \) and \( q = 1 \). In this case, we have \( 5n + 3 = 8 \) not a prime. QED.
Post a Comment
Read more