gXa's blog

By gXa, history, 12 months ago, ,

You are given N candies and K boxes. You need to find the number of ways to divide N candies in K boxes such that each box should have one candy and you should not count repetitive sequences. The boxes and candies are identical.

Is there any question similar asked before?

•
• +3
•

 » 12 months ago, # |   0 Would you consider 2 + 2 + 1, and 1 + 2 + 2 as different sequences for N = 5, k = 3 ?
•  » » 12 months ago, # ^ |   0 NO
 » 12 months ago, # |   0 I believe you are asking for the number of partitions of a number into k parts.Let us denote this number by f(n, k).Now, there are two possibilities — Either there is some box which has exactly one candy or every box has more than one candy.If the smallest number of candies in any box is 1. Then the problem reduces to finding f(n — 1, k — 1).Otherwise, let every box have at least one candy. Then we place one candy in each of the k boxes, and now distribute the remaining (n — k) candies into k boxes. This is given by f(n — k, k)f(n, k) = f(n — 1, k — 1) + f(n — k, k)I hope this helps.f(0, k) = 0, for all k f(1, 1) = 1 f(n, 1) = f(n, n) = 1, for all n
 » 12 months ago, # |   0 You want all boxes to have at least 1 candy. Then you can remove this restriction by simply subtracting K from N. Now the problem is simply to find the number of combinations with repeatings. This count is equal to C(n + k - 1, k - 1), where C(n, k) is the number of ways to chose k out of n values. You can find an easy explanation by googling "combinations with repeatings", or I can explain it if you want (googling will be faster).This problem if I'm not mistaken was asked in Codechef long challenge in the beginning of 2017.
•  » » 12 months ago, # ^ |   0 How would it take into account "no repetitive sequences", as u may count 1, 4 and 4, 1 as same sequences.
•  » » 12 months ago, # ^ | ← Rev. 2 →   0 N = 5, K = 2N -= K => 33+1 C 1 => 4 ways1 42 3 Only correct ones, so answer should be two
•  » » » 12 months ago, # ^ |   0 Simply divide the answer by K! or smth like that.
•  » » » » 12 months ago, # ^ |   0 I am unable to get your k! part.Can u plz provide problem link? I'll try to figure out myself.
•  » » » » 12 months ago, # ^ |   0 Can u plz help?
•  » » 12 months ago, # ^ |   0 But, the boxes are indistinguishable !