|
| |
|
|
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.
(Formerly M4306 N1801)
|
|
7
|
|
|
|
0, 6, 350, 43260, 14591171, 14657461469, 46173502811223, 474928141312623525, 16489412944755088235117, 1985178211854071817861662307, 846428472480689964807653763864449, 1299141117072945982773752362381072143359, 7268140170419155675761326840423792818571154945, 149650282980396792665043455999899697765782372693740287
(list;
graph;
refs;
listen;
history;
text;
internal format)
|
|
|
|
OFFSET
|
2,2
|
|
|
COMMENTS
|
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.
|
|
|
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).
|
|
|
LINKS
|
Table of n, a(n) for n=2..15.
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
|
|
|
FORMULA
|
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
|
|
|
MAPLE
|
with(combinat): T := proc(n) -sum(stirling1(n+1, k+1)*binomial(2^k-1, n), k=0..n-1); end proc:
|
|
|
MATHEMATICA
|
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 *)
|
|
|
PROG
|
(PARI) a(n) = -sum(k=0, n-1, stirling(n+1, k+1, 1)*binomial(2^k-1, n)); \\ Michel Marcus, Jun 05 2020
(Magma) [ -(&+[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
(Sage) [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
|
|
|
CROSSREFS
|
Cf. A000410, A002884, A046747.
Sequence in context: A289738 A211089 A221923 * A214445 A059415 A246112
Adjacent sequences: A000406 A000407 A000408 * A000410 A000411 A000412
|
|
|
KEYWORD
|
nonn,nice
|
|
|
AUTHOR
|
N. J. A. Sloane
|
|
|
EXTENSIONS
|
Edited by W. Edwin Clark, Nov 02 2003
|
|
|
STATUS
|
approved
|
| |
|
|
