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

Links

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

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

Example

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

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

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.

Sequence in context: A171072 A102035 A055179 * A317863 A318214 A318552

Adjacent sequences: A360631 A360632 A360633 * A360635 A360636 A360637

Keyword

nonn,tabl

Author

Alois P. Heinz, Feb 14 2023

Status

approved