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

Comments

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

Links

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

Formula

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

Example

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

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

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

Sequence in context: A010583 A306343 A238188 * A051007 A240166 A346801

Adjacent sequences: A360690 A360691 A360692 * A360694 A360695 A360696

Keyword

nonn,tabf

Author

Alois P. Heinz, Feb 16 2023

Status

approved