# Stars and bars with lower bound on individual parts

I was assigned the following problem for homework and would like to double check that I have approached it correctly.

Let $k \geq 2n$. In how many ways can we distribute $k$ sweets to $n$ children, if each child is supposed to get at least 2 of them?

This is a standard stars-and-bars problem, with the added constraint that each child gets at least two. In other words:

$x_1 + x_2 + \cdots + x_n = k$, such that $x_i \geq 2$, for $0 \leq i \leq n$

We can reduce this problem to solving over $y_i$ such that $y_i = x_i - 2$ and $y_i \geq 0$.

$\sum_{i=0}^n y_i = k$ or $\sum_{i=0}^n (x_i - 2) = k$ which reduces to $\sum_{i=0}^n x_i = k + 2n$.

Plugging this into standard stars and bars we get $\binom{n + k + 2n - 1}{n - 1} = \binom{k + 3n - 1}{n - 1}$

Is this solution correct? Am I far off? This seems weird that the search space is bigger in the constrained version than the regular ($\geq 0$) version.

-
Can you distinguish between individual sweets? If not, then your basic idea appears to be sound, but your arithmetic is off. You should have $\sum y_i = k-2n$ and do stars-and-bars directly on that. (Also, in order for there to be $n$ children, your indices should be $1$ to $n$ or $0$ to $n-1$, not $0$ to $n$). – Henning Makholm Jan 22 '12 at 21:07
I realized this as I was going over what I typed. Thank you. – Nicholas Mancuso Jan 22 '12 at 21:09

Once you’ve given two sweets to every child, there are only $k-2n$ sweets to be distributed, so you should be looking at $y_1+\cdots+y_n=k-2n$.