100 Days streak problem

Probability Level 4

If 100 identical dices are rolled then the_number of different outcomes of the numbers appearing on the dice are?

The answer is 96560646.

1 solution

Brian Charlesworth
Apr 18, 2015

Let $a_{k}$ represent the number of dice that show the number $k.$ Then we need to find the number of non-negative integer solutions to the equation

$a_{1} + a_{2} + a_{3} + a_{4} + a_{5} + a_{6} = 100$ where $0 \le a_{k} \le 100$ for integers $1 \le k \le 6.$

This is a now a stars and bars problem, which according to Theorem two in this link has the solution

$\dbinom{100 + 6 - 1}{100} = \dbinom{105}{100} = \boxed{96560646}.$

@Tanishq Varshney Nice problem, and congrats on the streak. :)

Brian Charlesworth - 6 years, 1 month ago

Thank you sir $\ddot \smile$

Tanishq Varshney - 6 years, 1 month ago

Congrats! @Tanishq Varshney Keep the streak alive!

Nihar Mahajan - 6 years, 1 month ago

@Nihar Mahajan – Congrats! I once got a 10,100 day streak. Oh, by the way, that's in binary (20). In binary, you'd have a 1,100,100 - a 1.1 million day streak!

vishnu c - 6 years, 1 month ago

Is there a theorem that can be used if the $a_i$ aren't distinct? I know that for this problem, if the dice were distinct then the number of ways would be $6^{100}$ . But if you're trying to find the number of non-distinct ordered pairs $)a_1,a_2,a_3,a_4)$ such that $a_1+a_2+a_3+a_4=100$ . What would you do then?

Trevor Arashiro - 6 years, 1 month ago

If I understand correctly, I think we would be looking at the partitions of $100$ of size $4.$ Looking at a simpler version, say $a_{1} + a_{2} + a_{3} + a_{4} = 5$ where the $a_{i}$ 's are non-negative and non-distinct, we would have solution quadruplets

$(5,0,0,0), (4,1,0,0), (3,2,0,0), (3,1,1,0), (2,2,1,0), (2,1,1,1).$

We could label this as $P(n;k)$ , the number of partitions of $n$ into at most $k$ parts. In this case we have $P(5;4) = 6.$ Here is the OEIS listing; there are some formulas but they're pretty scary, and the listing only goes up to $55.$ However, that's the general idea. :)

Edit: Here is a good paper that I think addresses the matter at hand.

Brian Charlesworth - 6 years, 1 month ago

Ok, wow, I thought there might have been something simple like stars and bars but guess not lol.

That's quite the interesting paper. It was a lot of fun to read through and I learned A LOT. Thanks for showing it to me :)

Trevor Arashiro - 6 years, 1 month ago

@Trevor Arashiro – You're welcome. That is a really good paper; I've bookmarked it for future reference. Partitions show up everywhere, (just like $\phi$ ); I just learned about Bell numbers last week and have started to realize how significant they are. The more you know ..... :)

Brian Charlesworth - 6 years, 1 month ago

100 Days streak problem

The answer is 96560646.

1 solution

0 pending reports