[Boards: 3 / a / aco / adv / an / asp / b / biz / c / cgl / ck / cm / co / d / diy / e / fa / fit / g / gd / gif / h / hc / his / hm / hr / i / ic / int / jp / k / lgbt / lit / m / mlp / mu / n / news / o / out / p / po / pol / qa / qst / r / r9k / s / s4s / sci / soc / sp / t / tg / toy / trash / trv / tv / u / v / vg / vip /vp / vr / w / wg / wsg / wsr / x / y ] [Search | Home]
How come you divide by the permutations that...
If images are not shown try to refresh the page. If you like this website, please disable any AdBlock software!

You are currently reading a thread in /sci/ - Science & Math

File: permutations.png (30 KB, 1261x324) Image search: [iqdb] [SauceNao] [Google]
30 KB, 1261x324
How come you divide by the permutations that are identical rather than subtracting?

I have been spending quite a bit of time thinking about this, though I have not come up with any formal reasons.

The closest thing my brain can put together is that you have some multiplicative rather than additive "overcounting".

Is it even possible to formally prove counting formulas like this without appealing to intuition?

Why is the product rule correct even?
>>
>>7798300
Think about grouping the original [math] 5 ! [/math] permutations into groups of two, each one containing the two permutations of [math]P_1[/math] and [math]P_2[/math] within that particular permutation of HAPPY.

For instance, one of the groups might be { H P[math] _1[/math] Y P [math] _2 [/math] A , H P[math] _2[/math] Y P [math] _1 [/math] A }.

The two elements in each group are identical, and elements in different groups are not identical, so we care about the number of groups. If there are 120 elements and we put them in groups of 2, there are 120 / 2 groups.

You can generalize this visual understanding to the general case, and to formally prove counting formulas like this without appealing to intuition.
>>
>Is it even possible to formally prove counting formulas like this without appealing to intuition?
It is more subtle than that.
Math is defined in such a way that these intuitive rules are correct. If you accept the fact that it is a reasonable model (which it is), then you might say that you have "proved" this intuitive thing.
But really, all you did is create a mathematical model of what you were talking about, prove things about your model, then interpret the result as a property of the initial object.

>Why is the product rule correct even?
If you have a bag containing objects coming in m shapes and n colours such that, for each shape, there is exactly one object of each colour, then you have mn objects.
Indeed, to count the objects, you may group them by shape: you then get m disjoing groups, each containing n objects. The total number of objects is the sum of the number of objects in each group, that is m times n.
You may formalize this argument using sets but that's basically the idea.
>>
>>7798321
so with 3 identical elements, each group would have 3! elements one for each ordering that otherwise appears identical? Diving makes sense to me here I think, the grouping explanation helps.

How does the multiplication (or repeated division) of group numbers when there are several groups of repeat elements like AABBC work out?

>>7798351
Well putting it that way makes it sound pretty sensible.
>>
>>7798406
AABBC
5! / (2! * 2!)
>>
>>7798834
Though why the multiplication of the two group permutations?
>>
>>7798857
There are 2! permutations of the two A's, and for each of these, there are 2! permutations of the two B's. So we add 2! to itself 2! times, which means multiplication.

It's the same reasoning as why the number of permutations of n objects is n*(n-1)*(n-1)*...*2*1.