# Distributing candies

Suppose ther are B boys and G girls in a classroom.Teacher wants to distribute candies among B boys and G girls such that:

1.Each student gets atleast one candy and atmost N candies.
2.sum of candies given to all boys equals sum of candies given to all girls.

find the number of different ways to do it.
Note:Two ways are considered different if there exists a student that received different number of candies in these two candies' distributions.

Example: if B=1 G=2 N=3 there are 3 ways, they are: (2, 1, 1), (3, 1, 2), (3, 2, 1).
if B=2 G=2 N=2 there are 6 ways, they are: (1, 1, 1, 1), (1, 2, 1, 2), (1, 2, 2, 1), (2, 1, 1, 2), (2, 1, 2, 1), (2, 2, 2, 2).

How to approach this problem?

• what is the total number of candies? – Dheeraj Kumar Dec 20 '14 at 11:23
• Assume Candies are infinite... – savvi singh Dec 20 '14 at 11:24
• There need not be more than $N(B+G)$ candies or in fact $2N\min(B,G)$ candies – Henry Dec 20 '14 at 11:32
• @Henry: yes you are right about that – savvi singh Dec 20 '14 at 11:35
• Due to the symmetry of the problem, you may as well assume that $B \leq G$. – Gabe Cunningham Dec 20 '14 at 11:43

With the function $c(m,x,t)$ counting the number of ways of distributing $m$ candies among $x$ people so nobody received more than $t$ (but they could receive zero), the answer would be $$\sum_{m=\max(B,G)}^{N\min(B,G)}\; c(m-B,B,N-1)c(m-G,G,N-1)$$

Added: To calculate $c(m,x,t)$, note that for all $t$ you start with $c(0,0,t)=1$ and $c(m,0,t)=0$ for $m \gt 0$, and then for $x\gt 0$ you can use:

$$c(m,x,t)=\sum_{j=0}^{\min(m,t)} c(m-j,x-1,t).$$

E.g. if $t=1$ then you get a table for $c(m,x,t)$ starting

x  m:0 1 2 3
-  ---------
0    1 0 0 0
1    1 1 0 0
2    1 2 1 0
3    1 3 3 1


while if $t=2$ then you get a table for $c(m,x,t)$ starting

x  m:0 1 2 3
-  ---------
0    1 0 0 0
1    1 1 1 0
2    1 2 3 2
3    1 3 6 7


Considering your example of $B=1$, $G=2$, $N=3$ we get $$c(2-1,1,3-1)c(2-2,2,3-1)+c(3-1,1,3-1)c(3-2,2,3-1)$$ $$=c(1,1,2)c(0,2,2)+c(2,1,2)c(1,2,2)$$ $$=1\times 1 + 1\times 2 = 3$$

while considering your example of $B=2$, $G=2$, $N=2$ we get $$c(2-2,2,2-1)c(2-2,2,2-1)+c(3-2,2,2-1)c(3-2,2,2-1)+c(4-2,2,2-1)c(4-2,2,2-1)$$ $$=c(0,2,1)c(0,2,1)+c(1,2,1)c(1,2,1)+c(2,2,1)c(2,2,1)$$ $$=1\times 1 + 2\times 2 + 1\times 1 = 6$$

so this approach reproduces your expected results.

• how to check if sum of candies given to boys is equal to sum of candies given to girls!!also each student receives atleast one candy!! – savvi singh Dec 20 '14 at 12:24
• @savvi singh: the number of ways of distributing $m-B$ balls among $B$ boys so each gets no more than $N-1$ is the same as the the number of ways of distributing $m$ balls among $B$ boys so each gets no more than $N$ and each gets at least one. Similarly the number of ways of distributing $m-G$ balls among $G$ girls so each gets no more than $N-1$ is the same as the the number of ways of distributing $m$ balls among $G$ girls so each gets no more than $N$ and each gets at least one. So this meets both your points. Calculating $c(m,x,t)$ is the hard part. – Henry Dec 20 '14 at 16:42

Each boy should get G number of candies and each girl should get B number of candies. This would ensure that sum of the candies received by boys and girls is equal.