cp's OEIS Frontend

A225588 Number of descent sequences of length n.

%I A225588 #50 Nov 13 2024 13:16:25
%S A225588 1,1,2,4,9,23,67,222,832,3501,16412,85062,484013,3004342,20226212,
%T A225588 146930527,1146389206,9566847302,85073695846,803417121866,
%U A225588 8032911742979,84796557160893,942648626858310,11009672174119829,134809696481902160,1727161011322322267,23110946295566466698,322435363123261622935
%N A225588 Number of descent sequences of length n.
%C A225588 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.
%C A225588 Replacing the function desc(.) by a function chg(.) that counts changes in the prefix gives A000522 (arrangements).
%C A225588 Replacing the function desc(.) by a function asc(.) that counts ascents in the prefix gives A022493 (ascent sequences).
%C A225588 Replacing the function desc(.) by a function eq(.) that counts successive equal parts in the prefix gives A000110 (set partitions).
%H A225588 Joerg Arndt, Alois P. Heinz and Vaclav Kotesovec, <a href="/A225588/b225588.txt">Table of n, a(n) for n = 0..490</a> (first 200 terms from Joerg Arndt and Alois P. Heinz)
%H A225588 David Callan, <a href="https://arxiv.org/abs/1911.02209">On Ascent, Repetition and Descent Sequences</a>, arXiv:1911.02209 [math.CO], 2019.
%e A225588 The a(5)=23 descent sequences of length 5 are (dots for zeros)
%e A225588 01:  [ . . . . . ]
%e A225588 02:  [ . . . . 1 ]
%e A225588 03:  [ . . . 1 . ]
%e A225588 04:  [ . . . 1 1 ]
%e A225588 05:  [ . . 1 . . ]
%e A225588 06:  [ . . 1 . 1 ]
%e A225588 07:  [ . . 1 . 2 ]
%e A225588 08:  [ . . 1 1 . ]
%e A225588 09:  [ . . 1 1 1 ]
%e A225588 10:  [ . 1 . . . ]
%e A225588 11:  [ . 1 . . 1 ]
%e A225588 12:  [ . 1 . . 2 ]
%e A225588 13:  [ . 1 . 1 . ]
%e A225588 14:  [ . 1 . 1 1 ]
%e A225588 15:  [ . 1 . 1 2 ]
%e A225588 16:  [ . 1 . 2 . ]
%e A225588 17:  [ . 1 . 2 1 ]
%e A225588 18:  [ . 1 . 2 2 ]
%e A225588 19:  [ . 1 1 . . ]
%e A225588 20:  [ . 1 1 . 1 ]
%e A225588 21:  [ . 1 1 . 2 ]
%e A225588 22:  [ . 1 1 1 . ]
%e A225588 23:  [ . 1 1 1 1 ]
%p A225588 b:= proc(n, i, t) option remember; `if`(n<1, 1,
%p A225588       add(b(n-1, j, t+`if`(j<i, 1, 0)), j=0..t+1))
%p A225588     end:
%p A225588 a:= n-> b(n-1, 0, 0):
%p A225588 seq(a(n), n=0..30);  # _Alois P. Heinz_, May 13 2013
%t A225588 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_ *)
%o A225588 (Sage)
%o A225588 # Program adapted from _Alois P. Heinz_'s Maple code in A022493.
%o A225588 # b(n,i,t) gives the number of length-n postfixes of descent sequences
%o A225588 # with a prefix having t descents and last element i.
%o A225588 @CachedFunction
%o A225588 def b(n,i,t):
%o A225588     if n<=1: return 1
%o A225588     return sum( b(n-1, j, t+(j<i)) for j in range(0,t+2) )
%o A225588 def a(n):  return b(n, 0, 0)
%o A225588 v225588=[a(n) for n in range(0,66)]
%o A225588 print(v225588)
%Y A225588 Cf. A225624 (triangle: descent sequences by numbers of descents).
%K A225588 nonn
%O A225588 0,3
%A A225588 _Joerg Arndt_, May 11 2013