A225588 -id:A225588 - cp's OEIS frontend

A225624 Triangle read by rows: T(n,k) is the number of descent sequences of length n with exactly k-1 descents, n>=1, 1<=k<=n.

1, 2, 0, 3, 1, 0, 4, 5, 0, 0, 5, 15, 3, 0, 0, 6, 35, 25, 1, 0, 0, 7, 70, 117, 28, 0, 0, 0, 8, 126, 405, 271, 22, 0, 0, 0, 9, 210, 1155, 1631, 483, 13, 0, 0, 0, 10, 330, 2871, 7359, 5126, 711, 5, 0, 0, 0, 11, 495, 6435, 27223, 36526, 13482, 889, 1, 0, 0, 0, 12, 715, 13299, 86919, 199924, 151276, 30906, 962, 0, 0, 0, 0

Offset: 1

Joerg Arndt, May 11 2013

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.
Row sums are A225588 (number of descent sequences).
First column is C(n,1)=n, second column is C(n+1,4) = A000332(n+1), third column appears to be A095664(n-5) for n>=5.

			Triangle begins:
01:  1,
02:  2, 0,
03:  3, 1, 0,
04:  4, 5, 0, 0,
05:  5, 15, 3, 0, 0,
06:  6, 35, 25, 1, 0, 0,
07:  7, 70, 117, 28, 0, 0, 0,
08:  8, 126, 405, 271, 22, 0, 0, 0,
09:  9, 210, 1155, 1631, 483, 13, 0, 0, 0,
10:  10, 330, 2871, 7359, 5126, 711, 5, 0, 0, 0,
11:  11, 495, 6435, 27223, 36526, 13482, 889, 1, 0, 0, 0,
12:  12, 715, 13299, 86919, 199924, 151276, 30906, 962, 0, 0, 0, 0,
13:  13, 1001, 25740, 247508, 903511, 1216203, 546001, 63462, 903, 0, 0, 0, 0,
...
The number of descents for the A225588(5)=23 descent sequences of length 5 are (dots for zeros):
.#:  descent seq.   no. of descents
01:  [ . . . . . ]    0
02:  [ . . . . 1 ]    0
03:  [ . . . 1 . ]    1
04:  [ . . . 1 1 ]    0
05:  [ . . 1 . . ]    1
06:  [ . . 1 . 1 ]    1
07:  [ . . 1 . 2 ]    1
08:  [ . . 1 1 . ]    1
09:  [ . . 1 1 1 ]    0
10:  [ . 1 . . . ]    1
11:  [ . 1 . . 1 ]    1
12:  [ . 1 . . 2 ]    1
13:  [ . 1 . 1 . ]    2
14:  [ . 1 . 1 1 ]    1
15:  [ . 1 . 1 2 ]    1
16:  [ . 1 . 2 . ]    2
17:  [ . 1 . 2 1 ]    2
18:  [ . 1 . 2 2 ]    1
19:  [ . 1 1 . . ]    1
20:  [ . 1 1 . 1 ]    1
21:  [ . 1 1 . 2 ]    1
22:  [ . 1 1 1 . ]    1
23:  [ . 1 1 1 1 ]    0
There are 5 sequences with 0 descents, 15 with 1 descents, 3 with 2 descents, and 0 for 3 or 5 descents. Therefore row 5 is [5, 15, 3, 0, 0].

Joerg Arndt and Alois P. Heinz, Rows n = 1..100, flattened (Rows n = 1..18 from Joerg Arndt)

b:= proc(n, i, t) option remember; local j; if n<1 then [0$t, 1]
      else []; for j from 0 to t+1 do zip((x, y)->x+y, %,
      b(n-1, j, t+`if`(jAlois P. Heinz, May 18 2013

b[n_, i_, t_] :=  b[n, i, t] =  Module[{j, pc}, If[n<1, Append[Array[0 &, t], 1], pc = {}; For[j = 0, j <= t+1, j++, pc = Plus @@ PadRight[ {pc, b[n-1, j, t+If[jJean-François Alcover, Feb 27 2014, after Alois P. Heinz *)

# After Alois P. Heinz.
@CachedFunction
def b(n, i, t, N):
    B = [0 for x in range(N)]
    if n < 1: B[t] = 1; return B
    for j in (0..t+1):
        B = map(operator.add, B, b(n-1, j, t+int(jPeter Luschny, May 20 2013; updated May 21 2013

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

Original entry on oeis.org

1, 1, 1, 1, 2, 4, 11, 34, 124, 512, 2380, 12294, 69972, 435399, 2942672, 21478882, 168473955, 1413823577, 12644505883, 120097766639, 1207617481139, 12818915877849, 143278176040760, 1682262113899134, 20704109403389717, 266568690074855277, 3583926627760681407

Offset: 0

Joerg Arndt and Alois P. Heinz, Feb 26 2014

nonn

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.

			The a(6) = 11 such descent sequences are (dots denote zeros):
01:  [ . 1 . 1 . 1 ]
02:  [ . 1 . 1 . 2 ]
03:  [ . 1 . 1 . 3 ]
04:  [ . 1 . 1 2 . ]
05:  [ . 1 . 1 2 1 ]
06:  [ . 1 . 2 . 1 ]
07:  [ . 1 . 2 . 2 ]
08:  [ . 1 . 2 . 3 ]
09:  [ . 1 . 2 1 . ]
10:  [ . 1 . 2 1 2 ]
11:  [ . 1 . 2 1 3 ]

Joerg Arndt and Alois P. Heinz, Table of n, a(n) for n = 0..200

Cf. A138265 (ascent sequence without two consecutive identical elements).

Cf. A225588 (all descent sequences).

# b(n, i, t): number of length-n postfixes of these sequences with a
#             valid prefix having t descents and rightmost element i.
b:= proc(n, i, t) option remember; `if`(n<1, 1,
      add(`if`(j=i, 0, b(n-1, j, t+`if`(j b(n-1, 0, 0):
seq(a(n), n=0..30);

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}]];
a[n_] := b[n - 1, 0, 0];
Table[a[n], {n, 0, 30}] (* Jean-François Alcover, Mar 07 2022, after Alois P. Heinz *)

@CachedFunction
def b(n, i, t):
    if n<1:
        return 1
    return sum(b(n-1, j, t+(j

cp's OEIS Frontend

A225624 Triangle read by rows: T(n,k) is the number of descent sequences of length n with exactly k-1 descents, n>=1, 1<=k<=n.

Views

Author

Keywords

Comments

Examples

Links

Programs

Maple

Mathematica

Sage