Results 1 to 3 of 3

Math Help - Combinatorics question

  1. #1
    Newbie
    Joined
    Dec 2010
    Posts
    3

    Combinatorics question

    Suppose k,n \geq 0. How many k-tuples (x_1,\ldots,x_k) are there for which each x_i \geq 0 and x_1+\ldots+x_k \leq n?
    Follow Math Help Forum on Facebook and Google+

  2. #2
    MHF Contributor
    Joined
    Oct 2009
    Posts
    5,537
    Thanks
    778
    You can use Theorem 2 (the formula for multinomial coefficients, or multiset numbers) on this page to find the number of tuples whose sum is i for each i\le n. Then use equation (10) (and (4), if necessary) on this page.
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Member
    Joined
    Sep 2009
    Posts
    177
    Thanks
    1
    introduce anouter variable a≥1, and let  x_1+...+x_k+a=n Clearly, x_1+...+x_k<n Now, we solve this equality. Subtract one from both sides, and let u=a-1. Then u≥0--like the other variables. So now, we have n-1 on the RHS and k+1=>k + signs. So, there are (n-1+k, n-1) solutions to the inequality.
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Question on Combinatorics
    Posted in the Discrete Math Forum
    Replies: 6
    Last Post: May 3rd 2012, 09:15 PM
  2. Combinatorics Question
    Posted in the Discrete Math Forum
    Replies: 4
    Last Post: November 24th 2009, 12:46 PM
  3. Combinatorics Question
    Posted in the Discrete Math Forum
    Replies: 0
    Last Post: September 28th 2009, 09:55 AM
  4. Combinatorics question
    Posted in the Statistics Forum
    Replies: 2
    Last Post: December 16th 2008, 10:12 AM
  5. Combinatorics question
    Posted in the Advanced Math Topics Forum
    Replies: 5
    Last Post: December 8th 2007, 02:12 PM

Search Tags


/mathhelpforum @mathhelpforum