1
$\begingroup$

I want to ask if I can find a $1$ from each row such that for every two of $1$ they are not in the same column.

  • 0
    http://en.wikipedia.org/wiki/Permutation_matrix2012-09-26

2 Answers 2

1

There are $n!$ ways to put $n \ 1$'s into an $n \times n$ grid so that no two are in the same row or column. Start with the first row and put a $1$ in any cell-this gives $n$ choices. Now put a $1$ in the second row in some other column-$n-1$ choices. As you go down the rows, you have fewer and fewer choices until at the bottom you have only one choice, so you have $n(n-1)(n-2)\cdots1=n!$ ways to do it.

1

Let us count the ways. For the first row, choose any of the $n$ places. For everyone of these choices, the $1$ can be put in the second row in any one of $n-1$ places. For all the $(n)(n-1)$ ways of putting the $1$'s in the first two rows, there are $n-2$ places to put the $1$ in the third row. And so on. So the number of different configurations with the desired property is $n!$.