2

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

Dunka
  • 2,787
  • 12
  • 41
  • 69

1 Answers1

2

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

Markus Scheuer
  • 108,315