The OEIS Foundation is supported by donations from users of the OEIS and by a grant from the Simons Foundation.



(Greetings from The On-Line Encyclopedia of Integer Sequences!)
A006125 a(n) = 2^(n*(n-1)/2).
(Formerly M1897)
1, 1, 2, 8, 64, 1024, 32768, 2097152, 268435456, 68719476736, 35184372088832, 36028797018963968, 73786976294838206464, 302231454903657293676544, 2475880078570760549798248448, 40564819207303340847894502572032, 1329227995784915872903807060280344576 (list; graph; refs; listen; history; text; internal format)



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


















(top-to-bottom distance = 2n) with dominoes like either of

o--o o-----o

|..| |.....|

|..| o-----o




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

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


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

Tobias Boege, Thomas Kahle, Construction Methods for Gaussoids, arXiv:1902.11260 [math.CO], 2019.

Taylor Brysiewicz, Fulvio Gesmundo, The Degree of Stiefel Manifolds, arXiv:1909.10085 [math.AG], 2019.

P. J. Cameron, Sequences realized by oligomorphic permutation groups, J. Integ. Seqs. Vol. 3 (2000), #00.1.5.

M. Ciucu, Perfect matchings of cellular graphs, J. Algebraic Combin., 5 (1996) 87-103.

M. Ciucu, Enumeration of perfect matchings in graphs with reflective symmetry, J. Combin. Theory Ser. A 77 (1997), no. 1, 67-97.

N. Elkies, G. Kuperberg, M. Larsen and J. Propp, Alternating sign matrices and domino tilings. Part I, Journal of Algebraic Combinatorics 1-2, 111-132 (1992).

N. Elkies, G. Kuperberg, M. Larsen and J. Propp, Alternating sign matrices and domino tilings. Part II, Journal of Algebraic Combinatorics 1-3, 219-234 (1992).

S.-P. Eu and T.-S. Fu, A simple proof of the Aztec diamond problem, 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.

H. Helfgott and I. 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.

W. Jockusch, Perfect matchings and perfect squares J. Combin. Theory Ser. A 67 (1994), no. 1, 100-115.

E. H. Kuo, Applications of graphical condensation for enumerating matchings and tilings, arXiv:math/0304090 [math.CO], 2003.

C. L. Mallows & N. J. A. Sloane, Emails, May 1991

W. H. Mills, D. P. Robbins and H. Rumsey, Jr., Alternating sign matrices and descending plane partitions, J. Combin. Theory Ser. A 34 (1983), 340-359.

G. Pfeiffer, Counting Transitive Relations, Journal of Integer Sequences, Vol. 7 (2004), Article 04.3.2.

J. Propp, Enumeration of matchings: problems and progress, in L. J. Billera et al. (eds.), New Perspectives in Algebraic Combinatorics

J. Propp, Enumeration of matchings: problems and progress, arXiv:math/9904150 [math.CO], 1999.

J. Propp, Lessons I learned from Richard Stanley, arXiv preprint [math.CO], 2015.

J. Propp and R. P. Stanley, Domino tilings with barriers, arXiv:math/9801067 [math.CO], 1998.

S. S. Skiena, Generating graphs

D. E. Speyer, Perfect matchings and the octahedral recurrence, arXiv:math/0402452 [math.CO], 2004.

R. P. Stanley, A combinatorial miscellany

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

D. Zeilberger, Dave Robbins's Art of Guessing, Adv. in Appl. Math. 34 (2005), 939-954.

Index entries for sequences related to dominoes


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


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


(PARI) a(n)=1<<binomial(n, 2) \\ Charles R Greathouse IV, Jun 15 2011

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

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


Cf. A000568 for the unlabeled analog, A006129, A053763, A006253, A004003.

Cf. A001187 (connected labeled graphs).

Cf. A095340, A103904, A005329, A114604.

Cf. A158474. - Gary W. Adamson, Mar 20 2009

Cf. A136652 (log). - Paul D. Hanna, Dec 04 2009

Sequence in context: A139683 A139684 A139685 * A193753 A006119 A296328

Adjacent sequences:  A006122 A006123 A006124 * A006126 A006127 A006128




N. J. A. Sloane


More terms from Vladeta Jovovic, Apr 09 2000



Lookup | Welcome | Wiki | Register | Music | Plot 2 | Demos | Index | Browse | More | WebCam
Contribute new seq. or comment | Format | Style Sheet | Transforms | Superseeker | Recent
The OEIS Community | Maintained by The OEIS Foundation Inc.

License Agreements, Terms of Use, Privacy Policy. .

Last modified October 19 20:17 EDT 2020. Contains 337892 sequences. (Running on oeis4.)