login
A238425
Number of descent sequences of length n without two consecutive identical elements (descent sequences without flat steps).
1
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
KEYWORD
nonn
AUTHOR
Joerg Arndt and Alois P. Heinz, Feb 26 2014
STATUS
approved