A001205 Number of clouds with n points; number of undirected 2-regular labeled graphs; or number of n X n symmetric matrices with (0,1) entries, trace 0 and all row sums 2.

1, 0, 0, 1, 3, 12, 70, 465, 3507, 30016, 286884, 3026655, 34944085, 438263364, 5933502822, 86248951243, 1339751921865, 22148051088480, 388246725873208, 7193423109763089, 140462355821628771, 2883013994348484940

Offset: 0

Author

N. J. A. Sloane

Keywords

• nonn
• easy
• nice

Comments

a(n) is the number of ways of covering K_n with cycles of length >= 3. Also number of 'frames' on n lines: given n lines in general position (none parallel and no three concurrent), a frame is a subset of n of the e C(n,2) points of intersection such that no three points are on the same line. - Mitch Harris, Jul 06 2006

References

• Miklos Bona, editor, Handbook of Enumerative Combinatorics, CRC Press, 2015, p. 410-411.
• L. Comtet, Advanced Combinatorics, Reidel, 1974, p. 276 and 279.
• S. R. Finch, Mathematical Constants, Cambridge, 2003, Section 5.6.7.
• Ph. Flajolet, Singular combinatorics, pp. 561-571, Proc. Internat. Congr. Math., Beijing 2002, Higher Education Press, Beijing, 2002, Vol III.
• I. P. Goulden and D. M. Jackson, Combinatorial Enumeration, John Wiley and Sons, N.Y., 1983, ex. 3.3.6b, 3.3.34.
• 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).
• R. P. Stanley, Enumerative Combinatorics, Cambridge, Vol. 2, 1999; see Example 5.2.8. Also problems 5.23 and 5.15(a), case k=3.
• Z. Tan and S. Gao, Enumeration of (0,1)-Symmetric Matrices, submitted [From Shanzhen Gao, Jun 05 2009] [apparently unpublished as of 2016]
• H. S. Wilf, Generatingfunctionology, Academic Press, NY, 1990, p. 77, Eq. 3.9.1.
• W. A. Whitworth, Choice and Chance, Bell, 1901, p. 269, ex. 160.

Links

• T. D. Noe, Table of n, a(n) for n=0..100
• Editorial note, Robinson's constant, Amer. Math. Monthly, 59 (1952), 296-297.
• Ph. Flajolet, Singular combinatorics, arXiv:math/0304465 [math.CO], 2003.
• Ph. Flajolet and A. Odlyzko, Singularity analysis of generating functions, [Research Report] RR-0826, INRIA. 1988.
• Atabey Kaygun, Enumerating Labeled Graphs that Realize a Fixed Degree Sequence, arXiv:2101.02299 [math.CO], 2021.
• Rui-Li Liu and Feng-Zhen Zhao, New Sufficient Conditions for Log-Balancedness, With Applications to Combinatorial Sequences, J. Int. Seq., Vol. 21 (2018), Article 18.5.7.
• H. Richter, Analyzing coevolutionary games with dynamic fitness landscapes, arXiv preprint arXiv:1603.06374 [q-bio.PE], 2016.
• R. Robinson, A new absolute geometric constant?, Amer. Math. Monthly, 58 (1951), 462-469.
• Weiping Wang, Tianming Wang, An automatic approach to the generating functions for some special sequences, Ars. Comb. 116 (2018) 263, Example 4.2
• H. S. Wilf, Generatingfunctionology, 2nd edn., Academic Press, NY, 1994, p. 86, Eq. 3.9.1.

Crossrefs

Cf. A000985, A000986, A002137. A diagonal of A059441 and A144163.

Programs

Maple

a := n -> (-1)^n*n!*add((3/4)^k*binomial(-1/2, n-k)*hypergeom([1/2,-k], [1/2-n+k], 1/3)/ k!, k=0..n): seq(simplify(a(n)), n=0..21); # Peter Luschny, Aug 26 2017

Mathematica

m = 21; CoefficientList[ Series[ Exp[-x/2 - x^2/4] / Sqrt[1-x], {x, 0, m}], x]*Table[n!, {n, 0, m}] (* Jean-François Alcover, Jun 21 2011, after e.g.f. *)

Maxima

a(n):=sum(sum(binomial(k,i)*binomial(i-1/2,n-k)*(3^(k-i)*n!)/(4^k*k!)*(-1)^(n-i),i,0,k),k,0,n);
makelist(a(n),n,0,12); /* Emanuele Munarini, Aug 25 2017 */

PARI

a(n)=if(n<0,0,n!*polcoeff(exp(-x/2-x^2/4+x*O(x^n))/sqrt(1-x+x*O(x^n)),n))

Formula

a(n) ~ n!*exp(-3/4)/sqrt(Pi*n).

E.g.f.: exp(-x/2-x^2/4)/sqrt(1-x).

D-finite with recurrence a(n+1) = n*(a(n)+a(n-2)*(n-1)/2).

1/4^n * Sum_{b=0..floor(n/2)} Sum_{g=0..n-2*b} (-1)^(b+g) * 2^(2b+g) * n! * (2n-4b-2g)! / (b! * g! * (n-2b-g)!^2). - Shanzhen Gao, Jun 05 2009

a(n) = (-1)^n*n!*Sum_{k=0..n}(3/4)^k*binomial(-1/2, n - k)*hypergeom([1/2, -k], [1/2 - n + k], 1/3)/ k!. - Peter Luschny, Aug 26 2017