Re: puzzle with string permutations [photo]

[Yuri Khan]

On Tue, 7 Jun 2022 at 21:18, Emanuel Berg <incal@dataswamp.org> wrote:

> It doesn't work exactly like that with strings, since for
> example the scrambled word "ogod" is actually, here, treated
> as
>
>   o_1 g o_2 d
>
> Yet the words
>
>   g o_1 o_2 d
>   g o_2 o_1 d
>
> are duplicates.

This extension of the concept of sets is called a multiset or a bag.
For each element, we also have a multiplicity. Let’s write it as {o:2,
g:1, d:1}.

Let’s solve the problem: Given a multiset of letters {X_1:n_1, …,
X_k:n_k}, how many distinct strings using up all of them are there?

First, we treat repeating letters as if they were distinct, e.g. by
numbering them as you did above: {o_1, o_2, g, d}. These are 4 letters
and there are 4! = 24 permutations.

However, every two permutations that only differ by the order of o_1
and o_2 are equivalent in our original unnumbered multiset. So we have
to divide by two: 4! / 2 = 24 / 2 = 12. dgoo, dogo, doog, gdoo, godo,
good, odgo, odog, ogdo, ogod, oodg, oogd.

What do we do if there are three or more instances of each letter?
Let’s consider a degenerate multiset {w:3}. If we number the
instances, it’s {w_1, w_2, w_3} and there are 3! = 6 permutations, but
clearly the only distinct string is www. So it looks like we need to
divide by 3! = 6: 3! / 3! = 6 / 6 = 1.

In general, with a multiset {X_1:n_1, …, X_k:n_k}, if we number each
letter, we get (n_1 + … + n_k)! permutations, and then we have to
adjust for duplicates for each individual letter by dividing by (n_1)!
… (n_k)!.

n_perm = (n_1 + … + n_k)! / (n_1)! … (n_k)!

For the above example of {o:2, g:1, d:1}:

n_perm = (2 + 1 + 1)! / 2! 1! 1! = 4! / 2 1 1 = 24 / 2 = 12.

(This problem was part of my exam in maths when I was applying at
Novosibirsk State University, Mechanics & Maths Department, in 1997.)

(You might also notice the formula is similar to that of a binomial
coefficient: C_{n,k} = n! / k! (n-k)!. That’s no coincidence.)