A360693 Number T(n,k) of sets of n words of length n over binary alphabet where the first letter occurs k times; triangle T(n,k), n>=0, n-signum(n)<=k<=n*(n-1)+signum(n), read by rows.

1, 1, 1, 2, 2, 2, 3, 10, 15, 15, 10, 3, 4, 37, 108, 228, 336, 394, 336, 228, 108, 37, 4, 5, 101, 600, 2150, 5645, 11680, 19752, 27820, 32935, 32935, 27820, 19752, 11680, 5645, 2150, 600, 101, 5, 6, 226, 2490, 14745, 61770, 200529, 535674, 1211485, 2368200

Offset: 0

Author

Alois P. Heinz, Feb 16 2023

Keywords

• nonn
• tabf

Comments

T(n,k) is defined for all n >= 0 and k >= 0. The triangle contains only the positive elements.

Examples

			T(2,3) = 2: {aa,ab}, {aa,ba}.
T(3,3) = 10: {aab,abb,bbb}, {aab,bab,bbb}, {aab,bba,bbb}, {aba,abb,bbb}, {aba,bab,bbb}, {aba,bba,bbb}, {abb,baa,bbb}, {abb,bab,bba}, {baa,bab,bbb}, {baa,bba,bbb}.
T(4,3) = 4: {abbb,babb,bbab,bbbb}, {abbb,babb,bbba,bbbb}, {abbb,bbab,bbba,bbbb}, {babb,bbab,bbba,bbbb}.
Triangle T(n,k) begins:
  1;
  1, 1;
  .  2, 2,  2;
  .  .  3, 10, 15,  15,  10,    3;
  .  .  .   4, 37, 108, 228,  336,  394,   336,   228,   108,    37,     4;
  .  .  .   .   5, 101, 600, 2150, 5645, 11680, 19752, 27820, 32935, 32935, ...;
  ...
		

Links

• Alois P. Heinz, Rows n = 0..33, flattened

Crossrefs

Row sums give A014070.

Column sums give A360695.

Main diagonal T(n,n) gives A154323(n-1) for n>=1.

T(n,n-1) gives A000027(n) for n>=1.

T(2n,2n^2) gives A360702.

Cf. A000290, A057427, A220886 (similar triangle for multisets).

Programs

Maple

g:= proc(n, i, j) option remember; expand(`if`(j=0, 1, `if`(i<0, 0, add(
      g(n, i-1, j-k)*x^(i*k)*binomial(binomial(n, i), k), k=0..j))))
    end:
T:= n-> (p-> seq(coeff(p, x, i), i=n-signum(n)..n*(n-1)+signum(n)))(g(n$3)):
seq(T(n), n=0..6);

Mathematica

g[n_, i_, j_] := g[n, i, j] = Expand[If[j == 0, 1, If[i < 0, 0, Sum[g[n, i - 1, j - k]*x^(i*k)*Binomial[Binomial[n, i], k], {k, 0, j}]]]];
T[n_] := Table[Coefficient[#, x, i], {i, n - Sign[n], n(n - 1) + Sign[n]}]&[g[n, n, n]];
Table[T[n], {n, 0, 6}] // Flatten (* Jean-François Alcover, May 26 2023, after Alois P. Heinz *)

Formula

T(n,k) = T(n,n^2-k).