cp's OEIS Frontend

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

%I A002861 M1182 N0455 #74 Feb 10 2025 04:38:31
%S A002861 1,2,4,9,20,51,125,329,862,2311,6217,16949,46350,127714,353272,981753,
%T A002861 2737539,7659789,21492286,60466130,170510030,481867683,1364424829,
%U A002861 3870373826,10996890237,31293083540,89173833915,254445242754,726907585652,2079012341822
%N A002861 Number of connected functions (or mapping patterns) on n unlabeled points, or number of rings and branches with n edges.
%D A002861 S. R. Finch, Mathematical Constants, Cambridge, 2003, Section 5.6.6.
%D A002861 R. A. Fisher, Contributions to Mathematical Statistics, Wiley, 1950, 41.399.
%D A002861 N. J. A. Sloane, A Handbook of Integer Sequences, Academic Press, 1973 (includes this sequence).
%D A002861 N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).
%H A002861 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 A002861 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 A002861 C. G. Bower, <a href="/transforms2.html">Transforms (2)</a>
%H A002861 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 A002861 Philippe Flajolet and Robert Sedgewick, <a href="http://algo.inria.fr/flajolet/Publications/books.html">Analytic Combinatorics</a>, 2009; see page 480
%H A002861 R. K. Guy, <a href="/A000081/a000081.pdf">Letter to N. J. A. Sloane, 1988-04-12</a> (annotated scanned copy)
%H A002861 INRIA Algorithms Project, <a href="http://ecs.inria.fr/services/structure?nbr=118">Encyclopedia of Combinatorial Structures 118</a>
%F A002861 CIK transform of A000081.
%F A002861 a(n) = A000081 + A027852 + A029852 + A029853 + A029868 + ... - _Geoffrey Critzer_, Oct 12 2012
%p A002861 spec2861 := [B, {A=Prod(Z,Set(A)), B=Cycle(A)}, unlabeled]; [seq(combstruct[count](spec2861,size=n), n=1..27)];
%t A002861 Needs["Combinatorica`"];
%t A002861 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 A002861 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 A002861 (PARI)
%o A002861 N=66;  A=vector(N+1, j, 1);
%o A002861 for (n=1, N, A[n+1] = 1/n * sum(k=1, n, sumdiv(k, d, d * A[d]) * A[n-k+1] ) );
%o A002861 A000081=concat([0], A);
%o A002861 H(t)=subst(Ser(A000081, 't), 't, t);
%o A002861 x='x+O('x^N);
%o A002861 L=sum(j=1,N, eulerphi(j)/j * log(1/(1-H(x^j))));
%o A002861 Vec(L)
%o A002861 \\ _Joerg Arndt_, Jul 10 2014
%Y A002861 Row sums of A339428.
%Y A002861 Cf. A000081, A001372.
%Y A002861 Cf. A027852, A029852, A029853, A029868.
%K A002861 nonn,nice
%O A002861 1,2
%A A002861 _N. J. A. Sloane_
%E A002861 More terms from _Philippe Flajolet_ and _Paul Zimmermann_, Mar 15 1996