0
$\begingroup$

How to express "$k$ things are the same" and "$n-k$ differ from each other as well as the $k$" as number of permutations?

I start with the obvious, which is the $n-k$ things differing from each other, which gives $(n-k)!$ permutations on the set "$n-k$".

However, I'm unsure about what counting the permutations of $n-k$ different things on the $k$ similar things means algebraically.

I believe $k$ similar things means that there's only one permutation, since with all orders of the $k$ elements, the sequence is the same.

But how do the two sets interact with each other? So what's the total amount of permutations?

Any hints?

$\endgroup$
  • $\begingroup$ Have you talked about derangements? I can only assume that's what "$n - k$ differ from each other" would mean. $\endgroup$ – pjs36 Mar 1 '18 at 14:08
1
$\begingroup$

When $k$ things are the same, it means that you cannot distinguish between a permutation amongst them.

Assuming that all $n-k+k=n$ things would be different, there would be $n!$ permutations. However, since permutations of the indistinguishable things will result in the same overall permutation, one has to divide by the number of permutations under the indistinguishable things, which is $k!$. This gives $$ \frac{n!}{k!} $$ overall permutations. Also refer to this website, and scroll down to "Permutations with Indistinguishable Objects".

$\endgroup$
  • $\begingroup$ Nice answer, but I couldn't find intuition for why must one divide? Isn't that like the ratio of "how many more permutations there in total compared to the similar set"? But that doesn't sound very intuitive. Or perhaps it should be read as that one removes the effect of "k! distinguishable objects" by dividing by it, so that the set of k elements is considered only "once" in the total number of permutations? $\endgroup$ – mavavilj Mar 1 '18 at 14:12
  • $\begingroup$ Maybe it is easier to think the other way round: Denote by M the number of permutations with k indistinguishable objects and n-k distinguishable objects. Then for each of these permutations you could make k! permutations among the indistinguishable objects, if they were distinguishable and therefore M*k! = n!, which gives the result. $\endgroup$ – Andreas Mar 6 '18 at 14:40

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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