0
$\begingroup$

I have the following problem: "There are 15 identical candies. How many ways are there to distribute them among 7 kids?"

I know the conventional way to solve a similar problem (unordered with repetition) is using the formula (n+k−1Ck) (=54,264) and I'm convinced with why this formula works. However, I'm trying to use another approach and I can't figure out why that doesn't work.

Please consider this other problem first: "There are 4 people and 9 different assignments. We need to distribute all assignments among people. No assignment should be assigned to two people. Every person can be given arbitrary number of assignments from 0 to 9. How many ways are there to do it?"

This is a 'Tuples' problem ie. ordered with repetitions and its solution is simply 4^9. Therefore, why can't I solve the first problem with a similar approach, but then dividing by n!

This is how I'm thinking: We have 15 candies and 7 kids. The first candy can be distributed in 7 ways (one of the 7 kids in going to take it). The second can also be distributed in 7 ways .. etc

So we now have 7^15 just like the approach we used for the second (assignments) problem. But now since the candies are identical, order doesn't matter, and we should divide by 15! .. But solving it this way gives a completely different and significantly smaller answer 4,747,561,509,943 / 1,307,674,368,000 = 3.63

What is wrong with thinking about the problem in this approach and why is it not working? I would just like to know what I'm missing here and learn from my mistake so that I don't approach a future problem with a similar thinking.

$\endgroup$
1
  • 1
    $\begingroup$ Your question is vague: you need to explain what you mean by a "distribution" and how to distinguish two distributions. For instance, if we fix an order of the children, would you consider the counts $(1,1,1,1,1,1,9)$ and $(9,1,1,1,1,1,1)$ (which differ only in which child received nine candles) to be the same or different? And would you even allow a distribution like $(15,0,0,0,0,0,0)$ or not? $\endgroup$
    – whuber
    Feb 5, 2022 at 14:43

2 Answers 2

0
$\begingroup$

Let's make it simpler and distribute 2 unique/similar candies among 2 kids.

With the similar candies there are 3 ways

0:2, 1:1 and 2:0

With the unique candies there are 4 ways

{}:{12}, {2}:{1}, {1}:{2} and {12}:{}


I am not sure where the intuition comes from that these two cases should be relating with each other by a factor $2!$. But it is clearly wrong in this example and I guess that the example may help to see why it is wrong whatever the reason is that $2!$ plays a role.

Possibly the devision by $n!$ relates to the specific samples when each kid has only a single candy, in which case there are $n!$ ways to order the candies among the particular distribution of number of candies. But, if any kid has more than one candies then this factor is wrong

$\endgroup$
0
$\begingroup$

The phrasing of the original question is ambiguous: does it matter which kid got 9 candies? If the answer is NO then the following distributions are identical: 1+1+1+1+1+1+9 = 9+1+1+1+1+1+1=15, then the problem becomes of restricted parts number partitions.

There is a recursive solution: $p_k(n)=p_k(n-k)+p_{k-1}(n-1)$ with $p_0(0)=1$ and $p_k(n)=0$ when $n,k\le 0$ and $|n|+|k|\ne 0$.

We have $p_7(15)=p_7(8)+p_6(14)=p_7(1)+p_6(7)+p_6(8)+p_5(13)=\dots=21$

Here's a few first distributions (LxM is for L kids with M candies each):

  • 9 + 6x1
  • 8 + 2 + 5x1
  • 7 + 3 + 5x1
  • 7 + 2x2 + 4x1
  • 6 + 4 + 5x1
  • 6 + 3 + 2 + 4x1
  • ...

Here's my code to calculate them:

# k - num of kids
# n - num of candies
def p(k,n,padding=''):
  padding+='/'
  if k==0 and n==0:
    ret = 1
  elif (n<=0 or k<=0) and (abs(n)+abs(k)>0):
    ret = 0
  elif n==k or k==1 or n-1==k: # obvious solutions
    ret = 1
  else:
    ret = p(k-1,n-1,padding) + p(k,n-k,padding)
  if ret!=0:
    print('{:s}p({:d},{:d})={:d}'.format(padding,k,n,ret))
  return ret

p(7,15)

If you go with this interpretation of the question, then the question goes away, because neither of your approaches solves the problem in this case.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.