|
%I #50 Mar 07 2020 05:41:32
%S 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,
%T 429,48,0,0,0,0,128,1611,2748,822,26,0,0,0,0,256,5281,15342,9305,1048,
%U 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
%N Triangle T(n,k) read by rows: T(n,k) is the number of length-n ascent sequences with exactly k descents.
%C Columns k=0-10 give: A011782, A066810(n-1), A241872, A241873, A241874, A241875, A241876, A241877, A241878, A241879, A241880.
%C The sequence of column k satisfies a linear recurrence with constant coefficients of order k*(k+5)/2 = A055998(k) for k>0.
%C T(2n,n) gives A241871(n).
%C Last nonzero elements of rows give A241881(n).
%C Row sums give A022493.
%H Joerg Arndt and Alois P. Heinz, <a href="/A238858/b238858.txt">Rows n = 0..140, flattened</a>
%e Triangle starts:
%e 00: 1;
%e 01: 1, 0;
%e 02: 2, 0, 0;
%e 03: 4, 1, 0, 0;
%e 04: 8, 7, 0, 0, 0;
%e 05: 16, 33, 4, 0, 0, 0;
%e 06: 32, 131, 53, 1, 0, 0, 0;
%e 07: 64, 473, 429, 48, 0, 0, 0, 0;
%e 08: 128, 1611, 2748, 822, 26, 0, 0, 0, 0;
%e 09: 256, 5281, 15342, 9305, 1048, 8, 0, 0, 0, 0;
%e 10: 512, 16867, 78339, 83590, 21362, 937, 1, 0, 0, 0, 0;
%e 11: 1024, 52905, 376159, 647891, 307660, 35841, 594, 0, 0, 0, 0, 0;
%e 12: 2048, 163835, 1728458, 4537169, 3574869, 834115, 45747, 262, 0, 0, 0, 0, 0;
%e ...
%e The 53 ascent sequences of length 5 together with their numbers of descents are (dots for zeros):
%e 01: [ . . . . . ] 0 28: [ . 1 1 . 1 ] 1
%e 02: [ . . . . 1 ] 0 29: [ . 1 1 . 2 ] 1
%e 03: [ . . . 1 . ] 1 30: [ . 1 1 1 . ] 1
%e 04: [ . . . 1 1 ] 0 31: [ . 1 1 1 1 ] 0
%e 05: [ . . . 1 2 ] 0 32: [ . 1 1 1 2 ] 0
%e 06: [ . . 1 . . ] 1 33: [ . 1 1 2 . ] 1
%e 07: [ . . 1 . 1 ] 1 34: [ . 1 1 2 1 ] 1
%e 08: [ . . 1 . 2 ] 1 35: [ . 1 1 2 2 ] 0
%e 09: [ . . 1 1 . ] 1 36: [ . 1 1 2 3 ] 0
%e 10: [ . . 1 1 1 ] 0 37: [ . 1 2 . . ] 1
%e 11: [ . . 1 1 2 ] 0 38: [ . 1 2 . 1 ] 1
%e 12: [ . . 1 2 . ] 1 39: [ . 1 2 . 2 ] 1
%e 13: [ . . 1 2 1 ] 1 40: [ . 1 2 . 3 ] 1
%e 14: [ . . 1 2 2 ] 0 41: [ . 1 2 1 . ] 2
%e 15: [ . . 1 2 3 ] 0 42: [ . 1 2 1 1 ] 1
%e 16: [ . 1 . . . ] 1 43: [ . 1 2 1 2 ] 1
%e 17: [ . 1 . . 1 ] 1 44: [ . 1 2 1 3 ] 1
%e 18: [ . 1 . . 2 ] 1 45: [ . 1 2 2 . ] 1
%e 19: [ . 1 . 1 . ] 2 46: [ . 1 2 2 1 ] 1
%e 20: [ . 1 . 1 1 ] 1 47: [ . 1 2 2 2 ] 0
%e 21: [ . 1 . 1 2 ] 1 48: [ . 1 2 2 3 ] 0
%e 22: [ . 1 . 1 3 ] 1 49: [ . 1 2 3 . ] 1
%e 23: [ . 1 . 2 . ] 2 50: [ . 1 2 3 1 ] 1
%e 24: [ . 1 . 2 1 ] 2 51: [ . 1 2 3 2 ] 1
%e 25: [ . 1 . 2 2 ] 1 52: [ . 1 2 3 3 ] 0
%e 26: [ . 1 . 2 3 ] 1 53: [ . 1 2 3 4 ] 0
%e 27: [ . 1 1 . . ] 1
%e There are 16 ascent sequences with no descent, 33 with one, and 4 with 2, giving row 4 [16, 33, 4, 0, 0, 0].
%p # b(n, i, t): polynomial in x where the coefficient of x^k is #
%p # the number of postfixes of these sequences of #
%p # length n having k descents such that the prefix #
%p # has rightmost element i and exactly t ascents #
%p b:= proc(n, i, t) option remember; `if`(n=0, 1, expand(add(
%p `if`(j<i, x, 1) *b(n-1, j, t+`if`(j>i, 1, 0)), j=0..t+1)))
%p end:
%p T:= n-> (p-> seq(coeff(p, x, i), i=0..n))(b(n, -1$2)):
%p seq(T(n), n=0..12);
%t 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 *)
%o (Sage) # Transcription of the Maple program
%o R.<x> = QQ[]
%o @CachedFunction
%o def b(n,i,t):
%o if n==0: return 1
%o return sum( ( x if j<i else 1 ) * b(n-1, j, t+(j>i) ) for j in range(t+2) )
%o def T(n): return b(n, -1, -1)
%o for n in range(0,10): print(T(n).list())
%Y Cf. A137251 (ascent sequences with k ascents), A242153 (ascent sequences with k flat steps).
%K nonn,tabl,look
%O 0,4
%A _Joerg Arndt_ and _Alois P. Heinz_, Mar 06 2014
|
