A002884 -id:A002884 - cp's OEIS frontend

A000409 Singular n X n (0,1)-matrices: the number of n X n (0,1)-matrices having distinct, nonzero ordered rows, but having at least two equal columns or at least one zero column.

0, 6, 350, 43260, 14591171, 14657461469, 46173502811223, 474928141312623525, 16489412944755088235117, 1985178211854071817861662307, 846428472480689964807653763864449, 1299141117072945982773752362381072143359, 7268140170419155675761326840423792818571154945, 149650282980396792665043455999899697765782372693740287

Offset: 2

N. J. A. Sloane

This is a lower bound for the set of all n X n (0,1)-matrices having distinct, nonzero ordered rows and determinant 0 (compare A000410).
Here ordered means that we take only one representative from the n! matrices obtained by all permutations of the distinct rows of an n X n matrix.
a(n) is also the number of sets of n distinct nonzero (0,1)-vectors in R^n that do not span R^n.

N. J. A. Sloane, A Handbook of Integer Sequences, Academic Press, 1973 (includes this sequence).
N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).

J. Kahn, J. Komlos and E. Szemeredi, On the probability that a random ±1-matrix is singular, J. AMS 8 (1995), 223-240.
Goran Kilibarda and Vladeta Jovovic, Enumeration of some classes of T_0-hypergraphs, arXiv:1411.4187 [math.CO], 2014.
J. Komlos, On the determinant of (0,1)-matrices, Studia Math. Hungarica 2 (1967), 7-21.
N. Metropolis and P. R. Stein, On a class of (0,1) matrices with vanishing determinants, J. Combin. Theory, 3 (1967), 191-198.
Index entries for sequences related to binary matrices

Cf. A000410, A002884, A046747.

[ -(&+[StirlingFirst(n+1,k+1)*Binomial(2^k-1,n): k in [0..n-1]]): n in [2..15]]; // G. C. Greubel, Jun 05 2020

with(combinat): T := proc(n) -sum(stirling1(n+1,k+1)*binomial(2^k-1,n),k=0..n-1); end proc:

a[n_] := -Sum[ StirlingS1[n+1, k+1]*Binomial[2^k-1, n], {k, 0, n-1}]; Table[a[n], {n, 2, 15}] (* Jean-François Alcover, Nov 21 2012, from formula *)

a(n) = -sum(k=0, n-1, stirling(n+1, k+1, 1)*binomial(2^k-1, n)); \\ Michel Marcus, Jun 05 2020

[sum((-1)^(n+k+1)*stirling_number1(n+1,k+1)*binomial(2^k-1,n) for k in (0..n-1)) for n in (2..15)] # G. C. Greubel, Jun 05 2020

a(n) = (-1)*Sum_{k=0..n-1} Stirling1(n+1, k+1)*binomial(2^k-1, n).

a(n) = binomial(2^n-1, n) - A094000(n). - Vladeta Jovovic, Nov 27 2005

Edited by W. Edwin Clark, Nov 02 2003

A052496 Number of nonsingular n X n matrices over GF(8).

Original entry on oeis.org

1, 7, 3528, 115379712, 241909719367680, 32467582052437076213760, 278893342293098904613804037898240, 153323163270070838469523866093442017326530560

Offset: 0

Vladeta Jovovic, Mar 16 2000

G. C. Greubel, Table of n, a(n) for n = 0..30

Cf. A027876, A109966.

Cf. A002884, A003791, A053290, A053291, A053292, A053293, A052497, A052498, A132036.

[1] cat [&*[(8^n-8^k): k in [0..n-1]]: n in [1..10]]; // Bruno Berselli, Jan 30 2013

Table[Product[(8^n - 8^j), {j, 0, n-1}], {n, 0, 10}] (* G. C. Greubel, May 14 2019 *)

{a(n) = prod(j=0,n-1, 8^n - 8^j)}; \\ G. C. Greubel, May 14 2019

[product(8^n - 8^j for j in (0..n-1)) for n in (0..10)] # G. C. Greubel, May 14 2019

a(n) = (8^n - 1)*(8^n - 8)*...*(8^n - 8^(n-1)).
a(n) = A109966(n)*A027876(n). - Bruno Berselli, Jan 30 2013
a(n) ~ c * 8^(n^2), where c = A132036. - Amiram Eldar, Jul 06 2025

A052497 Number of nonsingular n X n matrices over GF(9).

Original entry on oeis.org

1, 8, 5760, 339655680, 1624314979123200, 629282246371356907929600, 19747506525777609095698646040576000, 50195501537943419769100848121708339934527488000

