# Math Help - combinatorial proof

1. ## combinatorial proof

i hate these proofs i never understand what they mean i cant seem to get me head around them all tips appreciated.

show that the number of integer sequences ( $e_{1},e_{2},...,e_{n})$such that $0\leq e_{i} , i=1,2,..,n$ and $e_{1} +e_{2} +...+e_{n}=k$ is equal to

( n + k - 1 ) (brackets are meant to be over k aswel...
k

thanks.

2. Hello,

Originally Posted by skystar
i hate these proofs i never understand what they mean i cant seem to get me head around them all tips appreciated.

show that the number of integer sequences ( $e_{1},e_{2},...,e_{n})$such that $0\leq e_{i} , i=1,2,..,n$ and $e_{1} +e_{2} +...+e_{n}=k$ is equal to

( n + k - 1 ) (brackets are meant to be over k aswel...
k

thanks.
I'll show you the way one of my teacher taught us

Make a word this way :

$\underbrace{a\dots a}_{e_1 \text{ times}}b\underbrace{a\dots a}_{e_2 \text{ times}}b \dots b\underbrace{a\dots a}_{e_n \text{ times}}$

Do you agree that there are $e_1+e_2+\dots+e_n=k$ letters a ?
Plus, there are $n-1$ letters b (I'll let you do the counting).
Therefore, this word has $k+(n-1)$ letters.

So we're looking for all words of $k+(n-1)$ letters and containing k letters a and n-1 letters b.

This is the part you have to understand : it's equivalent to finding the possible places where b can be.

So this is the combinations of (p-1) among k+(n-1)..

If I have time, I'll try to post an example...