A123554 -id:A123554 - cp's OEIS frontend

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

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

Offset: 0

Stephen G Penrice, Mar 29 2000

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

			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

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).

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.

Row sums of A123554, A189898, A346412, A346214.

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

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

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

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

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

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

A057273 Triangle T(n,k) of the number of strongly connected digraphs on n labeled nodes and with k arcs, k=0..n*(n-1).

Original entry on oeis.org

1, 0, 0, 1, 0, 0, 0, 2, 9, 6, 1, 0, 0, 0, 0, 6, 84, 316, 492, 417, 212, 66, 12, 1, 0, 0, 0, 0, 0, 24, 720, 6440, 26875, 65280, 105566, 122580, 106825, 71700, 37540, 15344, 4835, 1140, 190, 20, 1, 0, 0, 0, 0, 0, 0, 120, 6480, 107850, 868830, 4188696, 13715940

Offset: 1

Vladeta Jovovic, Goran Kilibarda, Sep 14 2000

			Triangle begins:
  [1] 1;
  [2] 0,0,1;
  [3] 0,0,0,2,9,6,1;
  [4] 0,0,0,0,6,84,316,492,417,212,66,12,1;
  ...
Number of strongly connected digraphs on 3 labeled nodes is 18 = 2+9+6+1.

Archer, K., Gessel, I. M., Graves, C., & Liang, X. (2020). Counting acyclic and strong digraphs by descents. Discrete Mathematics, 343(11), 112041. See Table 2.

Andrew Howroyd, Table of n, a(n) for n = 1..2680 (rows 1..20)
Kassie Archer, Ira M. Gessel, Christina Graves, and Xuming Liang, Counting acyclic and strong digraphs by descents, arXiv:1909.01550 [math.CO], 20 Mar 2020. See Table 2.

Row sums give A003030.
The unlabeled version is A057276.
Cf. A057271, A057272, A057274, A057275, A062735.
Cf. A123554, A339590, A339807.

B(nn, e=2)={my(v=vector(nn)); for(n=1, nn, v[n] = e^(n*(n-1)) - sum(k=1, n-1, binomial(n,k)*e^((n-1)*(n-k))*v[k])); v}
Strong(n, e=2)={my(u=B(n, e), v=vector(n)); v[1]=1; for(n=2, #v, v[n] = u[n] + sum(j=1, n-1, binomial(n-1, j-1)*u[n-j]*v[j])); v}
row(n)={ Vecrev(Strong(n, 1+'y)[n]) }
{ for(n=1, 5, print(row(n))) } \\ Andrew Howroyd, Jan 10 2022

Terms a(46) and beyond from Andrew Howroyd, Jan 10 2022

A062735 Triangular array T(n,k) giving number of weakly connected digraphs with n labeled nodes and k arcs (n >= 1, 0 <= k <= n(n-1)).

Original entry on oeis.org

1, 0, 2, 1, 0, 0, 12, 20, 15, 6, 1, 0, 0, 0, 128, 432, 768, 920, 792, 495, 220, 66, 12, 1, 0, 0, 0, 0, 2000, 11104, 33880, 73480, 123485, 166860, 184426, 167900, 125965, 77520, 38760, 15504, 4845, 1140, 190, 20, 1, 0, 0, 0, 0, 0, 41472, 337920, 1536000, 5062080

Offset: 1

Vladeta Jovovic, Jul 12 2001

			1;
0, 2, 1;
0, 0, 12, 20,   15,    6,      1;
0, 0, 0, 128,  432,  768,    920,    792,    495,    220,     66,    12, 1;
0, 0, 0,   0, 2000, 11104, 33880,  73480, 123485, 166860, 184426, 167900, ...;
0, 0, 0,   0,    0, 41472, 337920,1536000,5062080,.. ;
0, 0, 0,   0,    0,     0, 1075648,...

Andrew Howroyd, Table of n, a(n) for n = 1..2680 (rows 1..20)
R. J. Mathar, Statistics on Small Graphs, arXiv:1709.09000 [math.CO], 2017; Table 76.

Cf. A003027 (row sums), A054733 (unlabeled case), A057273 (strongly connected), A097629 (diagonal), A123554 (not necessarily connected).

nn=7;s=Sum[(1+y)^(n^2-n) x^n/n!,{n,0,nn}];Range[0,nn]!CoefficientList[Series[Log[ s]+1,{x,0,nn}],{x,y}]//Grid  (* returns triangle indexed from n = 0, Geoffrey Critzer, Oct 07 2012 *)

row(n)={Vecrev(n!*polcoef(1 + log(sum(k=0, n, (1+y)^(k*(k-1))*x^k/k!, O(x*x^n))), n))}
{ for(n=0, 5, print(row(n))) } \\ Andrew Howroyd, Jan 11 2022

E.g.f.: 1+log( Sum_{n >= 0, k >= 0} binomial(n*(n-1), k)*x^n/n!*y^k ).

A054547 Triangular array giving number of labeled digraphs on n unisolated nodes and k=0..n*(n-1) arcs.

Original entry on oeis.org

0, 0, 2, 1, 0, 0, 12, 20, 15, 6, 1, 0, 0, 12, 140, 435, 768, 920, 792, 495, 220, 66, 12, 1, 0, 0, 0, 240, 2520, 11604, 34150, 73560, 123495, 166860, 184426, 167900, 125965, 77520, 38760, 15504, 4845, 1140, 190, 20, 1

Offset: 1

Vladeta Jovovic, Apr 09 2000

			Triangle T(n,k) begins:
  [0],
  [0,2,1],
  [0,0,12,20,15,6,1],
  [0,0,12,140,435,768,920,792,495,220,66,12,1],
  ...

Andrew Howroyd, Table of n, a(n) for n = 1..2680 (rows 1..20)

Row sums are A054545.
Column sums are A121252.
The unlabeled version is A350908.
Cf. A054548 (graphs), A062735, A123554.

row(n) = {Vecrev(sum(i=0, n, (-1)^(n-i)*binomial(n,i)*(1 + 'y)^(i*(i-1))), n*(n-1)+1)}
{ for(n=1, 6, print(row(n))) } \\ Andrew Howroyd, Jan 28 2022

T(n, k) = Sum_{i=0..n} (-1)^(n-i)*binomial(n, i)*binomial(i*(i-1), k).

cp's OEIS Frontend

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

Views

Author

Keywords

Comments

Examples

References

Links

Crossrefs

Programs

Maple

Mathematica

PARI

Python

Formula

A057273 Triangle T(n,k) of the number of strongly connected digraphs on n labeled nodes and with k arcs, k=0..n*(n-1).

Views

Author

Keywords

Examples

References

Links

Crossrefs

Programs

PARI

Extensions

A062735 Triangular array T(n,k) giving number of weakly connected digraphs with n labeled nodes and k arcs (n >= 1, 0 <= k <= n(n-1)).

Views

Author

Keywords

Examples

Links

Crossrefs

Programs

Mathematica

PARI

Formula

A054547 Triangular array giving number of labeled digraphs on n unisolated nodes and k=0..n*(n-1) arcs.

Views

Author

Keywords

Examples

Links

Crossrefs

Programs

PARI

Formula