Say we are given . In how many ways can we find positive integers such that

?

I think the answer must be (as I'm trying to follow something in a book and this would make sense) but I can't see how it follows.

Printable View

- Sep 9th 2010, 02:24 AMBoysilverInteresting Combinatorics Question
Say we are given . In how many ways can we find positive integers such that

?

I think the answer must be (as I'm trying to follow something in a book and this would make sense) but I can't see how it follows. - Sep 9th 2010, 02:35 AMyeKciM
- Sep 9th 2010, 03:01 AMBoysilver
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 (also, previously I said "positive integers" - I meant non-negative integers) such that

is 28 possibilities.

(I said " " last time - I meant . Sorry again!)

Just for clarity, I'll list them here:

(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 in the general case for any t and n. - Sep 9th 2010, 03:09 AMyeKciM
aaaaaah that:D:D:D

it's okay :D - Sep 9th 2010, 06:10 AMundefined
- Sep 9th 2010, 07:16 AMPlato
Here is an interesting connection.

I would have counted the total by .

That happens to equal . - Sep 10th 2010, 09:05 PMaman_cc
@Plato - Is there a good way to prove that

using combinatorial arguments? - Sep 11th 2010, 12:31 PMBoysilver
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 such that (for a given positive integer k)

is ? Sorry if I'm overlooking something obvious but have been thinking about this for a while. - Sep 11th 2010, 01:05 PMundefined
See theorem 2 here

Stars and bars (probability) - Wikipedia, the free encyclopedia - Sep 11th 2010, 01:06 PMPlato