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

Links

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

Formula

G.f.: exp(sum_{k=1..infinity) 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

Example

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

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

Crossrefs

First 3 columns are A001190, A036657, A036658.

Row sums are A088325.

T(2n,n) gives A305839.

Sequence in context: A061554 A296373 A345710 * A216956 A285522 A181039

Adjacent sequences: A088323 A088324 A088325 * A088327 A088328 A088329

Keyword

nonn,tabl,easy,changed

Author

N. J. A. Sloane, Nov 06 2003

Extensions

More terms from Vladeta Jovovic, Nov 06 2003

Status

approved