A059167 -id:A059167 - cp's OEIS frontend

A006125 a(n) = 2^(n*(n-1)/2).

1, 1, 2, 8, 64, 1024, 32768, 2097152, 268435456, 68719476736, 35184372088832, 36028797018963968, 73786976294838206464, 302231454903657293676544, 2475880078570760549798248448, 40564819207303340847894502572032, 1329227995784915872903807060280344576

Offset: 0

N. J. A. Sloane

Number of graphs on n labeled nodes; also number of outcomes of labeled n-team round-robin tournaments.
Number of perfect matchings of order n Aztec diamond. [see Speyer]
Number of Gelfand-Zeitlin patterns with bottom row [1,2,3,...,n]. [Zeilberger]
For n >= 1 a(n) is the size of the Sylow 2-subgroup of the Chevalley group A_n(2) (sequence A002884). - Ahmed Fares (ahmedfares(AT)my-deja.com), Apr 30 2001
From James Propp: (Start)
a(n) is the number of ways to tile the region
           o-----o
           |.....|
        o--o.....o--o
        |...........|
     o--o...........o--o
     |.................|
  o--o.................o--o
  |.......................|
  |.......................|
  |.......................|
  o--o.................o--o
     |.................|
     o--o...........o--o
        |...........|
        o--o.....o--o
           |.....|
           o-----o
(top-to-bottom distance = 2n) with dominoes like either of
  o--o      o-----o
  |..|  or  |.....|
  |..|      o-----o
  |..|
  o--o
(End)
The number of domino tilings in A006253, A004003, A006125 is the number of perfect matchings in the relevant graphs. There are results of Jockusch and Ciucu that if a planar graph has a rotational symmetry then the number of perfect matchings is a square or twice a square - this applies to these 3 sequences. - Dan Fux (dan.fux(AT)OpenGaia.com or danfux(AT)OpenGaia.com), Apr 12 2001
Let M_n denotes the n X n matrix with M_n(i,j)=binomial(2i,j); then det(M_n)=a(n+1). - Benoit Cloitre, Apr 21 2002
Smallest power of 2 which can be expressed as the product of n distinct numbers (powers of 2), e.g., a(4) = 1024 = 2*4*8*16. Also smallest number which can be expressed as the product of n distinct powers. - Amarnath Murthy, Nov 10 2002
The number of binary relations that are both reflexive and symmetric on an n-element set. - Justin Witt (justinmwitt(AT)gmail.com), Jul 12 2005
The number of symmetric binary relations on an (n-1)-element set. - Peter Kagey, Feb 13 2021
To win a game, you must flip n+1 heads in a row, where n is the total number of tails flipped so far. Then the probability of winning for the first time after n tails is A005329 / A006125. The probability of having won before n+1 tails is A114604 / A006125. - Joshua Zucker, Dec 14 2005
a(n) = A126883(n-1)+1. - Zerinvary Lajos, Jun 12 2007
Equals right border of triangle A158474 (unsigned). - Gary W. Adamson, Mar 20 2009
a(n-1) is the number of simple labeled graphs on n nodes such that every node has even degree. - Geoffrey Critzer, Oct 21 2011
a(n+1) is the number of symmetric binary matrices of size n X n. - Nathan J. Russell, Aug 30 2014
Let T_n be the n X n matrix with T_n(i,j) = binomial(2i + j - 3, j-1); then det(T_n) = a(n). - Tony Foster III, Aug 30 2018
k^(n*(n-1)/2) is the determinant of n X n matrix T_(i,j) = binomial(k*i + j - 3, j-1), in this case k=2. - Tony Foster III, May 12 2019
Let B_n be the n+1 X n+1 matrix with B_n(i, j) = Sum_{m=max(0, j-i)..min(j, n-i)} (binomial(i, j-m) * binomial(n-i, m) * (-1)^m), 0<=i,j<=n. Then det B_n = a(n+1). Also, deleting the first row and any column from B_n results in a matrix with determinant a(n). The matrices B_n have the following property: B_n * [x^n, x^(n-1) * y, x^(n-2) * y^2, ..., y^n]^T = [(x-y)^n, (x-y)^(n-1) * (x+y), (x-y)^(n-2) * (x+y)^2, ..., (x+y)^n]^T. - Nicolas Nagel, Jul 02 2019
a(n) is the number of positive definite (-1,1)-matrices of size n X n. - Eric W. Weisstein, Jan 03 2021
a(n) is the number of binary relations on a labeled n-set that are both total and antisymmetric. - José E. Solsona, Feb 05 2023

			From _Gus Wiseman_, Feb 11 2021: (Start)
This sequence counts labeled graphs on n vertices. For example, the a(0) = 1 through a(2) = 8 graph edge sets are:
  {}  {}  {}    {}
          {12}  {12}
                {13}
                {23}
                {12,13}
                {12,23}
                {13,23}
                {12,13,23}
This sequence also counts labeled graphs with loops on n - 1 vertices. For example, the a(1) = 1 through a(3) = 8 edge sets are the following. A loop is represented as an edge with two equal vertices.
  {}  {}    {}
      {11}  {11}
            {12}
            {22}
            {11,12}
            {11,22}
            {12,22}
            {11,12,22}
(End)

