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.

1, 0, 1, 0, 2, 3, 0, 4, 16, 13, 0, 8, 66, 132, 75, 0, 16, 248, 924, 1232, 541, 0, 32, 892, 5546, 13064, 13060, 4683, 0, 64, 3136, 30720, 114032, 195020, 155928, 47293, 0, 128, 10888, 162396, 893490, 2327960, 3116220, 2075948, 545835

Offset: 0

Author

Alois P. Heinz, Aug 31 2015

Keywords

• nonn
• tabl

Comments

From Vaclav Kotesovec, Oct 14 2017: (Start)

Conjecture: For k > 0 the recurrence order for column k is equal to k*(k+1)/2.

Column k > 0 is asymptotic to c(k) * d(k)^n, where c(k) and d(k) are constants (dependent only on k).

k c(k) d(k)

1 A131577(n) ~ 0.50000000000000000000000000 * 2.00000000000000000000000000^n.

2 A293579(n) ~ 0.60355339059327376220042218 * 3.41421356237309504880168872^n.

3 A293580(n) ~ 0.64122035031051210658648604 * 4.84732210186307263951891624^n.

4 A293581(n) ~ 0.66065168848540565019767995 * 6.28521350788324520158143964^n.

5 A293582(n) ~ 0.67250239588725756267924287 * 7.72502395887257562679242875^n.

6 A293583(n) ~ 0.68048292906885160660288253 * 9.16579514882621927923459043^n.

7 A293584(n) ~ 0.68622254929933439577377124 * 10.6071156901906815408327973^n.

8 A293585(n) ~ 0.69054873168854973836384871 * 12.0487797070167958138215794^n.

9 A293586(n) ~ 0.69392626461456654033893782 * 13.4906727630621977261008808^n.

10 A293587(n) ~ 0.69663630864564830007443110 * 14.9327261729129660014886221^n.

---

Conjecture: d(k+1) - d(k) tends to 1/log(2).

d(2) - d(1) = 1.414213562373095048801688724209698...

d(3) - d(2) = 1.433108539489977590717227522340838...

d(4) - d(3) = 1.437891406020172562062523400686067...

d(5) - d(4) = 1.439810450989330425210989107036901...

d(6) - d(5) = 1.440771189953643652442161677346934...

d(7) - d(6) = 1.441320541364462261598206961226199...

d(8) - d(7) = 1.441664016826114272988782079622148...

d(9) - d(8) = 1.441893056045401912279301345910755...

d(10)- d(9) = 1.442053409850768275387741352145193...

1 / log(2) = 1.442695040888963407359924681001892...

(End)

Examples

			A(3,2) = 16: 3aab, 3abb, 2aa1b, 2ab1a, 2ab1b, 2bb1a, 1a2ab, 1a2bb, 1b2aa, 1b2ab, 1a1a1b, 1a1b1a, 1a1b1b, 1b1a1a, 1b1a1b, 1b1b1a.
Triangle T(n,k) begins:
  1;
  0,  1;
  0,  2,    3;
  0,  4,   16,    13;
  0,  8,   66,   132,     75;
  0, 16,  248,   924,   1232,    541;
  0, 32,  892,  5546,  13064,  13060,   4683;
  0, 64, 3136, 30720, 114032, 195020, 155928, 47293;
  ...
		

Links

• Alois P. Heinz, Rows n = 0..140, flattened
• E. Munarini, M. Poneti, and S. Rinaldi, Matrix compositions, JIS 12 (2009) 09.4.8, Table 2.

Crossrefs

Columns k=0..10 give A000007, A131577, A293579, A293580, A293581, A293582, A293583, A293584, A293585, A293586, A293587.

Row sums give A120733.

Main diagonal gives A000670.

T(2n,n) gives A261784.

T(n+1,n)/2 gives A083385.

Cf. A261719 (same for partitions), A261780.

Programs

Maple

A:= proc(n, k) option remember; `if`(n=0, 1,
      add(A(n-j, k)*binomial(j+k-1, k-1), j=1..n))
    end:
T:= (n, k)-> add(A(n, k-i)*(-1)^i*binomial(k, i), i=0..k):
seq(seq(T(n, k), k=0..n), n=0..10);

Mathematica

A[n_, k_] := A[n, k] = If[n==0, 1,
    Sum[A[n-j, k]*Binomial[j+k-1, k-1], {j, 1, n}]];
T[n_, k_] := Sum[A[n, k-i]*(-1)^i*Binomial[k, i], {i, 0, k}];
Table[T[n, k], {n, 0, 10}, {k, 0, n}] // Flatten (* Jean-François Alcover, Feb 08 2017, translated from Maple *)

Formula

T(n,k) = Sum_{i=0..k} (-1)^i * C(k,i) * A261780(n,k-i).