Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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.

share|improve this question
2  
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

1 Answer 1

up vote 3 down vote accepted

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$.

share|improve this answer
    
I JUST realized that. Thank you. That fixes the "weirdness" I had with my current solution. –  Nicholas Mancuso Jan 22 '12 at 21:08

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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