Miklos Bona, editor, Handbook of Enumerative Combinatorics, CRC Press, 2015, page 547 (Fig. 9.7), 573.
G. Everest, A. van der Poorten, I. Shparlinski, and T. Ward, Recurrence Sequences, Amer. Math. Soc., 2003; p. 178.
J. L. Gross and J. Yellen, eds., Handbook of Graph Theory, CRC Press, 2004; p. 517.
F. Harary, Graph Theory. Addison-Wesley, Reading, MA, 1969, p. 178.
F. Harary and E. M. Palmer, Graphical Enumeration, Academic Press, NY, 1973, p. 3, Eq. (1.1.2).
J. Propp, Enumeration of matchings: problems and progress, in: New perspectives in geometric combinatorics, L. Billera et al., eds., Mathematical Sciences Research Institute series, vol. 38, Cambridge University Press, 1999.
N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).

N. J. A. Sloane, Table of n, a(n) for n = 0..50
F. Ardila and R. P. Stanley, Tilings, arXiv:math/0501170 [math.CO], 2005.
Paul Barry and Aoife Hennessy, Generalized Narayana Polynomials, Riordan Arrays, and Lattice Paths, Journal of Integer Sequences, Vol. 15, 2012, #12.4.8. - From _N. J. A. Sloane_, Oct 08 2012
Anders Björner and Richard P. Stanley, A combinatorial miscellany, 2010.
Tobias Boege and Thomas Kahle, Construction Methods for Gaussoids, arXiv:1902.11260 [math.CO], 2019.
Taylor Brysiewicz and Fulvio Gesmundo, The Degree of Stiefel Manifolds, arXiv:1909.10085 [math.AG], 2019.
Peter J. Cameron, Sequences realized by oligomorphic permutation groups, J. Integ. Seqs. Vol. 3 (2000), #00.1.5.
Mihai Ciucu, Perfect matchings of cellular graphs, J. Algebraic Combin., 5 (1996) 87-103.
Mihai Ciucu, Enumeration of perfect matchings in graphs with reflective symmetry, J. Combin. Theory Ser. A 77 (1997), no. 1, 67-97.
Thierry de la Rue and Élise Janvresse, Pavages aléatoires par touillage de dominos, Images des Mathématiques, CNRS, 2023. In French.
Noam Elkies, Greg Kuperberg, Michael Larsen, and James Propp, Alternating sign matrices and domino tilings. Part I, Journal of Algebraic Combinatorics 1-2, 111-132 (1992).
Noam Elkies, Greg Kuperberg, Michael Larsen, and James Propp, Alternating sign matrices and domino tilings. Part II, Journal of Algebraic Combinatorics 1-3, 219-234 (1992).
Sen-Peng Eu and Tung-Shan Fu, A simple proof of the Aztec diamond theorem, arXiv:math/0412041 [math.CO], 2004.
D. Grensing, I. Carlsen, and H.-Chr. Zapp, Some exact results for the dimer problem on plane lattices with non-standard boundaries, Phil. Mag. A, 41:5 (1980), 777-781.
Harald Helfgott and Ira M. Gessel, Enumeration of tilings of diamonds and hexagons with defects, arXiv:math/9810143 [math.CO], 1998.
Aoife Hennessy, A Study of Riordan Arrays with Applications to Continued Fractions, Orthogonal Polynomials and Lattice Paths, Ph. D. Thesis, Waterford Institute of Technology, Oct. 2011.
Pakawut Jiradilok, Some Combinatorial Formulas Related to Diagonal Ramsey Numbers, arXiv:2404.02714 [math.CO], 2024. See p. 19.
William Jockusch, Perfect matchings and perfect squares J. Combin. Theory Ser. A 67 (1994), no. 1, 100-115.
Eric H. Kuo, Applications of graphical condensation for enumerating matchings and tilings, Theoretical Computer Science, Vol. 319, No. 1-3 (2004), pp. 29-57, arXiv preprint, arXiv:math/0304090 [math.CO], 2003.
C. L. Mallows & N. J. A. Sloane, Emails, May 1991
W. H. Mills, David P. Robbins, and Howard Rumsey, Jr., Alternating sign matrices and descending plane partitions, J. Combin. Theory Ser. A 34 (1983), 340-359.
Götz Pfeiffer, Counting Transitive Relations, Journal of Integer Sequences, Vol. 7 (2004), Article 04.3.2.
James Propp, Enumeration of matchings: problems and progress, in L. J. Billera et al. (eds.), New Perspectives in Algebraic Combinatorics
James Propp, Enumeration of matchings: problems and progress, arXiv:math/9904150 [math.CO], 1999.
James Propp, Lessons I learned from Richard Stanley, arXiv preprint [math.CO], 2015.
James Propp and R. P. Stanley, Domino tilings with barriers, arXiv:math/9801067 [math.CO], 1998.
Steven S. Skiena, Generating graphs.
David E. Speyer, Perfect matchings and the octahedron recurrence, Journal of Algebraic Combinatorics, Vol. 25, No. 3 (2007), pp. 309-348, arXiv preprint, arXiv:math/0402452 [math.CO], 2004.
Jan Tóth and Ondřej Kuželka, Complexity of Weighted First-Order Model Counting in the Two-Variable Fragment with Counting Quantifiers: A Bound to Beat, arXiv:2404.12905 [cs.LO], 2024. See p. 24.
Herman Tulleken, Polyominoes 2.2: How they fit together, (2019).
Eric Weisstein's World of Mathematics, Connected Graph.
Eric Weisstein's World of Mathematics, Labeled Graph.
Eric Weisstein's World of Mathematics, Symmetric Matrix.
Doron Zeilberger, Dave Robbins's Art of Guessing, Adv. in Appl. Math. 34 (2005), 939-954.
Index entries for sequences related to dominoes

