Results 1 to 10 of 10

Math Help - Interesting Combinatorics Question

  1. #1
    Junior Member
    Joined
    Oct 2009
    Posts
    38

    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.
    Follow Math Help Forum on Facebook and Google+

  2. #2
    Senior Member yeKciM's Avatar
    Joined
    Jul 2010
    Posts
    456
    Quote Originally Posted by Boysilver View Post
    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
    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 )
    Last edited by yeKciM; September 9th 2010 at 02:00 AM.
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Junior Member
    Joined
    Oct 2009
    Posts
    38
    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.
    Follow Math Help Forum on Facebook and Google+

  4. #4
    Senior Member yeKciM's Avatar
    Joined
    Jul 2010
    Posts
    456
    aaaaaah that

    it's okay
    Follow Math Help Forum on Facebook and Google+

  5. #5
    MHF Contributor undefined's Avatar
    Joined
    Mar 2010
    From
    Chicago
    Posts
    2,340
    Awards
    1
    Quote Originally Posted by Boysilver View Post
    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.
    Last edited by undefined; September 9th 2010 at 05:31 AM.
    Follow Math Help Forum on Facebook and Google+

  6. #6
    MHF Contributor

    Joined
    Aug 2006
    Posts
    18,824
    Thanks
    1717
    Awards
    1
    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} .
    Follow Math Help Forum on Facebook and Google+

  7. #7
    Super Member
    Joined
    Apr 2009
    Posts
    678
    Thanks
    1
    @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?
    Follow Math Help Forum on Facebook and Google+

  8. #8
    Junior Member
    Joined
    Oct 2009
    Posts
    38
    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.
    Follow Math Help Forum on Facebook and Google+

  9. #9
    MHF Contributor undefined's Avatar
    Joined
    Mar 2010
    From
    Chicago
    Posts
    2,340
    Awards
    1
    Quote Originally Posted by Boysilver View Post
    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
    Follow Math Help Forum on Facebook and Google+

  10. #10
    MHF Contributor

    Joined
    Aug 2006
    Posts
    18,824
    Thanks
    1717
    Awards
    1
    Quote Originally Posted by Boysilver View Post
    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.
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Interesting Question...
    Posted in the Differential Geometry Forum
    Replies: 3
    Last Post: April 23rd 2010, 05:23 PM
  2. Interesting question
    Posted in the Discrete Math Forum
    Replies: 1
    Last Post: April 22nd 2009, 06:02 PM
  3. interesting question
    Posted in the Algebra Forum
    Replies: 4
    Last Post: January 27th 2009, 07:04 AM
  4. Interesting question ?....
    Posted in the Algebra Forum
    Replies: 3
    Last Post: January 4th 2009, 10:57 AM
  5. interesting question
    Posted in the Advanced Applied Math Forum
    Replies: 7
    Last Post: October 11th 2007, 09:48 PM

Search Tags


/mathhelpforum @mathhelpforum