2
$\begingroup$

The Full Question

(a) What is the generating function for the number of integer compositions with $2$ parts?

(b) What is the generating function for the number of integer compositions with $3$ parts?

(c) What is the generating function for the number of integer compositions with $2$ or $3$ parts?

My Work

Part A

Let $n =$ the number we are finding compositions for

We are trying to solve all the solutions for $x_1 + x_2 = n$ where $ x_1,x_2\geq 1$ and $n\geq2$

The general case for this is $n-1$

Which means our generating function is given by $\sum_{n=2}^{\infty}(k-1)x^{k}$

Part B

Same thought process as part A

Part C

$C = A \cup B$ so $C(x)=A(x)+B(x)$

My Problem

I can't think of a closed form of the generating function I came up with in part A. It doesn't seem to match any of the basic generating functions I was given (These kind of problems usually reduce to one of those). Does anyone know a closed form for that GF?

The Generating Functions I know

enter image description here

$\endgroup$
2
$\begingroup$

Note: Since your work is quite ok, we concentrate on your question and add a small remark to part B.)

The generating function $\sum_{n=2}^{\infty}(n-1)x^n$ is a variation of case 8.)

Indeed, we can write: \begin{align*} \sum_{n=2}^{\infty}(n-1)x^n&=\sum_{n=0}^{\infty}(n+1)x^{n+2}\\ &=x^2\sum_{n=0}^{\infty}(n+1)x^{n}\\ &=x^2\sum_{n=0}^{\infty}\binom{n+1}{n}x^{n}\tag{1}\\ &=x^2\sum_{n=0}^{\infty}\binom{-2}{n}(-x)^{n}\tag{2}\\ &=\left(\frac{x}{1-x}\right)^2\tag{3} \end{align*}

Comment:

  • In (1) we write $(n+1)$ as binomial coefficient $\binom{n+1}{n}$

  • In (2) we use the identity $\binom{-k}{n}=\binom{k+n-1}{k}(-1)^n$

  • In (3) we use the generating function according to your table entry 8.)

Part B:

We observe: Since $$\frac{x}{1-x}=x^1+x^2+x^3+\ldots$$ carries as exponents the possible solutions $1,2,3,\ldots$ of one $x_i$ in $$x_1+x_2+x_3+\ldots+x_k=n\qquad k\geq 1, n\geq k$$ the number of compositions of $n$ of $k$ variables $x_1,x_2,\ldots,x_k$ is the coefficient of $x^n$ of $$\left(\frac{x}{1-x}\right)^k$$

In case $k=3$ we obtain therefore the generating function $$\left(\frac{x}{1-x}\right)^3$$

$\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.