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,2

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.

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.

Links

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

Example

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].

Maple

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`(j<i, 1, 0)), 0) od; % fi
    end:
T:= proc(n) local l; l:= b(n-1, 0, 0): l[], 0$(n-nops(l)) end:
seq(T(n), n=1..13);  # Alois P. Heinz, May 18 2013

Mathematica

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[j<i, 1, 0]]}]]; pc]]; T[n_] := Module[{l}, l = b[n-1, 0, 0]; Join[l, Array[0&, n-Length[l]]]]; Table[T[n], {n, 1, 12}] // Flatten (* Jean-François Alcover, Feb 27 2014, after Alois P. Heinz *)

Prog

(Sage)  # 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(j<i), N))
    return B
def T(n): return b(n-1, 0, 0, n)
for n in (1..9): T(n)  #  Peter Luschny, May 20 2013; updated May 21 2013

Crossrefs

Sequence in context: A284871 A202064 A144955 * A168020 A321878 A225084

Adjacent sequences: A225621 A225622 A225623 * A225625 A225626 A225627

Keyword

nonn,tabl

Author

Joerg Arndt, May 11 2013

Status

approved