A079501 Number of compositions of the integer n with strictly smallest part in the first position.

1, 1, 2, 2, 4, 5, 8, 12, 19, 28, 45, 70, 110, 173, 275, 436, 695, 1107, 1769, 2831, 4537, 7276, 11683, 18774, 30194, 48592, 78247, 126062, 203192, 327645, 528518, 852815, 1376491, 2222294, 3588628, 5796196, 9363458, 15128631, 24447014, 39510108

Offset

1,3

Comments

Also number of compositions of n such that the first part is divisible by the number of parts . [Vladeta Jovovic, Dec 02 2009]

References

Arnold Knopfmacher and Neville Robbins, Compositions with parts constrained by the leading summand, Ars Combin. 76 (2005), 287-295.

Links

Alois P. Heinz, Table of n, a(n) for n = 1..1000

Formula

G.f.: Sum_{k>=1} (1-z)*z^k/(1-z-z^(k+1)).

G.f.: Sum_{k>=1} z^(2*k-1)/((1-z^k)*(1-z)^(k-1)), cf. A105039. - Vladeta Jovovic, Apr 05 2005

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

G.f.: Sum_{n>=1} q^n/(1-Sum_{k>=n+1} q^k). - Joerg Arndt, Jan 03 2024

Example

The a(9)=19 such compositions of 9 are
[ 1]  [ 1 2 2 2 2 ]
[ 2]  [ 1 2 2 4 ]
[ 3]  [ 1 2 3 3 ]
[ 4]  [ 1 2 4 2 ]
[ 5]  [ 1 2 6 ]
[ 6]  [ 1 3 2 3 ]
[ 7]  [ 1 3 3 2 ]
[ 8]  [ 1 3 5 ]
[ 9]  [ 1 4 2 2 ]
[10]  [ 1 4 4 ]
[11]  [ 1 5 3 ]
[12]  [ 1 6 2 ]
[13]  [ 1 8 ]
[14]  [ 2 3 4 ]
[15]  [ 2 4 3 ]
[16]  [ 2 7 ]
[17]  [ 3 6 ]
[18]  [ 4 5 ]
[19]  [ 9 ]
- Joerg Arndt, Jan 01 2013

Maple

b:= proc(n, s) option remember; `if`(n=0, 1, add(
      `if`(n-j>0 and n-j<=s, 0, b(n-j, s)), j=s+1..n))
    end:
a:= n-> 1 +add(b(n-j, j), j=1..n/2):
seq(a(n), n=1..60);  # Alois P. Heinz, Apr 29 2014

Mathematica

b[n_, s_] := b[n, s] = If[n == 0, 1, Sum[ If[n - j > 0 && n - j <= s, 0, b[n - j, s]], {j, s + 1, n}]]; a[n_] := 1 + Sum[b[n - j, j], {j, 1, n/2}]; Table[a[n], {n, 1, 60}] (* Jean-François Alcover, Jan 16 2015, after Alois P. Heinz *)

Crossrefs

Cf. A168655, A168656, A168657. [From Vladeta Jovovic, Dec 02 2009]

Sequence in context: A172128 A274154 A274153 * A093335 A093333 A116085

Adjacent sequences: A079498 A079499 A079500 * A079502 A079503 A079504

Keyword

nonn

Author

Arnold Knopfmacher, Jan 21 2003

Extensions

More terms from Benoit Cloitre, Jan 21 2003

Status

approved