A122086 -id:A122086 - cp's OEIS frontend

A125702 Number of connected categories with n objects and 2n-1 morphisms.

1, 1, 2, 3, 6, 10, 22, 42, 94, 203, 470, 1082, 2602, 6270, 15482, 38525, 97258, 247448, 635910, 1645411, 4289010, 11245670, 29656148, 78595028, 209273780, 559574414, 1502130920, 4046853091, 10939133170, 29661655793

Offset: 1

Franklin T. Adams-Watters and Christian G. Bower, Jan 05 2007

nonn

Also number of connected antitransitive relations on n objects (antitransitive meaning a R b and b R c implies not a R c); equivalently, number of free oriented bipartite trees, with all arrows going from one part to the other part.

Also the number of non-isomorphic multi-hypertrees of weight n - 1 with singletons allowed. A multi-hypertree with singletons allowed is a connected set multipartition (multiset of sets) with density -1, where the density of a set multipartition is the weight (sum of sizes of the parts) minus the number of parts minus the number of vertices. - Gus Wiseman, Oct 30 2018

			From _Gus Wiseman_, Oct 30 2018: (Start)
Non-isomorphic representatives of the a(1) = 1 through a(6) = 10 multi-hypertrees of weight n - 1 with singletons allowed:
  {}  {{1}}  {{12}}    {{123}}      {{1234}}        {{12345}}
             {{1}{1}}  {{2}{12}}    {{13}{23}}      {{14}{234}}
                       {{1}{1}{1}}  {{3}{123}}      {{4}{1234}}
                                    {{1}{2}{12}}    {{2}{13}{23}}
                                    {{2}{2}{12}}    {{2}{3}{123}}
                                    {{1}{1}{1}{1}}  {{3}{13}{23}}
                                                    {{3}{3}{123}}
                                                    {{1}{2}{2}{12}}
                                                    {{2}{2}{2}{12}}
                                                    {{1}{1}{1}{1}{1}}
(End)

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

Same as A122086 except for n = 1; see there for formulas. Cf. A125699.

Cf. A000081, A000272, A007716, A007717, A030019, A052888, A134954, A317631, A317632, A318697, A320921, A321155.

\\ TreeGf gives gf of A000081.
TreeGf(N)={my(A=vector(N, j, 1)); for (n=1, N-1, A[n+1] = 1/n * sum(k=1, n, sumdiv(k, d, d*A[d]) * A[n-k+1] ) ); x*Ser(A)}
seq(n)={Vec(2*TreeGf(n) - TreeGf(n)^2 - x)} \\ Andrew Howroyd, Nov 02 2019

a(n) = A122086(n) for n > 1.

G.f.: 2*f(x) - f(x)^2 - x where f(x) is the g.f. of A000081. - Andrew Howroyd, Nov 02 2019

A329054 Array read by antidiagonals: T(n,m) is the number of unlabeled bicolored trees with n nodes of one color and m of the other.

Original entry on oeis.org

1, 1, 1, 0, 1, 0, 0, 1, 1, 0, 0, 1, 1, 1, 0, 0, 1, 2, 2, 1, 0, 0, 1, 2, 4, 2, 1, 0, 0, 1, 3, 7, 7, 3, 1, 0, 0, 1, 3, 10, 14, 10, 3, 1, 0, 0, 1, 4, 14, 28, 28, 14, 4, 1, 0, 0, 1, 4, 19, 45, 65, 45, 19, 4, 1, 0, 0, 1, 5, 24, 73, 132, 132, 73, 24, 5, 1, 0

Offset: 0

Andrew Howroyd, Nov 02 2019

The two color classes are not interchangeable. Adjacent nodes cannot have the same color.

Essentially the same data as given in the irregular triangle A122085, but including complete columns for n = 0 and m = 0 to give a regular array.

			Array begins:
===================================================
n\m | 0  1  2   3    4    5     6     7      8
----+----------------------------------------------
  0 | 1, 1, 0,  0,   0,   0,    0,    0,     0, ...
  1 | 1, 1, 1,  1,   1,   1,    1,    1,     1, ...
  2 | 0, 1, 1,  2,   2,   3,    3,    4,     4, ...
  3 | 0, 1, 2,  4,   7,  10,   14,   19,    24, ...
  4 | 0, 1, 2,  7,  14,  28,   45,   73,   105, ...
  5 | 0, 1, 3, 10,  28,  65,  132,  242,   412, ...
  6 | 0, 1, 3, 14,  45, 132,  316,  693,  1349, ...
  7 | 0, 1, 4, 19,  73, 242,  693, 1742,  3927, ...
  8 | 0, 1, 4, 24, 105, 412, 1349, 3927, 10079, ...
  ...

