Return to Answer

OEIS Links.sccx, xcl v; scpsdcpacascds

Source Link

edit approved Nov 9, 2013 at 9:09

Abhimanyu Pallavi Sudhir

347
5
17

This looks like it will be a difficult question to answer in general, but here's the answers for $m \in \{2,3\}$. Let N(m,n) be the number of m by n (0,1)-matrices without a 2 by 2 all-1 submatrix.

Let A=00 B=01 C=10 D=11. Then any n by 2 (0,1)-matrix counted by N(2,n) is equivalent to a word of length n on the alphabet {A,B,C,D} without two D's. Hence \[N(2,n)=n \cdot 3^{n-1}+3^n.\] The first term counts when there is a D in the word, the other term counts without any D's. See: http://www.research.att.com/~njas/sequences/A006234 http://www.oeis.org/A006234

Now let A=000 B=001 C=010 D=011 E=100 F=101 G=110 H=111. Then any (0,1)-matrix counted by N(2,n) is equivalent to a word of length n without (a) two D's (b) two F's (c) two G's (d) two H's or (e) an H and one of D, F or G. Hence \[N(3,n)=n \cdot 4^{n-1}+\sum_{i=0}^{3} {3 \choose i} (n)_i 4^{n-i}\] where $(n)_i=n(n-1)\cdots(n-i+1)$. The first term is the number of words containing H. The sum counts the terms without any H: First we choose i of D, F or G, and place them in the word. The remaning letters must be A, B, C or E.

This looks like it will be a difficult question to answer in general, but here's the answers for $m \in \{2,3\}$. Let N(m,n) be the number of m by n (0,1)-matrices without a 2 by 2 all-1 submatrix.

Let A=00 B=01 C=10 D=11. Then any n by 2 (0,1)-matrix counted by N(2,n) is equivalent to a word of length n on the alphabet {A,B,C,D} without two D's. Hence \[N(2,n)=n \cdot 3^{n-1}+3^n.\] The first term counts when there is a D in the word, the other term counts without any D's. See: http://www.research.att.com/~njas/sequences/A006234

Now let A=000 B=001 C=010 D=011 E=100 F=101 G=110 H=111. Then any (0,1)-matrix counted by N(2,n) is equivalent to a word of length n without (a) two D's (b) two F's (c) two G's (d) two H's or (e) an H and one of D, F or G. Hence \[N(3,n)=n \cdot 4^{n-1}+\sum_{i=0}^{3} {3 \choose i} (n)_i 4^{n-i}\] where $(n)_i=n(n-1)\cdots(n-i+1)$. The first term is the number of words containing H. The sum counts the terms without any H: First we choose i of D, F or G, and place them in the word. The remaning letters must be A, B, C or E.

This looks like it will be a difficult question to answer in general, but here's the answers for $m \in \{2,3\}$. Let N(m,n) be the number of m by n (0,1)-matrices without a 2 by 2 all-1 submatrix.

Let A=00 B=01 C=10 D=11. Then any n by 2 (0,1)-matrix counted by N(2,n) is equivalent to a word of length n on the alphabet {A,B,C,D} without two D's. Hence \[N(2,n)=n \cdot 3^{n-1}+3^n.\] The first term counts when there is a D in the word, the other term counts without any D's. See: http://www.oeis.org/A006234

Now let A=000 B=001 C=010 D=011 E=100 F=101 G=110 H=111. Then any (0,1)-matrix counted by N(2,n) is equivalent to a word of length n without (a) two D's (b) two F's (c) two G's (d) two H's or (e) an H and one of D, F or G. Hence \[N(3,n)=n \cdot 4^{n-1}+\sum_{i=0}^{3} {3 \choose i} (n)_i 4^{n-i}\] where $(n)_i=n(n-1)\cdots(n-i+1)$. The first term is the number of words containing H. The sum counts the terms without any H: First we choose i of D, F or G, and place them in the word. The remaning letters must be A, B, C or E.

Source Link

created Jul 3, 2010 at 4:01

Douglas S. Stones

4.2k
2
37
53

This looks like it will be a difficult question to answer in general, but here's the answers for $m \in \{2,3\}$. Let N(m,n) be the number of m by n (0,1)-matrices without a 2 by 2 all-1 submatrix.

Let A=00 B=01 C=10 D=11. Then any n by 2 (0,1)-matrix counted by N(2,n) is equivalent to a word of length n on the alphabet {A,B,C,D} without two D's. Hence \[N(2,n)=n \cdot 3^{n-1}+3^n.\] The first term counts when there is a D in the word, the other term counts without any D's. See: http://www.research.att.com/~njas/sequences/A006234

Now let A=000 B=001 C=010 D=011 E=100 F=101 G=110 H=111. Then any (0,1)-matrix counted by N(2,n) is equivalent to a word of length n without (a) two D's (b) two F's (c) two G's (d) two H's or (e) an H and one of D, F or G. Hence \[N(3,n)=n \cdot 4^{n-1}+\sum_{i=0}^{3} {3 \choose i} (n)_i 4^{n-i}\] where $(n)_i=n(n-1)\cdots(n-i+1)$. The first term is the number of words containing H. The sum counts the terms without any H: First we choose i of D, F or G, and place them in the word. The remaning letters must be A, B, C or E.