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

Author

Arnold Knopfmacher, Jan 21 2003

Keywords

• nonn

Comments

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

Examples

			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
		

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

Crossrefs

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

Programs

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 *)

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

Extensions

More terms from Benoit Cloitre, Jan 21 2003