login
This site is supported by donations to The OEIS Foundation.

 

Logo


Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
A001373 Functional digraphs (digraphs of functions on n nodes where every node has outdegree 1 and loops of length 1 are forbidden).
(Formerly M1597 N0623)
11
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 (list; graph; refs; listen; history; text; internal format)
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]

Turner, James; Kautz, William H., 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) / prod(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 Russel in A000083 *) (* 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

Cf. A001372.

Sequence in context: A124124 A052450 A231385 * A284223 A241784 A211995

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

Added more terms, Joerg Arndt, Apr 17 2014

STATUS

approved

Lookup | Welcome | Wiki | Register | Music | Plot 2 | Demos | Index | Browse | More | WebCam
Contribute new seq. or comment | Format | Style Sheet | Transforms | Superseeker | Recent | More pages
The OEIS Community | Maintained by The OEIS Foundation Inc.

License Agreements, Terms of Use, Privacy Policy .

Last modified September 22 00:25 EDT 2017. Contains 292326 sequences.