Birthday problem with repetitions

  • Thread starter wintermute++
  • Start date
In summary, the conversation discusses the number of different sets of birthdays that can occur with k people and 365 days, when same birthdays are not distinguished in different orders. The equation ## C_{n+k-1, k} ## is used to calculate combinations with repetitions, and it is suggested that the answer is ## C_{365+k, k} ##. However, a simplified version with 2 people and 2 days shows that the correct answer should be ## C_{365+k-1, k} ##.
  • #1
wintermute++
30
0

Homework Statement


How many different sets of birthdays are available with k people and 365 days when we don’t distinguish the same
birthdays in different orders?

Homework Equations


[/B]
I approached this using what was proven in a previous problem, provided I did that right. This what I had:

## C_{n+k-1, k} ##

for combinations that involve repetitions.

The Attempt at a Solution



## C_{365+k-1,k} ##

Not much of an attempt at the solution since it seemed obvious enough. But the book says the answer is ## C_{365+k,k} ## and I'm struggling to get to this solution.
 
Physics news on Phys.org
  • #2
I agree with your answer. As a check, we can consider a much simplified version: 2 days, 2 people. C2+2-1,2 = 3: (1,1), (1,2), (2,2).
 
  • Like
Likes wintermute++
  • #3
Thanks haruspex. You've been a great help for me so far.
 

1. What is the "Birthday problem with repetitions"?

The Birthday problem with repetitions is a mathematical problem that asks how many people are needed in a group for there to be a certain probability that at least two of them have the same birthday, assuming that birthdays are equally likely to occur and that repetition of birthdays is allowed.

2. How is the probability of matching birthdays calculated in the "Birthday problem with repetitions"?

The probability of at least two people in a group having the same birthday can be calculated using the formula P(n) = 1 - (365!/[(365-n)!*365^n]), where n is the number of people in the group and 365 is the number of possible birthdays. This formula takes into account the repetition of birthdays.

3. What is the significance of the "Birthday problem with repetitions"?

The Birthday problem with repetitions has applications in various fields such as cryptography, statistics, and computer science. It demonstrates the counterintuitive probability of two people sharing the same birthday in a group, which can be useful in understanding the likelihood of a collision in hash functions and in estimating the number of trials needed for a certain success rate.

4. How does the inclusion of repetitions impact the results of the "Birthday problem"?

When repetitions are not allowed, the probability of matching birthdays decreases significantly as the number of people in the group increases. However, when repetitions are allowed, the probability remains relatively high even with a larger group size. This is because the inclusion of repetition increases the chances of a birthday match occurring.

5. Can the "Birthday problem with repetitions" be extended to include multiple people sharing the same birthday?

Yes, the "Birthday problem with repetitions" can be extended to include multiple people sharing the same birthday. This is known as the generalized birthday problem and the probability can be calculated using the formula P(n,m) = 1 - (365!/(365-nm)!*365^n), where n is the number of people in the group and m is the number of shared birthdays. This problem has various real-world applications, such as in estimating the likelihood of shared anniversaries in a company or organization.

Similar threads

  • Precalculus Mathematics Homework Help
Replies
9
Views
3K
  • Set Theory, Logic, Probability, Statistics
Replies
4
Views
2K
  • Precalculus Mathematics Homework Help
Replies
34
Views
2K
  • Precalculus Mathematics Homework Help
Replies
3
Views
918
  • Precalculus Mathematics Homework Help
Replies
2
Views
1K
  • Precalculus Mathematics Homework Help
Replies
1
Views
1K
  • Precalculus Mathematics Homework Help
Replies
7
Views
2K
Replies
2
Views
1K
  • Precalculus Mathematics Homework Help
Replies
5
Views
1K
  • Precalculus Mathematics Homework Help
Replies
12
Views
4K
Back
Top