Combinatorics question

**fermat** · January 10th 2011, 01:10 AM

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

**emakarov** · January 10th 2011, 01:44 AM

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.

**Chris11** · January 17th 2011, 03:56 PM

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.

Thread: Combinatorics question

LinkBack

Thread Tools

Display