Printable View
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 :DQuote:
Originally Posted by Boysilver
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$ )
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.
aaaaaah that:D:D:D
it's okay :D
I find it interesting and am not sure how to derive the expression you got, but there is a simple recurrence.Quote:
Originally Posted by Boysilver
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.
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} $.
@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?
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 hereQuote:
Originally Posted by Boysilver
Stars and bars (probability) - Wikipedia, the free encyclopedia
Sorry, but it me quite sometime to recall working on this.Quote:
Originally Posted by Boysilver
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.
