A128805 Number of valley-avoiding compositions with positive parts.

1, 1, 2, 4, 8, 15, 28, 52, 96, 177, 326, 600, 1104, 2032, 3740, 6884, 12672, 23327, 42942, 79052, 145528, 267905, 493192, 907928, 1671424, 3076959, 5664436, 10427772, 19196688, 35339553, 65057260, 119765152, 220477952, 405882064, 747196026, 1375527404

Offset

0,3

Links

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

S. Heubach and T. Mansour, Enumeration of 3-letter patterns in combinations, arXiv:math/0603285 [math.CO], 2006.

Milan Janjic, Enumerative Formulas for Some Functions on Finite Sets

Formula

The Heubach/Mansour paper has a complicated g.f.

Maple

b:= proc(n, t, l) option remember; `if`(n=0, 1, add(
      b(n-j, is(j<l), j), j=1..min(n, `if`(t, l, n))))
    end:
a:= n-> b(n, false, 0):
seq(a(n), n=0..40);  # Alois P. Heinz, Oct 24 2017

Mathematica

b[n_, t_, l_] := b[n, t, l] = If[n == 0, 1, Sum[b[n - j, j < l, j], {j, 1, Min[n, If[t, l, n]]}]];
a[n_] := b[n, False, 0];
Table[a[n], {n, 0, 40}] (* Jean-François Alcover, Nov 11 2017, after Alois P. Heinz *)
nmax = 50; CoefficientList[Series[1/(1 - Sum[x^((k + 1)^2)/Product[(1 - x^j), {j, 1, 2*k + 1}], {k, 0, Sqrt[nmax]}]/(1 + Sum[x^(k*(k + 2))/Product[(1 - x^j), {j, 1, 2*k}], {k, 1, Sqrt[nmax]}])), {x, 0, nmax}], x] (* Vaclav Kotesovec, Apr 18 2020 *)

Crossrefs

Cf. A128768.

Sequence in context: A320452 A073769 A008937 * A141018 A049864 A239554

Adjacent sequences: A128802 A128803 A128804 * A128806 A128807 A128808

Keyword

nonn

Author

Ralf Stephan, May 08 2007

Extensions

More terms from Vladeta Jovovic, Oct 04 2007

Status

approved