Offset: 0

Vladeta Jovovic, Mar 16 2000

G. C. Greubel, Table of n, a(n) for n = 0..30
Jeffrey Overbey, William Traves, and Jerzy Wojdylo, On the Keyspace of the Hill Cipher, Cryptologia, Vol. 29, Iss. 1 (2005), pp. 59-72; author's copy.

Cf. A027877, A053764.

Cf. A002884, A003792, A053290, A053291, A053292, A053293, A052496, A052498, A132037.

[1] cat [&*[(9^n - 9^k): k in [0..n-1]]: n in [1..10]]; // Bruno Berselli, Jan 28 2013

Table[Product[(9^n - 9^j), {j, 0, n-1}], {n, 0, 10}] (* G. C. Greubel, May 14 2019 *)

{a(n) = prod(j=0,n-1, 9^n - 9^j)}; \\ G. C. Greubel, May 14 2019

[product(9^n - 9^j for j in (0..n-1)) for n in (0..10)] # G. C. Greubel, May 14 2019

a(n) = (9^n - 1)*(9^n - 9)*...*(9^n - 9^(n-1)).
a(n) = A053764(n)*A027877(n). - Bruno Berselli, Jan 30 2013
a(n) ~ c * 9^(n^2), where c = A132037. - Amiram Eldar, Jul 06 2025

A056989 Number of nonsingular n X n (-1,0,1)-matrices (over the reals).

Original entry on oeis.org

1, 2, 48, 11808, 27947520, 609653621760, 119288919620689920

Offset: 0

Eric W. Weisstein

It would be nice to have an estimate for the asymptotic rate of growth.

			a(1) = 2: [1], [ -1].
a(2) = 48: There are 8 choices for the first column, u (say) and then the 2nd column can be anything except 0, u, -u, so 6 choices, giving a total of 8*6 = 48.

Minfeng Wang, C++ program to calculate A056989
Eric Weisstein's World of Mathematics, Nonsingular Matrix
Index entries for sequences related to binary matrices

Cf. A055165, A053290, A056990, A055165, A002884, A046747, A057981, A060722.

