3
$\begingroup$

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

$\endgroup$
3
  • $\begingroup$ permutations without fixed points are derangements but there are M cases at very least. $\endgroup$
    – user451844
    Sep 20, 2017 at 23:39
  • 1
    $\begingroup$ 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. $\endgroup$
    – orlp
    Sep 20, 2017 at 23:43
  • $\begingroup$ @orlp Yes that is correct. $\endgroup$
    – JacKeown
    Sep 21, 2017 at 15:59

2 Answers 2

1
$\begingroup$

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.

$\endgroup$
0
$\begingroup$

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

Bonus points for anyone who can explain this...possibly in terms of Möbius inversion?

$\endgroup$

You must log in to answer this question.

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