A238858 Triangle T(n,k) read by rows: T(n,k) is the number of length-n ascent sequences with exactly k descents.

1, 1, 0, 2, 0, 0, 4, 1, 0, 0, 8, 7, 0, 0, 0, 16, 33, 4, 0, 0, 0, 32, 131, 53, 1, 0, 0, 0, 64, 473, 429, 48, 0, 0, 0, 0, 128, 1611, 2748, 822, 26, 0, 0, 0, 0, 256, 5281, 15342, 9305, 1048, 8, 0, 0, 0, 0, 512, 16867, 78339, 83590, 21362, 937, 1, 0, 0, 0, 0, 1024, 52905, 376159, 647891, 307660, 35841, 594, 0, 0, 0, 0, 0

Offset: 0

Author

Joerg Arndt and Alois P. Heinz, Mar 06 2014

Keywords

• nonn
• tabl
• look

Comments

Columns k=0-10 give: A011782, A066810(n-1), A241872, A241873, A241874, A241875, A241876, A241877, A241878, A241879, A241880.

The sequence of column k satisfies a linear recurrence with constant coefficients of order k*(k+5)/2 = A055998(k) for k>0.

T(2n,n) gives A241871(n).

Last nonzero elements of rows give A241881(n).

Row sums give A022493.

Examples

			Triangle starts:
00:     1;
01:     1,      0;
02:     2,      0,       0;
03:     4,      1,       0,       0;
04:     8,      7,       0,       0,       0;
05:    16,     33,       4,       0,       0,      0;
06:    32,    131,      53,       1,       0,      0,     0;
07:    64,    473,     429,      48,       0,      0,     0,   0;
08:   128,   1611,    2748,     822,      26,      0,     0,   0, 0;
09:   256,   5281,   15342,    9305,    1048,      8,     0,   0, 0, 0;
10:   512,  16867,   78339,   83590,   21362,    937,     1,   0, 0, 0, 0;
11:  1024,  52905,  376159,  647891,  307660,  35841,   594,   0, 0, 0, 0, 0;
12:  2048, 163835, 1728458, 4537169, 3574869, 834115, 45747, 262, 0, 0, 0, 0, 0;
...
The 53 ascent sequences of length 5 together with their numbers of descents are (dots for zeros):
01:  [ . . . . . ]   0      28:  [ . 1 1 . 1 ]   1
02:  [ . . . . 1 ]   0      29:  [ . 1 1 . 2 ]   1
03:  [ . . . 1 . ]   1      30:  [ . 1 1 1 . ]   1
04:  [ . . . 1 1 ]   0      31:  [ . 1 1 1 1 ]   0
05:  [ . . . 1 2 ]   0      32:  [ . 1 1 1 2 ]   0
06:  [ . . 1 . . ]   1      33:  [ . 1 1 2 . ]   1
07:  [ . . 1 . 1 ]   1      34:  [ . 1 1 2 1 ]   1
08:  [ . . 1 . 2 ]   1      35:  [ . 1 1 2 2 ]   0
09:  [ . . 1 1 . ]   1      36:  [ . 1 1 2 3 ]   0
10:  [ . . 1 1 1 ]   0      37:  [ . 1 2 . . ]   1
11:  [ . . 1 1 2 ]   0      38:  [ . 1 2 . 1 ]   1
12:  [ . . 1 2 . ]   1      39:  [ . 1 2 . 2 ]   1
13:  [ . . 1 2 1 ]   1      40:  [ . 1 2 . 3 ]   1
14:  [ . . 1 2 2 ]   0      41:  [ . 1 2 1 . ]   2
15:  [ . . 1 2 3 ]   0      42:  [ . 1 2 1 1 ]   1
16:  [ . 1 . . . ]   1      43:  [ . 1 2 1 2 ]   1
17:  [ . 1 . . 1 ]   1      44:  [ . 1 2 1 3 ]   1
18:  [ . 1 . . 2 ]   1      45:  [ . 1 2 2 . ]   1
19:  [ . 1 . 1 . ]   2      46:  [ . 1 2 2 1 ]   1
20:  [ . 1 . 1 1 ]   1      47:  [ . 1 2 2 2 ]   0
21:  [ . 1 . 1 2 ]   1      48:  [ . 1 2 2 3 ]   0
22:  [ . 1 . 1 3 ]   1      49:  [ . 1 2 3 . ]   1
23:  [ . 1 . 2 . ]   2      50:  [ . 1 2 3 1 ]   1
24:  [ . 1 . 2 1 ]   2      51:  [ . 1 2 3 2 ]   1
25:  [ . 1 . 2 2 ]   1      52:  [ . 1 2 3 3 ]   0
26:  [ . 1 . 2 3 ]   1      53:  [ . 1 2 3 4 ]   0
27:  [ . 1 1 . . ]   1
There are 16 ascent sequences with no descent, 33 with one, and 4 with 2, giving row 4 [16, 33, 4, 0, 0, 0].
		

Links

• Joerg Arndt and Alois P. Heinz, Rows n = 0..140, flattened

Crossrefs

Cf. A137251 (ascent sequences with k ascents), A242153 (ascent sequences with k flat steps).

Programs

Maple

# b(n, i, t): polynomial in x where the coefficient of x^k is   #
#             the number of postfixes of these sequences of     #
#             length n having k descents such that the prefix   #
#             has rightmost element i and exactly t ascents     #
b:= proc(n, i, t) option remember; `if`(n=0, 1, expand(add(
      `if`(ji, 1, 0)), j=0..t+1)))
    end:
T:= n-> (p-> seq(coeff(p, x, i), i=0..n))(b(n, -1$2)):
seq(T(n), n=0..12);

Mathematica

b[n_, i_, t_] := b[n, i, t] = If[n == 0, 1, Sum[If[ji, 1, 0]], {j, 0, t+1}]]; T[n_] := Function[{p}, Table[Coefficient[p, x, i], {i, 0, n}]][b[n, -1, -1]]; Table[T[n], {n, 0, 12}] // Flatten (* Jean-François Alcover, Jan 06 2015, translated from Maple *)

Sage

# Transcription of the Maple program
R. = QQ[]
@CachedFunction
def b(n,i,t):
    if n==0: return 1
    return sum( ( x if ji) ) for j in range(t+2) )
def T(n): return b(n, -1, -1)
for n in range(0,10): print(T(n).list())