Displaying 11-20 of 88 results found.
Number of n X n rational {0,1}-matrices of determinant 0.
+10
17
1, 10, 338, 42976, 21040112, 39882864736, 292604283435872, 8286284310367538176
FORMULA
a(n) = 2^(n^2) - n! * binomial(2^n -1, n) + n! * A000410(n). a(n) + A055165(n) = 2^(n^2) = total number of n X n (0, 1) matrices. The probability that a random n X n {0,1}-matrix is singular is conjectured to be asymptotic to C(n+1, 2)*(1/2)^(n-1). [Corrected by N. J. A. Sloane, Jan 02 2007]
EXAMPLE
a(2)=10: the matrix of all 0's, 4 matrices with 2 zeros in the same row or column, 4 matrices with 3 zeros and the all-1 matrix.
MATHEMATICA
Sum[KroneckerDelta[Det[Array[Mod[Floor[k/(2^(n*(#1-1)+#2-1))], 2]&, {n, n}]], 0], {k, 0, (2^(n^2))-1}] (* John M. Campbell, Jun 24 2011 *) Count[Det /@ Tuples[{0, 1}, {n, n}], 0] (* David Trimas, Sep 23 2024 *)
PROG
(PARI) A046747(n) = m=matrix(n, n); ct=0; for(x=0, 2^(n*n)-1, a=binary(x+2^(n*n)); for(i=1, n, for(j=1, n, m[i, j]=a[n*i+j+1-n])); if(matdet(m)==0, ct=ct+1, ); ); ct \\ Randall L Rathbun(PARI) a(n)=sum(i=0, 2^n^2-1, matdet(matrix(n, n, x, y, (i>>(n*x+y-n-1))%2))==0) \\ Charles R Greathouse IV, Feb 21 2015
AUTHOR
Günter M. Ziegler (ziegler(AT)math.tu-berlin.de)
Nonsingular n X n matrices over GF(4).
+10
16
1, 3, 180, 181440, 2961100800, 775476766310400, 3251791214634074112000, 218210695042457748180566016000, 234298374547168764346587444978647040000, 4025200069765920285793155323595159699896401920000, 1106437515026051855463365435310419366987397763763798016000000
FORMULA
a(n) = (4^n - 1)*(4^n - 4)*...*(4^n - 4^(n-1)).
MATHEMATICA
Table[Product[4^n - 4^k, {k, 0, n-1}], {n, 0, 10}] (* Geoffrey Critzer, Jan 26 2013 *)
PROG
(Magma) [1] cat [&*[(4^n - 4^k): k in [0..n-1]]: n in [1..8]]; // Bruno Berselli, Jan 28 2013 (PARI) for(n=0, 10, print1(prod(k=0, n-1, 4^n - 4^k), ", ")) \\ G. C. Greubel, May 31 2018
Number of bases of an n-dimensional vector space over GF(2).
+10
15
1, 1, 3, 28, 840, 83328, 27998208, 32509919232, 132640470466560, 1927943976061501440, 100981078400558897823744, 19242660536873338307044442112, 13448310596010038676027219703234560, 34707333779115158227208335860718444216320, 332718225878012276874300952228513073208156487680
REFERENCES
R. Lidl and H. Niederreiter, Introduction to Finite Fields and Their Applications, Cambridge 1986
FORMULA
a(n) = (2^n-1)(2^n-2)...(2^n-2^(n-1))/n! = A002884(n)/n!.
EXAMPLE
a(2)=3 because the 3 bases are {01,10}, {01,11}, {10,11}.
MATHEMATICA
Table[Product[2^n - 2^k, {k, 0, n-1}]/n!, {n, 0, 20}] (* G. C. Greubel, May 16 2019 *)
PROG
(PARI) a(n) = prod(k=0, n-1, 2^n - 2^k)/n!; \\ Michel Marcus, Mar 25 2016 (Magma) [1] cat [(&*[2^n -2^k: k in [0..n-1]])/Factorial(n): n in [1..20]]; // G. C. Greubel, May 16 2019 (Sage) [product(2^n -2^k for k in (0..n-1))/factorial(n) for n in (0..20)] # G. C. Greubel, May 16 2019
AUTHOR
Fred Galvin (galvin(AT)math.ukans.edu), Jan 20 2000
Number of nonsingular n X n matrices over GF(5).
+10
14
1, 4, 480, 1488000, 116064000000, 226614960000000000, 11064475422000000000000000, 13506266841692625000000000000000000, 412177498341354683437500000000000000000000000
FORMULA
a(n) = (5^n - 1)*(5^n - 5)*...*(5^n - 5^(n-1)).
MATHEMATICA
Table[Product[5^n - 5^k, {k, 0, n-1}], {n, 0, 10}] (* Geoffrey Critzer, Jan 26 2013 *)
PROG
(Magma) [1] cat [&*[(5^n - 5^k): k in [0..n-1]]: n in [1..8]]; // Bruno Berselli, Jan 28 2013 (PARI) for(n=0, 10, print1(prod(k=0, n-1, 5^n - 5^k), ", ")) \\ G. C. Greubel, May 31 2018
Number of nonsingular n X n matrices over GF(7).
+10
14
1, 6, 2016, 33784128, 27811094169600, 1122211189922928537600, 2218959336124989671614429593600, 214992513152176999576908105619651923148800, 1020690003311610463765638355505358381593396977336320000, 237443634207909205360438080389756681126654524500073656592021585920000
FORMULA
a(n) = (7^n - 1)*(7^n - 7)*...*(7^n - 7^(n-1)).
MATHEMATICA
Table[Product[7^n - 7^k, {k, 0, n-1}], {n, 0, 10}] (* Vincenzo Librandi, Jan 28 2013 *)
PROG
(Magma) [1] cat [&*[(7^n - 7^k): k in [0..n-1]]: n in [1..7]]; // Bruno Berselli, Jan 28 2013 (PARI) for(n=0, 10, print1(prod(k=0, n-1, 7^n - 7^k), ", ")) \\ G. C. Greubel, May 31 2018
Number of idempotent n X n matrices over GF(2); also number of diagonalizable n X n matrices over GF(2).
+10
12
1, 2, 8, 58, 802, 20834, 1051586, 102233986, 19614424834, 7355623374338, 5494866505497602, 8087844439442585602, 23834930674299549249538, 138978138716920276085366786, 1626809921636911219317749563394, 37757678575184051755732304668884994
FORMULA
a(n) = sum(k=0...n, 2^(k(n-k))*[n,k]_2), where [n,k]_2 is the Gaussian binomial for q=2. - Marc van Leeuwen, May 22 2013
MAPLE
T:= proc(n, k) option remember; `if`(k<0 or k>n, 0,
`if`(n=0, 1, T(n-1, k-1)+2^k*T(n-1, k)))
end:
a:= n-> add(2^(k*(n-k))*T(n, k), k=0...n):
MATHEMATICA
nn = 10; g[n_] := (q - 1)^n q^Binomial[n, 2] FunctionExpand[
QFactorial[n, q]] /. q -> 2; G[z_] := Sum[z^k/g[k], {k, 0, nn}]; Table[g[n], {n, 0, nn}] CoefficientList[Series[G[z]^2, {z, 0, nn}], z] (* Geoffrey Critzer, Aug 04 2017 *) a[n_] := Block[{m}, Length@ Select[ Range[2^(n^2)], (m = Partition[ IntegerDigits[ #-1, 2, n^2], n]; Mod[m.m, 2] == m) &]]; a /@ Range[4] (* Giovanni Resta, Apr 09 2017 *)
AUTHOR
Yuval Dekel (dekelyuval(AT)hotmail.com), Sep 19 2003 and Vladeta Jovovic, Nov 04 2007
EXTENSIONS
This is the result of merging two independently submitted but identical sequences. Thanks to Geoffrey Critzer for suggesting this. - N. J. A. Sloane, Dec 26 2017
Number of n X n invertible binary matrices A such that A+I is invertible.
(Formerly M2170 N0866)
+10
11
0, 2, 48, 5824, 2887680, 5821595648, 47317927329792, 1544457148312846336, 202039706313624586813440, 105823549214125066767168438272, 221819704567105547916502447159246848
COMMENTS
Also number of linear orthomorphisms of GF(2)^n.
REFERENCES
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).
FORMULA
Reference gives a recurrence.
a(n) = 2^(n(n-1)/2) * A005327(n+1).
MAPLE
N:=proc(n, i) option remember; if i = 1 then 1 else (2^n-2^(i-1))*N(n, i-1); fi; end;
Oh:=proc(n) option remember; local r; global N;
if n=0 then RETURN(1) elif n=1 then RETURN(0) else
add( 2^(r-2)*N(n, r)*2^(r*(n-r))*Oh(n-r), r=2..n); fi; end;
[seq(Oh(n), n=1..15)];
MATHEMATICA
ni[n_, i_] := ni[n, i] = If[i == 1, 1, (2^n - 2^(i-1))*ni[n, i-1]]; a[0] = 1; a[1] = 0; a[n_] := a[n] = Sum[ 2^(r-2)*ni[n, r]*2^(r*(n-r))*a[n-r], {r, 2, n}]; Table[a[n], {n, 1, 11}] (* Jean-François Alcover, Jan 19 2012, after Maple *)
Array read by antidiagonals: T(n,k) is the order of the group GL(n,Z_k).
+10
11
1, 1, 1, 1, 1, 1, 1, 2, 6, 1, 1, 2, 48, 168, 1, 1, 4, 96, 11232, 20160, 1, 1, 2, 480, 86016, 24261120, 9999360, 1, 1, 6, 288, 1488000, 1321205760, 475566474240, 20158709760, 1, 1, 4, 2016, 1886976, 116064000000, 335522845163520, 84129611558952960, 163849992929280, 1
COMMENTS
All rows are multiplicative.
Equivalently, the number of invertible n X n matrices mod k.
Also, for k prime (but not higher prime powers) the number of nonsingular n X n matrices over GF(k).
For k >= 2, n! divides T(n,k) since the subgroup of GL(n,k) consisting of all permutation matrices is isomorphic to S_n (the n-th symmetric group). Note that a permutation matrix is an orthogonal matrix, hence having determinant +-1. - Jianing Song, Oct 29 2022
FORMULA
T(n,p^e) = (p^e)^(n^2) * Product_{j=1..n} (1 - 1/p^j) for prime p.
EXAMPLE
Array begins:
=================================================================
n\k| 1 2 3 4 5 6
---+-------------------------------------------------------------
0 | 1 1 1 1 1 1 ...
1 | 1 1 2 2 4 2 ...
2 | 1 6 48 96 480 288 ...
3 | 1 168 11232 86016 1488000 1886976 ...
4 | 1 20160 24261120 1321205760 116064000000 489104179200 ...
5 | 1 9999360 ...
...
MATHEMATICA
T[_, 1] = T[0, _] = 1; T[n_, k_] := T[n, k] = Module[{f = FactorInteger[k], p, e}, If[Length[f] == 1, {p, e} = f[[1]]; (p^e)^(n^2)* Product[(1 - 1/p^j), {j, 1, n}], Times @@ (T[n, Power @@ #]& /@ f)]];
PROG
(GAP)
T:=function(n, k) if k=1 or n=0 then return 1; else return Order(GL(n, Integers mod k)); fi; end;
for n in [0..5] do Print(List([1..6], k->T(n, k)), "\n"); od;
(PARI) T(n, k)={my(f=factor(k)); k^(n^2) * prod(i=1, #f~, my(p=f[i, 1]); prod(j=1, n, (1 - p^(-j))))}
Order of general affine group over GF(2), AGL(n,2).
+10
9
1, 2, 24, 1344, 322560, 319979520, 1290157424640, 20972799094947840, 1369104324918194995200, 358201502736997192984166400, 375234700595146883504949480652800, 1573079924978208093254925489963584716800
COMMENTS
For n > 0, a(n) = v(n+1)/v(n), where v = A203305 is the Vandermonde determinant of the first n of the numbers -2^j - 1; see the Mathematica section. - Clark Kimberling, Jan 01 2012
REFERENCES
J. M. Borwein, D. H. Bailey and R. Girgensohn, Experimentation in Mathematics, A K Peters, Ltd., Natick, MA, 2004. x+357 pp. See p. 54 (1.64).
LINKS
Putnam Competition 1999, Question A6, Amer. Math. Monthly 107 (Oct 2000), 721-732; see p. 725.
FORMULA
a(n) is asymptotic to C*2^(n*(n+1)) where C = 0.288788095086602421278899721... = prod(k>=1, 1-1/2^k) (cf. A048651). - Benoit Cloitre, Apr 11 2003 a(n) = (6*a(n-1)^2*a(n-3) - 8*a(n-1)*a(n-2)^2) / (a(n-2)*a(n-3)). [From Putman Exam]. - Max Alekseyev, May 18 2007 a(n) = 2^n * n! * A053601(n). (End) a(n) = Product_{j=0..n-1} (2^(n+1) - 2^(j+1)).
a(n) = (-1)^n * 2^binomial(n+1,2) * QPochhammer(2,2,n). (End)
MAPLE
A028365 := n->2^n*product(2^n-2^'i', 'i'=0..n-1); # version 1
A028365 := n->product(2^'j'-1, 'j'=1..n)*2^binomial(n+1, 2); # version 2
MATHEMATICA
RecurrenceTable[{a[1]==1, a[2]==2, a[3]==24, a[n]==(6a[n-1]^2 a[n-3] - 8a[n-1] a[n-2]^2)/(a[n-2] a[n-3])}, a[n], {n, 20}] (* Harvey P. Dale, Aug 03 2011 *) (* Next, the connection with Vandermonde determinants *)
f[j_]:= 2^j - 1; z = 15;
v[n_]:= Product[Product[f[k] - f[j], {j, k-1}], {k, 2, n}]
Table[v[n+1]/v[n], {n, z}] (* A028365 *) Table[(-1)^n*2^Binomial[n+1, 2]*QPochhammer[2, 2, n], {n, 0, 20}] (* G. C. Greubel, Aug 31 2023 *)
PROG
(PARI) a(n)=if(n<0, 0, prod(k=1, n, 2^k-1)*2^((n^2+n)/2)) /* Michael Somos, May 09 2005 */ (Magma) [1] cat [(&*[2^(n+1) - 2^(j+1): j in [0..n-1]]): n in [1..20]]; // G. C. Greubel, Aug 31 2023 (SageMath) [product(2^(n+1) - 2^(k+1) for k in range(n)) for n in range(21)] # G. C. Greubel, Aug 31 2023
a(n) = 6*a(n-1) - 8*a(n-2) for n > 1; a(0) = 3, a(1) = 14.
+10
9
3, 14, 60, 248, 1008, 4064, 16320, 65408, 261888, 1048064, 4193280, 16775168, 67104768, 268427264, 1073725440, 4294934528, 17179803648, 68719345664, 274877644800, 1099511103488, 4398045462528, 17592183947264, 70368739983360
COMMENTS
Binomial transform of A171498; second binomial transform of A171497; third binomial transform of A010703.
FORMULA
a(n) = 4*4^n - 2^n = 2^n * (2^(n+2) - 1).
G.f.: (3-4*x)/((1-2*x)*(1-4*x)).
MATHEMATICA
(* This program shows how A171499 arises from the Vandermonde determinant of (1, 2, 4, ..., 2^(n-1)). *) f[j_]:= 2^j - 1; z = 15;
v[n_]:= Product[Product[f[k] - f[j], {j, k-1}], {k, 2, n}]
d[n_]:= Product[(i-1)!, {i, n}]
Table[v[n+1]/v[n], {n, z}] (* A002884 *) Table[v[n]*v[n+2]/(2*v[n+1])^2, {n, z}] (* A171499 *) LinearRecurrence[{6, -8}, {3, 14}, 30] (* Harvey P. Dale, Sep 05 2021 *)
PROG
(PARI) {m=23; v=concat([3, 14], vector(m-2)); for(n=3, m, v[n]=6*v[n-1]-8*v[n-2]); v}
(SageMath) [4^(n+1) -2^n for n in range(31)] # G. C. Greubel, Aug 31 2023
Search completed in 0.039 seconds
|