login
The OEIS Foundation is supported by donations from users of the OEIS and by a grant from the Simons Foundation.

 

Logo


Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
A053763 a(n) = 2^(n^2 - n). 48

%I

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

%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 Cf. A053773, A006125, A000273, A000984, A002416, A319016.

%K easy,nonn,nice

%O 0,3

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

Lookup | Welcome | Wiki | Register | Music | Plot 2 | Demos | Index | Browse | More | WebCam
Contribute new seq. or comment | Format | Style Sheet | Transforms | Superseeker | Recent
The OEIS Community | Maintained by The OEIS Foundation Inc.

License Agreements, Terms of Use, Privacy Policy. .

Last modified April 16 18:53 EDT 2021. Contains 343050 sequences. (Running on oeis4.)