login
A238858
Triangle T(n,k) read by rows: T(n,k) is the number of length-n ascent sequences with exactly k descents.
16
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,4
COMMENTS
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.
LINKS
Joerg Arndt and Alois P. Heinz, Rows n = 0..140, flattened
EXAMPLE
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].
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`(j<i, x, 1) *b(n-1, j, t+`if`(j>i, 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[j<i, x, 1]*b[n-1, j, t+If[j>i, 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 *)
PROG
(Sage) # Transcription of the Maple program
R.<x> = QQ[]
@CachedFunction
def b(n, i, t):
if n==0: return 1
return sum( ( x if j<i else 1 ) * b(n-1, j, t+(j>i) ) for j in range(t+2) )
def T(n): return b(n, -1, -1)
for n in range(0, 10): print(T(n).list())
CROSSREFS
Cf. A137251 (ascent sequences with k ascents), A242153 (ascent sequences with k flat steps).
Sequence in context: A369731 A136334 A155039 * A106235 A288098 A118965
KEYWORD
nonn,tabl,look
AUTHOR
Joerg Arndt and Alois P. Heinz, Mar 06 2014
STATUS
approved