Re: enumerating binary matrices

On Tue, 18 Mar 2008 17:40:23 -0700 (PDT), canadan
<dan_lior@xxxxxxxxxxx> wrote:

Hello,

I need to count the number of m X n matrices with entries in {0,1}
such that:

1) the rows are distinct
2) the columns are non-constant (i.e. no column has all 1's or all
0's)

I think that I can count the number of matrices satisfying either
condition on it's own, but not both.

Can you help me? Any ideas or pointers to references are appreciated.

For positive integers m,n, let f(m,n) be the number of m x n matrices
satisfying your conditions.

A few special cases are easily proved:

f(1,1) = 2
f(1,n) = 0, if n > 1
f(2,n) = 2^n, for all n
f(m,n) = 0, if m > 2^n
f(m,n) = (2^n)!, if m = 2^m

Based on a recurrence relation, which appears similar, in spirit, to
the one posted by Mariano Suárez-Alvarez, here are all the nonzero
values of f(m,n) for 1<=m<=10, 1<=n<=10 ...

f(2,1) = 2
f(2,2) = 4
f(2,3) = 8
f(2,4) = 16
f(2,5) = 32
f(2,6) = 64
f(2,7) = 128
f(2,8) = 256
f(2,9) = 512
f(2,10) = 1024
f(3,2) = 24
f(3,3) = 192
f(3,4) = 1248
f(3,5) = 7680
f(3,6) = 46464
f(3,7) = 279552
f(3,8) = 1678848
f(3,9) = 10076160
f(3,10) = 60463104
f(4,2) = 24
f(4,3) = 1536
f(4,4) = 30816
f(4,5) = 491520
f(4,6) = 7250304
f(4,7) = 103735296
f(4,8) = 1465714176
f(4,9) = 20600586240
f(4,10) = 288891869184
f(5,3) = 6720
f(5,4) = 470400
f(5,5) = 19192320
f(5,6) = 655334400
f(5,7) = 20825656320
f(5,8) = 641400883200
f(5,9) = 19476742225920
f(5,10) = 587599569715200
f(6,3) = 20160
f(6,4) = 5604480
f(6,5) = 595607040
f(6,6) = 46494766080
f(6,7) = 3202461803520
f(6,8) = 208623669811200
f(6,9) = 13243595467898880
f(6,10) = 830466588909404160
f(7,3) = 40320
f(7,4) = 57335040
f(7,5) = 16388951040
f(7,6) = 2930815641600
f(7,7) = 433985840547840
f(7,8) = 59056473053491200
f(7,9) = 7723663386333511680
f(7,10) = 991046455449742540800
f(8,3) = 40320
f(8,4) = 518595840
f(8,5) = 418910284800
f(8,6) = 173404942018560
f(8,7) = 55182608063170560
f(8,8) = 15615108858304327680
f(8,9) = 4180708574445544243200
f(8,10) = 1089759843210900605829120
f(9,4) = 4151347200
f(9,5) = 10136835072000
f(9,6) = 9872036206018560
f(9,7) = 6778412149964636160
f(9,8) = 3986809959588893982720
f(9,9) = 2180056153829385016442880
f(9,10) = 1150732818956876071037829120
f(10,4) = 29059430400
f(10,5) = 233811422208000
f(10,6) = 546858521291980800
f(10,7) = 815503656697093324800
f(10,8) = 998695156253168863641600
f(10,9) = 1115064830593462899238502400
f(10,10) = 1190502133516164307025579212800

However, finding a closed form is probably impossible.

quasi
.

Relevant Pages

  • Re: enumerating binary matrices
    ... I need to count the number of m X n matrices with entries in ... the columns are non-constant (i.e. no column has all 1's or all ... I think that I can count the number of matrices satisfying either ...
    (sci.math)
  • enumerating binary matrices
    ... I need to count the number of m X n matrices with entries in ... the columns are non-constant (i.e. no column has all 1's or all ... Any ideas or pointers to references are appreciated. ...
    (sci.math)