A329228 -id:A329228 - cp's OEIS frontend

A001373 Number of functional digraphs (digraphs of functions on n nodes where every node has outdegree 1 and loops of length 1 are forbidden).

1, 0, 1, 2, 6, 13, 40, 100, 291, 797, 2273, 6389, 18264, 51916, 148666, 425529, 1221900, 3511507, 10111043, 29142941, 84112009, 243000149, 702758065, 2034150215, 5892907566, 17084615940, 49567063847, 143902155133, 418032946298, 1215076634226, 3533715961160, 10282042126394, 29931877173282, 87173224346464, 253989569994664

Offset: 0

N. J. A. Sloane

F. Harary and E. M. Palmer, Graphical Enumeration, Academic Press, NY, 1973, p. 70, Table 3.4.1.
N. J. A. Sloane, A Handbook of Integer Sequences, Academic Press, 1973 (includes this sequence).
N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).

Joerg Arndt, Table of n, a(n) for n = 0..508
Frank Harary, The number of functional digraphs, Mathematische Annalen, 138.3 (1959): 203-210. - From _N. J. A. Sloane_, Apr 08 2014
Ronald C. Read, Note on number of functional digraphs, Math. Ann., vol. 143 (1961), pp. 109-111.
N. J. A. Sloane, Transforms
L. Travis, Graphical Enumeration: A Species-Theoretic Approach, arXiv:math/9811127 [math.CO], 1998.
James Turner and William H. Kautz, A survey of progress in graph theory in the Soviet Union, SIAM Rev. 12 1970 suppl. iv+68 pp. MR0268074 (42 #2973). See p. 20 concerning calculation of a(n) for n <= 25 by Zakrevskii in 1961. - _N. J. A. Sloane_, Apr 08 2014

Column k=1 of A329228.

Cf. A001372, A002862, A000081.

Needs["Combinatorica`];
nn=30;s[n_,k_]:=s[n,k]=a[n+1-k]+If[n<2 k,0,s[n-k,k]];a[1]=1;a[n_]:=a[n]=Sum[a[i] s[n-1,i] i,{i,1,n-1}]/(n-1);rt=Table[a[i],{i,1,nn}];c=Drop[Apply[Plus,Table[Take[CoefficientList[CycleIndex[CyclicGroup[n],s]/.Table[s[j]->Table[Sum[rt[[i]] x^(k*i),{i,1,nn}],{k,1,nn}][[j]],{j,1,nn}],x],nn],{n,2,30}]],1];CoefficientList[Series[Product[1/(1-x^i)^c[[i]],{i,1,nn-1}],{x,0,nn}],x]  (* after code given by Robert A. Russell in A000081 *) (* Geoffrey Critzer, Oct 12 2012 *)

N=66;  A=vector(N+1, j, 1);
for (n=1, N, A[n+1] = 1/n * sum(k=1,n, sumdiv(k,d, d*A[d]) * A[n-k+1] ) );
v0000081=concat([0], A); \\ A000081
x='x+O('x^N);  T = Ser(v0000081);
gf = x/T  / prod(n=1,N, 1 - subst(T,'x,'x^n) );
v001373 = Vec(gf) \\ Joerg Arndt, Apr 17 2014

Euler transform of A002862.

G.f.: (x/T(x)) / Product_{n>=1} ( 1 - T(x^n) ) where T(x) is the g.f. of A000081, see the Read reference and the PARI code. - Joerg Arndt, Apr 17 2014

Sequence extended by Paul Zimmermann
More terms and better description from Christian G. Bower
More terms added by Joerg Arndt, Apr 17 2014

A350910 Triangle read by rows: T(n,k) is the number of k-regular digraphs on n unlabeled nodes, k = 0..n-1.

Original entry on oeis.org

1, 1, 1, 1, 1, 1, 1, 2, 2, 1, 1, 2, 5, 2, 1, 1, 4, 23, 23, 4, 1, 1, 4, 92, 415, 92, 4, 1, 1, 7, 624, 19041, 19041, 624, 7, 1, 1, 8, 5021, 1104045, 6510087, 1104045, 5021, 8, 1, 1, 12, 47034, 79818336, 2983458766, 2983458766, 79818336, 47034, 12, 1

Offset: 1

Andrew Howroyd, Jan 29 2022

			Triangle begins:
  1;
  1, 1;
  1, 1,   1;
  1, 2,   2,     1;
  1, 2,   5,     2,     1;
  1, 4,  23,    23,     4,   1;
  1, 4,  92,   415,    92,   4, 1;
  1, 7, 624, 19041, 19041, 624, 7, 1;
  ...

Columns k=0..6 are A000012, A002865, A219889, A219890, A219891, A219892, A219893.
Row sums are A350911.
Cf. A051031 (graphs), A329228 (semi-regular), A350912.

A129524 Number of unlabeled digraphs on n vertices such that every vertex has outdegree 2.

Original entry on oeis.org

0, 0, 1, 6, 79, 1499, 35317, 967255, 29949217, 1033242585, 39323062014, 1637375262965, 74075329383599, 3619112881630497, 189953824713590782, 10661151595417930874, 637230479685691806302, 40415532825383300892418, 2711124591869919503655096

Offset: 1

Vladeta Jovovic, May 29 2007

nonn

Andrew Howroyd, Table of n, a(n) for n = 1..50
L. Travis, [math/9811127] Graphical Enumeration: A Species-Theoretic Approach

Column k=2 of A329228.

Cf. A001373, A185193, A185194, A185303.

Terms a(10) and beyond from Andrew Howroyd, Nov 08 2019

A185193 Number of unlabeled digraphs on n vertices such that every vertex has outdegree 3.

Original entry on oeis.org

0, 0, 0, 1, 13, 1499, 257290, 56150820, 14971125930, 4829990898461, 1864386642498918, 851204815909786099, 454661054439318678263, 281270600132956104641972, 199701092658236514672384967, 161392692052798327047616107614, 147373164027242947672475065773269

Offset: 1

Nathaniel Johnston, Feb 08 2012

nonn

Andrew Howroyd, Table of n, a(n) for n = 1..50
L. Travis, [math/9811127] Graphical Enumeration: A Species-Theoretic Approach

Column k=3 of A329228.

Cf. A001373, A129524, A185194, A185303.

Terms a(10) and beyond from Andrew Howroyd, Nov 08 2019

A185194 Number of unlabeled digraphs on n vertices such that every vertex has outdegree 4.

Original entry on oeis.org

0, 0, 0, 0, 1, 40, 35317, 56150820, 111359017198, 278086517599356, 877760741062694898, 3482578978170418753715, 17204168691253789080138981, 104690934973509839187285618311, 776311587313178356520412354767734, 6942595716239018207126337605515965388

Offset: 1

Nathaniel Johnston, Feb 08 2012

nonn

Andrew Howroyd, Table of n, a(n) for n = 1..50
L. Travis, [math/9811127] Graphical Enumeration: A Species-Theoretic Approach

Column k=4 of A329228.

Cf. A001373, A129524, A185193, A185303.

Terms a(10) and beyond from Andrew Howroyd, Nov 08 2019

A185303 Number of unlabeled digraphs on n vertices such that every vertex has outdegree 5.

Original entry on oeis.org

0, 0, 0, 0, 0, 1, 100, 967255, 14971125930, 278086517599356, 6521004095675547914, 197419530111112377546537, 7747427934648623352166753715, 392370903258277676503800999871543, 25436929780226775791085690703723141426, 2090584629532654146005764252197925046719651

Offset: 1

Nathaniel Johnston, Feb 08 2012

nonn

Andrew Howroyd, Table of n, a(n) for n = 1..50
L. Travis, [math/9811127] Graphical Enumeration: A Species-Theoretic Approach

Column k=5 of A329228.

Cf. A001373, A129524, A185193, A185194.

Terms a(10) and beyond from Andrew Howroyd, Nov 08 2019

A259471 Triangle read by rows: T(n,k) is the number of semi-regular relations on n nodes with each node having out-degree k (0 <= k <= n).

Original entry on oeis.org

1, 1, 1, 1, 3, 1, 1, 7, 7, 1, 1, 19, 66, 19, 1, 1, 47, 916, 916, 47, 1, 1, 130, 16816, 91212, 16816, 130, 1, 1, 343, 373630, 12888450, 12888450, 373630, 343, 1, 1, 951, 9727010, 2411213698, 14334255100, 2411213698, 9727010, 951, 1, 1, 2615, 289374391, 575737451509, 22080097881081, 22080097881081, 575737451509, 289374391, 2615, 1

Offset: 0

N. J. A. Sloane, Jul 03 2015

			Triangle begins:
  1;
  1,   1;
  1,   3,     1;
  1,   7,     7,     1;
  1,  19,    66,    19,     1;
  1,  47,   916,   916,    47,   1;
  1, 130, 16816, 91212, 16816, 130, 1;
  ...

Andrew Howroyd, Table of n, a(n) for n = 0..1325
S. A. Choudum, K. R. Parthasarathy, Semi-regular relations and digraphs, Nederl. Akad. Wetensch. Proc. Ser. A. {75}=Indag. Math. 34 (1972), 326-334.

Columns k=1..3 are A001372, A003286, A005535.

Cf. A329228.

permcount[v_] := Module[{m = 1, s = 0, k = 0, t}, For[i = 1, i <= Length[v], i++, t = v[[i]]; k = If[i > 1 && t == v[[i - 1]], k + 1, 1]; m *= t*k; s += t]; s!/m];
edges[v_, k_] := Product[SeriesCoefficient[Product[g = GCD[v[[i]], v[[j]] ]; (1 + x^(v[[j]]/g) + O[x]^(k + 1))^g, {j, 1, Length[v]}], {x, 0, k}], {i, 1, Length[v]}];
T[n_, k_] := Module[{s = 0}, Do[s += permcount[p]*edges[p, k], {p, IntegerPartitions[n]}]; s/n!];
Table[T[n, k], {n, 0, 9}, {k, 0, n}] // Flatten (* Jean-François Alcover, Jan 08 2021, after Andrew Howroyd *)

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,k)={prod(i=1, #v, polcoef(prod(j=1, #v, my(g=gcd(v[i],v[j])); (1 + x^(v[j]/g) + O(x*x^k))^g), k))}
T(n,k)={my(s=0); forpart(p=n, s+=permcount(p)*edges(p,k)); s/n!} \\ Andrew Howroyd, Sep 13 2020

T(n,k) = T(n,n-k). - Andrew Howroyd, Sep 13 2020

Terms a(28) and beyond from Andrew Howroyd, Sep 13 2020

A329234 Number of digraphs on n unlabled vertices such that every vertex has the same outdegree.

Original entry on oeis.org

1, 1, 2, 4, 14, 107, 3080, 328126, 114236734, 141361169088, 565835083485352, 8280254429732072354, 401805920591472162735162, 73001963040583041357650757758, 44826822610575086782059677501403310, 104876792026574880566541471182849498480154, 841219618683014295050378892027503163229521608514

Offset: 0

Andrew Howroyd, Nov 08 2019

nonn

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

Row sums of A329228.

Cf. A000273.

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}
E(v, x) = {my(r=1/(1-x)); for(i=1, #v, r=serconvol(r, prod(j=1, #v, my(g=gcd(v[i], v[j])); (1 + x^(v[j]/g))^g)/(1 + x))); r}
a(n)={if(n<1, n==0, my(s=0); forpart(p=n, s+=permcount(p)*E(p, x+O(x^n))); vecsum(Vec(s))/n!)}

cp's OEIS Frontend

A001373 Number of functional digraphs (digraphs of functions on n nodes where every node has outdegree 1 and loops of length 1 are forbidden).

Views

Author

Keywords

References

Links

Crossrefs

Programs

Mathematica

PARI

Formula

Extensions

A350910 Triangle read by rows: T(n,k) is the number of k-regular digraphs on n unlabeled nodes, k = 0..n-1.

Views

Author

Keywords

Examples

Crossrefs

A129524 Number of unlabeled digraphs on n vertices such that every vertex has outdegree 2.

Views

Author

Keywords

Links

Crossrefs

Extensions

A185193 Number of unlabeled digraphs on n vertices such that every vertex has outdegree 3.

Views

Author

Keywords

Links

Crossrefs

Extensions

A185194 Number of unlabeled digraphs on n vertices such that every vertex has outdegree 4.

Views

Author

Keywords

Links

Crossrefs

Extensions

A185303 Number of unlabeled digraphs on n vertices such that every vertex has outdegree 5.

Views

Author

Keywords

Links

Crossrefs

Extensions

A259471 Triangle read by rows: T(n,k) is the number of semi-regular relations on n nodes with each node having out-degree k (0 <= k <= n).

Views

Author

Keywords

Examples

Links

Crossrefs

Programs

Mathematica

PARI

Formula

Extensions

A329234 Number of digraphs on n unlabled vertices such that every vertex has the same outdegree.

Views

Author

Keywords

Links

Crossrefs

Programs

PARI