A053763 -id:A053763 - cp's OEIS frontend

A054545 Number of labeled digraphs on n unisolated nodes (inverse binomial transform of A053763).

1, 0, 3, 54, 3861, 1028700, 1067510583, 4390552197234, 72022439672173161, 4721718122762915558520, 1237892818862615769794806443, 1298060597552993036455274183624814, 5444502293926142814638982021027945429501, 91343781554550362267223855965291602454111295060

Offset: 0

Vladeta Jovovic, Apr 09 2000

			2^(n*(n-1))=1+3*C(n,2)+54*C(n,3)+3861*C(n,4)+...

Andrew Howroyd, Table of n, a(n) for n = 0..50
N. J. A. Sloane, Transforms

Cf. A006129.

nn=20;s=Sum[2^(2Binomial[n,2])x^n/n!,{n,0,nn}];Range[0,nn]!CoefficientList[Series[ s/Exp[x],{x,0,nn}],x]  (* Geoffrey Critzer, Oct 07 2012 *)

a(n)={sum(k=0, n, (-1)^(n-k)*binomial(n, k)*2^(k*(k-1)))} \\ Andrew Howroyd, Nov 07 2019

a(n) = Sum_{k=0..n} (-1)^(n-k)*binomial(n, k)*2^(k*(k-1)).

Terms a(12) and beyond from Andrew Howroyd, Nov 07 2019

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

Original entry on oeis.org

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

A002416 a(n) = 2^(n^2).

Original entry on oeis.org

1, 2, 16, 512, 65536, 33554432, 68719476736, 562949953421312, 18446744073709551616, 2417851639229258349412352, 1267650600228229401496703205376, 2658455991569831745807614120560689152, 22300745198530623141535718272648361505980416, 748288838313422294120286634350736906063837462003712

Offset: 0

N. J. A. Sloane

For n >= 1, a(n) is the number of n X n (0, 1) matrices.
Also number of directed graphs on n labeled nodes allowing self-loops (cf. A053763).
1/2^(n^2) is the Hankel transform of C(n, n/2)*(1 + (-1)^n)/(2*2^n), or C(2n, n)/4^n with interpolated zeros. - Paul Barry, Sep 27 2007
Hankel transform of A064062. - Philippe Deléham, Nov 19 2007
a(n) is also the order of the semigroup (monoid) of all binary relations on an n-set. - Abdullahi Umar, Sep 14 2008
With offset = 1, a(n) is the number of n X n (0, 1) matrices with an even number of 1's in every row and in every column. - Geoffrey Critzer, May 23 2013
a(n) is the number of functions from an n-set to its power set (by definition of function including the empty function only when n = 0). - Rick L. Shepherd, Dec 27 2014

			G.f. = 1 + 2*x + 16*x^2 + 512*x^3 + 65536*x^4 + 33554432*x^5 + ...

John M. Howie, Fundamentals of semigroup theory. Oxford: Clarendon Press, (1995). - Abdullahi Umar, Sep 14 2008

Vincenzo Librandi, Table of n, a(n) for n = 0..33
Peter J. Cameron, Sequences realized by oligomorphic permutation groups, J. Integ. Seqs. Vol. 3 (2000), #00.1.5.
Theresia Eisenkölbl, 2-Enumerations of halved alternating sign matrices, arXiv:math/0106038 [math.CO], 2001.
Theresia Eisenkölbl, 2-Enumerations of halved alternating sign matrices, Séminaire Lotharingien Combin. 46, (2001), Article B46c, 11 pp.
Daniele A. Gewurz and Francesca Merola, Sequences realized as Parker vectors of oligomorphic permutation groups, J. Integer Seqs., Vol. 6, 2003.
F. Harary and R. W. Robinson, Labeled bipartite blocks, Canad. J. Math., 31 (1979), 60-68.
S. R. Kannan and Rajesh Kumar Mohapatra, Counting the Number of Non-Equivalent Classes of Fuzzy Matrices Using Combinatorial Techniques, arXiv:1909.13678 [math.GM], 2019.
Kent E. Morrison, Integer Sequences and Matrices Over Finite Fields, Journal of Integer Sequences, Vol. 9 (2006), Article 06.2.1.
Götz Pfeiffer, Counting Transitive Relations, Journal of Integer Sequences, Vol. 7 (2004), Article 04.3.2.
Eric Weisstein's World of Mathematics, 01-Matrix.
Index to divisibility sequences