Cf. A000568 for the unlabeled analog, A053763, A006253, A004003.
Cf. A001187 (connected labeled graphs).
Cf. A095340, A103904, A005329, A114604, A299998.
Cf. A158474. - Gary W. Adamson, Mar 20 2009
Cf. A136652 (log). - Paul D. Hanna, Dec 04 2009
The unlabeled version is A000088, or A002494 without isolated vertices.
The directed version is A002416.
The covering case is A006129.
The version for hypergraphs is A058891, or A016031 without singletons.
Row sums of A143543.
The case of connected edge set is A287689.
Cf. A000169, A000295, A036442, A059167, A100743, A136284, A327078.

[2^(n*(n-1) `div` 2) | n <- [0..20]] -- José E. Solsona, Feb 05 2023

[2^(n*(n-1) div 2): n in [0..20]]; // Vincenzo Librandi, Jul 03 2019

Join[{1}, 2^Accumulate[Range[0, 20]]] (* Harvey P. Dale, May 09 2013 *)
Table[2^(n (n - 1) / 2), {n, 0, 20}] (* Vincenzo Librandi, Jul 03 2019 *)
Table[2^Binomial[n, 2], {n, 0, 15}] (* Eric W. Weisstein, Jan 03 2021 *)
2^Binomial[Range[0, 15], 2] (* Eric W. Weisstein, Jan 03 2021 *)
Prepend[Table[Count[Tuples[{0, 1}, {n, n}], ?SymmetricMatrixQ], {n, 5}], 1] (* _Eric W. Weisstein, Jan 03 2021 *)
Prepend[Table[Count[Tuples[{-1, 1}, {n, n}], ?PositiveDefiniteMatrixQ], 1], {n, 4}] (* _Eric W. Weisstein, Jan 03 2021 *)

A006125(n):=2^(n*(n-1)/2)$ makelist(A006125(n), n, 0, 30); /* Martin Ettl, Oct 24 2012 */

a(n)=1<Charles R Greathouse IV, Jun 15 2011

def A006125(n): return 1<<(n*(n-1)>>1) # Chai Wah Wu, Nov 09 2023

