A360634 Number T(n,k) of sets of nonempty words over binary alphabet with a total of n letters of which k are the first letter; triangle T(n,k), n>=0, 0<=k<=n, read by rows.

1, 1, 1, 1, 3, 1, 2, 6, 6, 2, 2, 11, 16, 11, 2, 3, 18, 37, 37, 18, 3, 4, 28, 73, 100, 73, 28, 4, 5, 42, 133, 228, 228, 133, 42, 5, 6, 61, 227, 470, 593, 470, 227, 61, 6, 8, 86, 370, 899, 1370, 1370, 899, 370, 86, 8, 10, 119, 580, 1617, 2894, 3497, 2894, 1617, 580, 119, 10

Offset: 0

Author

Alois P. Heinz, Feb 14 2023

Keywords

• nonn
• tabl

Examples

			T(4,0) = 2: {bbbb}, {b,bbb}.
T(4,1) = 11: {abbb}, {babb}, {bbab}, {bbba}, {a,bbb}, {ab,bb}, {abb,b}, {b,bab}, {b,bba}, {ba,bb}, {a,b,bb}.
T(4,2) = 16: {aabb}, {abab}, {abba}, {baab}, {baba}, {bbaa}, {a,abb}, {a,bab}, {a,bba}, {aa,bb}, {aab,b}, {ab,ba}, {aba,b}, {b,baa}, {a,ab,b}, {a,b,ba}.
Triangle T(n,k) begins:
   1;
   1,   1;
   1,   3,   1;
   2,   6,   6,    2;
   2,  11,  16,   11,    2;
   3,  18,  37,   37,   18,    3;
   4,  28,  73,  100,   73,   28,    4;
   5,  42, 133,  228,  228,  133,   42,    5;
   6,  61, 227,  470,  593,  470,  227,   61,   6;
   8,  86, 370,  899, 1370, 1370,  899,  370,  86,   8;
  10, 119, 580, 1617, 2894, 3497, 2894, 1617, 580, 119, 10;
  ...
		

Links

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

Crossrefs

Columns k=0-2 give: A000009, A095944, A360650.

Row sums give A102866.

T(2n,n) gives A360638.

Cf. A055375 (the same for multisets), A200751, A208741.

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:
b:= proc(n, i) option remember; expand(`if`(n=0, 1,
     `if`(i<1, 0, add(b(n-i*j, i-1)*g(i$2, j), j=0..n/i))))
    end:
T:= (n, k)-> (p-> seq(coeff(p, x, i), i=0..degree(p)))(b(n$2)):
seq(T(n), n=0..15);

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}]]]];
b[n_, i_] := b[n, i] = Expand[If[n == 0, 1, If[i < 1, 0, Sum[b[n - i*j, i - 1]*g[i, i, j], {j, 0, n/i}]]]];
T[n_] := CoefficientList[b[n, n], x];
Table[T[n], {n, 0, 15}] // Flatten (* Jean-François Alcover, Dec 05 2023, after Alois P. Heinz *)

Formula

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

Sum_{k=0..2n} (-1)^k*T(2n,k) = A200751(n). - Alois P. Heinz, Sep 09 2023