# Suitable closed form for the A079501

• Let $$a(n)$$ be A079501 (i.e., number of compositions of the integer $$n$$ with strictly smallest part in the first position).

• The sequence begins with

$$1, 1, 2, 2, 4, 5, 8, 12, 19, 28, 45, 70, 110, 173, 275$$

• Let

$$b(n) = 1 + \sum\limits_{i=1}^{\left\lfloor\frac{n}{2}\right\rfloor}\sum\limits_{j=0}^{\left\lfloor\frac{n-2i-1}{i+1}\right\rfloor}\binom{n - i(j+2) - 1}{j}$$

I conjecture that $$b(n)=a(n).$$

Here is the PARI/GP program to compute $$b(n)$$:

b(n) = 1 + sum(i = 1, n\2, sum(j=0, (n-2*i-1)\(i+1), binomial(n - i*(j+2) - 1, j)))


Is there a way to prove it?

• $$i$$ is the first part in the composition
• $$j + 1$$ is the number of other parts in the composition
• $$+1$$ accounts for the case that there is only one part
Summing over $$i$$ and $$j$$, we want to count the number of $$a_1,...,a_{j + 1}$$ such that $$i + (i + 1 + a_1) + \cdots + (i + 1 + a_{j + 1}) = n$$ or equivalently $$a_1 + \cdots + a_{j + 1} = n - (j + 1)\cdot (i + 1) - i$$ which is $$\binom{n - (j + 1)\cdot (i + 1) - i + (j + 1) - 1}{(j + 1) - 1} = \binom{n - (j + 2)\cdot i - 1}{j}$$