login
This site is supported by donations 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)

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 xrange(0, t+2) )

def a(n):  return b(n, 0, 0)

v225588=[a(n) for n in xrange(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

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

License Agreements, Terms of Use, Privacy Policy .

Last modified June 23 02:54 EDT 2017. Contains 288633 sequences.