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

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,4

References

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).

Links

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

Formula

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

Mathematica

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 *)

Prog

(PARI)
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

Crossrefs

Column k=1 of A329228.

Cf. A001372, A002862, A000081.

Sequence in context: A124124 A052450 A231385 * A320804 A284223 A241784

Adjacent sequences: A001370 A001371 A001372 * A001374 A001375 A001376

Keyword

nonn,nice,easy

Author

N. J. A. Sloane

Extensions

Sequence extended by Paul Zimmermann

More terms and better description from Christian G. Bower

More terms added by Joerg Arndt, Apr 17 2014

Status

approved