Using generating functions to count number of ways to plan a semester

combinatoricsgenerating-functionsinteger-partitionssolution-verification

This is the question:

The semester of a college consists of n days. In how many ways can we separate the semester into sessions if each session has to consist of at least five days?

My work:
If $A(x)$ is the generating function for making subintervals of length $\geq 5$, then
$A(x)=\sum_{k \geq 5}x^k$. Now, If B(x) is the generating function for splitting the n days into disjoint nonempty subintervals, then, by composition, $B(x)=\frac{1}{1-A(x)}$. However, this does not give the answer. (Image from the book "Introduction to Enumerative And Analytic Combinatorics", Miklos Bona)

I want to know where I am going wrong and a solution to this question.

Best Answer

You want to count ordered partitions of $n$ into parts of size at least $5$. You have $$A(x)=x^5+x^6+\dots= \frac{x^5}{1-x}$$ and \begin{align} B(x) &= \frac{1}{1-A(x)} = \frac{1}{1-\frac{x^5}{1-x}} = \frac{1-x}{1-x-x^5} \\ &= 1x^0 + 1x^5 + 1x^6 + 1x^7 + 1x^8 + 1x^9 + 2 x^{10} + 3 x^{11} + 4 x^{12} + 5 x^{13} + 6 x^{14} + 8 x^{15} + \dots \end{align} These coefficients look correct. For example, $2x^{10}$ corresponds to $10$ and $5+5$. The $3x^{11}$ corresponds to $11$, $6+5$, and $5+6$. Why do you doubt it?


Alternatively, let $b_n$ be the desired count of partitions. Clearly, $$b_n = \begin{cases} 1 &\text{if $n=0$}\\ 0 &\text{if $n\in\{1,2,3,4\}$}\\ \end{cases} \tag1$$ For $n \ge 5$, condition on the size of the first part to obtain recurrence $$b_n = \sum_{k=5}^n b_{n-k} \tag2$$ Now $(1)$ and $(2)$ imply that \begin{align} B(x) &= 1x^0 + \sum_{n=5}^\infty \left(\sum_{k=5}^n b_{n-k}\right)x^n\\ &= 1 +\sum_{k=5}^\infty x^k \sum_{n=k}^\infty b_{n-k} x^{n-k}\\ &= 1 +\sum_{k=5}^\infty x^k B(x) \\ &= 1 +B(x) \frac{x^5}{1-x}. \end{align} Solving for $B(x)$ yields $$B(x)=\frac{1}{1-\frac{x^5}{1-x}} =\frac{1-x}{1-x-x^5}.$$

Related Question