Interesting Combinatorics Question

Printable View

September 9th 2010, 01:24 AM
Boysilver

Interesting Combinatorics Question

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

$a_0+\ldots+a_n<n$ ?

I think the answer must be ${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.
September 9th 2010, 01:35 AM
yeKciM

Quote:

Originally Posted by Boysilver

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

$a_0+\ldots+a_n<n$ ?

I think the answer must be ${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 :D
if you put

$n= 5 ; t=3$

you get

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

so if you look that $a_n \in \mathbb{N}$ you canthan for n=5 have
$1+2 < n$ and of course $2+1 < n$ but that's if the place of them is important ( $a_0, a_1 , ... ,a_n$ )
September 9th 2010, 02:01 AM
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 $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

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

is 28 possibilities.

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

Just for clarity, I'll list them here:

$(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 $t+n \choose t-1$ in the general case for any t and n.
September 9th 2010, 02:09 AM
yeKciM

aaaaaah that:D:D:D

it's okay :D
September 9th 2010, 05:10 AM
undefined

Quote:

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 $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

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

is 28 possibilities.

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

Just for clarity, I'll list them here:

$(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 $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 $f(n,t)$ . Restrict $n\ge0,t>0$ . We have

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

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

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

Edit: fixed mistake.
September 9th 2010, 06:16 AM
Plato

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

That happens to equal $\displaystyle \binom{n + t}{t-1}$ .
September 10th 2010, 08:05 PM
aman_cc

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

using combinatorial arguments?
September 11th 2010, 11:31 AM
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 $a_0,\ldots,a_n$ such that (for a given positive integer k)

$a_0+\ldots+a_n=k$

is $n+k\choose k$ ? Sorry if I'm overlooking something obvious but have been thinking about this for a while.
September 11th 2010, 12:05 PM
undefined

Quote:

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 $a_0,\ldots,a_n$ such that (for a given positive integer k)

$a_0+\ldots+a_n=k$

is $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
September 11th 2010, 12:06 PM
Plato

Quote:

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 $a_0,\ldots,a_n$ such that (for a given positive integer k)
$a_0+\ldots+a_n=k$
is $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 $n+1$ variables, $a_0,a_1,\cdots,a_n$ .
To put $k$ identical items into $n+1$ different cells can be done in $\displaystyle \binom{k+(n+1)-1}{k}=\binom{k+n}{k}$ ways.