A225588 Number of descent sequences of length n.

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

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

Adjacent sequences: A225585 A225586 A225587 * A225589 A225590 A225591

Keyword

nonn

Author

Joerg Arndt, May 11 2013

Status

approved