|
%I #42 Dec 31 2020 19:41:59
%S 1,0,1,0,2,3,0,4,16,13,0,8,66,132,75,0,16,248,924,1232,541,0,32,892,
%T 5546,13064,13060,4683,0,64,3136,30720,114032,195020,155928,47293,0,
%U 128,10888,162396,893490,2327960,3116220,2075948,545835
%N Number T(n,k) of compositions of n where each part i is marked with a word of length i over a k-ary alphabet whose letters appear in alphabetical order and all k letters occur at least once in the composition; triangle T(n,k), n >= 0, 0 <= k <= n, read by rows.
%C From _Vaclav Kotesovec_, Oct 14 2017: (Start)
%C Conjecture: For k > 0 the recurrence order for column k is equal to k*(k+1)/2.
%C Column k > 0 is asymptotic to c(k) * d(k)^n, where c(k) and d(k) are constants (dependent only on k).
%C k c(k) d(k)
%C 1 A131577(n) ~ 0.50000000000000000000000000 * 2.00000000000000000000000000^n.
%C 2 A293579(n) ~ 0.60355339059327376220042218 * 3.41421356237309504880168872^n.
%C 3 A293580(n) ~ 0.64122035031051210658648604 * 4.84732210186307263951891624^n.
%C 4 A293581(n) ~ 0.66065168848540565019767995 * 6.28521350788324520158143964^n.
%C 5 A293582(n) ~ 0.67250239588725756267924287 * 7.72502395887257562679242875^n.
%C 6 A293583(n) ~ 0.68048292906885160660288253 * 9.16579514882621927923459043^n.
%C 7 A293584(n) ~ 0.68622254929933439577377124 * 10.6071156901906815408327973^n.
%C 8 A293585(n) ~ 0.69054873168854973836384871 * 12.0487797070167958138215794^n.
%C 9 A293586(n) ~ 0.69392626461456654033893782 * 13.4906727630621977261008808^n.
%C 10 A293587(n) ~ 0.69663630864564830007443110 * 14.9327261729129660014886221^n.
%C ---
%C Conjecture: d(k+1) - d(k) tends to 1/log(2).
%C d(2) - d(1) = 1.414213562373095048801688724209698...
%C d(3) - d(2) = 1.433108539489977590717227522340838...
%C d(4) - d(3) = 1.437891406020172562062523400686067...
%C d(5) - d(4) = 1.439810450989330425210989107036901...
%C d(6) - d(5) = 1.440771189953643652442161677346934...
%C d(7) - d(6) = 1.441320541364462261598206961226199...
%C d(8) - d(7) = 1.441664016826114272988782079622148...
%C d(9) - d(8) = 1.441893056045401912279301345910755...
%C d(10)- d(9) = 1.442053409850768275387741352145193...
%C 1 / log(2) = 1.442695040888963407359924681001892...
%C (End)
%H Alois P. Heinz, <a href="/A261781/b261781.txt">Rows n = 0..140, flattened</a>
%H E. Munarini, M. Poneti, S. Rimaldi, <a href="https://cs.uwaterloo.ca/journals/JIS/VOL12/Rinaldi/rinaldi.html">Matrix compositions</a>, JIS 12 (2009) 09.4.8, Table 2.
%F T(n,k) = Sum_{i=0..k} (-1)^i * C(k,i) * A261780(n,k-i).
%e A(3,2) = 16: 3aab, 3abb, 2aa1b, 2ab1a, 2ab1b, 2bb1a, 1a2ab, 1a2bb, 1b2aa, 1b2ab, 1a1a1b, 1a1b1a, 1a1b1b, 1b1a1a, 1b1a1b, 1b1b1a.
%e Triangle T(n,k) begins:
%e 1;
%e 0, 1;
%e 0, 2, 3;
%e 0, 4, 16, 13;
%e 0, 8, 66, 132, 75;
%e 0, 16, 248, 924, 1232, 541;
%e 0, 32, 892, 5546, 13064, 13060, 4683;
%e 0, 64, 3136, 30720, 114032, 195020, 155928, 47293;
%e ...
%p A:= proc(n, k) option remember; `if`(n=0, 1,
%p add(A(n-j, k)*binomial(j+k-1, k-1), j=1..n))
%p end:
%p T:= (n, k)-> add(A(n, k-i)*(-1)^i*binomial(k, i), i=0..k):
%p seq(seq(T(n, k), k=0..n), n=0..10);
%t A[n_, k_] := A[n, k] = If[n==0, 1,
%t Sum[A[n-j, k]*Binomial[j+k-1, k-1], {j, 1, n}]];
%t T[n_, k_] := Sum[A[n, k-i]*(-1)^i*Binomial[k, i], {i, 0, k}];
%t Table[T[n, k], {n, 0, 10}, {k, 0, n}] // Flatten (* _Jean-François Alcover_, Feb 08 2017, translated from Maple *)
%Y Columns k=0..10 give A000007, A131577, A293579, A293580, A293581, A293582, A293583, A293584, A293585, A293586, A293587.
%Y Row sums give A120733.
%Y Main diagonal gives A000670.
%Y T(2n,n) gives A261784.
%Y T(n+1,n)/2 gives A083385.
%Y Cf. A261719 (same for partitions), A261780.
%K nonn,tabl
%O 0,5
%A _Alois P. Heinz_, Aug 31 2015
|
