A238425 Number of descent sequences of length n without two consecutive identical elements (descent sequences without flat steps).

1, 1, 1, 1, 2, 4, 11, 34, 124, 512, 2380, 12294, 69972, 435399, 2942672, 21478882, 168473955, 1413823577, 12644505883, 120097766639, 1207617481139, 12818915877849, 143278176040760, 1682262113899134, 20704109403389717, 266568690074855277, 3583926627760681407

Offset: 0

Author

Joerg Arndt and Alois P. Heinz, Feb 26 2014

Keywords

• nonn

Comments

A descent sequence is a sequence [d(1), d(2), ..., d(n)] where d(1)=0, d(k)>=0, and d(k) <= 1 + desc([d(1), d(2), ..., d(k-1)]) where desc(.) gives the number of descents of its argument, see A225588.

Examples

			The a(6) = 11 such descent sequences are (dots denote zeros):
01:  [ . 1 . 1 . 1 ]
02:  [ . 1 . 1 . 2 ]
03:  [ . 1 . 1 . 3 ]
04:  [ . 1 . 1 2 . ]
05:  [ . 1 . 1 2 1 ]
06:  [ . 1 . 2 . 1 ]
07:  [ . 1 . 2 . 2 ]
08:  [ . 1 . 2 . 3 ]
09:  [ . 1 . 2 1 . ]
10:  [ . 1 . 2 1 2 ]
11:  [ . 1 . 2 1 3 ]
		

Links

• Joerg Arndt and Alois P. Heinz, Table of n, a(n) for n = 0..200

Crossrefs

Cf. A138265 (ascent sequence without two consecutive identical elements).

Cf. A225588 (all descent sequences).

Programs

Maple

# b(n, i, t): number of length-n postfixes of these sequences with a
#             valid prefix having t descents and rightmost element i.
b:= proc(n, i, t) option remember; `if`(n<1, 1,
      add(`if`(j=i, 0, b(n-1, j, t+`if`(j b(n-1, 0, 0):
seq(a(n), n=0..30);

Mathematica

b[n_, i_, t_] := b[n, i, t] = If[n < 1, 1, Sum[If[j == i, 0, b[n - 1, j, t + If[j < i, 1, 0]]], {j, 0, t + 1}]];
a[n_] := b[n - 1, 0, 0];
Table[a[n], {n, 0, 30}] (* Jean-François Alcover, Mar 07 2022, after Alois P. Heinz *)

Sage

@CachedFunction
def b(n, i, t):
    if n<1:
        return 1
    return sum(b(n-1, j, t+(j