A105039 Number of compositions of n with unique smallest part.

1, 1, 3, 3, 8, 11, 20, 34, 59, 96, 167, 282, 475, 800, 1352, 2275, 3828, 6426, 10785, 18085, 30297, 50698, 84770, 141623, 236425, 394381, 657380, 1094975, 1822628, 3031843, 5040129, 8373594, 13903588, 23072567, 38267330, 63435438, 105103059

Offset

1,3

Links

Vincenzo Librandi, Table of n, a(n) for n = 1..1000

Formula

G.f.: Sum(k*x^(2*k-1)/((1-x^k)*(1-x)^(k-1)), k=1..infinity).

Also (1-x)^2*Sum(x^k/(1-x-x^(k+1))^2, k=1..infinity). - Vladeta Jovovic, Apr 05 2005

a(n) = 1 + sum(k=2..[(n+3)/2], k * sum(s=1..[(n-1)/k], binomial(n-k*s-1, k-2) ) ). - Max Alekseyev, Apr 15 2005

a(n) ~ (2*sqrt(5)-4)/10 * n * ((1+sqrt(5))/2)^n. - Vaclav Kotesovec, May 02 2014

Equivalently, a(n) ~ n * phi^(n-3) / 5, where phi = A001622 is the golden ratio. - Vaclav Kotesovec, Dec 07 2021

Example

a(5) = 8 because we have 5, 14, 41, 23, 32, 122, 212 and 221.

Maple

G:= sum(k*x^(2*k-1)/((1-x^k)*(1-x)^(k-1)), k=1..70): Gser:=series(G, x=0, 44): seq(coeff(Gser, x^n), n=1..41); # Emeric Deutsch, Apr 13 2005

Mathematica

nn=37; Drop[CoefficientList[Series[Sum[x^j/(1-x^(j+1)/(1-x))^2, {j, 1, nn}], {x, 0, nn}], x], 1] (* Geoffrey Critzer, Mar 31 2014 *)

Prog

(PARI) a(n)=1+sum(k=2, (n+3)\2, k*sum(s=1, (n-1)\k, binomial(n-k*s-1, k-2))) (Alekseyev)

Crossrefs

Cf. A079501, A097979.

Column k=1 of A238342.

Sequence in context: A233174 A185350 A279910 * A358834 A346005 A276552

Adjacent sequences: A105036 A105037 A105038 * A105040 A105041 A105042

Keyword

easy,nonn

Author

Vladeta Jovovic, Apr 03 2005

Extensions

More terms from Emeric Deutsch and Max Alekseyev, Apr 13 2005

Status

approved