|
%I M1897 #228 Apr 10 2024 10:38:41
%S 1,1,2,8,64,1024,32768,2097152,268435456,68719476736,35184372088832,
%T 36028797018963968,73786976294838206464,302231454903657293676544,
%U 2475880078570760549798248448,40564819207303340847894502572032,1329227995784915872903807060280344576
%N a(n) = 2^(n*(n-1)/2).
%C Number of graphs on n labeled nodes; also number of outcomes of labeled n-team round-robin tournaments.
%C Number of perfect matchings of order n Aztec diamond. [see Speyer]
%C Number of Gelfand-Zeitlin patterns with bottom row [1,2,3,...,n]. [Zeilberger]
%C 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
%C From _James Propp_: (Start)
%C a(n) is the number of ways to tile the region
%C o-----o
%C |.....|
%C o--o.....o--o
%C |...........|
%C o--o...........o--o
%C |.................|
%C o--o.................o--o
%C |.......................|
%C |.......................|
%C |.......................|
%C o--o.................o--o
%C |.................|
%C o--o...........o--o
%C |...........|
%C o--o.....o--o
%C |.....|
%C o-----o
%C (top-to-bottom distance = 2n) with dominoes like either of
%C o--o o-----o
%C |..| or |.....|
%C |..| o-----o
%C |..|
%C o--o
%C (End)
%C 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
%C 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
%C 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
%C 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
%C The number of symmetric binary relations on an (n-1)-element set. - _Peter Kagey_, Feb 13 2021
%C 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
%C a(n) = A126883(n-1)+1. - _Zerinvary Lajos_, Jun 12 2007
%C Equals right border of triangle A158474 (unsigned). - _Gary W. Adamson_, Mar 20 2009
%C 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
%C a(n+1) is the number of symmetric binary matrices of size n X n. - _Nathan J. Russell_, Aug 30 2014
%C 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
%C 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
%C 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
%C a(n) is the number of positive definite (-1,1)-matrices of size n X n. - _Eric W. Weisstein_, Jan 03 2021
%C 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
%D Miklos Bona, editor, Handbook of Enumerative Combinatorics, CRC Press, 2015, page 547 (Fig. 9.7), 573.
%D G. Everest, A. van der Poorten, I. Shparlinski and T. Ward, Recurrence Sequences, Amer. Math. Soc., 2003; p. 178.
%D J. L. Gross and J. Yellen, eds., Handbook of Graph Theory, CRC Press, 2004; p. 517.
%D F. Harary, Graph Theory. Addison-Wesley, Reading, MA, 1969, p. 178.
%D F. Harary and E. M. Palmer, Graphical Enumeration, Academic Press, NY, 1973, p. 3, Eq. (1.1.2).
%D 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.
%D N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).
%H N. J. A. Sloane, <a href="/A006125/b006125.txt">Table of n, a(n) for n = 0..50</a>
%H F. Ardila and R. P. Stanley, <a href="https://arxiv.org/abs/math/0501170">Tilings</a>, arXiv:math/0501170 [math.CO], 2005.
%H Paul Barry and Aoife Hennessy, <a href="https://cs.uwaterloo.ca/journals/JIS/VOL15/Barry2/barry190r.html">Generalized Narayana Polynomials, Riordan Arrays, and Lattice Paths</a>, Journal of Integer Sequences, Vol. 15, 2012, #12.4.8. - From _N. J. A. Sloane_, Oct 08 2012
%H Anders Björner and Richard P. Stanley, <a href="http://www-math.mit.edu/~rstan/papers/comb.pdf">A combinatorial miscellany</a>, 2010.
%H Tobias Boege and Thomas Kahle, <a href="https://arxiv.org/abs/1902.11260">Construction Methods for Gaussoids</a>, arXiv:1902.11260 [math.CO], 2019.
%H Taylor Brysiewicz and Fulvio Gesmundo, <a href="https://arxiv.org/abs/1909.10085">The Degree of Stiefel Manifolds</a>, arXiv:1909.10085 [math.AG], 2019.
%H Peter J. Cameron, <a href="http://www.cs.uwaterloo.ca/journals/JIS/VOL3/groups.html">Sequences realized by oligomorphic permutation groups</a>, J. Integ. Seqs. Vol. 3 (2000), #00.1.5.
%H Mihai Ciucu, <a href="https://www.researchgate.net/publication/225203580_Perfect_Matchings_of_Cellular_Graphs">Perfect matchings of cellular graphs</a>, J. Algebraic Combin., 5 (1996) 87-103.
%H Mihai Ciucu, <a href="https://mciucu.pages.iu.edu/symmgraphs.pdf">Enumeration of perfect matchings in graphs with reflective symmetry</a>, J. Combin. Theory Ser. A 77 (1997), no. 1, 67-97.
%H Thierry de la Rue and Élise Janvresse, <a href="https://images.math.cnrs.fr/Pavages-aleatoires-par-touillage-de-dominos.html">Pavages aléatoires par touillage de dominos</a>, Images des Mathématiques, CNRS, 2023. In French.
%H Noam Elkies, Greg Kuperberg, Michael Larsen and James Propp, <a href="http://dx.doi.org/10.1023/A:1022420103267">Alternating sign matrices and domino tilings. Part I</a>, Journal of Algebraic Combinatorics 1-2, 111-132 (1992).
%H Noam Elkies, Greg Kuperberg, Michael Larsen and James Propp, <a href="http://dx.doi.org/10.1023/A:1022483817303">Alternating sign matrices and domino tilings. Part II</a>, Journal of Algebraic Combinatorics 1-3, 219-234 (1992).
%H Sen-Peng Eu and Tung-Shan Fu, <a href="https://arxiv.org/abs/math/0412041">A simple proof of the Aztec diamond theorem</a>, arXiv:math/0412041 [math.CO], 2004.
%H D. Grensing, I. Carlsen and H.-Chr. Zapp, <a href="http://dx.doi.org/10.1080/01418618008239348">Some exact results for the dimer problem on plane lattices with non-standard boundaries</a>, Phil. Mag. A, 41:5 (1980), 777-781.
%H Harald Helfgott and Ira M. Gessel, <a href="https://arxiv.org/abs/math/9810143">Enumeration of tilings of diamonds and hexagons with defects</a>, arXiv:math/9810143 [math.CO], 1998.
%H Aoife Hennessy, <a href="http://repository.wit.ie/1693/1/AoifeThesis.pdf">A Study of Riordan Arrays with Applications to Continued Fractions, Orthogonal Polynomials and Lattice Paths</a>, Ph. D. Thesis, Waterford Institute of Technology, Oct. 2011.
%H Pakawut Jiradilok, <a href="https://arxiv.org/abs/2404.02714">Some Combinatorial Formulas Related to Diagonal Ramsey Numbers</a>, arXiv:2404.02714 [math.CO], 2024. See p. 19.
%H William Jockusch, <a href="http://dx.doi.org/10.1016/0097-3165(94)90006-X">Perfect matchings and perfect squares</a> J. Combin. Theory Ser. A 67 (1994), no. 1, 100-115.
%H Eric H. Kuo, <a href="https://doi.org/10.1016/j.tcs.2004.02.022">Applications of graphical condensation for enumerating matchings and tilings</a>, Theoretical Computer Science, Vol. 319, No. 1-3 (2004), pp. 29-57, <a href="https://arxiv.org/abs/math/0304090">arXiv preprint</a>, arXiv:math/0304090 [math.CO], 2003.
%H C. L. Mallows & N. J. A. Sloane, <a href="/A006123/a006123.pdf">Emails, May 1991</a>
%H W. H. Mills, David P. Robbins and Howard Rumsey, Jr., <a href="http://dx.doi.org/10.1016/0097-3165(83)90068-7">Alternating sign matrices and descending plane partitions</a>, J. Combin. Theory Ser. A 34 (1983), 340-359.
%H Götz Pfeiffer, <a href="http://www.cs.uwaterloo.ca/journals/JIS/VOL7/Pfeiffer/pfeiffer6.html">Counting Transitive Relations</a>, Journal of Integer Sequences, Vol. 7 (2004), Article 04.3.2.
%H James Propp, Enumeration of matchings: problems and progress, in L. J. Billera et al. (eds.), <a href="http://www.msri.org/publications/books/Book38/contents.html">New Perspectives in Algebraic Combinatorics</a>
%H James Propp, <a href="https://arxiv.org/abs/math/9904150">Enumeration of matchings: problems and progress</a>, arXiv:math/9904150 [math.CO], 1999.
%H James Propp, <a href="http://arxiv.org/abs/1501.00719">Lessons I learned from Richard Stanley</a>, arXiv preprint [math.CO], 2015.
%H James Propp and R. P. Stanley, <a href="https://arxiv.org/abs/math/9801067">Domino tilings with barriers</a>, arXiv:math/9801067 [math.CO], 1998.
%H Steven S. Skiena, <a href="http://www.cs.sunysb.edu/~algorith/files/generating-graphs.shtml">Generating graphs</a>.
%H David E. Speyer, <a href="https://doi.org/10.1007/s10801-006-0039-y">Perfect matchings and the octahedron recurrence</a>, Journal of Algebraic Combinatorics, Vol. 25, No. 3 (2007), pp. 309-348, <a href="https://arxiv.org/abs/math/0402452">arXiv preprint</a>, arXiv:math/0402452 [math.CO], 2004.
%H Herman Tulleken, <a href="https://www.researchgate.net/publication/333296614_Polyominoes">Polyominoes 2.2: How they fit together</a>, (2019).
%H Eric Weisstein's World of Mathematics, <a href="http://mathworld.wolfram.com/ConnectedGraph.html">Connected Graph</a>.
%H Eric Weisstein's World of Mathematics, <a href="http://mathworld.wolfram.com/LabeledGraph.html">Labeled Graph</a>.
%H Eric Weisstein's World of Mathematics, <a href="http://mathworld.wolfram.com/SymmetricMatrix.html">Symmetric Matrix</a>.
%H Doron Zeilberger, <a href="http://www.math.rutgers.edu/~zeilberg/DaveRobbins/guess.html">Dave Robbins's Art of Guessing</a>, Adv. in Appl. Math. 34 (2005), 939-954.
%H <a href="/index/Do#domino">Index entries for sequences related to dominoes</a>
%F 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
%F a(n) = 2^floor(n^2/2)/2^floor(n/2). - _Paul Barry_, Oct 04 2004
%F G.f. satisfies: A(x) = 1 + x*A(2x). - _Paul D. Hanna_, Dec 04 2009
%F a(n) = 2 * a(n-1)^2 / a(n-2). - _Michael Somos_, Dec 30 2012
%F 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
%F E.g.f. satisfies A'(x) = A(2x). - _Geoffrey Critzer_, Sep 07 2013
%F Sum_{n>=1} 1/a(n) = A299998. - _Amiram Eldar_, Oct 27 2020
%F 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
%e From _Gus Wiseman_, Feb 11 2021: (Start)
%e This sequence counts labeled graphs on n vertices. For example, the a(0) = 1 through a(2) = 8 graph edge sets are:
%e {} {} {} {}
%e {12} {12}
%e {13}
%e {23}
%e {12,13}
%e {12,23}
%e {13,23}
%e {12,13,23}
%e 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.
%e {} {} {}
%e {11} {11}
%e {12}
%e {22}
%e {11,12}
%e {11,22}
%e {12,22}
%e {11,12,22}
%e (End)
%t Join[{1}, 2^Accumulate[Range[0, 20]]] (* _Harvey P. Dale_, May 09 2013 *)
%t Table[2^(n (n - 1) / 2), {n, 0, 20}] (* _Vincenzo Librandi_, Jul 03 2019 *)
%t Table[2^Binomial[n, 2], {n, 0, 15}] (* _Eric W. Weisstein_, Jan 03 2021 *)
%t 2^Binomial[Range[0, 15], 2] (* _Eric W. Weisstein_, Jan 03 2021 *)
%t Prepend[Table[Count[Tuples[{0, 1}, {n, n}], _?SymmetricMatrixQ], {n, 5}], 1] (* _Eric W. Weisstein_, Jan 03 2021 *)
%t Prepend[Table[Count[Tuples[{-1, 1}, {n, n}], _?PositiveDefiniteMatrixQ], 1], {n, 4}] (* _Eric W. Weisstein_, Jan 03 2021 *)
%o (PARI) a(n)=1<<binomial(n,2) \\ _Charles R Greathouse IV_, Jun 15 2011
%o (Maxima) A006125(n):=2^(n*(n-1)/2)$ makelist(A006125(n), n, 0, 30); /* _Martin Ettl_, Oct 24 2012 */
%o (Magma) [2^(n*(n-1) div 2): n in [0..20]]; // _Vincenzo Librandi_, Jul 03 2019
%o (Haskell) [2^(n*(n-1) `div` 2) | n <- [0..20]] -- _José E. Solsona_, Feb 05 2023
%o (Python)
%o def A006125(n): return 1<<(n*(n-1)>>1) # _Chai Wah Wu_, Nov 09 2023
%Y Cf. A000568 for the unlabeled analog, A053763, A006253, A004003.
%Y Cf. A001187 (connected labeled graphs).
%Y Cf. A095340, A103904, A005329, A114604, A299998.
%Y Cf. A158474. - _Gary W. Adamson_, Mar 20 2009
%Y Cf. A136652 (log). - _Paul D. Hanna_, Dec 04 2009
%Y The unlabeled version is A000088, or A002494 without isolated vertices.
%Y The directed version is A002416.
%Y The covering case is A006129.
%Y The version for hypergraphs is A058891, or A016031 without singletons.
%Y Row sums of A143543.
%Y The case of connected edge set is A287689.
%Y Cf. A000169, A000295, A059167, A100743, A136284, A327078.
%K nonn,easy,nice,changed
%O 0,3
%A _N. J. A. Sloane_
%E More terms from _Vladeta Jovovic_, Apr 09 2000
| 