A238089 Number of compositions of n such that the minimum part is equal to 1 and the first 1 occurs before any maximum part in the composition.

0, 0, 0, 1, 3, 7, 16, 34, 73, 152, 318, 657, 1356, 2784, 5703, 11647, 23740, 48290, 98073, 198887, 402837, 815032, 1647424, 3327112, 6714352, 13540995, 27292175, 54978561, 110697947, 222790629, 448211668, 901392243, 1812185325, 3642182184, 7318157714

Offset

0,5

Comments

We note that the definition implies that the maximum part of the composition must be strictly greater than 1.

Links

Alois P. Heinz, Table of n, a(n) for n = 0..800

Formula

a(n) = Sum_{i>=2} x^(i+1)/(1-Sum_{j=2..i-1} x^j)/(1 - Sum{k=1..i-1} x^k)/(1 - Sum_{m=1..i} x^m).

a(n) ~ 2^(n-1). - Vaclav Kotesovec, May 01 2014

Example

a(5) = 7 because we have: 1+4, 1+1+3, 1+2+2, 1+3+1, 1+1+1+2, 1+1+2+1, 1+2+1+1.

Maple

b:= proc(n, t, m) option remember;
      `if`(n=0, t, add(`if`(j=1 and m>1, b(n-1, 1, m),
      `if`(j>=m, b(n-j, 0, j), b(n-j, t, m))), j=1..n))
    end:
a:= n-> b(n, 0$2):
seq(a(n), n=0..45);  # Alois P. Heinz, Feb 17 2014

Mathematica

nn=30; CoefficientList[Series[Sum[x^(i+1)/(1-Sum[x^j, {j, 2, i-1}])/(1-Sum[x^k, {k, 1, i-1}])/(1-Sum[x^m, {m, 1, i}]), {i, 2, nn}], {x, 0, nn}], x]
(* or *)
Table[Length[Select[Level[Table[Select[Compositions[n, k], Count[#, 0]==0&], {k, 1, n}], {2}], Min[Position[#, 1]]<Min[Position[#, Max[#]]]&]], {n, 0, 10}]

Crossrefs

Sequence in context: A054455 A178455 A281811 * A335713 A026734 A026767

Adjacent sequences: A238086 A238087 A238088 * A238090 A238091 A238092

Keyword

nonn

Author

Geoffrey Critzer, Feb 17 2014

Status

approved