Problem

Source: 2023 Iran MO 2nd round

Tags: combinatorics



3. We have a $n \times n$ board. We color the unit square $(i,j)$ black if $i=j$, red if $i<j$ and green if $i>j$. Let $a_{i,j}$ be the color of the unit square $(i,j)$. In each move we switch two rows and write down the $n$-tuple $(a_{1,1},a_{2,2},\cdots,a_{n,n})$. How many $n$-tuples can we obtain by repeating this process? (note that the order of the numbers are important)