Andrew Howroyd, Table of n, a(n) for n = 0..1325

Main diagonal is A119857.
Antidiagonal sums are A122086.
The equivalent array for labeled nodes is A072590.
Cf. A122085, A329053.

EulerXY(A)={my(j=serprec(A,x)); exp(sum(i=1, j, 1/i * subst(subst(A + x * O(x^(j\i)), x, x^i), y, y^i)))}
R(n)={my(A=O(x)); for(j=1, 2*n, A = if(j%2, 1, y)*x*EulerXY(A)); A};
P(n)={my(r1=R(n), r2=x*EulerXY(r1), s=r1+r2-r1*r2); Vec(1 + s)}
{ my(A=P(10)); for(n=0, #A\2, for(k=0, #A\2, print1(polcoef(A[n+k+1], k), ", ")); print) }

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

Original entry on oeis.org

1, 1, 1, 1, 1, 1, 1, 1, 1, 2, 2, 1, 1, 2, 4, 2, 1, 1, 3, 7, 7, 3, 1, 1, 3, 10, 14, 10, 3, 1, 1, 4, 14, 28, 28, 14, 4, 1, 1, 4, 19, 45, 65, 45, 19, 4, 1, 1, 5, 24, 73, 132, 132, 73, 24, 5, 1, 1, 5, 30, 105, 242, 316, 242, 105, 30, 5, 1, 1, 6, 37, 152, 412, 693, 693, 412, 152

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
1 0 1
Total( 1) = 2
1 1 1
Total( 2) = 1
1 2 1
2 1 1
Total( 3) = 2
1 3 1
2 2 1
3 1 1
Total( 4) = 3
1 4 1
2 3 2
3 2 2
4 1 1
Total( 5) = 6
1 5 1
2 4 2
3 3 4
4 2 2
5 1 1
Total( 6) = 10
.
From _Andrew Howroyd_, Nov 02 2019: (Start)
Triangle for n >= 2, 1 <= k < n:
   2 | 1;
   3 | 1, 1;
   4 | 1, 1,  1;
   5 | 1, 2,  2,   1;
   6 | 1, 2,  4,   2,   1;
   7 | 1, 3,  7,   7,   3,   1;
   8 | 1, 3, 10,  14,  10,   3,   1;
   9 | 1, 4, 14,  28,  28,  14,   4,   1;
  10 | 1, 4, 19,  45,  65,  45,  19,   4,  1;
  11 | 1, 5, 24,  73, 132, 132,  73,  24,  5, 1;
  12 | 1, 5, 30, 105, 242, 316, 242, 105, 30, 5, 1;
  ...
(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 A122086.

Cf. A329054 (regular array with same data).

A329053 Number of bicolored acyclic graphs on n unlabeled nodes.

Original entry on oeis.org

1, 2, 4, 8, 16, 32, 65, 134, 280, 598, 1300, 2884, 6516, 15008, 35147, 83680, 202139, 494982, 1226753, 3074146, 7779561, 19863702, 51125018, 132541616, 345867101, 907922596, 2396276355, 6355845398, 16934718359, 45309972502, 121697068925, 328029259192

Offset: 0

Andrew Howroyd, Nov 02 2019

nonn

The two color classes are not interchangeable. Adjacent nodes cannot have the same color.

Andrew Howroyd, Table of n, a(n) for n = 0..500

Antidiagonal sums of A329052.

Cf. A122086.

EulerT(v)={Vec(exp(x*Ser(dirmul(v,vector(#v,n,1/n))))-1, -#v)}
TreeGf(N)={my(A=vector(N, j, 1)); for (n=1, N-1, A[n+1] = 1/n * sum(k=1, n, sumdiv(k, d, d*A[d]) * A[n-k+1] ) ); x*Ser(A)}
seq(n)={concat([1], EulerT(Vec(2*TreeGf(n) - TreeGf(n)^2)))}

Euler transform of A122086.

cp's OEIS Frontend

A125702 Number of connected categories with n objects and 2n-1 morphisms.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

PARI

Formula

A329054 Array read by antidiagonals: T(n,m) is the number of unlabeled bicolored trees with n nodes of one color and m of the other.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

PARI

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

Views

Author

Keywords

Examples

References

Links

Crossrefs

A329053 Number of bicolored acyclic graphs on n unlabeled nodes.

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

PARI

Formula