OFFSET
0,3
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 example.
Replacing the function desc(.) by a function chg(.) that counts changes in the prefix gives A000522 (arrangements).
Replacing the function desc(.) by a function asc(.) that counts ascents in the prefix gives A022493 (ascent sequences).
Replacing the function desc(.) by a function eq(.) that counts successive equal parts in the prefix gives A000110 (set partitions).
LINKS
Joerg Arndt, Alois P. Heinz and Vaclav Kotesovec, Table of n, a(n) for n = 0..490 (first 200 terms from Joerg Arndt and Alois P. Heinz)
David Callan, On Ascent, Repetition and Descent Sequences, arXiv:1911.02209 [math.CO], 2019.
EXAMPLE
The a(5)=23 descent sequences of length 5 are (dots for zeros)
01: [ . . . . . ]
02: [ . . . . 1 ]
03: [ . . . 1 . ]
04: [ . . . 1 1 ]
05: [ . . 1 . . ]
06: [ . . 1 . 1 ]
07: [ . . 1 . 2 ]
08: [ . . 1 1 . ]
09: [ . . 1 1 1 ]
10: [ . 1 . . . ]
11: [ . 1 . . 1 ]
12: [ . 1 . . 2 ]
13: [ . 1 . 1 . ]
14: [ . 1 . 1 1 ]
15: [ . 1 . 1 2 ]
16: [ . 1 . 2 . ]
17: [ . 1 . 2 1 ]
18: [ . 1 . 2 2 ]
19: [ . 1 1 . . ]
20: [ . 1 1 . 1 ]
21: [ . 1 1 . 2 ]
22: [ . 1 1 1 . ]
23: [ . 1 1 1 1 ]
MAPLE
b:= proc(n, i, t) option remember; `if`(n<1, 1,
add(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); # Alois P. Heinz, May 13 2013
MATHEMATICA
b[n_, i_, t_] := b[n, i, t] = If[n<1, 1, Sum[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, Apr 09 2015, after Alois P. Heinz *)
PROG
(Sage)
# Program adapted from Alois P. Heinz's Maple code in A022493.
# b(n, i, t) gives the number of length-n postfixes of descent sequences
# with a prefix having t descents and last element i.
@CachedFunction
def b(n, i, t):
if n<=1: return 1
return sum( b(n-1, j, t+(j<i)) for j in range(0, t+2) )
def a(n): return b(n, 0, 0)
v225588=[a(n) for n in range(0, 66)]
print(v225588)
CROSSREFS
KEYWORD
nonn
AUTHOR
Joerg Arndt, May 11 2013
STATUS
approved