2
$\begingroup$

I'm having the following assignment:

For which positive integer $n$ will the equations $ x_1 + x_2 + x_3 + \ldots + x_{19} = n \tag{1}$ $ y_1 + y_2 + y_3 + \ldots + y_{64} = n \tag{2}$ have the same number of positive integer solutions?

I've gotten this far, with the help of notes from my teachers lectures. Though, I have been searching and looking for the answer to the following question:

How come that the following is true? Where does the $n$ disappear, and how can it be substituted with substracting one?

$\binom{n-1}{n-64} = \binom{n-1}{64-1} = \binom{n-1}{63}$

I'm thankful for any help I can get to understand this better!

Thanks, Z

2 Answers 2

2

I expect you know that the number of positive integer solutions of $w_1+w_2+\cdots +w_k=n$ is $\dbinom{n-1}{k-1}$.

So we want $\dbinom{n-1}{18}=\dbinom{n-1}{63}$.

The binomial coefficients $\dbinom{m}{i}$ are the same written forwards as backwards. Familiar, but requiring proof, is that the binomial coefficients increase until midway, and then decrease.

So the only way we can have $\dbinom{n-1}{18}=\dbinom{n-1}{63}$ is if $18+63=n-1$. That identifies $n$.

Remark: The fact that the number of positive solutions of $w_1+\cdots+w_k=n$ is $\dbinom{n-1}{k-1}$ is proved by a Stars and Bars argument.

Briefly, think of $n$ as $n$ pebbles laid out in a row. These pebbles have $n-1$ "gaps" between them. Choose $k-1$ of these gaps to put a separator into. This can be done in $\dbinom{n-1}{k-1}$ ways.

Let $w_1$ be the number of pebbles from the left end to the first separator, let $w_2$ be the number of pebbles between the first separator and the second, and so on. That gives us a solution of $w_1+\cdots+w_k=n$, and all solutions are obtained in this way. So there are exactly as many solutions as there are ways to place the separators.

  • 0
    Very nicely explained, I followed it all along! Thank you very much!2012-11-12
0

I want to explain you why

$\binom{n-1}{n-64} = \binom{n-1}{64-1} = \binom{n-1}{63}$

number $\binom{n}{k}$ gives number of chooses of $k$ objects from total $n$ objects but if we choose $k$ from $n$ objects we always left $n-k$ unchosen objects from $n$ objects that mean $\binom{n}{k}=\binom{n}{n-k}$ Above equation is called Theorem of symmetrie now applying T.S. we have that
$\binom{n-1}{n-64} = \binom{n-1}{n-1-(n-64)} = \binom{n-1}{n-1-n+64)}= \binom{n-1}{63}$