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
KEYWORD
nonn
AUTHOR
Joerg Arndt and Alois P. Heinz, Feb 26 2014
STATUS
approved