Sequence is given by the Hankel transform of A001003 (Schroeder's numbers) = 1, 1, 3, 11, 45, 197, 903, ...; example: det([1, 1, 3, 11; 1, 3, 11, 45; 3, 11, 45, 197; 11, 45, 197, 903]) = 2^6 = 64. - Philippe Deléham, Mar 02 2004
a(n) = 2^floor(n^2/2)/2^floor(n/2). - Paul Barry, Oct 04 2004
G.f. satisfies: A(x) = 1 + x*A(2x). - Paul D. Hanna, Dec 04 2009
a(n) = 2 * a(n-1)^2 / a(n-2). - Michael Somos, Dec 30 2012
G.f.: G(0)/x - 1/x, where G(k) = 1 + 2^(k-1)*x/(1 - 1/(1 + 1/G(k+1) )); (continued fraction). - Sergei N. Gladkovskii, Jul 26 2013
E.g.f. satisfies A'(x) = A(2x). - Geoffrey Critzer, Sep 07 2013
Sum_{n>=1} 1/a(n) = A299998. - Amiram Eldar, Oct 27 2020
a(n) = s_lambda(1,1,...,1) where s is the Schur polynomial in n variables and lambda is the partition (n,n-1,n-2,...,1). - Leonid Bedratyuk, Feb 06 2022
a(n) = Product_{1 <= j <= i <= n-1}  (i + j)/(2*i - 2*j + 1). Cf. A007685.  - Peter Bala, Oct 25 2024

More terms from Vladeta Jovovic, Apr 09 2000

A028242 Follow n+1 by n. Also (essentially) Molien series of 2-dimensional quaternion group Q_8.

Original entry on oeis.org

1, 0, 2, 1, 3, 2, 4, 3, 5, 4, 6, 5, 7, 6, 8, 7, 9, 8, 10, 9, 11, 10, 12, 11, 13, 12, 14, 13, 15, 14, 16, 15, 17, 16, 18, 17, 19, 18, 20, 19, 21, 20, 22, 21, 23, 22, 24, 23, 25, 24, 26, 25, 27, 26, 28, 27, 29, 28, 30, 29, 31, 30, 32, 31, 33, 32, 34, 33, 35, 34, 36, 35, 37, 36, 38

Offset: 0

N. J. A. Sloane

A two-way infinite sequences which is palindromic (up to sign). - Michael Somos, Mar 21 2003
Number of permutations of [n+1] avoiding the patterns 123, 132 and 231 and having exactly one fixed point. Example: a(0) because we have 1; a(2)=2 because we have 213 and 321; a(3)=1 because we have 3214. - Emeric Deutsch, Nov 17 2005
The ring of invariants for the standard action of Quaternions on C^2 is generated by x^4 + y^4, x^2 * y^2, and x * y * (x^4 - y^4). - Michael Somos, Mar 14 2011
A000027 and A001477 interleaved. - Omar E. Pol, Feb 06 2012
First differences are A168361, extended by an initial -1. (Or: a(n)-a(n-1) = A168361(n+1), for all n >= 1.) - M. F. Hasler, Oct 05 2017
Also the number of unlabeled simple graphs with n + 1 vertices and exactly n endpoints (vertices of degree 1). The labeled version is A327370. - Gus Wiseman, Sep 06 2019

			G.f. = 1 + 2*x^2 + x^3 + 3*x^4 + 2*x^5 + 4*x^6 + 3*x^7 + 5*x^8 + 4*x^9 + 6*x^10 + 5*x^11 + ...
Molien g.f. = 1 + 2*t^4 + t^6 + 3*t^8 + 2*t^10 + 4*t^12 + 3*t^14 + 5*t^16 + 4*t^18 + 6*t^20 + ...

D. Benson, Polynomial Invariants of Finite Groups, Cambridge, p. 23.
S. Mukai, An Introduction to Invariants and Moduli, Cambridge, 2003; see p. 15.
M. D. Neusel and L. Smith, Invariant Theory of Finite Groups, Amer. Math. Soc., 2002; see p. 97.
L. Smith, Polynomial Invariants of Finite Groups, A K Peters, 1995, p. 90.

Reinhard Zumkeller, Table of n, a(n) for n = 0..1000
Paul Barry, On a Central Transform of Integer Sequences, arXiv:2004.04577 [math.CO], 2020.
H. W. Gould, The inverse of a finite series and a third-order recurrent sequence, Fibonacci Quart. 44 (2006), no. 4, 302-315. See page 311.
T. Mansour and A. Robertson, Refined restricted permutations avoiding subsets of patterns of length three, Annals of Combinatorics, 6, 2002, 407-418 (Theorem 3.3).
MathOverflow, A question about an application of Molien's formula to find the generators and relations of an invariant ring.
Gus Wiseman, The a(3) = 2 through a(7) = 4 graphs with exactly n - 1 endpoints.
Index entries for Molien series.
Index entries for two-way infinite sequences.
Index entries for linear recurrences with constant coefficients, signature (1,1,-1).

Cf. A000124 (a=1, a=n+a), A028242 (a=1, a=n-a).
Partial sums give A004652. A030451(n)=a(n+1), n>0.
Cf. A052938 (same sequence except no leading 1,0,2).
Cf. A000027, A001477.
Column k = n - 1 of A327371.
Cf. A000035, A004526, A004110, A059167, A109613, A110654, A110657, A110658, A110660, A168361, A245797, A327227, A327369, A327370, A327377.

a:=[1];; for n in [2..80] do a[n]:=(n-1)-a[n-1]; od; a; # Muniru A Asiru, Dec 16 2018

import Data.List (transpose)
a028242 n = n' + 1 - m where (n',m) = divMod n 2
a028242_list = concat $ transpose [a000027_list, a001477_list]
-- Reinhard Zumkeller, Nov 27 2012

&cat[ [n+1, n]: n in [0..37] ]; // Klaus Brockhaus, Nov 23 2009

series((1+x^3)/(1-x^2)^2,x,80);
A028242:=n->floor((n+1+(-1)^n)/2): seq(A028242(n), n=0..100); # Wesley Ivan Hurt, Mar 17 2015

Table[(1 + 2 n + 3 (-1)^n)/4, {n, 0, 74}] (* or *)
LinearRecurrence[{1, 1, -1}, {1, 0, 2}, 75] (* or *)
CoefficientList[Series[(1 - x + x^2)/((1 - x) (1 - x^2)), {x, 0, 74}], x] (* Michael De Vlieger, May 21 2017 *)
Table[{n,n-1},{n,40}]//Flatten (* Harvey P. Dale, Jun 26 2017 *)
Table[3*floor(n/2)-n+1,{n,0,40}] (* Pierre-Alain Sallard, Dec 15 2018 *)

{a(n) = (n\2) - (n%2) + 1} \\ Michael Somos, Oct 02 1999

A028242(n)=n\2+!bittest(n,0) \\ M. F. Hasler, Oct 05 2017

s=((1+x^3)/(1-x^2)^2).series(x, 80); s.coefficients(x, sparse=False) # G. C. Greubel, Dec 16 2018

