1
$\begingroup$

I am given a string,let say- "abcd". Now I have to find all the strings that can be generated by permuting its character such that-

  1. There are exactly four mismatches in the generated strings and,
  2. The mismatches exists in pair, for e.g-

The string - "abcd" has three such permutations- "badc","cdab","dcba".

Explanation-

Let us consider "abcd" and "badc". Now there are exactly four mismatch with , i.e- (a,b),(b,a),(c,d),(d,c) and these mismatches exists in pair.

Note that "abcde" has fifteen such permutations- acbed,adebc,aedcb,baced,badce,baedc,cbaed,cdabe,ceadb,dbeac,dcbae,decab,ebdca,ecbda,edcba

Where I am failing?-

I am just finding the strings manually, but this becomes really time-consuming for strings of large length. Hence,I need a efficient solution

$\endgroup$
9
  • 1
    $\begingroup$ You ask for the number of permutations of $S_n$ such that in its cyclic decomposition, there are exactly two $2$-cycles (and no other cycles). Pick which four are used in the two cycles. Then, for the smallest appearing letter (number), pick which it is paired with. $\endgroup$
    – JMoravitz
    Mar 12, 2016 at 5:36
  • $\begingroup$ Can you please elaborate this? $\endgroup$ Mar 12, 2016 at 5:39
  • $\begingroup$ Ross's answer below arrives at the same answer, just choosing the steps for multiplication principle in a slightly different order. What needs elaboration? The steps for multiplication principle are detailed above already (pick the four to use, pick the partner for smallest picked in previous step). Do you wish for elaboration on the symmetric group? Or the cyclic notation for permutations? Or, perhaps on what the multiplication principle of counting says? $\endgroup$
    – JMoravitz
    Mar 12, 2016 at 5:44
  • $\begingroup$ @JMoravitz Some additional effects yields a general formula- n*(n-1)*(n-2)*(n-3)/8 when there is a string of 'n' characters and all the characters are distinct Like-for the case - "abcde", n=5 so there are 15 such permutations Reason- There are C(n, 4) ways to choose 4 mismatch places from n letters, and for every such quadruple, there are three ways to pair them, hence- C(n, 4) * 3 = n * (n - 1) * (n - 2) * (n - 3) / 8. Can you generalise this formula for the case when the string doesn't contains distinct character? $\endgroup$ Mar 12, 2016 at 6:18
  • $\begingroup$ Ok, JMoravitz will you be able to post another detailed explanation(as you did for -"abcdefgh" above) for a string containing repeating letters also(it would be preferable if you will take an example like- abbbbcccdeff). It will be very much helpful. $\endgroup$ Mar 12, 2016 at 6:37

2 Answers 2

1
$\begingroup$

Break it up via multiplication principle:

$$abcdefgh$$

  • Step 1: Pick which four of the $n$ letters are going to be swapped (for example $bdeg$, pictured below)

$$\color{grey}{a}\color{red}{b}\color{grey}{c}\color{red}{de}\color{grey}{f}\color{red}{g}\color{grey}{h}$$

How many ways can this step be done in for a string of $n$ letters?

$\binom{n}{4} = \frac{n!}{4!(n-4)!}$

  • Step 2: Color the smallest appearing chosen letter blue. Pick one more of the three remaining red chosen letters to color blue. (for example $g$ pictured below)

$$\color{grey}{a}\color{blue}{b}\color{grey}{c}\color{red}{de}\color{grey}{f}\color{blue}{g}\color{grey}{h}$$

How many ways can this step be done?

$3$ ways

Now, swap the blue letters, and swap the red letters.

$$agcedfbh$$

The pictured example has the following two mismatch pairs: $(b,g)$ and $(d,e)$.

It should be clear that every sequence of choices from the above steps will generate exactly a permutation of the desired type uniquely and that all permutations are generated by exactly one sequence of choices. Multiplication principle then says that the number of such permutations is the product of the number of available choices at each step.


Beginnings of a generalization:

Let the string to be permuted be $\underbrace{aa\dots a}_{\alpha_a~\text{copies}} \underbrace{bb\dots b}_{\alpha_b~\text{copies}} cc\dots c\dots \underbrace{kk\dots k}_{\alpha_k~\text{copies}}$ where there are $k$ distinct letters appearing, and $\alpha_a+\alpha_b+\dots+\alpha_k = n$ letters total (counting repeated letters).

Let $\chi_{a,0}$ denote the event that two $a$'s were swapped between themselves and no other $a$'s were swapped. Let $\chi_{a,1}$ denote the event that two $a$'s were swapped between themselves and a third $a$ was swapped with a different letter. Let $\chi_{a,2}$ denote the event that four $a$'s were swapped amongst eachother. Define similar events for the other letters.

Temporarily assume every letter distinct (each copy of a particular letter, assume it has a specific subscript number for example)

$$a_1b_1b_2b_3b_4c_1c_2c_3d_1e_1f_1f_2$$

Count how many permutations exist with the desired properties as above temporarily ignoring the fact that some letters are intended to be identical.

$3\binom{n}{4}$ ways

Remove those permutations which swap at least one pair of identical letters. To count how many of these there are, we try to count $|\chi_{a,0}\cup \chi_{a,1}\cup \chi_{a,2}\cup \chi_{b,0}\cup \dots\cup \chi_{k,2}|$.

By inclusion exclusion, this is $\sum\limits_{x\in\{a,b,\dots,k\}}\sum\limits_{i=0}^2|\chi_{x,i}| -\sum\limits_{\{x,y\}\subset\{a,b,\dots,k\},~x< y}|\chi_{x,0}\cap \chi_{y,0}|$

To count $|\chi_{x,0}|$, pick the two offending letter $x$'s, and then pick the other two non-$x$'s. $\binom{\alpha_x}{2}\binom{n-\alpha_x}{2}$ such permutations.

To count $|\chi_{x,1}|$, pick the three offending $x$'s, pick one of them to be paired with a non-$x$, and pick the non $x$ to be paired with. $\binom{\alpha_x}{3}\cdot 3\cdot (n-\alpha_x)$ such permutations.

To count $|\chi_{x,2}|$, pick the four offending $x$'s and then pick how they were paired. $3\binom{\alpha_x}{4}$ such permutations.

Notice, that in expanding the union for inclusion-exclusion, the only surviving intersections are of the form $\chi_{x,0}\cap \chi_{y,0}$ with $x\neq y$ since any other intersection would imply that there were five or more selected letters.

To count $|\chi_{x,0}\cap \chi_{y,0}|$, select the two offending $x$'s and select the two offending $y$'s. $\binom{\alpha_x}{2}\binom{\alpha_y}{2}$ such permutations.

Removing these from the original total, we have then a final total of:

$$3\binom{n}{4} - \sum\limits_{x\in \{a,b,\dots,k\}}\left(\binom{\alpha_x}{2}\binom{n-\alpha_x}{2}+\binom{\alpha_x}{3}\cdot 3\cdot (n-\alpha_x)+3\binom{\alpha_x}{4}\right) + \sum\limits_{\{x,y\}\subset\{a,b,\dots,k\},~x<y}\binom{\alpha_x}{2}\binom{\alpha_y}{2}$$

For a specific example, such as $abbbbcccdeff$, we would have $3\binom{12}{4} - \underbrace{\binom{4}{2}\binom{8}{2}}_{\chi_{b,0}} - \underbrace{\binom{4}{3}3\cdot 8}_{\chi_{b,1}} - \underbrace{3}_{\chi_{b,2}} - \underbrace{\binom{3}{2}}_{\chi_{c,0}}-\underbrace{\binom{3}{3}\cdot 3\cdot 9}_{\chi_{c,1}}-\underbrace{\binom{2}{2}\binom{10}{2}}_{\chi_{f,0}}+\underbrace{\binom{4}{2}\binom{3}{2}}_{\chi_{b,0}\cap\chi_{c,0}}+\underbrace{\binom{4}{2}\binom{2}{2}}_{\chi_{b,0}\cap\chi_{f,0}}+\underbrace{\binom{3}{2}\binom{2}{2}}_{\chi_{c,0}\cap\chi_{f,0}} = 1170$

