1. ## Interesting Combinatorics Question

Say we are given $\displaystyle n,t \in \mathbb{N}$. In how many ways can we find positive integers $\displaystyle a_0,\ldots,a_n$ such that

$\displaystyle a_0+\ldots+a_n<n$ ?

I think the answer must be $\displaystyle {t+n\choose t-1}$ (as I'm trying to follow something in a book and this would make sense) but I can't see how it follows.

2. Originally Posted by Boysilver
Say we are given $\displaystyle n,t \in \mathbb{N}$. In how many ways can we find positive integers $\displaystyle a_0,\ldots,a_n$ such that

$\displaystyle a_0+\ldots+a_n<n$ ?

I think the answer must be $\displaystyle {t+n\choose t-1}$ (as I'm trying to follow something in a book and this would make sense) but I can't see how it follows.
perhaps i didn't quite understand what you have asking but that can be checked very easy
if you put

$\displaystyle n= 5 ; t=3$

you get

$\displaystyle \displaystyle \binom{8 }{2} = \frac {8\cdot 7 \cdot 6!}{6! \cdot 2 } = 28 >n ?$

so if you look that $\displaystyle a_n \in \mathbb{N}$ you canthan for n=5 have
$\displaystyle 1+2 < n$ and of course $\displaystyle 2+1 < n$ but that's if the place of them is important ($\displaystyle a_0, a_1 , ... ,a_n$ )

3. Yes, I didn't explain very clearly. In your example, what I'm saying is that I'd like to prove that the number of ways in which we can find non-negative integers $\displaystyle a_0,a_1,a_2,a_3,a_4,a_5$ (also, previously I said "positive integers" - I meant non-negative integers) such that

$\displaystyle a_0+a_1+a_2+a_3+a_4+a_5<3$

is 28 possibilities.

(I said "$\displaystyle \ldots < n$" last time - I meant $\displaystyle <t$. Sorry again!)

Just for clarity, I'll list them here:

$\displaystyle (a_0,a_1,a_2,a_3,a_4,a_5) =$ (0,0,0,0,0,0), (1,0,0,0,0,0), (1,0,0,0,0,1), (1,0,0,0,1,0), (1,0,0,1,0,0), (1,0,1,0,0,0), (1,1,0,0,0,0), (0,1,0,0,0,0), (0,1,0,0,0,1), (0,1,0,0,1,0), (0,1,0,1,0,0), (0,1,1,0,0,0), (0,0,1,0,0,0), (0,0,1,0,0,1), (0,0,1,0,1,0), (0,0,1,1,0,0), (0,0,0,1,0,0), (0,0,0,1,0,1), (0,0,0,1,1,0), (0,0,0,0,1,0), (0,0,0,0,1,1), (0,0,0,0,0,1), (2,0,0,0,0,0), (0,2,0,0,0,0), (0,0,2,0,0,0), (0,0,0,2,0,0), (0,0,0,0,2,0), (0,0,0,0,0,2).

So there are indeed 28. I'd like a way of proving that the number of ways will be $\displaystyle t+n \choose t-1$ in the general case for any t and n.

4. aaaaaah that

it's okay

5. Originally Posted by Boysilver
Yes, I didn't explain very clearly. In your example, what I'm saying is that I'd like to prove that the number of ways in which we can find non-negative integers $\displaystyle a_0,a_1,a_2,a_3,a_4,a_5$ (also, previously I said "positive integers" - I meant non-negative integers) such that

$\displaystyle a_0+a_1+a_2+a_3+a_4+a_5<3$

is 28 possibilities.

(I said "$\displaystyle \ldots < n$" last time - I meant $\displaystyle <t$. Sorry again!)

Just for clarity, I'll list them here:

$\displaystyle (a_0,a_1,a_2,a_3,a_4,a_5) =$ (0,0,0,0,0,0), (1,0,0,0,0,0), (1,0,0,0,0,1), (1,0,0,0,1,0), (1,0,0,1,0,0), (1,0,1,0,0,0), (1,1,0,0,0,0), (0,1,0,0,0,0), (0,1,0,0,0,1), (0,1,0,0,1,0), (0,1,0,1,0,0), (0,1,1,0,0,0), (0,0,1,0,0,0), (0,0,1,0,0,1), (0,0,1,0,1,0), (0,0,1,1,0,0), (0,0,0,1,0,0), (0,0,0,1,0,1), (0,0,0,1,1,0), (0,0,0,0,1,0), (0,0,0,0,1,1), (0,0,0,0,0,1), (2,0,0,0,0,0), (0,2,0,0,0,0), (0,0,2,0,0,0), (0,0,0,2,0,0), (0,0,0,0,2,0), (0,0,0,0,0,2).

So there are indeed 28. I'd like a way of proving that the number of ways will be $\displaystyle t+n \choose t-1$ in the general case for any t and n.
I find it interesting and am not sure how to derive the expression you got, but there is a simple recurrence.

Call the number we're looking for $\displaystyle f(n,t)$. Restrict $\displaystyle n\ge0,t>0$. We have

$\displaystyle \forall n:f(n,1)=1$

$\displaystyle \forall t:f(0,t)=t$

$\displaystyle \displaystyle f(n,t)=\sum_{k=0}^{t-1} f(n-1,t-k)\ \ \ \ ,\ \ \ t > 1\ \&\ n > 0$

Edit: fixed mistake.

6. Here is an interesting connection.
I would have counted the total by $\displaystyle \displaystyle \sum\limits_{k = 0}^{t - 1} \binom{n + k}{k}$.

That happens to equal $\displaystyle \displaystyle \binom{n + t}{t-1}$.

7. @Plato - Is there a good way to prove that
$\displaystyle \displaystyle \sum\limits_{k = 0}^{t - 1} \binom{n + k}{k} = \displaystyle \binom{n + t}{t-1}$

using combinatorial arguments?

8. It's easy to prove the above by induction but I agree that there looks like there should be some nicer, intuitive combinatorial argument.

I'm struggling with the part before though - how do we know that the number of ways of finding non-negative integers $\displaystyle a_0,\ldots,a_n$ such that (for a given positive integer k)

$\displaystyle a_0+\ldots+a_n=k$

is $\displaystyle n+k\choose k$ ? Sorry if I'm overlooking something obvious but have been thinking about this for a while.

9. Originally Posted by Boysilver
It's easy to prove the above by induction but I agree that there looks like there should be some nicer, intuitive combinatorial argument.

I'm struggling with the part before though - how do we know that the number of ways of finding non-negative integers $\displaystyle a_0,\ldots,a_n$ such that (for a given positive integer k)

$\displaystyle a_0+\ldots+a_n=k$

is $\displaystyle n+k\choose k$ ? Sorry if I'm overlooking something obvious but have been thinking about this for a while.
See theorem 2 here

Stars and bars (probability) - Wikipedia, the free encyclopedia

10. Originally Posted by Boysilver
I'm struggling with the part before though - how do we know that the number of ways of finding non-negative integers $\displaystyle a_0,\ldots,a_n$ such that (for a given positive integer k)
$\displaystyle a_0+\ldots+a_n=k$
is $\displaystyle n+k\choose k$ ? Sorry if I'm overlooking something obvious but have been thinking about this for a while.
Sorry, but it me quite sometime to recall working on this.
We actually have $\displaystyle n+1$ variables, $\displaystyle a_0,a_1,\cdots,a_n$.
To put $\displaystyle k$ identical items into $\displaystyle n+1$ different cells can be done in $\displaystyle \displaystyle \binom{k+(n+1)-1}{k}=\binom{k+n}{k}$ ways.