Expansion of the Molien series for standard action of Quaternions on C^2: (1 + t^6) / (1 - t^4)^2 = (1 - t^12) / ((1 - t^4)^2 * (1 - t^6)) in powers of t^2.
Euler transform of length 6 sequence [0, 2, 1, 0, 0, -1]. - Michael Somos, Mar 14 2011
a(n) = n - a(n-1) [with a(0) = 1] = A000035(n-1) + A004526(n). - Henry Bottomley, Jul 25 2001
G.f.: (1 - x + x^2) / ((1 - x) * (1 - x^2)) = ( 1+x^2-x ) / ( (1+x)*(x-1)^2 ).
a(2*n) = n + 1, a(2*n + 1) = n, a(-1 - n) = -a(n).
a(n) = a(n - 1) + a(n - 2) - a(n - 3).
a(n) = floor(n/2) + 1 - n mod 2. a(2*k) = k+1, a(2*k+1) = k; A110657(n) = a(a(n)), A110658(n) = a(a(a(n))); a(n) = A109613(n)-A110654(n) = A110660(n)/A110654(n). - Reinhard Zumkeller, Aug 05 2005
a(n) = 2*floor(n/2) - floor((n-1)/2). - Wesley Ivan Hurt, Oct 22 2013
a(n) = floor((n+1+(-1)^n)/2). - Wesley Ivan Hurt, Mar 15 2015
a(n) = (1 + 2n + 3(-1)^n)/4. - Wesley Ivan Hurt, Mar 18 2015
a(n) = Sum_{i=1..floor(n/2)} floor(n/(n-i)) for n > 0. - Wesley Ivan Hurt, May 21 2017
a(2n) = n+1, a(2n+1) = n, for all n >= 0. - M. F. Hasler, Oct 05 2017
a(n) = 3*floor(n/2) - n + 1. - Pierre-Alain Sallard, Dec 15 2018
E.g.f.: ((2 + x)*cosh(x) + (x - 1)*sinh(x))/2. - Stefano Spezia, Aug 01 2022
Sum_{n>=2} (-1)^(n+1)/a(n) = 1. - Amiram Eldar, Oct 04 2022

First part of definition adjusted to match offset by Klaus Brockhaus, Nov 23 2009

A095983 Number of 2-edge-connected labeled graphs on n nodes.

Original entry on oeis.org

0, 0, 0, 1, 10, 253, 11968, 1047613, 169181040, 51017714393, 29180467201536, 32121680070545657, 68867078000231169536, 290155435185687263172693, 2417761175748567327193407488, 40013922635723692336670167608181, 1318910073755307133701940625759574016

Offset: 0

Yifei Chen (yifei(AT)mit.edu), Jul 17 2004

nonn

From Falk Hüffner, Jun 28 2018: (Start)
Essentially the same sequence arises as the number of connected bridgeless labeled graphs (graphs that are k-edge connected for k >= 2, starting elements of this sequence are 1, 1, 0, 1, 10, 253, 11968, ...).
Labeled version of A007146. (End)
The spanning edge-connectivity of a graph is the minimum number of edges that must be removed (without removing incident vertices) to obtain a graph that is disconnected or covers fewer vertices. This sequence counts graphs with spanning edge-connectivity >= 2, which, for n > 1, are connected graphs with no bridges. - Gus Wiseman, Sep 20 2019

Jinyuan Wang, Table of n, a(n) for n = 0..82
P. Hanlon and R. W. Robinson, Counting bridgeless graphs, J. Combin. Theory, B 33 (1982), 276-305.
Gus Wiseman, The a(4) = 10 labeled graphs with spanning edge-connectivity >= 2.
Gus Wiseman, Non-isomorphic representatives of the a(5) = 253 graphs with spanning edge-connectivity >= 2.

Cf. A053549, A198046.
The unlabeled version is A007146.
Row sums of A327069 if the first two columns are removed.
BII-numbers of set-systems with spanning edge-connectivity >= 2 are A327109.
Graphs with spanning edge-connectivity 2 are A327146.
Graphs with non-spanning edge-connectivity >= 2 are A327200.
2-vertex-connected graphs are A013922.
Graphs without endpoints are A059167.
Graphs with spanning edge-connectivity 1 are A327071.
Cf. A001187, A002218, A052446, A059166, A100743, A322395, A327079, A327144.

