Given a question as follows.
We must go shopping either everyday or every 2 days. How many distinct sequences are there in 14 days? Note that there is an additional constraint where there must be a shopping on the 14th day.
Attempt
Some possible sequences for illustration purpose only.
$\{(1,2),(3,4),(5,6),(7,8),(9,10),(11,12),(13,14)\}$
$\{(1,2),(3),(4,5),(6,7),(8,9),(10,11),(12,13),(14)\}$
$\{(1),(2,3),(4,5),(6,7),(8,9),(10,11),(12,13),(14)\}$
$\{(1),(2),(3),(4),(5),(6),(7),(8),(9),(10),(11),(12),(13),(14)\}$
etc
Convert the sequence above into the following
- $\{2,2,2,2,2,2,2\}$
- $\{2,1,2,2,2,2,2, 1\}$
- $\{1,2,2,2,2,2,2, 1\}$
- $\{1,1,1,1,1,1,1,1,1,1,1,1,1,1\}$
- etc
It is about partitioning 14 balls into $k$ boxes ($7\leq k\leq 14$) in which each box must contain at least one ball and at most 2 balls.
I translated this problem into finding the sum of coefficients of $x^{14}$ in expanding $(x+x^2)^i$ for $7\leq i\leq 14$. The sum is 610 with the help of Mathematica code below.
Table[Coefficient[(x + x^2)^i, x, 14], {i, 7, 14}] // Total
My attempt with hand leads to a tedious calculation at the end as follows.
\begin{align} \text{Required answer} &=[x^{14}]\sum_{i=7}^{14}\left(x+x^2\right)^i\\ &=[x^{14}]\sum_{i=7}^{14}x^i\left(1+x\right)^i\\ &=[x^{14}]\left(x^7\left(1+x\right)^7\sum_{i=0}^{7}\left(1+x\right)^i\right)\\ &=[x^{7}]\left(\left(1+x\right)^7\sum_{i=0}^{7}\left(1+x\right)^i\right)\\ &=[x^{7}]\sum_{k=0}^{7}\sum_{i=0}^{7}\sum_{j=0}^{i} {7 \choose k} {i \choose j} x^{j+k} \end{align}
Does the last triple summation have a simple representation (if there are any identities)?
If $a_n$ means the number of shoppings in $n$ days then we have $a_1=2$ and $a_2 = 3$ and $$a_{n+1}=a_n+a_{n-1}$$ then we found $a_{14}$ in $$2,3,5,8,13,21,34,55,89,144,233,377,610,987,...$$ and it is $987$.
If we write $0$ for day when we don't go and $1$ when we go we have: