0
$\begingroup$

Let $p_k(n)$ denote the number of partitions of the positive integer $n$ into at most $k$ parts. I am trying to answer a question which asks me to show that the generating function for the sequence $\{ p_k(n) \}$ is given by $$ P_k(n) := \frac{1}{\prod_{r=1}^k (1-x^r)} $$

Can anyone help me to understand how this might be done?

$\endgroup$
1
$\begingroup$

Recall that $$\frac{1}{1-x^a}=\sum _{i = 0}^{\infty}x^{ai},$$ hence the product looks like $$(1+x+x^2+\cdots +\color{red}{x^{x_1}}+\cdots )(1+x^2+x^4+\cdots +\color{red}{x^{2x_2}}+\cdots )\cdots (1+x^k+x^{2k}+\cdots +\color{red}{x^{kx_k}}+\cdots)$$ so when you multiply together you are picking the $x_1,x_2,\cdots ,x_k$ in each part and so the coefficient that you ended up with $x^n$ is $$\sum _{1*x_1+2x_2+\cdots kx_k=n}1=|\{(x_1,\cdots ,x_k):\sum _{i = 1}^ki*x_i=\underbrace{1+1+\cdots +1}_{x_1}+\underbrace{2+\cdots +2}_{x_2}+\cdots +\underbrace{k+\cdots +k}_{x_k}=n\}|=p_k(n)$$

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.