|
%I #32 Mar 24 2017 00:47:55
%S 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,
%T 405,271,22,0,0,0,9,210,1155,1631,483,13,0,0,0,10,330,2871,7359,5126,
%U 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
%N 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.
%C 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.
%C Row sums are A225588 (number of descent sequences).
%C 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.
%H Joerg Arndt and Alois P. Heinz, <a href="/A225624/b225624.txt">Rows n = 1..100, flattened</a> (Rows n = 1..18 from Joerg Arndt)
%e Triangle begins:
%e 01: 1,
%e 02: 2, 0,
%e 03: 3, 1, 0,
%e 04: 4, 5, 0, 0,
%e 05: 5, 15, 3, 0, 0,
%e 06: 6, 35, 25, 1, 0, 0,
%e 07: 7, 70, 117, 28, 0, 0, 0,
%e 08: 8, 126, 405, 271, 22, 0, 0, 0,
%e 09: 9, 210, 1155, 1631, 483, 13, 0, 0, 0,
%e 10: 10, 330, 2871, 7359, 5126, 711, 5, 0, 0, 0,
%e 11: 11, 495, 6435, 27223, 36526, 13482, 889, 1, 0, 0, 0,
%e 12: 12, 715, 13299, 86919, 199924, 151276, 30906, 962, 0, 0, 0, 0,
%e 13: 13, 1001, 25740, 247508, 903511, 1216203, 546001, 63462, 903, 0, 0, 0, 0,
%e ...
%e The number of descents for the A225588(5)=23 descent sequences of length 5 are (dots for zeros):
%e .#: descent seq. no. of descents
%e 01: [ . . . . . ] 0
%e 02: [ . . . . 1 ] 0
%e 03: [ . . . 1 . ] 1
%e 04: [ . . . 1 1 ] 0
%e 05: [ . . 1 . . ] 1
%e 06: [ . . 1 . 1 ] 1
%e 07: [ . . 1 . 2 ] 1
%e 08: [ . . 1 1 . ] 1
%e 09: [ . . 1 1 1 ] 0
%e 10: [ . 1 . . . ] 1
%e 11: [ . 1 . . 1 ] 1
%e 12: [ . 1 . . 2 ] 1
%e 13: [ . 1 . 1 . ] 2
%e 14: [ . 1 . 1 1 ] 1
%e 15: [ . 1 . 1 2 ] 1
%e 16: [ . 1 . 2 . ] 2
%e 17: [ . 1 . 2 1 ] 2
%e 18: [ . 1 . 2 2 ] 1
%e 19: [ . 1 1 . . ] 1
%e 20: [ . 1 1 . 1 ] 1
%e 21: [ . 1 1 . 2 ] 1
%e 22: [ . 1 1 1 . ] 1
%e 23: [ . 1 1 1 1 ] 0
%e 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].
%p b:= proc(n, i, t) option remember; local j; if n<1 then [0$t, 1]
%p else []; for j from 0 to t+1 do zip((x, y)->x+y, %,
%p b(n-1, j, t+`if`(j<i, 1, 0)), 0) od; % fi
%p end:
%p T:= proc(n) local l; l:= b(n-1, 0, 0): l[], 0$(n-nops(l)) end:
%p seq(T(n), n=1..13); # _Alois P. Heinz_, May 18 2013
%t 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_ *)
%o (Sage) # After Alois P. Heinz.
%o @CachedFunction
%o def b(n, i, t, N):
%o B = [0 for x in range(N)]
%o if n < 1: B[t] = 1; return B
%o for j in (0..t+1):
%o B = map(operator.add, B, b(n-1, j, t+int(j<i), N))
%o return B
%o def T(n): return b(n-1, 0, 0, n)
%o for n in (1..9): T(n) # _Peter Luschny_, May 20 2013; updated May 21 2013
%K nonn,tabl
%O 1,2
%A _Joerg Arndt_, May 11 2013
|
