algorithm - Possible NxN matrices, t 1's in each row and column, none in diagonal? -

background:

• this credit in logic , algorithms class, covering propositional logic, p implies q kind of thing, think prof wanted give , assignment out of our depth.

• i implement in c++, right want understand whats going on in example....which don't.

example

enclosed walkthrough lefty algorithm computes number of nxn 0-1 matrices t ones in each row , column, none on main diagonal. algorithm used verify equations presented counts possible matrices, not construct them. called "lefty", reasonably simple, , best described example. suppose wanted compute number of 6x6 0-1 matrices 2 ones in each row , column, no ones on main diagonal. first create state vector of length 6, filled 2s:

(2 2 2 2 2 2)

this state vector symbolizes number of ones must yet place in each column. accompany integer call "puck", initialized 1. puck increase 1 each time perform ones placement in row of matrix (a "round"), , think of puck "covering up" column wonít able place ones in round. since starting first row (and hence first round), place 2 ones in column, since puck 1, cannot place ones in first column. corresponds forced 0 must place in first column, since 1,1 entry part of matrixís main diagonal. algorithm iterate on possible choices, show each round, shall make choice, 2nd , 6th columns. drop state vector subtracting 1 2nd , 6th values, , advance puck:

(2 1 2 2 2 1); 2

for second round, puck 2, cannot place 1 in column. choose place ones in 4th , 6th columns instead , advance puck:

(2 1 2 1 2 0); 3

now @ point, can place 2 ones anywhere 3rd , 6th columns. @ stage algorithm treats possibilities di§erently: can place ones before puck (in column indexes less puck value), and/or ones after puck (in column indexes greater puck value). before puck, can place 1 there 1, or there 2; after puck, can place 1 in 4th or 5th columns. suppose place ones in 4th , 5th columns. drop state vector , advance puck once more:

(2 1 2 0 1 0); 4

1 4th round, once again notice can place ones before puck, and/or ones after. before puck, can place:

(a) 2 ones in columns of value 2 (1 choice)

(b) 1 one in column of value 2 (2 choices)

(c) 1 one in column of value 1 (1 choice)

(d) 1 one in column of value 2 , 1 one in column of value 1 (2 choices).

after choose 1 of options (a)-(d), must multiply listed number of choices 1 each way place remaining ones right of puck. so, option (a), there 1 way place ones. option (b), there 2 possible ways each possible placement of remaining 1 right of puck. since there 1 nonzero value remaining right of puck, there 2 ways total. option (c), there 1 possible way each possible placement of remaining 1 right of puck. again, since there 1 nonzero value remaining, there 1 way total. option (d), there 2 possible ways place ones. choose option (a). drop state vector , advance puck:

(1 1 1 0 1 0); 5

since puck "covering" 1 in 5th column, can place ones before puck. there (3 take 2) ways place 2 ones in 3 columns of value 1, multiply 3 number of ways remaining possibilities. after choosing 1st , 3rd columns (though doesnít matter since weíre left of puck; 2 of 3 do), drop state vector , advance puck 1 final time:

(0 1 0 0 1 0); 6

there 1 way place ones in situation, terminate count of 1. must take account multiplications along way: 1*1*1*1*3*1 = 3.

another way of thinking of varying row start first matrix, focus on lower-left 2x3 submatrix, , note how many ways there permute columns of submatrix. since there 3 such ways, 3 matrices.

what think understand

• this algorithm counts the possible 6x6 arrays 2 1's in each row , column none in descending diagonal.

• instead of constructing matrices uses "state_vector" filled 6 2's, representing how many 2's in column, , "puck" represents index of diagonal , current row algorithm iterates.

what don't understand

• the algorithm comes value of 1 each row except 5 assigned 3, @ end these values multiplied end result. these values supposed possible placements each row there many possibilities row 1, why given one, why did algorithm wait until row 5 figure possible permutations?

  any appreciated!

i think going on tradeoff between doing combinatorics , doing recursion.

the algorithm using recursion add counts each choice of placing 1's. example considers single choice @ each stage, full count needs add results possible choices.

now quite possible final answer using recursion way down. every time reach bottom add 1 total count.

the normal next step cache result of calling recursive function improves speed. however, memory use such dynamic programming approach depends on number of states need expanded.

the combinatorics in later stages making use of fact once puck has passed column, exact arrangement of counts in columns doesn't matter need evaluate 1 representative of each type , add resulting counts multiplied number of equivalent ways.

this both reduces memory use , improves speed of algorithm.

note cannot use combinatorics counts right of puck, these order of counts still important due restriction diagonal.

p.s. can compute number of ways counting number of n*n matrices 2 1's in each column (and no diagonal entries) pure combinatorics as:

a(n) = sum_{k=0..n} sum_{s=0..k} sum_{j=0..n-k} (-1)^(k+j-s)*n!*(n-k)!*(2n-k-2j-s)!/(s!*(k-s)!*(n-k-j)!^2*j!*2^(2n-2k-j)) 

according oeis.