A000220 -id:A000220 - cp's OEIS frontend

A228601 Triangle read by rows: T(n,k) is the number of trees with n vertices and having k distinct rootings (1 <= k <= n).

1, 1, 0, 0, 1, 0, 0, 2, 0, 0, 0, 1, 1, 1, 0, 0, 2, 1, 2, 1, 0, 0, 1, 2, 4, 1, 2, 1, 0, 2, 1, 7, 4, 4, 4, 1, 0, 1, 2, 7, 7, 9, 10, 8, 3, 0, 2, 3, 12, 10, 17, 19, 20, 17, 6, 0, 1, 2, 12, 14, 28, 37, 45, 46, 35, 15, 0, 2, 1, 18, 21, 46, 60, 87, 106, 103, 78, 29

Offset: 1

Emeric Deutsch, Oct 20 2013

The entries in the triangle have been obtained - painstakingly - from the Read & Wilson reference (pp. 63-73); the white vertices indicate the possible distinct rootings for the given tree.

			Row 4 is 0,2,0,0 because the trees with 4 vertices are (i) the path tree abcd with 2 distinct rootings (at a and at b) and (ii) the star tree with 4 vertices having, obviously, 2 distinct rootings.
Triangle starts:
  1;
  1, 0;
  0, 1, 0;
  0, 2, 0, 0;
  0, 1, 1, 1, 0;
  0, 2, 1, 2, 1, 0;
  0, 1, 2, 4, 1, 2, 1;

R. C. Read and R. J. Wilson, An Atlas of Graphs, Oxford, 1998.

Sean A. Irvine, Rows n=1..44 of triangle, flattened
F. Harary, R. W. Robinson, Isomorphic factorizations VIII: bisectable trees, Combinatorica 4 (2) (1984) 169-179.

Cf. A000055, A000081, A000220.

Sum of entries in row n = A000055(n).
Sum_{k=1..n} k*T(n,k)  = A000081(n).
T(n,n) = A000220(n).
Let A214568(x,y) be the bivariate g.f. of A214568, then this g.f. is A214568(x,y) -( [A214568(x,y)]^2 + A214568(x^2,y^2) )/2 + A214568(x^2,y), see eq. (4.8) by Harary-Robinson. - R. J. Mathar, Sep 16 2015

A309352 Number of free trees of n vertices whose automorphisms are a 2-group.

Original entry on oeis.org

1, 1, 1, 1, 1, 2, 4, 6, 13, 26, 56, 122, 278, 634, 1494, 3540, 8542, 20774, 51116, 126648, 316452, 795510, 2012476, 5117613, 13079677, 33576706, 86555074, 223965633, 581573118, 1515084771, 3959038337, 10374543765, 27258298145

Offset: 0

Kevin Ryde, Jul 24 2019

nonn

A 2-group is a group with order some power 2^k. In free tree automorphisms, this means at a given vertex an adjacent subtree can appear there twice, but not three or more times.

Free trees are counted from rooted trees in the usual way by rooting at a centroid. This is in the generating function of A000055 (all free) from A000081 (all rooted). From all rooted trees, subtract the unbalanced where root not centroid, and allow bicentroidals with same halves. a(n) follows this way from A248869 rooted 2-groups. With root as centroid, the free automorphisms are all and only the rooted automorphisms, except swap halves of a bi-centroidal. Such a swap can be part of a 2-group, so same halves allowed.

			a(4)=1 is path-4 having automorphism group S2 (reverse the path), and excludes star-4 which is S3 order 6 (permute the leaves).  a(5)=2 excludes star-5 which is S4 on the leaves.

Kevin Ryde, Table of n, a(n) for n = 0..2213

Cf. A000055, A000220, A248869.

h:= proc(n, m, t) option remember; `if`(m=0, binomial(n+t, t),
      `if`(n=0, 0, add(h(n-1, m-j, t+1), j=1..min(2, m))))
    end:
b:= proc(n, i) option remember; `if`(n=0, 1, `if`(i<1, 0,
      add(b(n-i*j, i-1)*h(g(i), j, 0), j=0..n/i)))
    end:
g:= n-> `if`(n<2, n, b(n-1$2)):
a:= n-> `if`(n=0, 1, g(n)-add(g(j)*g(n-j), j=0..n/2)+
        `if`(n::even, (t-> t*(t+1)/2)(g(n/2)), 0)):
seq(a(n), n=0..35);  # Alois P. Heinz, Aug 01 2019

h[n_, m_, t_] := h[n, m, t] = If[m == 0, Binomial[n + t, t], If[n == 0, 0, Sum[h[n-1, m-j, t+1], {j, 1, Min[2, m]}]]];
b[n_, i_] := b[n, i] = If[n==0, 1, If[i<1, 0, Sum[b[n - i j, i-1] h[g[i], j, 0], {j, 0, n/i}]]];
g[n_] := If[n < 2, n, b[n-1, n-1]];
a[n_] := If[n == 0, 1, g[n] - Sum[g[j] g[n-j], {j, 0, n/2}] + If[EvenQ[n], #(#+1)/2&[g[n/2]], 0]];
a /@ Range[0, 35] (* Jean-François Alcover, Nov 14 2020, after Alois P. Heinz *)

a(n) = A248869(n) - (Sum_{i=1..floor(n/2)} A248869(i)*A248869(n-i)) + (binomial(A248869(n/2)+1,2) if n even), for n>=1.

G.f.: g(x) = 1 + T(x) - T^2(x)/2 + T(x^2)/2, where T(x) = x + x^2 + 2*x^3 + 3*x^4 + ... is the g.f. for A248869.

A290667 Number of asymmetric equicolorable (unrooted) trees with 2*n vertices.

Original entry on oeis.org

0, 0, 0, 1, 4, 19, 84, 378, 1727, 8126, 39055, 191902, 960681

Offset: 1

John P. McSorley, Aug 08 2017

Any tree with 2n vertices is a bipartite graph with s vertices in one part and t vertices in the other part, where s <= t and s + t = 2n. We count trees with s = t = n, and which are asymmetric, that is, their only automorphism is the identity automorphism. These are also called identity trees.

			a(3) = 0 because there are six trees with 6 vertices, but only three of these have s = t = n = 3, and none of these three is asymmetric. The fourth term a(4) = 1 because there are nine trees with 8 vertices with s = t = n = 4 but only 1 is asymmetric, namely tree T46. See "Atlas of Graphs", page 65.

R. C. Read and R. J. Wilson, Atlas of Graphs, Oxford Science Publications, Clarendon Press, OUP, 2004.

F. Hüffner, tinygraph, software for generating integer sequences based on graph properties.
Austin Mohr, Unlabeled Trees.

Cf. A119856 (equicolorable trees with 2n vertices), A000220 (asymmetric trees with n vertices).

a(10)-a(13) added using tinygraph by Falk Hüffner, Jul 25 2019

cp's OEIS Frontend

A228601 Triangle read by rows: T(n,k) is the number of trees with n vertices and having k distinct rootings (1 <= k <= n).

Views

Author

Keywords

Comments

Examples

References

Links

Crossrefs

Formula

A309352 Number of free trees of n vertices whose automorphisms are a 2-group.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Maple

Mathematica

Formula

A290667 Number of asymmetric equicolorable (unrooted) trees with 2*n vertices.

Views

Author

Keywords

Comments

Examples

References

Links

Crossrefs

Extensions