cp's OEIS Frontend

A238425 Number of descent sequences of length n without two consecutive identical elements (descent sequences without flat steps).

%I A238425 #22 Mar 07 2022 09:03:08
%S A238425 1,1,1,1,2,4,11,34,124,512,2380,12294,69972,435399,2942672,21478882,
%T A238425 168473955,1413823577,12644505883,120097766639,1207617481139,
%U A238425 12818915877849,143278176040760,1682262113899134,20704109403389717,266568690074855277,3583926627760681407
%N A238425 Number of descent sequences of length n without two consecutive identical elements (descent sequences without flat steps).
%C A238425 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.
%H A238425 Joerg Arndt and Alois P. Heinz, <a href="/A238425/b238425.txt">Table of n, a(n) for n = 0..200</a>
%e A238425 The a(6) = 11 such descent sequences are (dots denote zeros):
%e A238425 01:  [ . 1 . 1 . 1 ]
%e A238425 02:  [ . 1 . 1 . 2 ]
%e A238425 03:  [ . 1 . 1 . 3 ]
%e A238425 04:  [ . 1 . 1 2 . ]
%e A238425 05:  [ . 1 . 1 2 1 ]
%e A238425 06:  [ . 1 . 2 . 1 ]
%e A238425 07:  [ . 1 . 2 . 2 ]
%e A238425 08:  [ . 1 . 2 . 3 ]
%e A238425 09:  [ . 1 . 2 1 . ]
%e A238425 10:  [ . 1 . 2 1 2 ]
%e A238425 11:  [ . 1 . 2 1 3 ]
%p A238425 # b(n, i, t): number of length-n postfixes of these sequences with a
%p A238425 #             valid prefix having t descents and rightmost element i.
%p A238425 b:= proc(n, i, t) option remember; `if`(n<1, 1,
%p A238425       add(`if`(j=i, 0, b(n-1, j, t+`if`(j<i, 1, 0))), j=0..t+1))
%p A238425     end:
%p A238425 a:= n-> b(n-1, 0, 0):
%p A238425 seq(a(n), n=0..30);
%t A238425 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}]];
%t A238425 a[n_] := b[n - 1, 0, 0];
%t A238425 Table[a[n], {n, 0, 30}] (* _Jean-François Alcover_, Mar 07 2022, after _Alois P. Heinz_ *)
%o A238425 (Sage)
%o A238425 @CachedFunction
%o A238425 def b(n, i, t):
%o A238425     if n<1:
%o A238425         return 1
%o A238425     return sum(b(n-1, j, t+(j<i)) for j in range(t+2))
%o A238425 def a(n):
%o A238425     if n<1:
%o A238425         return 1
%o A238425     return sum((-1)**(n-k)*binomial(n-1, k-1)*b(k-1, 0, 0) for k in range(n+1))
%o A238425 [a(n) for n in range(33)]
%o A238425 # end of program
%Y A238425 Cf. A138265 (ascent sequence without two consecutive identical elements).
%Y A238425 Cf. A225588 (all descent sequences).
%K A238425 nonn
%O A238425 0,5
%A A238425 _Joerg Arndt_ and _Alois P. Heinz_, Feb 26 2014