For a smaller example which should be able to be brute forced, $abbde$ would have $3\binom{5}{4} - \binom{2}{2}\binom{3}{2} = 15-3=12$. Specifically, they are $adebb,aedbb,babed,badbe,baedb,bbaed,bdabe,beadb,dbeab,debab,ebdba,edbba$ (copied from your earlier list, replaced $c$'s with $b$'s, and deleted the three offending permutations)

$\endgroup$
11
  • $\begingroup$ What if the letters are not distinct, say- "abbcd"? $\endgroup$ Mar 12, 2016 at 6:05
  • $\begingroup$ Then it becomes a much harder problem. You could approach similarly by temporarily assuming all letters to be unique, but then exclude the number of those solutions which accidentally swapped (at least) two identical letters (since we wouldn't have been able to tell). Approach via inclusion-exclusion in that case. The number of solutions will depend on the amount of repitition among the letters. $\endgroup$
    – JMoravitz
    Mar 12, 2016 at 6:08
  • $\begingroup$ Some additional effects yields a general formula- n*(n-1)*(n-2)*(n-3)/8 when there is a string of 'n' characters and all the characters are distinct Like-for the case - "abcde", n=5 so there are 15 such permutations Reason- There are C(n, 4) ways to choose 4 mismatch places from n letters, and for every such quadruple, there are three ways to pair them, hence- C(n, 4) * 3 = n * (n - 1) * (n - 2) * (n - 3) / 8. Can you generalise this formula for the case when the string doesn't contains distinct character? $\endgroup$ Mar 12, 2016 at 6:17
  • $\begingroup$ @RachitBelwariar I would much rather not because it will be an incredibly messy formula to generalize. It would be easier to work with a specific example with specific amounts of repetitions. The method in doing so, I already described in my previous comment. $\endgroup$
    – JMoravitz
    Mar 12, 2016 at 6:20
  • $\begingroup$ Ok, JMoravitz will you be able to post another detailed explanation(as you did for -"abcdefgh" above) for a string containing repeating letters also(it would be preferable if you will take an example like- abbbbcccdeff). It will be very much helpful. $\endgroup$ Mar 12, 2016 at 6:25
1
$\begingroup$

Hint: Let the string have length $n$. You choose two places for the first pair to swap, $n \choose 2$ ways. Then you choose two places for the second pair in (how many?) ways. But you could have chosen the pairs in the other order....

$\endgroup$
5
  • $\begingroup$ In another words, my question asks for all the permutations of the string such that these permutations after exactly two swaps gives the original string, like- "badc" after exactly two swaps gives -"abcd". For "abcde" the number of such permutations is 45 $\endgroup$ Mar 12, 2016 at 5:43
  • $\begingroup$ @Rachit for $abcde$ it is fifteen, not $45$. For $abcdef$ it will be $45$. For $abcdefg$ it will be $105$, etc... Ross and I both understood your question, and his answer is an appropriate hint (which is practically a full solution already). Apply the multiplication principle to find the general solution. $\endgroup$
    – JMoravitz
    Mar 12, 2016 at 5:48
  • $\begingroup$ @RachitBelwariar: your hand count for $abcde$ comes up with the right number, which is $15$. Following the hint, you pick the first pair in ${5 \choose 2}=10$ ways, the second pair in ${3 \choose 2}$ ways, so you have $10 \cdot 3$ ways to make these two choices, but if you chose the pair in the other order you get the same permutation, so $30/2=15$. As JMoravitz says, his approach reaches the same answer in another route. If you unpack the combination numbers into factorials you can show they agree. It is good to understand both-each works in some cases. $\endgroup$ Mar 12, 2016 at 6:05
  • $\begingroup$ What if the letters are not distinct, say- "abbcd"? $\endgroup$ Mar 12, 2016 at 6:06
  • $\begingroup$ @RachitBelwariar: that is a new question. You need to define whether swapping the two $b$'s is allowed. I suggest you work on it based on your understanding of this one. A good way to see if you understand the answer to a question is to extend it like this. $\endgroup$ Mar 12, 2016 at 6:11

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.