0
$\begingroup$

I more or less understand this answer that when you want to count number of permutations with repetitive symbols, for example for symbols a,a,a,b,b. You take 5! and divide by 3! * 2! because a occurs 3 times and b 2 times. As I said I understand the answer I linked.

What I don't understand is following, it seems the formula to compute permutation with repetitive symbols is actually the binomial coefficient, e.g. the answer to above question would be

C[5,3].

I fail to see the relationship between (1) the problem to compute permutations with repetitive symbols and (2) the problem which binomial coefficient C[N,K] solves, which is to list subsets of N elements of size K. These two address seemingly two different tasks.

Can anyone help me see the relationship between these two problems? And why the binomial coefficient solves the problem with permutation with repetitive symbols?

Ah actually I observed interesting thing now, those two problems have same solutions when in repetitions we have only two different characters, e.g. in following cases both the answer I linked and binomial coefficient formula will give correct results: "ccaaaa", "ddddffff", "ggggghhhh".

However, if we have more symbols with repetitions then binomial coefficient doesn't work anymore, e.g. in such cases it doesn't work anymore: "aaaabbbccccdddd" - because in binomial coefficient you can't express denominator like 4!3!4!4!, which is correct denominator in this case according to answer I linked.

So can someone explain why the two problems have same answer when we have two distinct letters with repetitions? Like I said again I am looking for such explanations because the two problems (binomial coefficient and permutation with repetitive symbols) address seemingly two different things.

To sum up I am interested more on intuitive level how and why can we use the binomial coefficient to solve the problem of permutation when we have two repeating symbols?

$\endgroup$

1 Answer 1

Reset to default
1
$\begingroup$

Well, the number of ways you can arrange $a,a,a,b,b$ amounts to the number of ways to choose the locations for the three $a$s, since the $b$s will just go in the other two spots. But choosing locations for the $a$s is simply choosing a $3$-element subset of the set of all $5$ locations, of which there are $C[5,3],$ as you noticed.

Let's number our spots--$\{1,2,3,4,5\}.$ Then if we went with the arrangement $aabab,$ this would correspond to the subset $\{1,2,4\},$ for example. On the other hand, the subset $\{2,3,5\}$ would correspond to the arrangement $baaba.$

As you already observed, this only works with two types of objects to permute, since the locations of the first type of object tell the whole story. Otherwise, we can analogously use multinomial coefficients. (Note that the article uses "permutations with repetition" differently than you do.)

$\endgroup$
5
  • $\begingroup$ I've expanded my answer to try to clear this up. Does it seem like it makes sense? If so, can you provide me with an example or two, so I can verify your understanding? $\endgroup$
    – Cameron Buie
    Jul 4, 2018 at 18:46
  • $\begingroup$ Yeah I think I got it you reduced the permutation problem to following: what are subsets of length 3 of 5 elements? assuming that those 5 elements are indexes of for a. And those subsets actually give all the different permutations, right? $\endgroup$
    – user574115
    Jul 4, 2018 at 18:47
  • $\begingroup$ so the trick was to use C[N,M] for indexes; that is why I failed to see the relationship originally $\endgroup$
    – user574115
    Jul 4, 2018 at 18:48
  • $\begingroup$ Yep! That's the idea. $\endgroup$
    – Cameron Buie
    Jul 4, 2018 at 18:48
  • $\begingroup$ thanks i suppose now it makes more sense, interesting. $\endgroup$
    – user574115
    Jul 4, 2018 at 18:50

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy