MHB How Do You Categorize Permutations of a 20-Object Set into Distinct Patterns?

[adamtj]

Hello, I am hoping this is in the right sub group please do let me know if I chose incorrectly.

So I have part of this solved ( I think)

The basics:
Total population of objects :20
slots to fill: 5
total population of sets: 3.2MM (20^⁵)My goal is to organize this total population into groups.
aaaaa - 5 of a kind
aaaab - 4 of a kind, 1 single
aaabb - 3 of a kind, 1 pair
aaabc - 3 of a kind, 2 singles
aabbc - 2 pairs, 1 single
aabcd - 1 pair, 3 singles
abcde - all singles

so using _nP_r I came up with the following:

category-count
aaaaa-20
aaaab-380
aaabc -6,840
aaabb-380
aabbc -6,840
aabcd -116,280
abcde -1,860,480

This is incomplete as it sums to 1,991,220.
the next step as I was seeing it was that there are variations of each category:
Example: aaaab,aaaba,aabaa and so on.
the plan was to calculate the permutations for each and then multiplying that by the initial calculations. but this yields much too large a population. so now I am stuck.

Here is the google sheets document I have been working with:
https://docs.google.com/spreadsheets/d/1yrWacgebsqIsOwsofIR_sNjHG5FdlLs3VOJE7s4DRDA/edit?usp=sharing

Any hints and help are greatly appreciated!

 

[Opalg]

Hello, I am hoping this is in the right sub group please do let me know if I chose incorrectly.

So I have part of this solved ( I think)

The basics:
Total population of objects :20
slots to fill: 5
total population of sets: 3.2MM (20^⁵)My goal is to organize this total population into groups.
aaaaa - 5 of a kind
aaaab - 4 of a kind, 1 single
aaabb - 3 of a kind, 1 pair
aaabc - 3 of a kind, 2 singles
aabbc - 2 pairs, 1 single
aabcd - 1 pair, 3 singles
abcde - all singles

so using _nP_r I came up with the following:

category-count
aaaaa-20
aaaab-380
aaabc -6,840
aaabb-380
aabbc -6,840
aabcd -116,280
abcde -1,860,480

This is incomplete as it sums to 1,991,220.
the next step as I was seeing it was that there are variations of each category:
Example: aaaab,aaaba,aabaa and so on.
the plan was to calculate the permutations for each and then multiplying that by the initial calculations. but this yields much too large a population. so now I am stuck.

Here is the google sheets document I have been working with:
https://docs.google.com/spreadsheets/d/1yrWacgebsqIsOwsofIR_sNjHG5FdlLs3VOJE7s4DRDA/edit?usp=sharing

Any hints and help are greatly appreciated!

Hi adamtj and welcome to MHB!

Your solution is on the right lines, but you are counting some of the outcomes more than once.

I agree with all the "category-counts" that you have for the groups. But most of the multiplication factors (in column H of the spreadsheet) are too big. The last one in particular (for the group abcde) should be 1, not 120, because you have already counted the choices a, b, c, d, e, in that order, when coming up with the total 1,860,480 for that group.

I agree with your multipliers 1 and 5 for the first two groups. For the third group (aaabc), you have already taken into account which types are to be used, namely a for the one that occurs three times, and b and c (in that order) for the two types that appear once each. The only further thing to be specified is which of the five positions are occupied by the three a's. That gives ${5\choose3} = 10$ as your multiplying factor.

For the groups aaabb and aabcd the multiplier is again 10, for the same sort of reason.

That leaves the hard case aabbc. Here, there are five places where the c could come. For each of those there are three possible orderings of the a's and b's (with an a coming first), namely aabb, abab, abba. So the multiplier here is 15.

So your multipliers in column H should be 1, 5, 10, 10, 15, 10, 1. If you use those values you should find that the sum of the entries in column I is $3,200,000 = 20^5$, as it should be.

 

[adamtj]

Hi adamtj and welcome to MHB!

Your solution is on the right lines, but you are counting some of the outcomes more than once.

I agree with all the "category-counts" that you have for the groups. But most of the multiplication factors (in column H of the spreadsheet) are too big. The last one in particular (for the group abcde) should be 1, not 120, because you have already counted the choices a, b, c, d, e, in that order, when coming up with the total 1,860,480 for that group.

I agree with your multipliers 1 and 5 for the first two groups. For the third group (aaabc), you have already taken into account which types are to be used, namely a for the one that occurs three times, and b and c (in that order) for the two types that appear once each. The only further thing to be specified is which of the five positions are occupied by the three a's. That gives ${5\choose3} = 10$ as your multiplying factor.

For the groups aaabb and aabcd the multiplier is again 10, for the same sort of reason.

That leaves the hard case aabbc. Here, there are five places where the c could come. For each of those there are three possible orderings of the a's and b's (with an a coming first), namely aabb, abab, abba. So the multiplier here is 15.

So your multipliers in column H should be 1, 5, 10, 10, 15, 10, 1. If you use those values you should find that the sum of the entries in column I is $3,200,000 = 20^5$, as it should be.

Hello Opalg

You are not going to believe me but I literally just figured the same thing as you posted and was coming back to share my findings!

As you stated, i knew 120 was not possible and knew it should be 1, but didn't have a good explanation as to why until I realized it was because abcde already accounts for all variations. so from that I hypothesized that any single objects could be grouped into an "x" object. so abcde became xxxxx and aabcd =aaxxx and so forth from that I was able to get the same numbers you did! :-)

again thank you very much for your help!

 

[adamtj]

Hi adamtj and welcome to MHB!

Your solution is on the right lines, but you are counting some of the outcomes more than once.

I agree with all the "category-counts" that you have for the groups. But most of the multiplication factors (in column H of the spreadsheet) are too big. The last one in particular (for the group abcde) should be 1, not 120, because you have already counted the choices a, b, c, d, e, in that order, when coming up with the total 1,860,480 for that group.

I agree with your multipliers 1 and 5 for the first two groups. For the third group (aaabc), you have already taken into account which types are to be used, namely a for the one that occurs three times, and b and c (in that order) for the two types that appear once each. The only further thing to be specified is which of the five positions are occupied by the three a's. That gives ${5\choose3} = 10$ as your multiplying factor.

For the groups aaabb and aabcd the multiplier is again 10, for the same sort of reason.

That leaves the hard case aabbc. Here, there are five places where the c could come. For each of those there are three possible orderings of the a's and b's (with an a coming first), namely aabb, abab, abba. So the multiplier here is 15.

So your multipliers in column H should be 1, 5, 10, 10, 15, 10, 1. If you use those values you should find that the sum of the entries in column I is $3,200,000 = 20^5$, as it should be.

in the case of aabbc, is there a function for this? I ask because 5r is just the start, I would like to do something similar for 6r too.