A144163 -id:A144163 - cp's OEIS frontend

A144164 Number of simple graphs on n labeled nodes, where each maximally connected subgraph is either a tree or a cycle, also row sums of A144163, A215861.

1, 1, 2, 8, 45, 338, 3304, 40485, 602075, 10576466, 214622874, 4941785261, 127282939615, 3625467047196, 113140481638088, 3838679644895477, 140681280613912089, 5538276165405744140, 233086092164091031114, 10443453353262112373541, 496313160155209940833001

Offset: 0

Alois P. Heinz, Sep 12 2008

nonn

			a(3) = 8, because there are 8 simple graphs on 3 labeled nodes, where each maximally connected subgraph is either a tree or a cycle, with edge-counts 0(1), 1(3), 2(3), 3(1):
.1.2. .1-2. .1.2. .1.2. .1-2. .1.2. .1-2. .1-2.
..... ..... ../.. .|... ../.. .|/.. .|... .|/..
.3... .3... .3... .3... .3... .3... .3... .3...

Alois P. Heinz, Table of n, a(n) for n = 0..140
Index entries for sequences related to trees

Row sums of triangles A144163, A215861.
The unlabeled version is A215978.
Cf. A138464, A144161, A007318, A000142.

f:= proc(n,k) option remember; local j; if k=0 then 1 elif k<0 or n<=k then 0 elif k=n-1 then n^(n-2) else add(binomial(n-1,j) *f(j+1,j) *f(n-1-j,k-j), j=0..k) fi end:
c:= proc(n,k) option remember; local i,j; if k=0 then 1 elif k<0 or n add(T(n,k), k=0..n):
seq(a(n), n=0..25);

f[n_, k_] := f[n, k] = Module[{j}, Which[k == 0, 1, k<0 || n <= k, 0, k == n-1, n^(n-2), True, Sum[Binomial[n-1, j]*f[j+1, j]*f[n-1-j, k-j], {j, 0, k}]]]; c[n_, k_] := c[n, k] = Module[{i, j}, If[k == 0, 1, If[k<0 || nJean-François Alcover, Mar 05 2014, after Alois P. Heinz *)

from sympy.core.cache import cacheit
from sympy import binomial, prod
@cacheit
def f(n, k): return 1 if k==0 else 0 if k<0 or n<=k else n**(n - 2) if k == n - 1 else sum(binomial(n - 1, j)*f(j + 1, j)*f(n - 1 - j, k - j) for j in range(k + 1))
@cacheit
def c(n, k): return 1 if k==0 else 0 if k<0 or nIndranil Ghosh, Aug 07 2017

a(n) = Sum_{k=0..n} A144163(n,k).

a(n) ~ c * n^(n-2), where c = 1.66789780037... . - Vaclav Kotesovec, Sep 08 2014

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.

Original entry on oeis.org

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

Offset: 0

N. J. A. Sloane

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

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.

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.

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

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

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. *)

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 */

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))

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

cp's OEIS Frontend

A144164 Number of simple graphs on n labeled nodes, where each maximally connected subgraph is either a tree or a cycle, also row sums of A144163, A215861.

Views

Author

Keywords

Examples

Links

Crossrefs

Programs

Maple

Mathematica

Python

Formula