cp's OEIS Frontend

A261781 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.

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