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,5

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)

Links

Alois P. Heinz, Rows n = 0..140, flattened

E. Munarini, M. Poneti, S. Rimaldi, Matrix compositions, JIS 12 (2009) 09.4.8, Table 2.

Formula

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

Example

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

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 *)

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.

Sequence in context: A258818 A261275 A140326 * A211402 A256064 A126436

Adjacent sequences: A261778 A261779 A261780 * A261782 A261783 A261784

Keyword

nonn,tabl

Author

Alois P. Heinz, Aug 31 2015

Status

approved