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

1, 1, 4, 64, 4096, 1048576, 1073741824, 4398046511104, 72057594037927936, 4722366482869645213696, 1237940039285380274899124224, 1298074214633706907132624082305024, 5444517870735015415413993718908291383296, 91343852333181432387730302044767688728495783936

Offset: 0

Author

Stephen G Penrice, Mar 29 2000

Keywords

• easy
• nonn
• nice

Comments

Nilpotent n X n matrices over GF(2). Also number of simple digraphs (without self-loops) on n labeled nodes (see also A002416).

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

(-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 n-element 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) <= n-1,

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) <= n-1 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 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

Examples

			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
		

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), 499-504.
• Murray Gerstenhaber, On the number of nilpotent matrices with coefficients in a finite field, Illinois J. Math., Vol. 5 (1961), 330-333.
• Antal Iványi, Leader election in synchronous networks, Acta Univ. Sapientiae, Mathematica, 5, 2 (2013) 54-82.
• Pakawut Jiradilok, Some Combinatorial Formulas Related to Diagonal Ramsey Numbers, arXiv:2404.02714 [math.CO], 2024. See p. 19.
• Greg Kuperberg, Symmetry classes of alternating-sign matrices under one roof, Annals of mathematics, Second Series, Vol. 156, No. 3 (2002), pp. 835-866, arXiv preprint, arXiv:math/0008184 [math.CO], 2000-2001 (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.

Crossrefs

Row sums of A123554, A189898, A346412, A346214.

Cf. A053773, A006125, A000273, A000984, A002416, A319016.

Programs

Maple

seq(4^(binomial(n, n-2)), n=0..12); # Zerinvary Lajos, Jun 16 2007
a:=n->mul(4^j, j=1..n-1): 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 *)

PARI

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

Python

def A053763(n): return 1<Chai Wah Wu, Jul 05 2024

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, n-2). - Zerinvary Lajos, Jun 16 2007

a(n) = Sum_{i=0..n^2-n} binomial(n^2-n, 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

Sum_{n>=0} a(n)*u^n/A002884(n) = Product_{r>=1} 1/(1-u/q^r). - Geoffrey Critzer, Oct 28 2021