A002861 - OEIS

%I M1182 N0455 #72 Jun 10 2024 15:34:45

%S 1,2,4,9,20,51,125,329,862,2311,6217,16949,46350,127714,353272,981753,

%T 2737539,7659789,21492286,60466130,170510030,481867683,1364424829,

%U 3870373826,10996890237,31293083540,89173833915,254445242754,726907585652,2079012341822

%N Number of connected functions (or mapping patterns) on n unlabeled points, or number of rings and branches with n edges.

%C A000081 + A027852 + A029852 + A029853 + A029868 + ... - _Geoffrey Critzer_, Oct 12 2012

%D S. R. Finch, Mathematical Constants, Cambridge, 2003, Section 5.6.6.

%D R. A. Fisher, Contributions to Mathematical Statistics, Wiley, 1950, 41.399.

%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 Alois P. Heinz, <a href="/A002861/b002861.txt">Table of n, a(n) for n = 1..1000</a> (first 500 terms from C. G. Bower)

%H A. L. Agore, A. Chirvasitu, and G. Militaru, <a href="https://arxiv.org/abs/2303.06700">The set-theoretic Yang-Baxter equation, Kimura semigroups and functional graphs</a>, arXiv:2303.06700 [math.QA], 2023.

%H C. G. Bower, <a href="/transforms2.html">Transforms (2)</a>

%H Oscar Defrain, Antonio E. Porreca and Ekaterina Timofeeva, <a href="https://doi.org/10.1016/j.dam.2024.05.030">Polynomial-delay generation of functional digraphs up to isomorphism</a>, Disc. Appl. Math., vol 357 (2024), pp. 24-33.

%H Philippe Flajolet and Robert Sedgewick, <a href="http://algo.inria.fr/flajolet/Publications/books.html">Analytic Combinatorics</a>, 2009; see page 480

%H R. K. Guy, <a href="/A000081/a000081.pdf">Letter to N. J. A. Sloane, 1988-04-12</a> (annotated scanned copy)

%H INRIA Algorithms Project, <a href="http://ecs.inria.fr/services/structure?nbr=118">Encyclopedia of Combinatorial Structures 118</a>

%F CIK transform of A000081.

%p spec2861 := [B, {A=Prod(Z,Set(A)), B=Cycle(A)}, unlabeled]; [seq(combstruct[count](spec2861,size=n), n=1..27)];

%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}]; Apply[Plus, Table[Take[CoefficientList[CycleIndex[CyclicGroup[n], s] /. Table[s[j] -> Table[Sum[rt[[i]] x^(k * i), {i, nn}], {k, 1, nn}][[j]], {j, nn}], x], nn], {n, 30}]]  (* _Geoffrey Critzer_, Oct 12 2012, after code given by _Robert A. Russell_ in A000081 *)

%t M = 66; A = Table[1, {M + 1}]; For[n = 1, n <= M, n++, A[[n + 1]] = 1/n * Sum[Sum[d * A[[d]], {d, Divisors[k]}] * A[[n - k + 1]], {k, n}]]; A81 = {0} ~ Join ~ A; H[t_] = A81.t^Range[0, Length[A81] - 1]; L = Sum[EulerPhi[j]/j * Log[1/(1 - H[x^j])], {j, M}] + O[x]^M; CoefficientList[L, x] // Rest (* _Jean-François Alcover_, Dec 28 2019, after _Joerg Arndt_ *)

%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 A000081=concat([0], A);

%o H(t)=subst(Ser(A000081, 't), 't, t);

%o x='x+O('x^N);

%o L=sum(j=1,N, eulerphi(j)/j * log(1/(1-H(x^j))));

%o Vec(L)

%o \\ _Joerg Arndt_, Jul 10 2014

%Y Row sums of A339428.

%Y Cf. A000081, A001372.

%Y Cf. A027852, A029852, A029853, A029868.

%K nonn,nice

%O 1,2

%A _N. J. A. Sloane_

%E More terms from _Philippe Flajolet_ and _Paul Zimmermann_, Mar 15 1996