(* A brute force solution up to n = 4 *) a[n_] := a[n] = (m = Array[x, {n, n}]; cnt = 0; iter = {#, -1, 1}& /@ Flatten[m]; Do[ If[ Det[m] != 0, cnt++], Evaluate[ Sequence @@ iter]]; cnt); Table[ Print[a[n]]; a[n], {n, 1, 4}] (* Jean-François Alcover, Oct 11 2012 *)

a(n) = A060722(n) - A057981(n). - Alois P. Heinz, Dec 02 2019

a(4) from Winston C. Yang (winston(AT)cs.wisc.edu), Aug 27 2000
Entry revised by N. J. A. Sloane, Jan 02 2007
a(5) from Giovanni Resta, Feb 20 2009
a(0)=1 prepended by Alois P. Heinz, Dec 02 2019
a(0)-a(5) confirmed and a(6) added by Minfeng Wang, May 01 2024

A296548 Triangle read by rows: T(n,k) is the number of diagonalizable n X n matrices over GF(2) that have rank k, n >= 0, 0 <= k <= n.

Original entry on oeis.org

1, 1, 1, 1, 6, 1, 1, 28, 28, 1, 1, 120, 560, 120, 1, 1, 496, 9920, 9920, 496, 1, 1, 2016, 166656, 714240, 166656, 2016, 1, 1, 8128, 2731008, 48377856, 48377856, 2731008, 8128, 1, 1, 32640, 44216320, 3183575040, 13158776832, 3183575040, 44216320, 32640, 1

Offset: 0

Geoffrey Critzer, Dec 15 2017

Equivalently, T(n,k) is the number of n X n matrices, P, over GF(2) with rank k, such that P^2 = P.

Equivalently, T(n,k) is the number of direct sum decompositions of the vector space GF(2)^n into exactly two subspaces U and W such that the dimension of U is k.

			Triangle T(n,k) begins:
  1;
  1,    1;
  1,    6,      1;
  1,   28,     28,      1;
  1,  120,    560,    120,      1;
  1,  496,   9920,   9920,    496,    1;
  1, 2016, 166656, 714240, 166656, 2016, 1;
  ...

Geoffrey Critzer, Combinatorics of Vector Spaces over Finite Fields, Master's thesis, Emporia State University, 2018.
Kent E. Morrison, Integer Sequences and Matrices Over Finite Fields, Journal of Integer Sequences, Vol. 9 (2006), Article 06.2.1.

Cf. A132186 (row sums).

b:= proc(n, k) option remember; `if`(k<0 or k>n, 0,
      `if`(n=0, 1, b(n-1, k-1)+2^k*b(n-1, k)))
    end:
T:= (n,k)-> 2^(k*(n-k))*b(n, k):
seq(seq(T(n, k), k=0..n), n=0..8);  # Alois P. Heinz, Dec 02 2024

nn = 8; g[n_] := (q - 1)^n  q^Binomial[n, 2] FunctionExpand[
    QFactorial[n, q]] /. q -> 2; Grid[Map[Select[#, # > 0 &] &,
  Table[g[n], {n, 0, nn}] CoefficientList[Series[Sum[(u z)^r/g[r] , {r, 0, nn}] Sum[z^r/g[r], {r, 0, nn}], {z, 0, nn}], {z, u}]]]

T(n,k)/A002884(n) is the coefficient of y^k*x^n in the expansion of Sum_{n>=0} x^n\A002884(n) * Sum_{n>=0} y*x^n\A002884(n).

T(n,k) = A002884(n)/(A002884(k)*A002884(n-k)) = A022166(n,k)*2^(k(n-k)).

A203303 Vandermonde determinant of the first n terms of (1,2,4,8,16,...).

Original entry on oeis.org

1, 1, 6, 1008, 20321280, 203199794380800, 4096245678214226116608000, 671169825411994707343327912777482240000, 3589459026274030507466469204160461571257625328222208000000, 2511229721141086754031154605327661795863172723306019839389105937236728217600000000

Offset: 1

Clark Kimberling, Jan 01 2012

nonn

Each term divides its successor, as in A002884. Indeed, 2*v(n+1)/v(n) divides v(n+2)/v(n+1), as in A171499.

Robert Israel, Table of n, a(n) for n = 1..22
Daniel M. Kane, Carlo Sanna, and Jeffrey Shallit, Waring's theorem for binary powers, arXiv:1801.04483 [math.NT], Jan 13 2018.

Cf. A000079, A002884, A171499.

[1] cat [(&*[(&*[2^(k+1) -2^j: j in [0..k]]): k in [0..n-2]]): n in [2..15]]; // G. C. Greubel, Aug 31 2023

# First program
with(LinearAlgebra):
a:= n-> Determinant(VandermondeMatrix([2^i$i=0..n-1])):
seq(a(n), n=1..12);  # Alois P. Heinz, Jul 23 2017
# Second program
f:= n -> 2^(n*(n-1)*(n-2)/6)*mul((2^k-1)^(n-k),k=1..n-1):
seq(f(n),n=1..12); # Robert Israel, Jan 16 2018

(* First program *)
f[j_]:= 2^(j-1); z = 15;
v[n_]:= Product[Product[f[k] - f[j], {j,k-1}], {k,2,n}]
Table[v[n], {n,z}]                     (* A203303 *)
Table[v[n+1]/v[n], {n,z}]              (* A002884 *)
Table[v[n]*v[n+2]/(2*v[n+1]^2), {n,z}]  (* A171499 *)
Table[FactorInteger[v[n]], {n,z}]
(* Second program *)
Table[Product[2^(k+1) -2^j, {k,0,n-2}, {j,0,k}], {n,15}] (* G. C. Greubel, Aug 31 2023 *)

[product(product(2^(k+1) -2^j for j in range(k+1)) for k in range(n-1)) for n in range(1,16)] # G. C. Greubel, Aug 31 2023

From Robert Israel, Jan 16 2018: (Start)
a(n) = Product_{0 <= i < j <= n-1} (2^j - 2^i).
a(n) = 2^(n*(n-1)*(n-2)/6) * Product_{1<=k<=n-1} (2^k-1)^(n-k). (End)
a(n) ~ 1/A335011 * 2^(n*(n-1)*(2*n-1)/6) * QPochhammer(1/2)^n. - Vaclav Kotesovec, May 19 2020
a(n) = Product_{k=0..n-2} ( 2^(k+1)^2 * QPochhammer(2^(-k-1); 2; k+1) ). - G. C. Greubel, Aug 31 2023

A286331 Triangle read by rows: T(n,k) is the number of n X n matrices of rank k over F_2.

Original entry on oeis.org

1, 1, 1, 1, 9, 6, 1, 49, 294, 168, 1, 225, 7350, 37800, 20160, 1, 961, 144150, 4036200, 19373760, 9999360, 1, 3969, 2542806, 326932200, 8543828160, 39687459840, 20158709760, 1, 16129, 42677334, 23435953128, 2812314375360, 71124337751040, 325139829719040, 163849992929280

Offset: 0

Geoffrey Critzer, May 07 2017

			Triangle T(n,k) begins:
  1;
  1,   1;
  1,   9,      6;
  1,  49,    294,     168;
  1, 225,   7350,   37800,    20160;
  1, 961, 144150, 4036200, 19373760, 9999360;
  ...
T(2,1) = 9 because there are 9, 2 X 2 matrices in F_2 that have rank 1: {{0, 0}, {0, 1}}, {{0, 0}, {1, 0}}, {{0, 0}, {1, 1}}, {{0, 1}, {0, 0}}, {{0, 1}, {0, 1}}, {{1, 0},  {0, 0}}, {{1, 0}, {1, 0}}, {{1,1}, {0, 0}}, {{1, 1}, {1, 1}}.

Robert Israel, Table of n, a(n) for n = 0..1710 (rows 0 to 57, flattened)
Geoffrey Critzer, Combinatorics of Vector Spaces over Finite Fields, Master's thesis, Emporia State University, 2018.
Kent E. Morrison, Integer Sequences and Matrices Over Finite Fields, Journal of Integer Sequences, Vol. 9 (2006), Article 06.2.1.
Wikipedia, q-binomial

Main diagonal is A002884.
Column for k = 1 is A060867.
Row sums are A002416.

T:= (n,k) -> mul((2^n-2^j)^2/(2^k-2^j),j=0..k-1):
seq(seq(T(n,k),k=0..n),n=0..10); # Robert Israel, May 15 2017

q = 2; Table[Table[Product[(q^n - q^i)^2/(q^k - q^i), {i, 0, k - 1}], {k, 0, n}], {n, 0, 6}] // Grid

T(n,k) = Product_{j=0..k-1} (2^n - 2^j)^2/(2^k - 2^j) = A022166(n,k) * Product_{j=0..k-1} (2^n - 2^j).

A034383 Number of labeled groups.

Original entry on oeis.org

1, 2, 3, 16, 30, 480, 840, 22080, 68040, 1088640, 3991680, 259459200, 518918400, 16605388800, 163459296000, 10353459916800, 22230464256000, 1867358997504000, 6758061133824000, 648773868847104000, 5474029518397440000, 122618261212102656000

Offset: 1

Christian G. Bower

nonn

From Jianing Song, Mar 02 2024: (Start)
In other words, number of ways to define a group structure on a set of n elements. Note that for a group G, a group structure on the set G is given by mapping (x,y) to sigma^(-1)(sigma(x)*sigma(y)), where sigma is a bijection on the set G; sigma and sigma' give the same structure if and only if sigma' is the composition of a group automorphism of G and sigma.
By definition, a(n) = A034381(n) if n in A003277, otherwise a(n) > A034381(n). The indices of records of a(n)/A034381(n) among the known terms are 1, 4, 8, 16, 24, 32, 48, 64, 96, 128, 192, with a(192)/A034381(192) = 122774329/1640520 ~ 74.8.
Also by definition, a(n) >= A000001(n)*n!/A059773(n). If the conjecture A059773(2^r) = A002884(r) is true, then A059773(2^r) <= 2^(r^2), while A000001(2^r) >= 2^((2/27)*r^2*(r-6)) (see the Math Stack Exchange link below), so a(2^r)/A034381(2^r) tends to infinity quickly as r tends to infinity.
The sequence is strictly increasing for the first 256 terms (a(256) > A034381(256) > A034381(255) = a(255) since 255 is in A003277). On the other hand, assuming that A059773(2^r) = A002884(r), then a(2^20)/(2^20)! >= A000001(2^20)/A002884(20) > 99798.4, while a(2^20+1)/(2^20)! = A034381(2^20+1)/(2^20)! = (2^20+1)/phi(2^20+1) since 2^20+1 = 17*61681 is in A003277, so we would have a(2^20) > a(2^20+1). It is conjectured a(2^r) > a(2^r+1) for all sufficiently large r. (End)

Stephen A. Silver, Table of n, a(n) for n = 1..255
H. U. Besche, The Small Groups library
Math Stack Exchange, Known bounds for the number of groups of a given order.
Index entries for sequences related to groups

Cf. A000001, A034381, A034382, A058157, A058163.

A034383 := function(n) local fn, sum, k; fn := Factorial(n); sum := 0; for k in [1 .. NrSmallGroups(n)] do sum := sum + fn / Size(AutomorphismGroup(SmallGroup(n,k))); od; return sum; end; # Stephen A. Silver, Feb 10 2013

a(n) = n * A058163(n).

a(n) = Sum n!/|Aut(G)|, where the sum is taken over the different products G of cyclic groups with |G| = n.

More terms from Stephen A. Silver, Feb 10 2013

A052498 Number of nonsingular n X n matrices over GF(11).

Original entry on oeis.org

1, 10, 13200, 2124276000, 41393302251840000, 97602635428252959312000000, 27847155251069188894843979022720000000, 961359275427083998992553051820498439890246400000000

Offset: 0

Vladeta Jovovic, Mar 16 2000

Vincenzo Librandi, Table of n, a(n) for n = 0..30

Cf. A027879, A110195.

Cf. A002884, A053290, A053291, A053292, A053293, A052496, A052497, A132267.

[1] cat [&*[(11^n - 11^k): k in [0..n-1]]: n in [1..10]]; // Bruno Berselli, Jan 28 2013

Table[Product[11^n - 11^k, {k, 0, n-1}], {n, 0, 10}] (* Vincenzo Librandi, Jan 28 2013 *)

{a(n) = prod(j=0,n-1, 11^n - 11^j)}; \\ G. C. Greubel, May 14 2019

[product(11^n - 11^j for j in (0..n-1)) for n in (0..10)] # G. C. Greubel, May 14 2019

a(n) = (11^n - 1)*(11^n - 11)*...*(11^n - 11^(n-1)).
a(n) = A110195(n)*A027879(n). - Bruno Berselli, Jan 30 2013
a(n) ~ c * 11^(n^2), where c = A132267. - Amiram Eldar, Jul 06 2025

A083402 Let A_n be the upper triangular matrix in the group GL(n,2) that has zero entries below the main diagonal and 1 elsewhere; a(n) is the size of the conjugacy class of this matrix in GL(n,2).

Original entry on oeis.org

1, 3, 42, 2520, 624960, 629959680, 2560156139520, 41781748196966400, 2732860586067178291200, 715703393163961188325785600, 750102961052993818881476159078400, 3145391744524297920839316348340273152000, 52764474940208177704130232748554603290689536000

Offset: 1

Yuval Dekel (dekelyuval(AT)hotmail.com), Jun 12 2003

nonn

			For example for n=4 the matrix is / 1,1,1,1 / 0,1,1,1 / 0,0,1,1 / 0,0,0,1 /.

Eric M. Schmidt, Table of n, a(n) for n = 1..30

Cf. A002884, A070731, A082877, A062383.

a:= n-> 2^((n-1)*(n-2)/2) *mul(2^k-1, k=1..n):
seq(a(n), n=1..15);  # Alois P. Heinz, May 14 2013

a[n_] := 2^((n-1)*(n-2)/2)*Product[2^k-1, {k, 1, n}]; Table[a[n], {n, 1, 15}] (* Jean-François Alcover, Feb 17 2014, after Alois P. Heinz *)

a(n) = A002884(n) / 2^(n-1).

More terms from Eric M. Schmidt, May 14 2013

cp's OEIS Frontend

A000409 Singular n X n (0,1)-matrices: the number of n X n (0,1)-matrices having distinct, nonzero ordered rows, but having at least two equal columns or at least one zero column.

Views

Author

Keywords

Comments

References

Links

Crossrefs

Programs

Magma

Maple

Mathematica

PARI

Sage

Formula

Extensions

A052496 Number of nonsingular n X n matrices over GF(8).

Views

Author

Keywords

Links

Crossrefs

Programs

Magma

Mathematica

PARI

Sage

Formula

A052497 Number of nonsingular n X n matrices over GF(9).

Views

Author

Keywords

Links

Crossrefs

Programs

Magma

Mathematica

PARI

Sage

Formula

A056989 Number of nonsingular n X n (-1,0,1)-matrices (over the reals).

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

Formula

Extensions

A296548 Triangle read by rows: T(n,k) is the number of diagonalizable n X n matrices over GF(2) that have rank k, n >= 0, 0 <= k <= n.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Maple

Mathematica

Formula

A203303 Vandermonde determinant of the first n terms of (1,2,4,8,16,...).

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Magma

Maple

Mathematica

SageMath

Formula

A286331 Triangle read by rows: T(n,k) is the number of n X n matrices of rank k over F_2.

Views