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

Discussion Overview

The discussion revolves around categorizing permutations of a set of 20 objects into distinct patterns, specifically focusing on how to organize these permutations into groups based on the frequency of object occurrences. The scope includes combinatorial reasoning and mathematical calculations related to permutations.

Discussion Character

  • Exploratory, Technical explanation, Mathematical reasoning

Main Points Raised

  • One participant outlines a method for categorizing permutations based on the number of identical objects, providing specific categories and their counts.
  • Another participant agrees with the initial categorization but points out that some outcomes are counted multiple times, suggesting corrections to the multiplication factors used in calculations.
  • Further clarification is provided on how to determine the correct multipliers for each category, with specific combinatorial reasoning for groups like aaabc, aaabb, and aabbc.
  • A participant expresses realization of the same corrections independently, reinforcing the understanding of how certain groupings account for variations.
  • There is a query about whether a function exists for calculating permutations in a similar manner for a different set size, indicating interest in extending the discussion to larger sets.

Areas of Agreement / Disagreement

Participants generally agree on the initial categorization of groups but identify discrepancies in the multiplication factors, leading to a collaborative effort to refine the calculations. The discussion remains unresolved regarding the broader application of the method to different set sizes.

Contextual Notes

Some assumptions about the counting methods and the definitions of categories may not be fully articulated, and the discussion does not resolve the mathematical steps for larger permutations.

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.