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

  • Context: MHB 
  • Thread starter Thread starter adamtj
  • Start date Start date
Click For Summary
SUMMARY

The discussion centers on categorizing permutations of a 20-object set into distinct patterns, specifically when filling 5 slots. The total number of sets is calculated as 3.2 million (20^5). The user initially categorized permutations into groups such as "aaaaa" (5 of a kind) and "abcde" (all singles), but faced challenges with overcounting in their calculations. The correct multipliers for each category were identified, leading to a total of 3,200,000 permutations, confirming the initial population count.

PREREQUISITES
  • Understanding of permutations and combinations, specifically nPr
  • Familiarity with combinatorial counting techniques
  • Basic knowledge of Google Sheets for data organization
  • Experience with mathematical grouping and categorization
NEXT STEPS
  • Explore advanced combinatorial techniques for larger sets, such as 6-object permutations
  • Learn about generating functions in combinatorics
  • Investigate the use of software tools for combinatorial calculations
  • Study the principles of multinomial coefficients for complex grouping
USEFUL FOR

Mathematicians, data analysts, and anyone involved in combinatorial optimization or pattern recognition in large datasets will benefit from this discussion.

adamtj
Messages
3
Reaction score
0
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^5)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 nPr 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!
 
Physics news on Phys.org
adamtj said:
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^5)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 nPr 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.
 
Opalg said:
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!
 
Opalg said:
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.