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,5

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.

Links

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

Example

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 ]

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<i, 1, 0))), j=0..t+1))
    end:
a:= n-> 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 *)

Prog

(Sage)
@CachedFunction
def b(n, i, t):
    if n<1:
        return 1
    return sum(b(n-1, j, t+(j<i)) for j in range(t+2))
def a(n):
    if n<1:
        return 1
    return sum((-1)**(n-k)*binomial(n-1, k-1)*b(k-1, 0, 0) for k in range(n+1))
[a(n) for n in range(33)]
# end of program

Crossrefs

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

Cf. A225588 (all descent sequences).

Sequence in context: A289588 A362638 A344489 * A358075 A071115 A357891

Adjacent sequences: A238422 A238423 A238424 * A238426 A238427 A238428

Keyword

nonn

Author

Joerg Arndt and Alois P. Heinz, Feb 26 2014

Status

approved