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

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

Offset: 0

Author

N. J. A. Sloane

Keywords

• nonn
• easy

Comments

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

Examples

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

References

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

Links

• 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

Crossrefs

Bisection of A060656.

Cf. A053763, A064062, A064231, A319015.

Programs

GAP

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

Magma

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

Mathematica

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

PARI

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

PARI

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

Sage

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

Formula

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