Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

In how many ways we can arrange two strings (with distinct elements) such that the order is intact?

For example if the strings are , "aA" and "bk". The valid arrangements are: "aAbk","abAk","abkA","baAk","bakA" and "bkaA" and the invalid arrangements are "akbA", "Aabk". So, in this case the required answer is $6$.

I am looking for a combinatorial approach to solve this problem. Any idea?

share|improve this question
add comment

3 Answers

If the first string has length $n_1$ and the second has length $n_2$, the answer is $\binom{n_1+n_2}{n_1}=\binom{n_1+n_2}{n_2}$. Indeed, the arrangement is uniquely determined when in the sequence of $n_1+n_2$ places you decide which are occupied by characters from the first string. Then you have a set of $n_1$ places to fill with the characters of the first string in the correct order, and the remaining places form a set of $n_2$ places to fill with the characters of the second string in the correct order.

share|improve this answer
add comment

well see it as a binary string 00 is aA and 11 is bk. now 0011,0101,0110,1001,1010,1100 are solutions, as you can see replacing the first 0 with a and second with A. and the first 1 with b and the second with k. we have all solutions. So this is just a binomial coefficient.

So let $s$ be the length of string 1 and $t$ be the length of string 2, then the count of all combinations is $\binom{s+t}{t}$.

In your example $\binom{4}{2} = 6$

share|improve this answer
add comment

Another way to look at it, using the variables of Carlo Verschoor's solution:

Take $(s+t)$ things, s labelled "1" and t labelled "2". These can be arranged in $(s+t)!$ ways. Then divide by $s!$ and $t!$ to give the distinct arrangements of 1's and 2's. Each arrangement is a different instruction set for selecting the next available item from the indicated, ordered string.

For example, "112122121..." means to take the first two characters from the start of string #1, then next from the start of String #2, then the next available in string #1, then the next two available in String #2, and so on...

share|improve this answer
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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