A119856 -id:A119856 - cp's OEIS frontend

A119857 Number of equicolored (unrooted) trees on 2n nodes.

1, 1, 4, 14, 65, 316, 1742, 10079, 61680, 391473, 2565262, 17237962, 118341446, 827194809, 5872518213, 42256545977, 307681822711, 2263881127801, 16813356777456, 125917441081662, 950148951332802, 7218810159035143, 55187741462110393, 424318236236124092

Offset: 1

N. J. A. Sloane, Aug 04 2006

nonn

For precise definition, recurrence and asymptotics see the Pippenger reference.

Andrew Howroyd, Table of n, a(n) for n = 1..100
N. Pippenger, Enumeration of equicolorable trees, SIAM J. Discrete Math., 14 (2001), 93-115.

Main diagonal of A329054.

Cf. A119855, A119856.

\\ R is b.g.f of rooted trees x nodes, y in one part
R(n)={my(A=O(x)); for(j=1, 2*n, A = if(j%2,1,y)*x*exp(sum(i=1, j, 1/i * subst(subst(A + x * O(x^(j\i)), x, x^i), y, y^i)))); A};
seq(n)={my(A=Pol(R(n))); my(r(x,y)=substvec(A, ['x,'y], [x,y/x])); Vec(polcoeff((r(x,y/x) + r(y/x,x) - r(x,y/x)*r(y/x,x)), 0) + O(y*y^n))} \\ Andrew Howroyd, May 23 2018

Terms a(8) and beyond from Andrew Howroyd, May 21 2018

A119855 Number of equicolorable rooted trees on 2n nodes.

Original entry on oeis.org

1, 2, 9, 44, 249, 1506, 9687, 64803, 447666, 3169566, 22897260, 168168164, 1252391041, 9437809359, 71850420813, 551876468717, 4272100488830, 33299732401378, 261165251593743, 2059638535690473, 16324255856903830, 129969379170062142, 1039056925387672998

Offset: 1

N. J. A. Sloane, Aug 04 2006

nonn

For precise definition, recurrence and asymptotics see the Pippenger reference.

An equicolorable tree is a tree which can be colored with two colors with adjacent nodes having different colors and there being an equal number of nodes of each color. - Andrew Howroyd, May 21 2018

N. Pippenger, Enumeration of equicolorable trees, SIAM J. Discrete Math., 14 (2001), 93-115.

Andrew Howroyd, Table of n, a(n) for n = 1..100

Cf. A119856, A119857.

\\ R is b.g.f of rooted trees x nodes, y in one part
R(n)={my(A=O(x)); for(j=1, 2*n, A = if(j%2,1,y)*x*exp(sum(i=1, j, 1/i * subst(subst(A + x * O(x^(j\i)), x, x^i), y, y^i)))); A};
seq(n)={my(A=Pol(R(n))); my(r(x,y)=substvec(A, ['x,'y], [x,y/x])); Vec(polcoeff(r(x, y/x), 0) + O(y*y^n))} \\ Andrew Howroyd, May 23 2018

Terms a(8) and beyond from Andrew Howroyd, May 21 2018

A122087 Triangle read by rows: T(n,k) = number of unlabeled free bicolored trees with n nodes (n >= 1) and k (1 <= k <= floor(n/2), except k = 0 if n = 1 ) nodes of one color and n-k nodes of the other color (the colors are interchangeable).

Original entry on oeis.org

1, 1, 1, 1, 1, 1, 2, 1, 2, 3, 1, 3, 7, 1, 3, 10, 9, 1, 4, 14, 28, 1, 4, 19, 45, 37, 1, 5, 24, 73, 132, 1, 5, 30, 105, 242, 168, 1, 6, 37, 152, 412, 693, 1, 6, 44, 204, 660, 1349, 895, 1, 7, 52, 274, 1008, 2472, 3927, 1, 7, 61, 351, 1479, 4219, 8105, 5097, 1, 8

Offset: 1

N. J. A. Sloane, Oct 19 2006

			K M N gives the number N of unlabeled free bicolored trees with K nodes of one color and M nodes of the other color.
0 1 1
Total( 1) = 1
1 1 1
Total( 2) = 1
1 2 1
Total( 3) = 1
1 3 1
2 2 1
Total( 4) = 2
1 4 1
2 3 2
Total( 5) = 3
1 5 1
2 4 2
3 3 3
Total( 6) = 6
1 6 1
2 5 3
3 4 7
Total( 7) = 11
1 7 1
2 6 3
3 5 10
4 4 9
Total( 8) = 23
From _Andrew Howroyd_, Apr 05 2023: (Start)
Triangle begins:
  n\k| 0 1  2   3    4    5    6
 ----+----------------------------
   1 | 1;
   2 | . 1;
   3 | . 1;
   4 | . 1, 1;
   5 | . 1, 2;
   6 | . 1, 2,  3;
   7 | . 1, 3,  7;
   8 | . 1, 3, 10,   9;
   9 | . 1, 4, 14,  28;
  10 | . 1, 4, 19,  45,  37;
  11 | . 1, 5, 24,  73, 132;
  12 | . 1, 5, 30, 105, 242, 168;
    ...
(End)

R. W. Robinson, Numerical implementation of graph counting algorithms, AGRC Grant, Math. Dept., Univ. Newcastle, Australia, 1978.

R. W. Robinson, Rows 1 through 30, flattened

Row sums give A000055.

Cf. A119856, A329054, A362019 (labeled version).

T(n,k) = A329054(k, n-k) for 2*k < n; T(2*n,n) = A119856(n). - Andrew Howroyd, Apr 04 2023

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

A119857 Number of equicolored (unrooted) trees on 2n nodes.

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

PARI

Extensions

A119855 Number of equicolorable rooted trees on 2n nodes.

Views

Author

Keywords

Comments

References

Links

Crossrefs

Programs

PARI

Extensions

A122087 Triangle read by rows: T(n,k) = number of unlabeled free bicolored trees with n nodes (n >= 1) and k (1 <= k <= floor(n/2), except k = 0 if n = 1 ) nodes of one color and n-k nodes of the other color (the colors are interchangeable).

Views

Author

Keywords

Examples

References

Links

Crossrefs

Formula

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

Views

Author

Keywords

Comments

Examples

References

Links

Crossrefs

Extensions