Bisection of A060656.

Cf. A053763, A064062, A064231, A319015.

List([0..15], n-> 2^(n^2) ); # G. C. Greubel, Jul 03 2019

[2^(n^2): n in [0..15]]; // Vincenzo Librandi, May 13 2011

Table[2^(n^2), {n,0,15}] (* Vladimir Joseph Stephan Orlovsky, Dec 13 2008 *)

a(n)=polresultant((x-1)^n,(x+1)^n,x) \\ Ralf Stephan

a(n)=2^n^2 \\ Charles R Greathouse IV, Jun 23 2021

[2^(n^2) for n in (0..15)] # G. C. Greubel, Jul 03 2019

G.f. satisfies: A(x) = 1 + 2*x*A(4x). - Paul D. Hanna, Dec 04 2009

a(n) = 2^n * Sum_{i = 0..C(n, 2)} C(C(n, 2), i)*3^i. The summation conditions on the number of symmetric pairs (a,b) with aA027465, A013610. - Geoffrey Critzer, Nov 05 2024

G.f.: 1 / (1 - 2^1*x / (1 - 2^1*(2^2-1)*x / (1 - 2^5 * x / (1 - 2^3*(2^4-1)*x / (1 - 2^9*x / (1 - 2^5*(2^6-1)*x / ...)))))). - Michael Somos, May 12 2012

a(n) = [x^n] 1/(1 - 2^n*x). - Ilya Gutkovskiy, Oct 10 2017

Sum_{n>=0} 1/a(n) = A319015. - Amiram Eldar, Oct 14 2020

A151374 Number of walks within N^2 (the first quadrant of Z^2) starting at (0, 0), ending on the vertical axis and consisting of 2n steps taken from {(-1, -1), (-1, 0), (1, 1)}.

Original entry on oeis.org

1, 2, 8, 40, 224, 1344, 8448, 54912, 366080, 2489344, 17199104, 120393728, 852017152, 6085836800, 43818024960, 317680680960, 2317200261120, 16992801914880, 125210119372800, 926554883358720, 6882979133521920, 51309480813527040, 383705682605506560, 2877792619541299200

Offset: 0

Manuel Kauers, Nov 18 2008

A052701 shifted one place left. - R. J. Mathar, Dec 13 2008
Expansion of c(2*x), where c(x) is the g.f. of A000108. - Philippe Deléham, Feb 26 2009; simplified by Alexander Burstein, Jul 31 2018
From Joerg Arndt, Oct 22 2012: (Start)
Also the number of strings of length 2*n of two different types of balanced parentheses.
For example, a(1) = 2, since the two possible strings of length 2 are [] and (), a(2) = 8, since the 8 possible strings of length 4 are (()), [()], ([]), [[]], ()(), [](), ()[], and [][].
The number of strings of length 2*n of t different types of balanced parentheses is given by t^n * A000108(n): there are n opening parentheses in the strings, giving t^n choices for the type (the closing parentheses are chosen to match). (End)
Number of Dyck paths of length 2n in which the step U=(1,1) come in 2 colors. - José Luis Ramírez Ramírez, Jan 31 2013
Row sums of triangle in A085880. - Philippe Deléham, Nov 15 2013
Hankel transform is 2^(n+n^2) = A053763(n+1). - Philippe Deléham, Nov 15 2013