seq[n_] := Module[{v, p, q, c}, v[_] = 0; p = x*D[#, x]& @ Log[ Sum[ 2^Binomial[k, 2]*x^k/k!, {k, 0, n}] + O[x]^(n+1)]; q = x*E^p; p -= q; For[k = 3, k <= n, k++, c = Coefficient[p, x, k]; v[k] = c*(k-1)!; p -= c*q^k]; Join[{0}, Array[v, n]]];
seq[16] (* Jean-François Alcover, Aug 13 2019, after Andrew Howroyd *)
csm[s_]:=With[{c=Select[Subsets[Range[Length[s]],{2}],Length[Intersection@@s[[#]]]>0&]},If[c=={},s,csm[Sort[Append[Delete[s,List/@c[[1]]],Union@@s[[c[[1]]]]]]]]];
spanEdgeConn[vts_,eds_]:=Length[eds]-Max@@Length/@Select[Subsets[eds],Union@@#!=vts||Length[csm[#]]!=1&];
Table[Length[Select[Subsets[Subsets[Range[n],{2}]],spanEdgeConn[Range[n],#]>=2&]],{n,0,5}] (* Gus Wiseman, Sep 20 2019 *)

\\ here p is initially A053549, q is A198046 as e.g.f.s.
seq(n)={my(v=vector(n));
my(p=x*deriv(log(sum(k=0, n, 2^binomial(k, 2) * x^k / k!) + O(x*x^n))));
my(q=x*exp(p)); p-=q;
for(k=3, n, my(c=polcoeff(p,k)); v[k]=c*(k-1)!; p-=c*q^k);
concat([0],v)} \\ Andrew Howroyd, Jun 18 2018

seq(n)={my(p=x*deriv(log(sum(k=0, n, 2^binomial(k, 2) * x^k / k!) + O(x*x^n)))); Vec(serlaplace(log(x/serreverse(x*exp(p)))/x-1), -(n+1))} \\ Andrew Howroyd, Dec 28 2020

a(n) = A001187(n) - A327071(n). - Gus Wiseman, Sep 20 2019

Name corrected and more terms from Pavel Irzhavski, Nov 01 2014
Offset corrected by Falk Hüffner, Jun 17 2018
a(12)-a(16) from Andrew Howroyd, Jun 18 2018

A004110 Number of n-node unlabeled graphs without endpoints (i.e., no nodes of degree 1).

Original entry on oeis.org

1, 1, 1, 2, 5, 16, 78, 588, 8047, 205914, 10014882, 912908876, 154636289460, 48597794716736, 28412296651708628, 31024938435794151088, 63533059372622888758054, 244916078509480823407040988, 1783406527599529094009748567708, 24605674623474428415849066062642456

Offset: 0

N. J. A. Sloane

nonn

a(n) is also the number of unlabeled mating graphs with n nodes. A mating graph has no two vertices with identical sets of neighbors. - Tanya Khovanova, Oct 23 2008

F. Harary, Graph Theory, Wiley, 1969. See illustrations in Appendix 1.
F. Harary and E. Palmer, Graphical Enumeration, (1973), compare formula (8.7.11).
R. W. Robinson, personal communication.
R. W. Robinson, Numerical implementation of graph counting algorithms, AGRC Grant, Math. Dept., Univ. Newcastle, Australia, 1976.
N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).

Andrew Howroyd, Table of n, a(n) for n = 0..50 (terms 0..26 from R. W. Robinson)
David Cook II, Nested colourings of graphs, arXiv preprint arXiv:1306.0140 [math.CO], 2013.
Ira M. Gessel and Ji Li, Enumeration of point-determining graphs, J. Combinatorial Theory Ser. A 118 (2011), 591-612.
Hemanshu Kaul and Jeffrey A. Mudrock, Counting List Colorings of Unlabeled Graphs, arXiv:2409.06063 [math.CO], 2024. See p. 6.
R. J. Mathar, Illustrations for n=1..5 nodes.
Ronald C. Read, The enumeration of mating-type graphs, Report CORR 89-38, Dept. Combinatorics and Optimization, Univ. Waterloo, 1989.
R. W. Robinson, Graphs without endpoints - computer printout.
N. J. A. Sloane, Illustration of a(0)-a(5).

Row sums of A123551.
Cf. A059166 (n-node connected labeled graphs without endpoints), A059167 (n-node labeled graphs without endpoints), A004108 (n-node connected unlabeled graphs without endpoints), A006024 (number of labeled mating graphs with n nodes), A129584 (bi-point-determining graphs).
If isolated nodes are forbidden, see A261919.
Cf. A000088.

permcount[v_] := Module[{m = 1, s = 0, k = 0, t}, For[i = 1, i <= Length[v], i++, t = v[[i]]; k = If[i > 1 && t == v[[i - 1]], k + 1, 1]; m *= t * k; s += t]; s!/m];
edges[v_] := Sum[GCD[v[[i]], v[[j]]], {i, 2, Length[v]}, {j, 1, i - 1}] + Total[Quotient[v, 2]];
a[n_] := Sum[permcount[p] * 2^edges[p] * Coefficient[Product[1 - x^p[[i]], {i, 1, Length[p]}], x, n - k]/k!, {k, 1, n}, {p, IntegerPartitions[k]}]; a[0] = 1;
Table[a[n], {n, 0, 18}] (* Jean-François Alcover, Oct 27 2018, after Andrew Howroyd *)

\\ Compare A000088.
permcount(v) = {my(m=1, s=0, k=0, t); for(i=1, #v, t=v[i]; k=if(i>1&&t==v[i-1], k+1, 1); m*=t*k; s+=t); s!/m}
edges(v) = {sum(i=2, #v, sum(j=1, i-1, gcd(v[i], v[j]))) + sum(i=1, #v, v[i]\2)}
a(n) = {my(s=0); sum(k=1, n, forpart(p=k, s+=permcount(p) * 2^edges(p) * polcoef(prod(i=1, #p, 1-x^p[i]), n-k)/k!)); s} \\ Andrew Howroyd, Sep 09 2018

A004108 Number of n-node unlabeled connected graphs without endpoints.

Original entry on oeis.org

1, 1, 0, 1, 3, 11, 61, 507, 7442, 197772, 9808209, 902884343, 153723152913, 48443147912137, 28363697921914475, 30996525982586676021, 63502034385272108655525, 244852545421597419740767106, 1783161611489937453151313949442, 24603891216883233547700609793901996

Offset: 0

N. J. A. Sloane

nonn

Also number of n-node unlabeled connected mating graphs, cf. A006024 and A092430 (conjectured by Vladeta Jovovic, proved by G. Kilibarda). - Vladeta Jovovic, Oct 07 2004

F. Harary and E. Palmer, Graphical Enumeration, (1973), formula (8.7.11).
Goran Kilibarda, "Enumeration of unlabeled mating graphs", Belgrade, 2004, to be published.
R. W. Robinson, personal communication.
R. W. Robinson, Numerical implementation of graph counting algorithms, AGRC Grant, Math. Dept., Univ. Newcastle, Australia, 1977.
N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).

Andrew Howroyd, Table of n, a(n) for n = 0..50 (terms 1..26 from R. W. Robinson)
David Cook II, Nested colourings of graphs, arXiv preprint arXiv:1306.0140 [math.CO], 2013.
Gabe Cunningham and Igor Minevich, Graph Products of Groups, arXiv:2502.05648 [math.GR], 2025. See p. 5.
Hemanshu Kaul and Jeffrey A. Mudrock, Counting List Colorings of Unlabeled Graphs, arXiv:2409.06063 [math.CO], 2024. See p. 6.
Goran Kilibarda, Enumeration of Unlabeled Mating Graphs, Graphs and Combinatorics, Volume 23, Number 2 / April, 2007, pp. 183-199.
R. W. Robinson, Connected graphs without endpoints - computer printout.
Eric Weisstein's World of Mathematics, Connected Graph.

Cf. A059166 (n-node connected labeled graphs without endpoints), A059167 (n-node labeled graphs without endpoints), A004110 (Euler Transform, n-node unlabeled graphs without endpoints).
Cf. A006024, A092430 (n-node labeled connected mating graphs).
See also A261919.
Cf. A342556, A342557.
Counts include those for distance-critical graphs, A349402.

terms = 19;
mob[m_, n_] := If[Mod[m, n] == 0, MoebiusMu[m/n], 0];
EULERi[b_] := Module[{a, c, i, d}, c = {}; For[i = 1, i <= Length[b], i++, c = Append[c, i*b[[i]] - Sum[c[[d]]*b[[i - d]], {d, 1, i - 1}]]]; a = {}; For[i = 1, i <= Length[b], i++, a = Append[a, (1/i)*Sum[mob[i, d]*c[[d]], {d, 1, i}]]]; Return[a]];
permcount[v_] := Module[{m = 1, s = 0, k = 0, t}, For[i = 1, i <= Length[v], i++, t = v[[i]]; k = If[i > 1 && t == v[[i - 1]], k + 1, 1]; m *= t*k; s += t]; s!/m];
edges[v_] := Sum[GCD[v[[i]], v[[j]]], {i, 2, Length[v]}, {j, 1, i - 1}] + Total[Quotient[v, 2]];
b[n_] := Sum[permcount[p]*2^edges[p]*Coefficient[Product[1 - x^p[[i]], {i, 1, Length[p]}], x, n - k]/k!, {k, 1, n}, {p, IntegerPartitions[k]}];
A004110 = Table[b[n], {n, 1, terms-1}];
Join[{1}, EULERi[A004110]] (* Jean-François Alcover, Jan 21 2019, after Andrew Howroyd *)

Inverse Euler transform of A004110. - Andrew Howroyd, Sep 09 2018

a(0)=1 prepended by Andrew Howroyd, Sep 09 2018

A245797 The number of labeled graphs of n vertices that have endpoints, where an endpoint is a vertex with degree 1.

Original entry on oeis.org

0, 1, 6, 49, 710, 19011, 954184, 90154415, 16108626420, 5481798833245, 3582369649269620, 4532127781040045649, 11177949079089720090800, 54050029251399545975868271, 514598463471970554205910304780, 9677402372862708729859372687791391

Offset: 1

Chai Wah Wu, Aug 01 2014

nonn

Andrew Howroyd, Table of n, a(n) for n = 1..50

Equal to row sums of A245796.
The covering case is A327227.
The connected case is A327362.
The generalization to set-systems is A327228.
BII-numbers of set-systems with minimum degree 1 are A327105.
Cf. A001187, A006129, A059166, A059167, A100743, A136284, A327079, A327098, A327103, A327229, A327230.

m = 16;
egf = Exp[x^2/2]*Sum[2^Binomial[n, 2]*(x/Exp[x])^n/n!, {n, 0, m}];
A059167[n_] := SeriesCoefficient[egf, {x, 0, n}]*n!;
a[n_] := 2^(n(n-1)/2) - A059167[n];
Array[a, m] (* Jean-François Alcover, Feb 23 2019 *)
Table[Length[Select[Subsets[Subsets[Range[n],{2}]],Min@@Length/@Split[Sort[Join@@#]]==1&]],{n,0,5}] (* Gus Wiseman, Sep 11 2019 *)

a(n) = 2^(n*(n+1)/2) - A059167(n).

Binomial transform of A327227 (assuming a(0) = 0).

a(9)-a(16) from Andrew Howroyd, Oct 26 2017

A327227 Number of labeled simple graphs covering n vertices with at least one endpoint/leaf.

Original entry on oeis.org

0, 0, 1, 3, 31, 515, 15381, 834491, 83016613, 15330074139, 5324658838645, 3522941267488973, 4489497643961740521, 11119309286377621015089, 53893949089393110881259181, 513788884660608277842596504415, 9669175277199248753133328740702449

Offset: 0

Gus Wiseman, Sep 01 2019

nonn

Covering means there are no isolated vertices.
A leaf is an edge containing a vertex that does not belong to any other edge, while an endpoint is a vertex belonging to only one edge.
Also graphs with minimum vertex-degree 1.

			The a(4) = 31 edge-sets:
  {12,34}  {12,13,14}  {12,13,14,23}
  {13,24}  {12,13,24}  {12,13,14,24}
  {14,23}  {12,13,34}  {12,13,14,34}
           {12,14,23}  {12,13,23,24}
           {12,14,34}  {12,13,23,34}
           {12,23,24}  {12,14,23,24}
           {12,23,34}  {12,14,24,34}
           {12,24,34}  {12,23,24,34}
           {13,14,23}  {13,14,23,34}
           {13,14,24}  {13,14,24,34}
           {13,23,24}  {13,23,24,34}
           {13,23,34}  {14,23,24,34}
           {13,24,34}
           {14,23,24}
           {14,23,34}
           {14,24,34}

Andrew Howroyd, Table of n, a(n) for n = 0..50

Column k=1 of A327366.
The non-covering version is A245797.
The unlabeled version is A324693.
The generalization to set-systems is A327229.
BII-numbers of set-systems with minimum degree 1 are A327105.
Cf. A001187, A006129, A059166, A059167, A100743, A136284, A327079, A327098, A327103, A327228, A327230.

Table[Length[Select[Subsets[Subsets[Range[n],{2}]],Union@@#==Range[n]&&Min@@Length/@Split[Sort[Join@@#]]==1&]],{n,0,5}]

Inverse binomial transform of A245797, if we assume A245797(0) = 0.

A059166 Number of n-node connected labeled graphs without endpoints.

Original entry on oeis.org

1, 1, 0, 1, 10, 253, 12058, 1052443, 169488200, 51045018089, 29184193354806, 32122530765469967, 68867427921051098084, 290155706369032525823085, 2417761578629525173499004146, 40013923790443379076988789688611, 1318910080173114018084245406769861936

Offset: 0

Vladeta Jovovic, Jan 12 2001

Miklos Bona, editor, Handbook of Enumerative Combinatorics, CRC Press, 2015, p. 404.

Vaclav Kotesovec, Table of n, a(n) for n = 0..80

Cf. A059167 (n-node labeled graphs without endpoints), A004108 (n-node connected unlabeled graphs without endpoints), A004110 (n-node unlabeled graphs without endpoints).

Cf. A001187, A007146, A095983, A100743, A261919, A322395.

c:= proc(n) option remember; `if`(n=0, 1, 2^(n*(n-1)/2)-
      add(k*binomial(n, k)*2^((n-k)*(n-k-1)/2)*c(k), k=1..n-1)/n)
    end:
a:= n-> max(0, add((-1)^i*binomial(n, i)*c(n-i)*(n-i)^i, i=0..n)):
seq(a(n), n=0..20);  # Alois P. Heinz, Oct 27 2017

Flatten[{1,1,0,Table[n!*Sum[(-1)^(n-j)*SeriesCoefficient[1+Log[Sum[2^(k*(k-1)/2)*x^k/k!,{k,0,j}]],{x,0,j}]*j^(n-j)/(n-j)!,{j,0,n}],{n,3,15}]}] (* Vaclav Kotesovec, May 14 2015 *)
c[0] = 1; c[n_] := c[n] = 2^(n*(n-1)/2) - Sum[k*Binomial[n, k]*2^((n-k)*(n - k - 1)/2)*c[k], {k, 1, n-1}]/n; a[0] = a[1] = 1; a[2] = 0; a[n_] := Sum[(-1)^i*Binomial[n, i]*c[n-i]*(n-i)^i, {i, 0, n}]; Table[a[n], {n, 0, 15}] (* Jean-François Alcover, Oct 27 2017, using Alois P. Heinz's code for c(n) *)

seq(n)={Vec(serlaplace(1 + x^2/2 + log(sum(k=0, n, 2^binomial(k, 2)*(x*exp(-x + O(x^n)))^k/k!))))} \\ Andrew Howroyd, Sep 09 2018

a(n) = Sum_{i=0..n} (-1)^i*binomial(n, i)*c(n-i)*(n-i)^i, for n>2, a(0)=1, a(1)=1, a(2)=0, where c(n) is number of n-node connected labeled graphs (cf. A001187).
E.g.f.: 1 + x^2/2 + log(Sum_{n >= 0} 2^binomial(n, 2)*(x*exp(-x))^n/n!).
a(n) ~ 2^(n*(n-1)/2). - Vaclav Kotesovec, May 14 2015
Logarithmic transform of A100743, if we assume a(1) = 0. - Gus Wiseman, Aug 15 2019

More terms from John Renze (jrenze(AT)yahoo.com), Feb 01 2001

cp's OEIS Frontend

A006125 a(n) = 2^(n*(n-1)/2).

Views

Author

Keywords

Comments

Examples

References

Links

Crossrefs

Programs

Haskell

Magma

Mathematica

Maxima

PARI

Python

Formula

Extensions

A028242 Follow n+1 by n. Also (essentially) Molien series of 2-dimensional quaternion group Q_8.

Views

Author

Keywords

Comments

Examples

References

Links

Crossrefs

Programs

GAP

Haskell

Magma

Maple

Mathematica

PARI

PARI

Sage

Formula

Extensions

A095983 Number of 2-edge-connected labeled graphs on n nodes.

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Mathematica

PARI

PARI

Formula

Extensions

A004110 Number of n-node unlabeled graphs without endpoints (i.e., no nodes of degree 1).

Views

Author

Keywords

Comments

References

Links

Crossrefs

Programs

Mathematica

PARI

A004108 Number of n-node unlabeled connected graphs without endpoints.

Views

Author

Keywords

Comments

References

Links

Crossrefs

Programs

Mathematica

Formula

Extensions

A245797 The number of labeled graphs of n vertices that have endpoints, where an endpoint is a vertex with degree 1.

Views

Author

Keywords

Links