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

Author

N. J. A. Sloane

Keywords

• nonn
• nice
• easy

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

Crossrefs

Column k=1 of A329228.

Cf. A001372, A002862, A000081.

Programs

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

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

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

Extensions

Sequence extended by Paul Zimmermann

More terms and better description from Christian G. Bower

More terms added by Joerg Arndt, Apr 17 2014