login
This site is supported by donations to The OEIS Foundation.

 

Logo


Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
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
1, 24, 736, 486200, 15717093608, 41301356272912040, 12775545227876350768099688, 645382645785863222088428068265093848, 6899505383250315051751361998008633233501722290328 (list; graph; refs; listen; history; text; internal format)
OFFSET

1,2

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)

LINKS

Table of n, a(n) for n=1..9.

EXAMPLE

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

CROSSREFS

Cf. A039622.

Sequence in context: A062313 A239815 A279659 * A175604 A283873 A269147

Adjacent sequences:  A062525 A062526 A062527 * A062529 A062530 A062531

KEYWORD

nonn,nice

AUTHOR

Floor van Lamoen, Jul 10 2001

EXTENSIONS

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

More terms from Jon E. Schoenfield, Aug 15 2009

STATUS

approved

Lookup | Welcome | Wiki | Register | Music | Plot 2 | Demos | Index | Browse | More | WebCam
Contribute new seq. or comment | Format | Style Sheet | Transforms | Superseeker | Recent
The OEIS Community | Maintained by The OEIS Foundation Inc.

License Agreements, Terms of Use, Privacy Policy. .

Last modified November 15 11:14 EST 2019. Contains 329144 sequences. (Running on oeis4.)