Results 1 to 10 of 10

Thread: Interesting Combinatorics Question

  1. #1
    Junior Member
    Joined
    Oct 2009
    Posts
    40

    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.
    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 $\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$ )
    Last edited by yeKciM; Sep 9th 2010 at 02:00 AM.
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Junior Member
    Joined
    Oct 2009
    Posts
    40
    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.
    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 $\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.
    Last edited by undefined; Sep 9th 2010 at 05:31 AM.
    Follow Math Help Forum on Facebook and Google+

  6. #6
    MHF Contributor

    Joined
    Aug 2006
    Posts
    21,774
    Thanks
    2823
    Awards
    1
    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} $.
    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 \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
    40
    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.
    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 $\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
    Follow Math Help Forum on Facebook and Google+

  10. #10
    MHF Contributor

    Joined
    Aug 2006
    Posts
    21,774
    Thanks
    2823
    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 $\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.
    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: Apr 23rd 2010, 05:23 PM
  2. Interesting question
    Posted in the Discrete Math Forum
    Replies: 1
    Last Post: Apr 22nd 2009, 06:02 PM
  3. interesting question
    Posted in the Algebra Forum
    Replies: 4
    Last Post: Jan 27th 2009, 07:04 AM
  4. Interesting question ?....
    Posted in the Algebra Forum
    Replies: 3
    Last Post: Jan 4th 2009, 10:57 AM
  5. interesting question
    Posted in the Advanced Applied Math Forum
    Replies: 7
    Last Post: Oct 11th 2007, 09:48 PM

Search Tags


/mathhelpforum @mathhelpforum