Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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.

share|cite|improve this question
Sure, put them all down the main diagonal. Or do you want the number of different ways to do it? – André Nicolas Sep 26 '12 at 0:32

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.

share|cite|improve this answer

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!$.

share|cite|improve this answer

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.