4

Say we have a sequence "abc123". I am trying to count the sequences that are permutations of this, yet preserve the order such that the 3 will never come before 1 or 2, b won't come before a, etc. So "a1b23c" is acceptable but "a2b31c" is not.

I attempted to count cases by hand and got the following.

$ abc123, ab1c23, ab12c3, a12bc3, a12b3c, a1b23c, a1b2c3 ,a123bc, a1bc23 ,ab123c $ and $123abc, 12a3bc, 12ab3c, 1ab23c, 1ab2c3, 1a2bc3, 1a2b3c, 1abc23, 1a23bc, 12abc3$

(I essentially reasoned that the first value had to be an $a$ or 1, so I organized them grouped based on their starting value.) This gives me 20 total permutations as a result found by brute force, and I am not sure if I am under counting or if there is a more mathematical way of approaching this permutations problem with regards to "choosing" positions and permuting the contents of the sequence.

rubyquartz
  • 511
  • 1
  • 3
  • 12
  • These are "shuffles". They are counted by binomial coefficients. See https://ncatlab.org/nlab/show/shuffle if you are feeling brave. – Angina Seng May 03 '17 at 18:58

1 Answers1

3

To create these shuffles, write down all sequences of three stars and three circle, such as $*\circ\circ*\circ*$ or $\circ\circ***\circ$. Then replace all stars by $a$, $b$, $c$ from the left, and all circles by $1$, $2$, $3$ from the left. So $*\circ\circ*\circ*$ becomes $a12b3c$ etc. So the number of these shuffles is $\binom63$.

If you have $m$ numbers and $n$ letters, you'll get $\binom{m+n}m$ shuffles.

Angina Seng
  • 158,341