login
The OEIS is supported by the many generous donors to the OEIS Foundation.

 

Logo
Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
A225588 Number of descent sequences of length n. 3
1, 1, 2, 4, 9, 23, 67, 222, 832, 3501, 16412, 85062, 484013, 3004342, 20226212, 146930527, 1146389206, 9566847302, 85073695846, 803417121866, 8032911742979, 84796557160893, 942648626858310, 11009672174119829, 134809696481902160, 1727161011322322267, 23110946295566466698, 322435363123261622935 (list; graph; refs; listen; history; text; internal format)
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
Cf. A225624 (triangle: descent sequences by numbers of descents).
Sequence in context: A124461 A026898 A088930 * A089844 A113997 A125789
KEYWORD
nonn
AUTHOR
Joerg Arndt, May 11 2013
STATUS
approved

Lookup | Welcome | Wiki | Register | Music | Plot 2 | Demos | Index | Browse | More | WebCam
Contribute new seq. or comment | Format | Style Sheet | Transforms | Superseeker | Recents
The OEIS Community | Maintained by The OEIS Foundation Inc.

License Agreements, Terms of Use, Privacy Policy. .

Last modified March 19 01:57 EDT 2024. Contains 370952 sequences. (Running on oeis4.)