Vincenzo Librandi, Table of n, a(n) for n = 0..200
Paul Barry, Generalized Eulerian Triangles and Some Special Production Matrices, arXiv:1803.10297 [math.CO], 2018.
Paul Barry, Riordan arrays, the A-matrix, and Somos 4 sequences, arXiv:1912.01126 [math.CO], 2019.
Mireille Bousquet-Mélou and Marni Mishna, Walks with small steps in the quarter plane, arXiv:0810.4387 [math.CO], 2008-2009.
J. Bouttier, P. Di Francesco and E. Guitter, Statistics of planar graphs viewed from a vertex: a study via labeled trees, Nucl. Phys. B, Vol. 675, No. 3 (2003), pp. 631-660. See p. 631, eq. (3.3).
Marek Bożejko, Maciej Dołęga, Wiktor Ejsmont and Światosław R. Gal, Reflection length with two parameters in the asymptotic representation theory of type B/C and applications, arXiv:2104.14530 [math.RT], 2021.
Vedran Čačić and Vjekoslav Kovač, On the fraction of IL formulas that have normal forms, arXiv:1309.3408 [math.LO], 2013.
Stefano Capparelli and Alberto Del Fra, Dyck Paths, Motzkin Paths, and the Binomial Transform, Journal of Integer Sequences, Vol. 18 (2015), Article 15.8.5.
Grégory Chatel and Vincent Pilaud, Cambrian Hopf algebras, Adv. Math. 311, 598-633 (2017). Prop. 3.
Zhi Chen and Hao Pan, Identities involving weighted Catalan-Schröder and Motzkin Paths, arXiv:1608.02448 [math.CO], 2016. See eq. (1.13), a=b=2.
Nicolas Crampe, Julien Gaboriaud and Luc Vinet, Racah algebras, the centralizer Z_n(sl_2) and its Hilbert-Poincaré series, arXiv:2105.01086 [math.RT], 2021.
Hsien-Kuei Hwang, Mihyun Kang and Guan-Huei Duh, Asymptotic Expansions for Sub-Critical Lagrangean Forms, LIPIcs Proceedings of Analysis of Algorithms 2018, Vol. 110, Schloss Dagstuhl-Leibniz-Zentrum für Informatik, 2018.
Bradley Robert Jones, On tree hook length formulas, Feynman rules and B-series, Master's thesis, Simon Fraser University, 2014.
Georg Muntingh, Implicit Divided Differences, Little Schröder Numbers and Catalan Numbers, J. Int. Seq., Vol. 15 (2012), Article 12.6.5; arXiv preprint, arXiv:1204.2709 [math.CO], 2012.
L. Poulain d'Andecy, Centralisers and Hecke algebras in Representation Theory, with applications to Knots and Physics, arXiv:2304.00850 [math.RT], 2023. See p. 64.

Cf. A000108, A046521, A052701, A053763, A085880.

[2^n * Catalan(n): n in [0..25]]; // Vincenzo Librandi, Oct 24 2012

A151374_list := proc(n) local j, a, w; a := array(0..n); a[0] := 1;
for w from 1 to n do a[w] := 2*(a[w-1]+add(a[j]*a[w-j-1],j=1..w-1)) od;
convert(a,list)end: A151374_list(23); # Peter Luschny, May 19 2011

aux[i_Integer, j_Integer, n_Integer] := Which[Min[i, j, n] < 0 || Max[i, j] > n, 0, n == 0, KroneckerDelta[i, j, n], True, aux[i, j, n] = aux[-1 + i, -1 + j, -1 + n] + aux[1 + i, j, -1 + n] + aux[1 + i, 1 + j, -1 + n]]; Table[Sum[aux[0, k, 2 n], {k, 0, 2 n}], {n, 0, 25}]

my(x='x+O('x^66)); Vec(sqrt(2-8*x-2*sqrt(1-8*x))/(4*x)) \\ Joerg Arndt, May 11 2013

def A151374():
    a, n = 1, 1
    while True:
        yield a
        n += 1
        a = a * (8*n - 12) // n
A = A151374()
print([next(A) for  in range(24)]) # _Peter Luschny, Nov 30 2016

a(n) = 2^n * A000108(n). - Philippe Deléham, Feb 01 2009
From Gary W. Adamson, Jul 12 2011: (Start)
a(n) is the top left term in M^n, M = the following infinite square production matrix:
   2, 2, 0, 0, 0, 0, ...
   2, 2, 2, 0, 0, 0, ...
   2, 2, 2, 2, 0, 0, ...
   2, 2, 2, 2, 2, 0, ...
   2, 2, 2, 2, 2, 2, ...
   ...
