3
$\begingroup$

Given a string:

$AABBC=A^2B^2C^1$

I am trying to find the Total Permutations (this may be incorrect):

$\dfrac{5!}{2!\cdot2!}=30$

My question is how would I find the partial sums (perhaps the wrong choice in words) when added together would give an index such that:

  • $AABBC=1$
  • $ABABC=2$
  • $CBABA=29$
  • $CBBAA=30$ (30 might be the wrong number here but is suppose to be the last)

I have tried to draw out a tree structure to get an idea and thought with as the minimum:

$CAABB$

$4(\dfrac{4!}{2!\cdot2!})$ + 1

And:

$CABAB$

I would get something like:

$4(\dfrac{4!}{2!\cdot2!}) + 0 + 1(\dfrac{2!}{2!}) + 0 + 0$

But I am missing something here. How would I find the sums needed for $BACAB$ ?

More specifically I am trying to find the index of a word that is arbitrarily long in alphanumeric.

So the string may also be something like:

$AAAAABBBBDDEEFFFGGGGGHIIIIJJJJKLMOOOPZZZZZ$

$\endgroup$

2 Answers 2

Reset to default
1
$\begingroup$

Here is one way to make an index, illustrated by using $BACAB$ as an example.

First, take the number of letters to the right of the $C$ and multiply by $6$. In this case we get $12$.

Now for each $B$ we take the number of $A$'s that are to the right of it, and we add that to our running total. In our case the first $B$ has two $A$'s to the right, while the second $B$ has none. That means we're up at $12 + 2 = 14$.

Lastly, add $1$ if the first non-$C$ letter is a $B$. In this case it is, so we add $1$ to get to $15$.

This gives you a unique number from $0$ to $29$ to each of the $30$ possible permutations. If you want it to go from $1$ to $30$, just add one, in this example we'd get $16$.

This indexing would not sort the list alphabetically. It would, for instance, put $BAABC$ in front of $ACBBA$. Then again, that is one way you could do it: Write the list of all permutations in alphabetical order, and just index them from there.

$\endgroup$
3
  • $\begingroup$ Thanks Arthur. Would this technique also work for a longer string? Something like: "AABBCDFHIIIIIIILNNOORSTTTUU" and "'HONORIFICABILITUDINITATIBUS" $\endgroup$
    – jmunsch
    Jul 31, 2015 at 22:31
  • 1
    $\begingroup$ (Note, I made an error, the $C$ position is worth $6$ points) What I did was first to fix $C$, and see how many permutations the other letters can make around that. That's how many points I give to each position of $C$. Then it was just a matter of trying to find a good way to give each of the $6$ different $B$-placements a unique value between $0$ and $5$. In the case of a longer word, like your first one, there is for instance only one S. Figure out the number of permutations of "AABBCDFHIIIIIIILNNOORTTTUU", and say that every letter to the right of "S" is worth that many points. $\endgroup$
    – Arthur
    Jul 31, 2015 at 22:39
  • 1
    $\begingroup$ Then do exactly the same with the rest, ignoring the S for the rest of the calculation (this is definitely a recursive process, if you've ever encountered those in computer science). Once you're done with the single letters C, D, F, H, L, R and S, you need to figure out a way to number the different positions of let's say the two U's in some unique way. Again, to each of the placements of the two U's, you assign a multiple of the number of ways all the remainging letters "AABBIIIIIIINNOOTTT" can be arranged. $\endgroup$
    – Arthur
    Jul 31, 2015 at 22:39
1
$\begingroup$

Take your letters, and distinguish same letters with subscripts, like $A_1 A_2 B_1 B_2 C$. That gives $2 + 2 + 1 = 5$ different symbols, that can be permuted in $5!$ ways. If you erase the subindices, this means e. g. $A_1 A_2$ are now the same, need to divide by $2! 2! 1!$, so the total is

$$ \frac{5!}{2! 2! 1!} = \binom{2 + 2 + 1}{2, 2, 1} $$

This is a multinomial coefficient, the coefficient of $a^2 b^2 c$ in $(a + b + c)^5$

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .