Kloster's Pen Problem

[jackeown]

My roommate posed the following problem to me last week:

If you have M pens, each of a different color, and each of which have N parts, then how many ways can you put them back together so that at least one pen is a solid color?

For example, you might have 3 pens each with 4 parts.
Call their colors Red, Green, and Blue (R,G, and B) and call their parts 1,2,3, and 4.

We can write them as follows:
(each column is a pen of a solid color in the following picture)

R1 G1 B1
R2 G2 B2
R3 G3 B3
R4 G4 B4

The first row must always contain parts of type 1.
The second row must always contain parts of type 2.
The nth row must always contain parts of type n.
So the question can be rephrased as follows:

How many valid ways can you re-arrange that matrix so that no column is all the same color?

---

For an answer and full in-depth response, I'm willing to give 5 steem.

Valid until October 15th 2017

Comments

[jackeown]

If it helps, I think it might have something to do with derangements.

[jackeown]

I just found the solution, so the reward is no longer valid (unless you can give a good explanation)