(End)
E.g.f.: KummerM(1/2, 2, 8*x). - Peter Luschny, Aug 26 2012
From Sergei N. Gladkovskii, Apr 05 2013: (Start)
E.g.f.: Let F(x)=Sum_{n>=0} a(n)*x^n/(2*n)!, then F(x) = E(0)/(1-sqrt(x)) where E(k) = 1 - sqrt(x)/(1 - sqrt(x)/(sqrt(x) - (k+1)*(k+2)/2/E(k+1) )); (continued fraction ).
G.f.: 1 + 4*x/(G(0)-4*x) where G(k) = k*(8*x+1) + 4*x + 2 - 2*x*(2*k+3)*(2*k+4)/G(k+1); (continued fraction). (End)
G.f.: sqrt(2-8*x-2*sqrt(1-8*x))/(4*x). - Mark van Hoeij, May 10 2013
G.f.: (1-sqrt(1-8*x))/(4*x). - Philippe Deléham, Nov 15 2013
D-finite with recurrence (n+1)*a(n) + 4*(-2*n+1)*a(n-1) = 0. - R. J. Mathar, Mar 05 2014
a(n) = 4^n*2F1((1-n)/2,-n/2;1;1)/(n+1). - Benedict W. J. Irwin, Jul 12 2016
a(n) ~ 8^n*n^(-3/2)/sqrt(Pi). - Ilya Gutkovskiy, Jul 12 2016
From Peter Bala, Aug 17 2021: (Start)
a(n) = Sum_{k = 0..floor(n/2)} A046521(n,2*k)*Catalan(2*k).
G.f.: A(x) = 1/sqrt(1 - 4*x)*e(x/(1 - 4*x)), where e(x) = (c(x) + c(-x))/2 is the even part of the function c(x) = (1 - sqrt(1 - 4*x))/(2*x), the g.f. of the Catalan numbers A000108. Inversely, (c(x) + c(-x))/2 = 1/sqrt(1 + 4*x)*A(x/(1 + 4*x)).
x*A(x) = Series reversion of (x - 2*x^2). (End)
Sum_{n>=0} 1/a(n) = 68/49 + 96*arctan(1/sqrt(7)) / (49*sqrt(7)). - Vaclav Kotesovec, Nov 23 2021
Sum_{n>=0} (-1)^n/a(n) = 20/27 - 16*log(2)/81. - Amiram Eldar, Jan 25 2022
G.f.: 1/(1-2*x/(1-2*x/(1-2*x/(1-2*x/(1-2*x/(1-2*x/(1-2*x/(1-2*x/(1-...))))))))) (continued fraction). - Nikolaos Pantelidis, Nov 20 2022
a(n) = 2*Sum_{k=1..n} a(k-1)*a(n-k), a(0) = 1. - Mehdi Naima, Jan 16 2023

A052880 Expansion of e.g.f.: LambertW(1-exp(x))/(1-exp(x)).

Original entry on oeis.org

1, 1, 4, 26, 243, 2992, 45906, 845287, 18182926, 447797646, 12429760889, 384055045002, 13075708703910, 486430792977001, 19632714343389296, 854503410602781782, 39898063449977239323, 1989371798838577172796, 105503454201101084456182, 5930110732782743218645271

Offset: 0

encyclopedia(AT)pommard.inria.fr, Jan 25 2000

A simple grammar.

Also the number of transitive reflexive early confluent binary relations R on n labeled elements. Early confluency means that (xRy and xRz) implies (yRz or zRy) for all x, y, z.

Alois P. Heinz, Table of n, a(n) for n = 0..378
INRIA Algorithms Project, Encyclopedia of Combinatorial Structures 851

Row sums of A135313.
Main diagonal of A135302.
Cf. A033917, A053763.

spec := [S,{B=Set(Z,1 <= card),S=Set(C),C=Prod(B,S)},labeled]: seq(combstruct[count](spec,size=n), n=0..20);
# second Maple program:
b:= proc(n, m) option remember; `if`(n=0,
     (m+1)^(m-1), m*b(n-1, m)+b(n-1, m+1))
    end:
a:= n-> b(n, 0):
seq(a(n), n=0..27);  # Alois P. Heinz, Jul 15 2022

CoefficientList[Series[-LambertW[-E^x+1]/(E^x-1), {x, 0, 20}], x]* Range[0, 20]! (* Vaclav Kotesovec, Nov 27 2012 *)
f[0, ] = 1; f[k, x_] := f[k, x] = Exp[Sum[x^m/m!*f[k-m, x], {m, 1, k}]];
(* b = A135302 *) b[0, 0] = 1; b[, 0] = 0; b[n, k_] := SeriesCoefficient[ f[k, x], {x, 0, n}]*n!;
a[n_] := b[n, n];
a /@ Range[0, 20] (* Jean-François Alcover, Oct 14 2019 *)

{Stirling2(n, k)=n!*polcoeff(((exp(x+x*O(x^n))-1)^k)/k!, n)}
{a(n)=local(A=1+x); for(i=1, n, A=sum(m=0, n, sum(k=0, m, Stirling2(m, k)*(A+x*O(x^n))^k)*x^m/m!)); n!*polcoeff(A, n)} \\ Paul D. Hanna, Mar 09 2013

x='x+O('x^30); Vec(serlaplace(-lambertw(-exp(x)+1)/(exp(x)-1))) \\ G. C. Greubel, Feb 19 2018

a(n) = Sum_{k=0..n} Stirling2(n, k)*(k+1)^(k-1). - Vladeta Jovovic, Nov 12 2003
a(n) ~ sqrt(1+exp(1)) * n^(n-1) / (exp(n-1)*(log(1+exp(1))-1)^(n-1/2)). - Vaclav Kotesovec, Nov 27 2012
E.g.f. A(x) satisfies: A(x) = Sum_{n>=0} x^n/n! * Sum_{k=0..n} Stirling2(n,k) * A(x)^k. - Paul D. Hanna, Mar 09 2013
E.g.f. A(x) satisfies: A(x) = exp((exp(x) - 1)*A(x)). - Ilya Gutkovskiy, Apr 04 2019

Edited by Alois P. Heinz, Nov 21 2010

A027637 a(n) = Product_{i=1..n} (4^i - 1).

Original entry on oeis.org

1, 3, 45, 2835, 722925, 739552275, 3028466566125, 49615367752825875, 3251543125681443718125, 852369269595510700600441875, 893773106866112632882108339078125, 3748755223447856814435325652920396921875

Offset: 0

N. J. A. Sloane

The q-analog of double factorials (A000165) evaluated at q=2. - Michael Somos, Sep 12 2014
3^n*5^(floor(n/2))|a(n) for n>=1. - G. C. Greubel, Nov 21 2015
Given probability p = 1/4^n that an outcome will occur at the n-th stage of an infinite process, then starting at n=1, 1-a(n)/A053763(n+1) is the probability that the outcome has occurred up to and including the n-th iteration. The limiting ratio is 1-A100221 ~ 0.3114625. - Bob Selcoe, Mar 01 2016

G. C. Greubel, Table of n, a(n) for n = 0..50

Cf. A000165.
Sequences of the form q-Pochhammer(n, q, q): A005329 (q=2), A027871 (q=3), this sequence (q=4), A027872 (q=5), A027873 (q=6), A027875 (q=7), A027876 (q=8), A027877 (q=9), A027878 (q=10), A027879 (q=11), A027880 (q=12).
Cf. A053763, A100221.

[1] cat [&*[4^k-1: k in [1..n]]: n in [1..11]]; // Vincenzo Librandi, Dec 24 2015

A027637 := proc(n)
    mul( 4^i-1,i=1..n) ;
end proc:
seq(A027637(n),n=0..8) ;

A027637 = Table[Product[4^i - 1, {i, n}], {n, 0, 9}] (* Alonso del Arte, Nov 14 2011 *)
a[ n_] := If[ n < 0, 0, Product[ (q^(2 k) - 1) / (q - 1), {k, n}] /. q -> 2]; (* Michael Somos, Sep 12 2014 *)
Abs@QPochhammer[4, 4, Range[0, 10]] (* Vladimir Reshetnikov, Nov 20 2015 *)

a(n) = prod(i=1, n, 4^i-1); \\ Michel Marcus, Nov 21 2015

from sage.combinat.q_analogues import q_pochhammer
def A027637(n): return (-1)^n*q_pochhammer(n, 4, 4)
[A027637(n) for n in (0..15)] # G. C. Greubel, Aug 04 2022

a(n) ~ c * 2^(n*(n+1)), where c = Product_{k>=1} (1-1/4^k) = A100221 = 0.688537537120339715456514357293508184675549819378... . - Vaclav Kotesovec, Nov 21 2015
a(n) = 4^(binomial(n+1,2))*(1/4;1/4){n} = (4; 4){n}, where (a;q){n} is the q-Pochhammer symbol. - _G. C. Greubel, Dec 24 2015
G.f.: Sum_{n>=0} 4^(n*(n+1)/2)*x^n / Product_{k=0..n} (1 + 4^k*x). - Ilya Gutkovskiy, May 22 2017
Sum_{n>=0} (-1)^n/a(n) = A100221. - Amiram Eldar, May 07 2023

