A088326 Triangle T(n,k) (n>=1, 1<=k<=n) read by rows, giving number of Piet Hut's "coat-hanger" arrangements: unlabeled forests of rooted trees with n edges and k connected components, in which the outdegree of each node is <= 2 and the symmetric group acts on the components.

1, 1, 1, 2, 1, 1, 3, 3, 1, 1, 6, 5, 3, 1, 1, 11, 12, 6, 3, 1, 1, 23, 23, 14, 6, 3, 1, 1, 46, 52, 29, 15, 6, 3, 1, 1, 98, 109, 68, 31, 15, 6, 3, 1, 1, 207, 244, 147, 74, 32, 15, 6, 3, 1, 1, 451, 532, 337, 163, 76, 32, 15, 6, 3, 1, 1, 983, 1196, 757, 380, 169, 77, 32, 15, 6, 3, 1, 1

Offset: 1

Author

N. J. A. Sloane, Nov 06 2003

Keywords

• nonn
• tabl
• easy

Examples

			See A088325 for illustration.
Triangle begins
   1
   1  1
   2  1 1
   3  3 1 1
   6  5 3 1 1
  11 12 6 3 1 1
  ...
		

Links

• Alois P. Heinz, Rows n = 1..141, flattened

Crossrefs

First 3 columns are A001190, A036657, A036658.

Row sums are A088325.

T(2n,n) gives A305839.

Programs

Maple

g:= proc(n) option remember; `if`(n<2, n, `if`(n::odd, 0,
      (t-> t*(1-t)/2)(g(n/2)))+add(g(i)*g(n-i), i=1..n/2))
    end:
b:= proc(n, i, p) option remember; `if`(p>n, 0, `if`(n=0, 1,
      `if`(min(i, p)<1, 0, add(b(n-i*j, i-1, p-j)*binomial(
       g(i+1)+j-1, j), j=0..min(n/i, p)))))
    end:
T:= (n, k)-> b(n$2, k):
seq(seq(T(n, k), k=1..n), n=1..14);  # Alois P. Heinz, Sep 11 2017

Mathematica

g[n_] := g[n] = If[n<2, n, If[OddQ[n], 0, Function[t, t*(1-t)/2][g[n/2]]] + Sum[g[i]*g[n - i], {i, 1, n/2}]];
b[n_, i_, p_] := b[n, i, p] = If[p>n, 0, If[n == 0, 1, If[Min[i, p]<1, 0, Sum[b[n-i*j, i-1, p-j]*Binomial[g[i+1]+j-1, j], {j, 0, Min[n/i, p]}]]]];
T[n_, k_] := b[n, n, k];
Table[T[n, k], {n, 1, 14}, {k, 1, n}] // Flatten (* Jean-François Alcover, Jun 11 2018, after Alois P. Heinz *)

Formula

G.f.: exp( Sum_{k>=1} z^k*B(x^k)/k ), where B(x) = x + x^2 + 2*x^3 + 3*x^4 + 6*x^5 + 11*x^6 + ... = G001190(x)/x - 1 and G001190 is the g.f. for the Wedderburn-Etherington numbers A001190.

G.f.: Product_{j>=1} 1/(1-y*x^j)^A001190(j+1). - Alois P. Heinz, Sep 11 2017

Extensions

More terms from Vladeta Jovovic, Nov 06 2003