login
a(n) = 2^(n^2).
121

%I #113 Nov 06 2024 04:42:31

%S 1,2,16,512,65536,33554432,68719476736,562949953421312,

%T 18446744073709551616,2417851639229258349412352,

%U 1267650600228229401496703205376,2658455991569831745807614120560689152,22300745198530623141535718272648361505980416,748288838313422294120286634350736906063837462003712

%N a(n) = 2^(n^2).

%C For n >= 1, a(n) is the number of n X n (0, 1) matrices.

%C Also number of directed graphs on n labeled nodes allowing self-loops (cf. A053763).

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

%C Hankel transform of A064062. - _Philippe Deléham_, Nov 19 2007

%C a(n) is also the order of the semigroup (monoid) of all binary relations on an n-set. - _Abdullahi Umar_, Sep 14 2008

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

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

%D John M. Howie, Fundamentals of semigroup theory. Oxford: Clarendon Press, (1995). - _Abdullahi Umar_, Sep 14 2008

%H Vincenzo Librandi, <a href="/A002416/b002416.txt">Table of n, a(n) for n = 0..33</a>

%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 Theresia Eisenkölbl, <a href="https://arxiv.org/abs/math/0106038">2-Enumerations of halved alternating sign matrices</a>, arXiv:math/0106038 [math.CO], 2001.

%H Theresia Eisenkölbl, <a href="https://www.mat.univie.ac.at/~slc/wpapers/s46eisenko.html">2-Enumerations of halved alternating sign matrices</a>, Séminaire Lotharingien Combin. 46, (2001), Article B46c, 11 pp.

%H Daniele A. Gewurz and Francesca Merola, <a href="http://www.cs.uwaterloo.ca/journals/JIS/VOL6/Gewurz/gewurz5.html">Sequences realized as Parker vectors of oligomorphic permutation groups</a>, J. Integer Seqs., Vol. 6, 2003.

%H F. Harary and R. W. Robinson, <a href="http://dx.doi.org/10.4153/CJM-1979-007-3">Labeled bipartite blocks</a>, Canad. J. Math., 31 (1979), 60-68.

%H S. R. Kannan and Rajesh Kumar Mohapatra, <a href="https://arxiv.org/abs/1909.13678">Counting the Number of Non-Equivalent Classes of Fuzzy Matrices Using Combinatorial Techniques</a>, arXiv:1909.13678 [math.GM], 2019.

%H Kent E. Morrison, <a href="http://www.cs.uwaterloo.ca/journals/JIS/VOL9/Morrison/morrison37.html">Integer Sequences and Matrices Over Finite Fields</a>, Journal of Integer Sequences, Vol. 9 (2006), Article 06.2.1.

%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 Eric Weisstein's World of Mathematics, <a href="http://mathworld.wolfram.com/01-Matrix.html">01-Matrix</a>.

%H <a href="/index/Di#divseq">Index to divisibility sequences</a>

%F G.f. satisfies: A(x) = 1 + 2*x*A(4x). - _Paul D. Hanna_, Dec 04 2009

%F 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 a<b in an n X n binary matrix. Cf. A027465, A013610. - _Geoffrey Critzer_, Nov 05 2024

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

%F a(n) = [x^n] 1/(1 - 2^n*x). - _Ilya Gutkovskiy_, Oct 10 2017

%F Sum_{n>=0} 1/a(n) = A319015. - _Amiram Eldar_, Oct 14 2020

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

%t Table[2^(n^2), {n,0,15}] (* _Vladimir Joseph Stephan Orlovsky_, Dec 13 2008 *)

%o (PARI) a(n)=polresultant((x-1)^n,(x+1)^n,x) \\ _Ralf Stephan_

%o (PARI) a(n)=2^n^2 \\ _Charles R Greathouse IV_, Jun 23 2021

%o (Magma) [2^(n^2): n in [0..15]]; // _Vincenzo Librandi_, May 13 2011

%o (Sage) [2^(n^2) for n in (0..15)] # _G. C. Greubel_, Jul 03 2019

%o (GAP) List([0..15], n-> 2^(n^2) ) # _G. C. Greubel_, Jul 03 2019

%Y Bisection of A060656.

%Y Cf. A053763, A064062, A064231, A319015.

%K nonn,easy,changed

%O 0,2

%A _N. J. A. Sloane_