

A053763


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


48



1, 1, 4, 64, 4096, 1048576, 1073741824, 4398046511104, 72057594037927936, 4722366482869645213696, 1237940039285380274899124224, 1298074214633706907132624082305024, 5444517870735015415413993718908291383296, 91343852333181432387730302044767688728495783936
(list;
graph;
refs;
listen;
history;
text;
internal format)



OFFSET

0,3


COMMENTS

Nilpotent n X n matrices over GF(2). Also number of simple digraphs (without selfloops) on n labeled nodes (see also A002416).
For n >= 1 a(n) is the size of the Sylow 2subgroup of the Chevalley group A_n(4) (sequence A053291).  Ahmed Fares (ahmedfares(AT)mydeja.com), Apr 30 2001
(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
The number of reflexive binary relations on an nelement set.  Justin Witt (justinmwitt(AT)gmail.com), Jul 12 2005
From Rick L. Shepherd, Dec 24 2008: (Start)
Number of gift exchange scenarios where, for each person k of n people,
i) k gives gifts to g(k) of the others, where 0 <= g(k) <= n1,
ii) k gives no more than one gift to any specific person,
iii) k gives no single gift to two or more people and
iv) there is no other person j such that j and k jointly give a single gift.
(In other words  but less precisely  each person k either gives no gifts or gives exactly one gift per person to 1 <= g(k) <= n1 others.) (End)
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 selfloops) 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


REFERENCES

J. L. Gross and J. Yellen, eds., Handbook of Graph Theory, CRC Press, 2004; p. 521.
F. Harary and E. M. Palmer, Graphical Enumeration, Academic Press, NY, 1973, p. 5, Eq. (1.1.5).


LINKS

T. D. Noe, Table of n, a(n) for n = 0..35
Marcus Brinkmann, Extended Affine and CCZ Equivalence up to Dimension 4, Ruhr University Bochum (2019).
N. J. Fine and I. N. Herstein, The probability that a matrix be nilpotent, Illinois J. Math., 2 (1958), 499504.
Murray Gerstenhaber, On the number of nilpotent matrices with coefficients in a finite field, Illinois J. Math., Vol. 5 (1961), 330333.
Antal Iványi, Leader election in synchronous networks, Acta Univ. Sapientiae, Mathematica, 5, 2 (2013) 5482.
Greg Kuperberg, Symmetry classes of alternatingsign matrices under one roof, Annals of mathematics, Second Series, Vol. 156, No. 3 (2002), pp. 835866, arXiv preprint, arXiv:math/0008184 [math.CO], 20002001 (see Th. 3).
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.


FORMULA

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
a(n) = 4^binomial(n, n2).  Zerinvary Lajos, Jun 16 2007
a(n) = Sum_{i=0..n^2n} binomial(n^2n, i).  Rick L. Shepherd, Dec 24 2008
G.f. A(x) satisfies: A(x) = 1 + x * A(4*x).  Ilya Gutkovskiy, Jun 04 2020
Sum_{n>=1} 1/a(n) = A319016.  Amiram Eldar, Oct 27 2020


EXAMPLE

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


MAPLE

seq(4^(binomial(n, n2)), n=0..12); # Zerinvary Lajos, Jun 16 2007
a:=n>mul(4^j, j=1..n1): seq(a(n), n=0..12); # Zerinvary Lajos, Oct 03 2007


MATHEMATICA

Table[2^(2*Binomial[n, 2]), {n, 0, 20}] (* Geoffrey Critzer, Oct 04 2012 *)


PROG

(PARI) a(n)=1<<(n^2n) \\ Charles R Greathouse IV, Nov 20 2012


CROSSREFS

Cf. A053773, A006125, A000273, A000984, A002416, A319016.
Sequence in context: A088065 A053718 A053773 * A193611 A193755 A194501
Adjacent sequences: A053760 A053761 A053762 * A053764 A053765 A053766


KEYWORD

easy,nonn,nice


AUTHOR

Stephen G. Penrice (spenrice(AT)ets.org), Mar 29 2000


STATUS

approved



