Discrete Mathematics - Is my answer correct?

Question

$x_1 + x_2 + x_3 = 15$ where $x_1$ and $x_2$ and $x_3$ are non negative integers. How many solutions are there when $1\le x_1\le 6$?

the solution i came up with is = $\binom{15+3-1}{15} - \binom{6+3-1}{6}$

Is this correct?

Is just $x_1$ between $1$ and $6$ or all three variables? And what's the reasoning behind your solution? — mathse, Jun 03 '14 at 14:11
yeah just x1 is from 1 to 6. Well the answer is just a guess thats why i need confirmation. — sam, Jun 03 '14 at 14:13

André Nicolas · Accepted Answer · 2014-06-03T14:41:37.667

An expression like your answer is correct.

We want to distribute $15$ identical candies between $3$ kids, so that Kid 1 gets between $1$ and $6$ candies. We use Stars and Bars ideas that are familiar to you.

There are $\binom{15+3-1}{15}$ ways to give out the candies without restriction. We want to remove the ways in which Kid 1 gets $0$, and also the ways she gets more than $6$.

Giving Kid 1 $0$ means we are distributing $15$ candies among $2$ kids. The number of ways is $\binom{15+2-1}{15}$.

Now we count the number of ways Kid 1 gets more than $6$. Give her $7$. Now we have $8$ candies, to be distributed among $3$ kids. The number of ways is $\binom{8+3-1}{8}$.

The total is therefore $\dbinom{15+3-1}{15}-\dbinom{15+2-1}{15}-\dbinom{8+3-1}{8}$.

Remark: Stars and Bars is overkill for $3$ kids, but would work equally simply for a problem with the same structure, but more candies and kids.

You are welcome. By the way, I prefer $\binom{n+k-1}{k-1}$ as the number of ways to give $n$ candies to $k$ kids, but used your equivalent $\binom{n+k-1}{n}$. — André Nicolas, Jun 03 '14 at 14:52

Dahn · Answer 2 · 2014-06-03T14:35:27.880

1

I am unsure of how you reached your answer, however, let's look at the problem this way:

Let's look at a simple case. Say $x_1$ is $1$. Then you are asking the question how many non-negative integer solutions are there to $x_2+x_3=14$. It is not too hard to verify that there is exactly fifteen solutions (careful with those OBOEs!).

Now, there's five more $x_1$'s to go through. Each of them is going to give you $15-x_1+1$ solutions. That makes up for the sum $$ \sum^6_{x_n=1}{15-x_1+1}=15+14+13+12+11+10=75$$

Which is different from your answer $136-28=108$

edited Jun 03 '14 at 14:35

answered Jun 03 '14 at 14:14

Dahn

5,574

The number of nonnegative solutions to $x+y=14$ is $15$ and your summation should start with $15$ and end at $10$. ($14=14+0=13+1=\cdots=0+14$). – mathse Jun 03 '14 at 14:33
So, in fact, my original answer was correct? – Dahn Jun 03 '14 at 14:36
1

The current one is correct, it seems to me. – mathse Jun 03 '14 at 14:37

score 1 · Answer 3 · answered Jun 03 '14 at 14:41

The number of compositions of $n$ with $k$ parts is $\binom{n+k-1}{n}=\binom{n+k-1}{k-1}$, so your solution subtracts from all solutions the solutions where all three variables sum up to $6$, which is not what you are looking for.

Generalizing Dahn Jahn's answer, we find

$$\sum_{i=1}^m\binom{n-i+k-1-1}{k-1-1}=\sum_{i=1}^{m}\binom{n-i+k-2}{k-2}$$

as the solution whenever $x_1$ satisfies $1\le x_1\le m$ (in your example $k=3,n=15$).

Discrete Mathematics - Is my answer correct?

3 Answers3