A062528 Number of ways to fill an n X n matrix with numbers 1, 2, ..., n*n such that each row and each column is decreasing or increasing.

1, 24, 736, 486200, 15717093608, 41301356272912040, 12775545227876350768099688, 645382645785863222088428068265093848, 6899505383250315051751361998008633233501722290328

Offset: 1

Author

Floor van Lamoen, Jul 10 2001

Keywords

• nonn
• nice

Comments

From Jon E. Schoenfield, 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 i-th 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 k-th run, for k=1..R. Similarly, for i=1..n, let c(i)=1 if the i-th 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 k-th 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 k-th 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_{k=1..C} T(LC(k),n), where T(m,n) is as defined at A060854; similarly, if C=1 and R > 1, the number of solutions is Product_{k=1..R} T(LR(k),n).

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)

Examples

			a(2) = 4! = 24 because every arrangement of the four elements of a 2 X 2 matrix satisfies the conditions.
		

Crossrefs

Cf. A039622.

Extensions

a(3) changed from 5320 to 736 by R. H. Hardin, Feb 17 2002

More terms from Jon E. Schoenfield, Aug 15 2009