-1
$\begingroup$

How many ways are there to color a chess table of size n*n with n different colors. We color in such a way that in each horizontal row there are all colors and at the same time in no vertical row there are two fields of the same color next to each other. I think we can use derangements for this but I'm not sure how.

$\endgroup$
1
  • $\begingroup$ Where did this question come from? $\endgroup$
    – coffeemath
    Dec 10, 2018 at 15:46

1 Answer 1

3
$\begingroup$

Fill in the first row any way you like. How many options? Now, you are correct, the second row has to be a derangement of the first. How many options there? Each row in turn is a derangement of the one above.

$\endgroup$
11
  • $\begingroup$ So for the first row I think there are n^n ways we can color the first row. So for the second row there are D(n^n) ways to color it? But how do I continue this? $\endgroup$
    – ponikoli
    Dec 10, 2018 at 19:20
  • $\begingroup$ No, you need one of each color in the first row, so there are fewer. How many? $\endgroup$ Dec 10, 2018 at 19:35
  • $\begingroup$ There is n^n * n^(n-1) * n^(n-2) * n^(n-3) ... n^1. $\endgroup$
    – ponikoli
    Dec 10, 2018 at 19:44
  • $\begingroup$ The first row has $n$ objects that you can put in any order, so there are $n!$ ways to do it. $\endgroup$ Dec 10, 2018 at 20:52
  • $\begingroup$ Then the second row has D(n!) ways to do it. The third D(D(n!)) etc..? $\endgroup$
    – ponikoli
    Dec 11, 2018 at 9:00

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .