Combinations
- Thread starter Aspen
- Start date
Never mind
I dont need help any more I figured it out! thank you! :3
Im learning about combinations, but I get them mixed up with permutation. I dont have a specific problem could somebody just explain them to me? Thanks
Also I dont know what subject this is so I guessed pre-algebra, sorry
I dont need help any more I figured it out! thank you! :3
- Joined
- Nov 24, 2012
- Messages
- 3,021
Even though you've figured it out, I thought I might post this anyway, both for you and for others who might wonder the same thing.
Suppose we wish to find out how many subsets of cardinality m can be constructed from an original set of cardinality n, where m ≤ n. Let's begin by setting up a placeholder for one such subset:
{__,__,__,...,__,__,__}
Note that there are m blank spaces, corresponding to the cardinality of the subset. If we were to construct a subset at random from the original set, we would have n choices for the first blank space. In the next space, we would have n - 1 choices, in the next space n - 2 choices and so on down to a number of choices represented by the value n - (m - 1). This means that the total number of unique permutations, or sequences of elements, we could encounter would be given by:
\(\displaystyle n(n-1)(n-2)\cdots(n-(m-2))(n-(m-1))\)
Using factorial notation, we can write this as:
\(\displaystyle \dfrac{n!}{(n-m)!}\equiv\text{nPr}(n,m)\)
This is the number of permutations that arise when taking n things m at a time. In basic set theory, two sets are equivalent if they contain the same elements, regardless of the order in which they happen to be listed. Suppose that now we have our subset of cardinality m. How many ways can the same group of elements be ordered? For the first space, we would have m choices, for the second m - 2, and so on until there is 1 choice for the last space. In factorial notation this is m!.
So we take the number of permutations, divide by the number of ways the elements can be arranged, and arrive at the number of combinations:
\(\displaystyle \dfrac{n!}{m!(n-m)!}\equiv\text{nCr}(n,m)\)
Suppose we wish to find out how many subsets of cardinality m can be constructed from an original set of cardinality n, where m ≤ n. Let's begin by setting up a placeholder for one such subset:
{__,__,__,...,__,__,__}
Note that there are m blank spaces, corresponding to the cardinality of the subset. If we were to construct a subset at random from the original set, we would have n choices for the first blank space. In the next space, we would have n - 1 choices, in the next space n - 2 choices and so on down to a number of choices represented by the value n - (m - 1). This means that the total number of unique permutations, or sequences of elements, we could encounter would be given by:
\(\displaystyle n(n-1)(n-2)\cdots(n-(m-2))(n-(m-1))\)
Using factorial notation, we can write this as:
\(\displaystyle \dfrac{n!}{(n-m)!}\equiv\text{nPr}(n,m)\)
This is the number of permutations that arise when taking n things m at a time. In basic set theory, two sets are equivalent if they contain the same elements, regardless of the order in which they happen to be listed. Suppose that now we have our subset of cardinality m. How many ways can the same group of elements be ordered? For the first space, we would have m choices, for the second m - 2, and so on until there is 1 choice for the last space. In factorial notation this is m!.
So we take the number of permutations, divide by the number of ways the elements can be arranged, and arrive at the number of combinations:
\(\displaystyle \dfrac{n!}{m!(n-m)!}\equiv\text{nCr}(n,m)\)