A003027 Number of weakly connected digraphs with n labeled nodes.

Original entry on oeis.org

1, 3, 54, 3834, 1027080, 1067308488, 4390480193904, 72022346388181584, 4721717643249254751360, 1237892809110149882059440768, 1298060596773261804821355107253504, 5444502293680983802677246555274553481984, 91343781554246596956424128384394531707099632640

Offset: 1

N. J. A. Sloane

R. W. Robinson, Counting labeled acyclic digraphs, pp. 239-273 of F. Harary, editor, New Directions in the Theory of Graphs. Academic Press, NY, 1973.
N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).

T. D. Noe, Table of n, a(n) for n=1..30
A. Iványi, Leader election in synchronous networks, Acta Univ. Sapientiae, Mathematica, 5, 2 (2013) 54-82.

The unlabeled case is A003085.
Row sums of A062735.
Cf. A053763 (not necessarily connected), A003030 (strongly connected).

b:= n-> 2^(n^2-n):
a:= proc(n) option remember; local k; `if`(n=0, 1,
      b(n)- add(k*binomial(n,k) *b(n-k)*a(k), k=1..n-1)/n)
    end:
seq(a(n), n=1..20);  # Alois P. Heinz, Oct 21 2012

Range[0, 20]! CoefficientList[Series[D[1 + Log[Sum[2^(n^2 - n) x^n/n!, {n, 0, 20}]], x], {x, 0,20}], x]
c[n_]:=2^(n(n-1))-Sum[k Binomial[n,k]c[k] 2^((n-k)(n-k-1)),{k,1,n-1}]/n;c[0]=1;Table[c[i],{i,0,20}]  (* Geoffrey Critzer, Oct 24 2012 *)

