login
This site is supported by donations to The OEIS Foundation.

 

Logo


Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
A006125 a(n) = 2^(n*(n-1)/2).
(Formerly M1897)
208

%I M1897

%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 |..| |.....|

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

%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 Tobias Boege, Thomas Kahle, <a href="https://arxiv.org/abs/1902.11260">Construction Methods for Gaussoids</a>, arXiv:1902.11260 [math.CO], 2019.

%H P. 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 M. Ciucu, <a href="http://www.math.gatech.edu/~ciucu/list.html">Perfect matchings of cellular graphs</a>, J. Algebraic Combin., 5 (1996) 87-103.

%H M. Ciucu, <a href="http://www.math.gatech.edu/~ciucu/list.html">Enumeration of perfect matchings in graphs with reflective symmetry</a>, J. Combin. Theory Ser. A 77 (1997), no. 1, 67-97.

%H N. Elkies, G. Kuperberg, M. Larsen and J. 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 N. Elkies, G. Kuperberg, M. Larsen and J. 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 S.-P. Eu and T.-S. Fu, <a href="https://arxiv.org/abs/math/0412041">A simple proof of the Aztec diamond problem</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 H. Helfgott and I. 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 W. 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 E. H. Kuo, <a href="https://arxiv.org/abs/math/0304090">Applications of graphical condensation for enumerating matchings and tilings</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, D. P. Robbins and H. 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. 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 J. 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 J. Propp, <a href="https://arxiv.org/abs/math/9904150">Enumeration of matchings: problems and progress</a>, arXiv:math/9904150 [math.CO], 1999.

%H J. Propp, <a href="http://arxiv.org/abs/1501.00719">Lessons I learned from Richard Stanley</a>, arXiv preprint [math.CO], 2015.

%H J. 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 S. S. Skiena, <a href="http://www.cs.sunysb.edu/~algorith/files/generating-graphs.shtml">Generating graphs</a>

%H D. E. Speyer, <a href="https://arxiv.org/abs/math/0402452">Perfect matchings and the octahedral recurrence</a>, arXiv:math/0402452 [math.CO], 2004.

%H R. P. Stanley, <a href="http://www-math.mit.edu/~rstan/papers/comb.pdf">A combinatorial miscellany</a>

%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 D. 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

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

%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

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

%Y Cf. A001187 (connected labeled graphs).

%Y Cf. A095340, A103904, A005329, A114604.

%Y Cf. A158474. - _Gary W. Adamson_, Mar 20 2009

%Y Cf. A136652 (log). - _Paul D. Hanna_, Dec 04 2009

%K nonn,easy,nice

%O 0,3

%A _N. J. A. Sloane_

%E 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 November 17 03:06 EST 2019. Contains 329216 sequences. (Running on oeis4.)