|
%I #108 Apr 10 2024 10:42:58
%S 1,1,4,64,4096,1048576,1073741824,4398046511104,72057594037927936,
%T 4722366482869645213696,1237940039285380274899124224,
%U 1298074214633706907132624082305024,5444517870735015415413993718908291383296,91343852333181432387730302044767688728495783936
%N a(n) = 2^(n^2 - n).
%C Nilpotent n X n matrices over GF(2). Also number of simple digraphs (without self-loops) on n labeled nodes (see also A002416).
%C For n >= 1 a(n) is the size of the Sylow 2-subgroup of the Chevalley group A_n(4) (sequence A053291). - Ahmed Fares (ahmedfares(AT)my-deja.com), Apr 30 2001
%C (-1)^ceiling(n/2) * resultant of the Chebyshev polynomial of first kind of degree n and Chebyshev polynomial of first kind of degree (n+1) (cf. A039991). - _Benoit Cloitre_, Jan 26 2003
%C The number of reflexive binary relations on an n-element set. - Justin Witt (justinmwitt(AT)gmail.com), Jul 12 2005
%C From _Rick L. Shepherd_, Dec 24 2008: (Start)
%C Number of gift exchange scenarios where, for each person k of n people,
%C i) k gives gifts to g(k) of the others, where 0 <= g(k) <= n-1,
%C ii) k gives no more than one gift to any specific person,
%C iii) k gives no single gift to two or more people and
%C iv) there is no other person j such that j and k jointly give a single gift.
%C (In other words -- but less precisely -- each person k either gives no gifts or gives exactly one gift per person to 1 <= g(k) <= n-1 others.) (End)
%C In general, sequences of the form m^((n^2 - n)/2) enumerate the graphs with n labeled nodes with m types of edge. a(n) therefore is the number of labeled graphs with n nodes with 4 types of edge. To clarify the comment from Benoit Cloitre, dated Jan 26 2003, in this context: simple digraphs (without self-loops) have four types of edge. These types of edges are as follows: the absent edge, the directed edge from A -> B, the directed edge from B -> A and the bidirectional edge, A <-> B. - _Mark Stander_, Apr 11 2019
%D J. L. Gross and J. Yellen, eds., Handbook of Graph Theory, CRC Press, 2004; p. 521.
%D F. Harary and E. M. Palmer, Graphical Enumeration, Academic Press, NY, 1973, p. 5, Eq. (1.1.5).
%H T. D. Noe, <a href="/A053763/b053763.txt">Table of n, a(n) for n = 0..35</a>
%H Marcus Brinkmann, <a href="https://www.researchgate.net/publication/332564840_Extended_Affine_and_CCZ_Equivalence_Classes_up_to_Dimension_4">Extended Affine and CCZ Equivalence up to Dimension 4</a>, Ruhr University Bochum (2019).
%H N. J. Fine and I. N. Herstein, <a href="http://projecteuclid.org/euclid.ijm/1255454112">The probability that a matrix be nilpotent</a>, Illinois J. Math., 2 (1958), 499-504.
%H Murray Gerstenhaber, <a href="http://projecteuclid.org/euclid.ijm/1255629831">On the number of nilpotent matrices with coefficients in a finite field</a>, Illinois J. Math., Vol. 5 (1961), 330-333.
%H Antal Iványi, <a href="https://doi.org/10.2478/ausm-2014-0005">Leader election in synchronous networks</a>, Acta Univ. Sapientiae, Mathematica, 5, 2 (2013) 54-82.
%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 Greg Kuperberg, <a href="https://www.jstor.org/stable/3597283">Symmetry classes of alternating-sign matrices under one roof</a>, Annals of mathematics, Second Series, Vol. 156, No. 3 (2002), pp. 835-866, <a href="https://arxiv.org/abs/math/0008184">arXiv preprint</a>, arXiv:math/0008184 [math.CO], 2000-2001 (see Th. 3).
%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.
%F Sequence given by the Hankel transform (see A001906 for definition) of A059231 = {1, 1, 5, 29, 185, 1257, 8925, 65445, 491825, ...}; example: det([1, 1, 5, 29; 1, 5, 29, 185; 5, 29, 185, 1257; 29, 185, 1257, 8925]) = 4^6 = 4096. - _Philippe Deléham_, Aug 20 2005
%F a(n) = 4^binomial(n, n-2). - _Zerinvary Lajos_, Jun 16 2007
%F a(n) = Sum_{i=0..n^2-n} binomial(n^2-n, i). - _Rick L. Shepherd_, Dec 24 2008
%F G.f. A(x) satisfies: A(x) = 1 + x * A(4*x). - _Ilya Gutkovskiy_, Jun 04 2020
%F Sum_{n>=1} 1/a(n) = A319016. - _Amiram Eldar_, Oct 27 2020
%F Sum_{n>=0} a(n)*u^n/A002884(n) = Product_{r>=1} 1/(1-u/q^r). - _Geoffrey Critzer_, Oct 28 2021
%e a(2)=4 because there are four 2 x 2 nilpotent matrices over GF(2):{{0,0},{0,0}},{{0,1},{0,0}},{{0,0},{1,0}},{{1,1,},{1,1}} where 1+1=0. - _Geoffrey Critzer_, Oct 05 2012
%p seq(4^(binomial(n, n-2)), n=0..12); # _Zerinvary Lajos_, Jun 16 2007
%p a:=n->mul(4^j, j=1..n-1): seq(a(n), n=0..12); # _Zerinvary Lajos_, Oct 03 2007
%t Table[2^(2*Binomial[n,2]), {n,0,20}] (* _Geoffrey Critzer_, Oct 04 2012 *)
%o (PARI) a(n)=1<<(n^2-n) \\ _Charles R Greathouse IV_, Nov 20 2012
%Y Row sums of A123554, A189898, A346412, A346214.
%Y Cf. A053773, A006125, A000273, A000984, A002416, A319016.
%K easy,nonn,nice
%O 0,3
%A _Stephen G Penrice_, Mar 29 2000
|