v=Vec(log(sum(n=0, default(seriesprecision), 2^(n^2-n)*x^n/n!))); for(i=1, #v, v[i]*=(i-1)!); v \\ Charles R Greathouse IV, Feb 14 2011

b = lambda n: 2^(n^2-n)
@cached_function
def A003027(n):
    return b(n) - sum(k*binomial(n, k)*b(n-k)*A003027(k) for k in (1..n-1)) / n
[A003027(n) for n in (1..13)] # Peter Luschny, Jan 18 2016

a(n) = A062738(n)/2^n, since binary relations = digraphs with loops. - Ralf Stephan and Vladeta Jovovic, Mar 24 2004
E.g.f.: log(sum n>=0, 2^(n^2-n)*x^n/n!).
a(n) = A053763(n) - (1/n) * Sum_{k=1..n-1} k*C(n,k)*a(k)*A053763(n-k). - Geoffrey Critzer, Oct 24 2012

Corrected and extended by Vladeta Jovovic, Goran Kilibarda

A053291 Nonsingular n X n matrices over GF(4).

Original entry on oeis.org

1, 3, 180, 181440, 2961100800, 775476766310400, 3251791214634074112000, 218210695042457748180566016000, 234298374547168764346587444978647040000, 4025200069765920285793155323595159699896401920000, 1106437515026051855463365435310419366987397763763798016000000

Offset: 0

Stephen G Penrice, Mar 04 2000

Vincenzo Librandi, Table of n, a(n) for n = 0..40

Cf. A002884, A003788, A027637, A053763, A053290, A053292, A053293.

Cf. A100221, A115490.

[1] cat [&*[(4^n - 4^k): k in [0..n-1]]: n in [1..8]]; // Bruno Berselli, Jan 28 2013

Table[Product[4^n - 4^k, {k,0,n-1}], {n,0,10}] (* Geoffrey Critzer, Jan 26 2013 *)

for(n=0,10, print1(prod(k=0,n-1, 4^n - 4^k), ", ")) \\ G. C. Greubel, May 31 2018

a(n) = (4^n - 1)*(4^n - 4)*...*(4^n - 4^(n-1)).
a(n) = A053763(n)*A027637(n). - Bruno Berselli, Jan 30 2013
From Amiram Eldar, Jul 06 2025: (Start)
a(n) = Product_{k=1..n} A115490(k).
a(n) ~ c * 4^(n^2), where c = A100221. (End)

More terms from Vladeta Jovovic, Mar 16 2000

A053764 a(n) = 3^(n^2 - n).

Original entry on oeis.org

1, 1, 9, 729, 531441, 3486784401, 205891132094649, 109418989131512359209, 523347633027360537213511521, 22528399544939174411840147874772641, 8727963568087712425891397479476727340041449, 30432527221704537086371993251530170531786747066637049, 955004950796825236893190701774414011919935138974343129836853841, 269721605590607563262106870407286853611938890184108047911269431464974473521

Offset: 0

Stephen G Penrice, Mar 29 2000

Number of nilpotent n X n matrices X over GF(3), that is, the number of n X n matrices X over GF(3) satisfying X^k = 0 for some k >= 1.
More generally, Fine and Herstein prove that the probability that an n X n matrix over GF(p^m) is nilpotent is 1/p^(mn) and the probability that an n X n matrix over Z/mZ is nilpotent is 1/k^n, where k is the product of the distinct prime factors of m.
Is this the same sequence (apart from the initial term) as A053854? - Philippe Deléham, Dec 09 2007
[1,9,729,531441,3486784401,...] is the Hankel transform of A005159. - Philippe Deléham, Dec 10 2007

Vincenzo Librandi, Table of n, a(n) for n = 0..46
N. J. Fine and I. N. Herstein, The probability that a matrix be nilpotent, Illinois J. Math., 2 (1958), 499-504.
Joël Gay and Vincent Pilaud, The weak order on Weyl posets, arXiv:1804.06572 [math.CO], 2018.
M. Gerstenhaber, On the number of nilpotent matrices with coefficients in a finite field, Illinois J. Math., Vol. 5 (1961), 330-333.

Cf. A053763, A380592.

Table[(3^(n^2 - n)), {n, 0, 20}] (* Vincenzo Librandi, Feb 24 2014 *)

a(n) = 3^(n^2 - n); \\ Joerg Arndt, Feb 23 2014

Sequence given by the Hankel transform (see A001906 for definition) of A082181 = {1, 1, 10, 109, 1270, 15562, 198100, ...}; example: det([1, 1, 10, 109; 1, 10, 109, 1270; 10, 109, 1270, 15562; 109, 1270, 15562, 198100]) = 9^6 = 531441. - Philippe Deléham, Aug 20 2005

More terms from James Sellers, Apr 08 2000

A326225 Number of Hamiltonian unlabeled n-vertex digraphs (without loops).

Original entry on oeis.org

0, 1, 1, 4, 61, 3725, 844141, 626078904

Offset: 0

Gus Wiseman, Jun 15 2019

A digraph is Hamiltonian if it contains a directed cycle passing through every vertex exactly once.

			Non-isomorphic representatives of the a(3) = 4 digraph edge-sets:
  {12,23,31}
  {12,13,21,32}
  {12,13,21,23,31}
  {12,13,21,23,31,32}

The labeled case is A326219.
The case with loops is A326226.
The undirected case is A003216.
Non-Hamiltonian unlabeled digraphs (without loops) are A326222.
Cf. A000595, A002416, A003087, A003216, A053763, A246446, A326204, A326218, A326223.

a(5)-a(7) from Sean A. Irvine, Jun 16 2019

cp's OEIS Frontend

A054545 Number of labeled digraphs on n unisolated nodes (inverse binomial transform of A053763).

Views

Author

Keywords

Examples

Links

Crossrefs

Programs

Mathematica

PARI

Formula

Extensions

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

A002416 a(n) = 2^(n^2).

Views

Author

Keywords

Comments

Examples

References

Links

Crossrefs

Programs

GAP

Magma

Mathematica

PARI

PARI

Sage

Formula

A151374 Number of walks within N^2 (the first quadrant of Z^2) starting at (0, 0), ending on the vertical axis and consisting of 2n steps taken from {(-1, -1), (-1, 0), (1, 1)}.

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Magma

Maple

Mathematica

PARI

Sage

Formula

A052880 Expansion of e.g.f.: LambertW(1-exp(x))/(1-exp(x)).

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Maple

Mathematica

PARI

PARI

Formula

Extensions

A027637 a(n) = Product_{i=1..n} (4^i - 1).

Views

Author

Keywords