3

Okay let me briefly explain my doubt.

I'll explain some easy problems,so that you can study easily my mind and you can guess what confusion i might be going through right now.

This may be silly.But please help me out.

How do you permute the letters ABC with no character can be repeated?

We can do $3!$ arrangements.

Like, 3 ways to choose the first character, 2 ways for the second one,one way for the last character.

Okay,so far so good.

Now,how do you permute $AAB$?

$$AAB,ABA,BAA,BAA,ABA,AAB.$$

The formula will be like dividing the number of times each letter repeats.

Like, $3!/2!$ (Since $A$ is repeated).

I don't understand this part.Why we need to divide by $2!$? Reason is being told as $A$ is repeated twice. So what? What happens internally? What happens when we divide ? Subtraction should make sense here since we are eliminating the redundancy. But dividing gives the actual answer! Can somebody explain me clearly why dividing with repeated terms makes sense?

Please and thanks.

Sebastiano
  • 7,649
vaidy_mit
  • 631
  • Short answer: because you've got twice as many. That's why you need to divide by $2!=2$. If you had, say AAAB, you'd have $3!=6$times as much and would need to divide by that. – Dahn Jan 31 '14 at 15:47
  • Can you elaborate by expanding that example sir ? I'm confused. – vaidy_mit Jan 31 '14 at 15:50
  • Sadly I can't now, but others will surely do that and help you. By the way, no need to call this a silly question, it is a perfectly understandable confusion when one deals with combinatorics for the first time :) – Dahn Jan 31 '14 at 15:52
  • Thank you sir ! :D Thanks for that encouragement :D – vaidy_mit Jan 31 '14 at 15:53
  • Thanks all for the answers :) – vaidy_mit Feb 01 '14 at 18:34

5 Answers5

2

Another approach

Let's number the individual As: $$A_1,A_2,B ||A_2,A_1,B || A_1,B, A_2 || A_2,B,A_1 || B,A_1,A_2 || B,A_2,A_1$$

As you can see, we've got $3!=6$ permutations, just as we'd expect. But then somebody comes in and says "hang on, those two As are exactly the same!" - now, for example, $B,A_1,A_2$ and $B,A_2,A_1$ is the same ordering of one $B$ and two $A$s.

We need to get rid of the overcounting. We know that these duplicate answers come in pairs and so the only thing we need to do to get the right answer is to divide by two.

Dahn
  • 5,574
1

In every of the 6 permutations of $AAB$ there are $2$ $A$'s. That means we could interchange them and get the same result. So we divide by 2. (We divide, not subtract, since we counted every sequence twice!)

If we had a more general case with $a$ $A$'s and $b$ $B$'s, then each time we could permute the $A$'s in $a!$ ways and the $B$'s in $b!$ ways while the final sequence is fixed. So we would have $(a+b)!/(a!b!)$ permutations in total.

I hope this makes it clearer.

Alex
  • 2,354
1

Our Maths teacher Mr Smith told us that division was subtraction with counting.

i.e. 8 / 2 = 4 because you can take 2 from 8 exactly four times.

In this case you want to eliminate i.e. subtract the redundant repetitions. So how many are there? There is one redundant repetition for each unique permutation. So if $n$ is the number of unique permutations, you've ended up with $n+n$. Subtract one $n$ and you'll get what you want.

Equivalently, you've got $2n$, so divide by 2 to get what you want.

oks
  • 1,345
1

I want to start a bit higher:

Start with the 24 options of ABCD.

ABCD ABDC ACBD ACDB ADBC ADCB

BACD BADC BCAD BCDA BDAC BDCA

CABD CADB CBAD CBDA CDAB CDBA

DABC DACB DBAC DBCA DCAB DCBA

Then replace the C and the D both with an A

How many different options remain, by which factor is that 24 divided?

Willemien
  • 6,582
1

This can be understood by renaming the second A to A'. This gives you obviously 3!=6 possible permutations:

AA'B
ABA'
A'AB
A'BA
BAA'
BA'A

Now you can group these into pairs whose elements are equal except of A and A' being swapped:

AA'B, A'AB
ABA', A'BA
BAA', BA'A

Since A and A' shall not be distinguished we only keep one permutation from each pair, effectively dividing by two.

The same argument works for any number of A, A', A'', ... (k times) grouping them into tuples of k! elements.

wonce
  • 458