# Set of permutations with no collectively fixed points

My roommate posed the following problem to me the other day:

If you have M pens of the same brand, and each is a different color and is composed of N pieces of that same color, then how many ways can you reassemble all of the pens such that at least one pen is a solid color?

I wrote up the problem with a better explanation here.

I think it's probably easier to find the number of ways to reassemble the pens with NONE of them in a solid color and then subtract that from the total.

I figured out that that's equivalent to asking, how can you choose $N-1$ permutations (not necessarily distinct) from $S_m$ such that there's no fixed point which is shared by all of them.

So for $N=2$, it's a derangement problem. Do you know of a way to extend this for larger $N$?

Thanks,
John (Jack) McKeown

• permutations without fixed points are derangements but there are M cases at very least.
– user451844
Sep 20, 2017 at 23:39
• I assume that each piece is numbered, and each pen must consist of exactly one of each piece? For example for N = 3 we can assume that the pen consists of an ink cartridge, a tip and a hull, and you can't form a pen using 3 hulls.
– orlp
Sep 20, 2017 at 23:43
• @orlp Yes that is correct. Sep 21, 2017 at 15:59

The $n$ on the right hand side should be an $n-1$ so that when there are $2$ parts to the pens we get back the formula for derangements. The counting here is the principle of inclusion and exclusion, which is technically Möbius inversion on the Boolean lattice.
The answer is this for m pens and n pieces per pen: $$f(m,n) = \sum_{j=0}^{m} (-1)^{m-j}\binom{m}{j}(j!)^n$$ I got this equation from here: https://oeis.org/A135810