Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

I was solving a combinatorics problem when I encountered difficulties. The problem was:

$x_1 \in \{0,1\}$

$x_2 \in \{0,1,2\}$

. .

$x_{n-1}\in\{0,1,2..,n-1\}$

We have to find the number of ways we can choose $x_1,x_2..x_{n-1}$ such that

$x_1+x_2+..+x_{n-1}=k$

$Given \ k\in\mathbb N \ and \ k\leq \frac{n(n-1)}{2}$

I approached this problem by developing a generating function.

$(t^0+t^1)(t^0+t^1+t^2)...(t^0+t^1+...+t^{n-1})$

Which solves to

$\frac{(1-t^2)(1-t^3)...(1-t^n)}{(1-t)^{n-1}}$

I planned to find the coefficient of $t^k$ in the expression above but i just cannot find a way. I dont know where I am not able to catch the pattern or something. I looked it up, and I stumbled upon q factorials whose definition seemed to be precisely the generating function I have encountered above. My aim remains the same, to calculate the coefficient of $t^k$ in the above generating function, which you may consider to be the coefficient of $q^k$ in the q factorial of $n$, thus effectively solving the original problem. Please help me find the coefficient and if you have an alternative approach to the original problem, that would be welcome! Thanks!

For reference : http://mathworld.wolfram.com/q-Factorial.html

share|improve this question
    
oeis.org/A008302 –  Samuel Jan 13 '13 at 10:15

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Browse other questions tagged or ask your own question.