|
COMMENT
|
Contribution from Jon E. Schoenfield (jonscho(AT)hiwaay.net), Aug 16 2009: (Start)
Number the rows of the matrix as 1..n from bottom to top, and the columns as 1..n from left to right. For i=1..n, let r(i)=1 if the ith row increases toward the right, -1 if it decreases; let R be the number of runs of consecutive rows having the same r value, and let LR(k) be the length of the kth run, for k=1..R. Similarly, for i=1..n, let c(i)=1 if the ith column increases toward the top, -1 if it decreases; let C be the number of runs of consecutive columns having the same c value, and let LC(k) be the length of the kth run, for k=1..C.
For each of the 4 possible combinations of the vectors r and c in which R=C=1, the number of solutions is A039622(n). In any combination where R=1 and C>1, the matrix can be partitioned into C rectangular sections (the kth one being LC(k) columns wide and n rows high); the numbers 1 through LC(1)*n must be placed in the first section, the next LC(2)*n numbers in the second section, etc., so the total number of solutions is product(T(LC(k),n),k=1..C), where T(m,n) is as defined at A060854; similarly, if C=1 and R>1, the number of solutions is product(T(LR(k),n),k=1..R).
In any combination where R=2, C=2, and r(1)=c(1), the matrix can be partitioned into 4 rectangular sections, with the lower left and lower right sections covering rows 1..LR(1), the upper left and upper right covering the remaining rows, the lower and upper left covering columns 1..LC(1), and the lower and upper right covering the remaining columns. Then, if r(1)=c(1)=1, the numbers 1 through LR(1)*LC(1)+LR(2)*LC(2) must be apportioned between the lower left and upper right sections; if r(1)=c(1)=-1, they must be apportioned between the other two sections. Either way, the number of solutions for such a combination of the vectors r and c is binomial(LR(1)*LC(1)+LR(2)*LC(2),LR(1)*LC(1)) * binomial(LR(1)*LC(2)+LR(2)*LC(1),LR(1)*LC(2)) * T(LR(1),LC(1)) * T(LR(1),LC(2)) * T(LR(2),LC(1)) * T(LR(2),LC(2)).
No solutions exist where R=C=2 and r(1)<>c(1), nor are there any solutions where R=2 and C>2, R>2 and C=2, or R>2 and C>2. (End)
|
