|
%I M1597 N0623 #60 Jun 17 2022 14:46:00
%S 1,0,1,2,6,13,40,100,291,797,2273,6389,18264,51916,148666,425529,
%T 1221900,3511507,10111043,29142941,84112009,243000149,702758065,
%U 2034150215,5892907566,17084615940,49567063847,143902155133,418032946298,1215076634226,3533715961160,10282042126394,29931877173282,87173224346464,253989569994664
%N Number of functional digraphs (digraphs of functions on n nodes where every node has outdegree 1 and loops of length 1 are forbidden).
%D F. Harary and E. M. Palmer, Graphical Enumeration, Academic Press, NY, 1973, p. 70, Table 3.4.1.
%D N. J. A. Sloane, A Handbook of Integer Sequences, Academic Press, 1973 (includes this sequence).
%D N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).
%H Joerg Arndt, <a href="/A001373/b001373.txt">Table of n, a(n) for n = 0..508</a>
%H Frank Harary, <a href="http://dx.doi.org/10.1007/BF01342903">The number of functional digraphs</a>, Mathematische Annalen, 138.3 (1959): 203-210. - From _N. J. A. Sloane_, Apr 08 2014
%H Ronald C. Read, <a href="http://dx.doi.org/10.1007/BF01342974">Note on number of functional digraphs</a>, Math. Ann., vol. 143 (1961), pp. 109-111.
%H N. J. A. Sloane, <a href="/transforms.txt">Transforms</a>
%H L. Travis, <a href="https://arxiv.org/abs/math/9811127">Graphical Enumeration: A Species-Theoretic Approach</a>, arXiv:math/9811127 [math.CO], 1998.
%H James Turner and William H. Kautz, <a href="http://dx.doi.org/10.1137/1012125">A survey of progress in graph theory in the Soviet Union</a>, 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
%F Euler transform of A002862.
%F 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
%t Needs["Combinatorica`];
%t 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 *)
%o (PARI)
%o N=66; A=vector(N+1, j, 1);
%o for (n=1, N, A[n+1] = 1/n * sum(k=1,n, sumdiv(k,d, d*A[d]) * A[n-k+1] ) );
%o v0000081=concat([0], A); \\ A000081
%o x='x+O('x^N); T = Ser(v0000081);
%o gf = x/T / prod(n=1,N, 1 - subst(T,'x,'x^n) );
%o v001373 = Vec(gf) \\ _Joerg Arndt_, Apr 17 2014
%Y Column k=1 of A329228.
%Y Cf. A001372, A002862, A000081.
%K nonn,nice,easy
%O 0,4
%A _N. J. A. Sloane_
%E Sequence extended by _Paul Zimmermann_
%E More terms and better description from _Christian G. Bower_
%E More terms added by _Joerg Arndt_, Apr 17 2014
|
