A339645 -id:A339645 - cp's OEIS frontend

A101389 Number of n-vertex unlabeled oriented graphs without endpoints.

1, 1, 1, 3, 21, 369, 16929, 1913682, 546626268, 406959998851, 808598348346150, 4358157210587930509, 64443771774627635711718, 2636248889492487709302815665, 300297332862557660078111708007894, 95764277032243987785712142452776403618, 85885545190811866954428990373255822969983915

Offset: 0

Goran Kilibarda, Vladeta Jovovic, Jan 14 2005

nonn

			a(3) = 3 because there are 2 distinct orientations of the triangle K_3 plus the empty graph on 3 vertices.

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

Cf. A100569 (labeled case), A100548, A101388, A004110, A004108, A059166, A059167, A001174.

\\ See links in A339645 for combinatorial species functions.
oedges(v) = {sum(i=2, #v, sum(j=1, i-1, gcd(v[i], v[j]))) + sum(i=1, #v, (v[i]-1)\2)}
ographsCycleIndex(n)={my(s=0); forpart(p=n, s+=permcount(p) * 3^oedges(p) * sMonomial(p)); s/n!}
ographs(n)={sum(k=0, n, ographsCycleIndex(k)*x^k) + O(x*x^n)}
trees(n,k)={sRevert(x*sv(1)/sExp(k*x*sv(1) + O(x^n)))}
cycleIndexSeries(n)={my(g=ographs(n), tr=trees(n,2), tu=tr-tr^2); sSolve( g/sExp(tu), tr )*symGroupSeries(n)}
NumUnlabeledObjsSeq(cycleIndexSeries(15)) \\ Andrew Howroyd, Dec 27 2020

\\ faster stand-alone version
permcount(v) = {my(m=1, s=0, k=0, t); for(i=1, #v, t=v[i]; k=if(i>1&&t==v[i-1], k+1, 1); m*=t*k; s+=t); s!/m}
edges(v) = {sum(i=2, #v, sum(j=1, i-1, gcd(v[i],v[j]))) + sum(i=1, #v, (v[i]-1)\2)}
seq(n)={Vec(sum(k=0, n, my(s=0); forpart(p=k, s+=permcount(p) * 3^edges(p) * prod(i=1, #p, my(d=p[i]); (1-x^d)^2 + O(x*x^(n-k))) ); x^k*s/k!)/(1-x^2))} \\ Andrew Howroyd, Jan 22 2021

a(0)=1 prepended and terms a(9) and beyond from Andrew Howroyd, Dec 27 2020

A304485 Regular triangle where T(n,k) is the number of inequivalent colorings of free pure symmetric multifunctions (with empty expressions allowed) with n positions and k leaves.

Original entry on oeis.org

1, 1, 0, 1, 2, 0, 1, 6, 4, 0, 1, 12, 23, 7, 0, 1, 20, 81, 73, 12, 0, 1, 30, 209, 407, 206, 19, 0, 1, 42, 451, 1566, 1751, 534, 30, 0, 1, 56, 858, 4711, 9593, 6695, 1299, 45, 0, 1, 72, 1494, 11951, 39255, 51111, 23530, 3004, 67, 0, 1, 90, 2430, 26752, 130220, 278570, 245319, 77205, 6664, 97, 0

Offset: 1

Gus Wiseman, Aug 17 2018

A free pure symmetric multifunction (with empty expressions allowed) f in EOME is either (case 1) a positive integer, or (case 2) a possibly empty expression of the form h[g_1, ..., g_k] where k >= 0, h is in EOME, each of the g_i for i = 1, ..., k is in EOME, and for i < j we have g_i <= g_j under a canonical total ordering of EOME, such as the Mathematica ordering of expressions.

T(n,k) is also the number of inequivalent colorings of orderless Mathematica expressions with n positions and k leaves.

			Inequivalent representatives of the T(5,3) = 23 Mathematica expressions:
  1[][1,1]  1[1,1][]  1[1][1]  1[1[1]]  1[1,1[]]
  1[][1,2]  1[1,2][]  1[1][2]  1[1[2]]  1[1,2[]]
  1[][2,2]  1[2,2][]  1[2][1]  1[2[1]]  1[2,1[]]
  1[][2,3]  1[2,3][]  1[2][2]  1[2[2]]  1[2,2[]]
                      1[2][3]  1[2[3]]  1[2,3[]]
Triangle begins:
    1
    1    0
    1    2    0
    1    6    4    0
    1   12   23    7    0
    1   20   81   73   12    0
    1   30  209  407  206   19    0
    1   42  451 1566 1751  534   30    0

Andrew Howroyd, Table of n, a(n) for n = 1..325 (rows 1..25)

Row sums are A300626.

Cf. A000612, A007716, A052893, A053492, A277996, A280000, A317676.

\\ See links in A339645 for combinatorial species functions.
cycleIndexSeries(n)={my(p=O(x)); for(n=1, n, p = x*sv(1) + x*p*sExp(p)); p}
T(n)={my(v=Vec(InequivalentColoringsSeq(sFuncSubst(cycleIndexSeries(n), i->sv(i)*y^i)))); vector(n, n, Vecrev(v[n]/y, n))}
{ my(A=T(10)); for(n=1, #A, print(A[n])) } \\ Andrew Howroyd, Jan 01 2021

Terms a(37) and beyond from Andrew Howroyd, Jan 01 2021

A330473 Regular triangle where T(n,k) is the number of non-isomorphic multiset partitions of k-element multiset partitions of multisets of size n.

Original entry on oeis.org

1, 0, 1, 0, 2, 4, 0, 3, 8, 10, 0, 5, 28, 38, 33, 0, 7, 56, 146, 152, 91, 0, 11, 138, 474, 786, 628, 298, 0, 15, 268, 1388, 3117, 3808, 2486, 910, 0, 22, 570, 3843, 11830, 19147, 18395, 9986, 3017, 0, 30, 1072, 10094, 40438, 87081, 110164, 86388, 39889, 9945

Offset: 0

Gus Wiseman, Dec 20 2019

As an alternative description, T(n,k) is the number of non-isomorphic multisets of nonempty multisets of nonempty multisets with n leaves whose multiset union consists of k multisets.

			Triangle begins:
   1
   0   1
   0   2   4
   0   3   8  10
   0   5  28  38  33
   0   7  56 146 152  91
   0  11 138 474 786 628 298
For example, row n = 3 counts the following multiset partitions:
  {{111}}  {{1}{11}}    {{1}{1}{1}}
  {{112}}  {{1}{12}}    {{1}{1}{2}}
  {{123}}  {{1}{23}}    {{1}{2}{3}}
           {{2}{11}}    {{1}}{{1}{1}}
           {{1}}{{11}}  {{1}}{{1}{2}}
           {{1}}{{12}}  {{1}}{{2}{3}}
           {{1}}{{23}}  {{2}}{{1}{1}}
           {{2}}{{11}}  {{1}}{{1}}{{1}}
                        {{1}}{{1}}{{2}}
                        {{1}}{{2}}{{3}}

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

Row sums are A318566.
Column k = 1 is A000041 (for n > 0).
Column k = n is A007716.
Partitions of partitions of partitions are A007713.
Twice-factorizations are A050336.
The 2-dimensional version is A317533.
See A330472 for a variation.
Cf. A001055, A050336, A061260, A269134, A292504, A306186, A317791.

\\ See links in A339645 for combinatorial species functions.
ColGf(k, n)={my(A=symGroupSeries(n)); OgfSeries(sCartProd(sExp(A), sSubstOp(polcoef(sExp(A), k, x)*x^k + O(x*x^n), A) ))}
M(n, m=n)={Mat(vector(m+1, k, Col(ColGf(k-1, n), -(n+1))))}
{ my(A=M(10)); for(n=1, #A, print(A[n, 1..n])) } \\ Andrew Howroyd, Jan 18 2023

Terms a(36) and beyond from Andrew Howroyd, Jan 18 2023

A339647 Number of inequivalent leaf colorings of series-reduced planted trees with n leaves using exactly 2 colors.

Original entry on oeis.org

0, 1, 3, 17, 73, 369, 1795, 9192, 47324, 249164, 1326449, 7155620, 38979373, 214304435, 1187338427, 6624057963, 37178881395, 209802434879, 1189621738769, 6774546637528, 38729276531965, 222191966031306, 1278819536137209, 7381798618249920, 42724974018583842

Offset: 1

Andrew Howroyd, Dec 16 2020

nonn

Equivalence is up to permutation of the colors.

			a(2) = 1: (12).
a(3) = 3: (112), (1(12)), (1(22)).
a(4) = 17: (1112), (1122), (11(12)), (11(22)), (12(11)), (12(12)), (1(112)), (1(122)), (1(222)), (1(1(12))), (1(1(22))), (1(2(11))), (1(2(12))), (1(2(22))), ((11)(12)), ((11)(22)), ((12)(12)).

The case that colors may not be interchanged is A319377.
Column 2 of A339645.
Cf. A000669, A339646.

\\ See A339647 for cycleIndexSeries and InequivalentColoringsSeq.
{ my(S=cycleIndexSeries(20)); InequivalentColoringsSeq(S,2) - InequivalentColoringsSeq(S,1) }

A340028 Number of unlabeled 2-connected graphs with n vertices rooted at a pair of noninterchangeable vertices.

Original entry on oeis.org

0, 1, 1, 7, 55, 655, 11147, 287791, 11787747, 804475261, 94875366649, 19825870580671, 7466490852631207, 5129453728126116131, 6487332587944013948099, 15213161506747424007012971, 66536415576917924594383104139, 545371527333985035460963541248785

Offset: 1

Andrew Howroyd, Jan 02 2021

nonn

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

Cf. A002218, A004115, A241768, A304070, A304074, A340029.

\\ See A004115 for graphsSeries and A339645 for combinatorial species functions.
cycleIndexSeries(n)={my(g=graphsSeries(n), gcr=sPoint(g)/g); x*sPoint(sSolve( sLog( gcr/(x*sv(1)) ), gcr ))}
{ my(N=15); Vec(OgfSeries(cycleIndexSeries(N)), -N) }

A340029 Number of unlabeled 2-connected graphs with n vertices rooted at a pair of indistinguishable vertices.

Original entry on oeis.org

0, 1, 1, 6, 37, 388, 6004, 148759, 5974184, 404509191, 47552739892, 9923861406343, 3735194287263442, 2565376853616300801, 3244070698095148283628, 7607050619214875184974489, 33269229977451262849539412860, 272689940536978851416633440863567

Offset: 1

Andrew Howroyd, Jan 02 2021

nonn

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

Cf. A002218, A004115, A241768, A303829, A303831, A340028.

\\ See A004115 for graphsSeries and A339645 for combinatorial species functions.
blockGraphs(n)={my(gc=sLog(graphsSeries(n)), gcr=sPoint(gc)); intformal(x*sSolve( sLog( gcr/(x*sv(1)) ), gcr ), sv(1)) + sSolve(subst(gc, sv(1), 0), gcr)}
cycleIndexSeries(n)={sCartProd(blockGraphs(n), x^2 * symGroupCycleIndex(2) * symGroupSeries(n-2))}
{ my(N=15); Vec(OgfSeries(cycleIndexSeries(N)), -N) }

A339233 Number of inequivalent colorings of oriented series-parallel networks with n colored elements.

Original entry on oeis.org

1, 4, 21, 165, 1609, 19236, 266251, 4175367, 72705802, 1387084926, 28689560868, 638068960017, 15158039092293, 382527449091778, 10207466648995608, 286876818184163613, 8462814670769394769, 261266723355912507073, 8419093340955799898258, 282519424041100564770142

Offset: 1

Andrew Howroyd, Dec 22 2020

nonn

Equivalence is up to permutation of the colors. Any number of colors may be used. See A339228 for additional details.

			In the following examples elements in series are juxtaposed and elements in parallel are separated by '|'.
a(1) = 1: (1).
a(2) = 4: (11), (12), (1|1), (1|2).
a(3) = 21: (111), (112), (121), (122), (123), (1(1|1)), (1(1|2)), (1(2|2)), (1(2|3)), ((1|1)1), ((1|1)2), ((1|2)1), ((1|2)3), (1|1|1), (1|1|2), (1|2|3), (1|11), (1|12), (1|21), (1|22), (1|23).

Cf. A003430 (uncolored), A339226, A339228, A339229, A339287 (unoriented), A339645.

\\ See links in A339645 for combinatorial species functions.
cycleIndexSeries(n)={my(Z=x*sv(1), p=Z+O(x^2)); for(n=2, n, p=sEulerT(p^2/(1+p) + Z)-1); p}
InequivalentColoringsSeq(cycleIndexSeries(15))

A339287 Number of inequivalent colorings of unoriented series-parallel networks with n colored elements.

Original entry on oeis.org

1, 4, 15, 105, 873, 9997, 134582, 2096206, 36391653, 693779666, 14346005530, 319042302578, 7579064231400, 191264021808301, 5103735168371201, 143438421861618397, 4231407420255210941, 130633362289335958866, 4209546674788934624394, 141259712052820378949746

Offset: 1

Andrew Howroyd, Dec 22 2020

nonn

Equivalence is up to permutation of the colors and reversal of all parts combined in series. Any number of colors may be used. See A339282 for additional details.

			In the following examples elements in series are juxtaposed and elements in parallel are separated by '|'.
a(1) = 1: (1).
a(2) = 4: (11), (12), (1|1), (1|2).
a(3) = 15: (111), (112), (121), (123), (1(1|1)), (1(1|2)), (1(2|2)), (1(2|3)), (1|1|1), (1|1|2), (1|2|3), (1|11), (1|12), (1|22), (1|23).

Cf. A339225 (uncolored), A339233 (oriented), A339280, A339282, A339283, A339645.

\\ See links in A339645 for combinatorial species functions.
B(n)={my(Z=x*sv(1), p=Z+O(x^2)); for(n=2, n, p=sEulerT(p^2/(1+p) + Z)-1); p}
cycleIndexSeries(n)={my(Z=x*sv(1), q=sRaise(B((n+1)\2), 2), s=x^2*sv(2)+q^2/(1+q), p=Z+O(x^2), t=p); for(n=1, n\2, t=Z + q*(1 + p); p=Z + sEulerT(t+(s-sRaise(t, 2))/2) - t - 1); (p+t-Z+B(n))/2}
InequivalentColoringsSeq(cycleIndexSeries(15))

A339646 Number of inequivalent leaf colorings of series-reduced planted trees with n leaves using at most 2 colors.

Original entry on oeis.org

1, 2, 5, 22, 85, 402, 1885, 9453, 48090, 251476, 1333517, 7177585, 39048327, 214523186, 1188037961, 6626311639, 37186187183, 209826251622, 1189699762371, 6774803376279, 38730124684829, 222194778028278, 1278828889503773, 7381829822338301, 42725078403203912

Offset: 1

Andrew Howroyd, Dec 16 2020

nonn

Equivalence is up to permutation of the colors.

			a(1) = 1: 1.
a(2) = 2: (11), (12).
a(3) = 5: (111), (112), (1(11)), (1(12)), (1(22)).

The case that colors may not be interchanged is A050381.

Cf. A000669, A339645, A339647.

\\ See A339645 for cycleIndexSeries and InequivalentColoringsSeq.
InequivalentColoringsSeq(cycleIndexSeries(20),2)

a(n) = A339647(n) - A000669(n).

A361367 Number of weakly 2-connected simple digraphs with n unlabeled nodes.

Original entry on oeis.org

7, 129, 7447, 1399245, 853468061, 1774125803324, 12983268697759210, 340896057593147232397, 32512334188761655225275067, 11365639780174824680535568799361, 14668665138188644335253106665956458513, 70315069858161131939222463684374769308619684

Offset: 3

Manfred Scheucher, Mar 09 2023

nonn

M. Kirchweger, M. Scheucher, and S. Szeider, SAT-Based Generation of Planar Graphs, in preparation.

Directed variant of A002218.

Cf. A000273, A003085.

\\ See links in A339645 for combinatorial species functions.
edges(v) = {2*sum(i=2, #v, sum(j=1, i-1, gcd(v[i], v[j]))) + sum(i=1, #v, v[i]-1)}
graphsCycleIndex(n)={my(s=0); forpart(p=n, s+=permcount(p) * 2^edges(p) * sMonomial(p)); s/n!}
graphsSeries(n)={sum(k=0, n, graphsCycleIndex(k)*x^k) + O(x*x^n)}
cycleIndexSeries(n)={my(g=graphsSeries(n), gc=sLog(g), gcr=sPoint(gc)); intformal(x*sSolve( sLog( gcr/(x*sv(1)) ), gcr ), sv(1)) + sSolve(subst(gc, sv(1), 0), gcr)}
{ my(N=15); Vec(-2*x^2 + OgfSeries(cycleIndexSeries(N))) } \\ Andrew Howroyd, Mar 09 2023

Terms a(7) and beyond from Andrew Howroyd, Mar 09 2023

cp's OEIS Frontend

A101389 Number of n-vertex unlabeled oriented graphs without endpoints.

Views

Author

Keywords

Examples

Links

Crossrefs

Programs

PARI

PARI

Extensions

A304485 Regular triangle where T(n,k) is the number of inequivalent colorings of free pure symmetric multifunctions (with empty expressions allowed) with n positions and k leaves.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

PARI

Extensions

A330473 Regular triangle where T(n,k) is the number of non-isomorphic multiset partitions of k-element multiset partitions of multisets of size n.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

PARI

Extensions

A339647 Number of inequivalent leaf colorings of series-reduced planted trees with n leaves using exactly 2 colors.

Views

Author

Keywords

Comments

Examples

Crossrefs

Programs

PARI

A340028 Number of unlabeled 2-connected graphs with n vertices rooted at a pair of noninterchangeable vertices.

Views

Author

Keywords

Links

Crossrefs

Programs

PARI

A340029 Number of unlabeled 2-connected graphs with n vertices rooted at a pair of indistinguishable vertices.

Views

Author

Keywords

Links

Crossrefs

Programs

PARI

A339233 Number of inequivalent colorings of oriented series-parallel networks with n colored elements.

Views

Author

Keywords

Comments

Examples

Crossrefs

Programs

PARI

A339287 Number of inequivalent colorings of unoriented series-parallel networks with n colored elements.

Views

Author

Keywords

Comments

Examples

Crossrefs

Programs

PARI

A339646 Number of inequivalent leaf colorings of series-reduced planted trees with n leaves using at most 2 colors.

Views

Author