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.

%I A000409 M4306 N1801 #35 Dec 17 2022 12:48:30
%S A000409 0,6,350,43260,14591171,14657461469,46173502811223,474928141312623525,
%T A000409 16489412944755088235117,1985178211854071817861662307,
%U A000409 846428472480689964807653763864449,1299141117072945982773752362381072143359,7268140170419155675761326840423792818571154945,149650282980396792665043455999899697765782372693740287
%N 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.
%C A000409 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).
%C A000409 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.
%C A000409 a(n) is also the number of sets of n distinct nonzero (0,1)-vectors in R^n that do not span R^n.
%D A000409 N. J. A. Sloane, A Handbook of Integer Sequences, Academic Press, 1973 (includes this sequence).
%D A000409 N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).
%H A000409 J. Kahn, J. Komlos and E. Szemeredi, <a href="https://doi.org/10.1090/S0894-0347-1995-1260107-2">On the probability that a random ±1-matrix is singular</a>, J. AMS 8 (1995), 223-240.
%H A000409 Goran Kilibarda and Vladeta Jovovic, <a href="https://arxiv.org/abs/1411.4187">Enumeration of some classes of T_0-hypergraphs</a>, arXiv:1411.4187 [math.CO], 2014.
%H A000409 J. Komlos, <a href="http://real-j.mtak.hu/5453/">On the determinant of (0,1)-matrices</a>, Studia Math. Hungarica 2 (1967), 7-21.
%H A000409 N. Metropolis and P. R. Stein, <a href="https://doi.org/10.1016/S0021-9800(67)80006-1">On a class of (0,1) matrices with vanishing determinants</a>, J. Combin. Theory, 3 (1967), 191-198.
%H A000409 <a href="/index/Mat#binmat">Index entries for sequences related to binary matrices</a>
%F A000409 a(n) = (-1)*Sum_{k=0..n-1} Stirling1(n+1, k+1)*binomial(2^k-1, n).
%F A000409 a(n) = binomial(2^n-1, n) - A094000(n). - _Vladeta Jovovic_, Nov 27 2005
%p A000409 with(combinat): T := proc(n) -sum(stirling1(n+1,k+1)*binomial(2^k-1,n),k=0..n-1); end proc:
%t A000409 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 *)
%o A000409 (PARI) a(n) = -sum(k=0, n-1, stirling(n+1, k+1, 1)*binomial(2^k-1, n)); \\ _Michel Marcus_, Jun 05 2020
%o A000409 (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
%o A000409 (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
%Y A000409 Cf. A000410, A002884, A046747.
%K A000409 nonn,nice
%O A000409 2,2
%A A000409 _N. J. A. Sloane_
%E A000409 Edited by _W. Edwin Clark_, Nov 02 2003