I have searched for the answer for this on the site (and on the Internet) and have not found the answer. I do apologize if this is answered and I do not have the vocabulary to ask or search for the question properly.
I am trying to determine a mathematical method for determining how many unique n-element sets can be made from a base group of elements when each element can be used only once per set.
For instance, take the numbers 0, 1, 2, 3, 4, 5, 6
0, 1, and 21 are invalid because they are not complete sets.
012, 013, 014, 015, 016, 023, 024, 025, 026, etc. are all valid.
020 is not because it uses element 0 twice.
Given the valid sets above:
021, 102, 210 are invalid (duplicates) because they use the same elements as 012.
I have determined by brute force that the answer to this for 3 element sets out of 7 unique elements is 35.
012, 013, 014, 015, 016, 023, 024, 025, 026, 034, 035, 036, 045, 046, 056, 123, 124, 125, 126, 134, 135, 136, 145, 146, 156, 234, 235, 236, 245, 246, 256, 345, 346, 356, 456
For 3 element sets out of 5 unique elements (0, 1, 2, 3, 4) is 10.
012, 013, 014, 023, 024, 034, 123, 124, 134, 234
I would like to be able to calculate the answer to this problem for any combination of base elements, and n-element sets. Using the brute force approach I am using would be impractical for large sets from very large numbers of elements.
Best Answer
The number of $k$-element subsets of an $n$-element set is often denoted by $\binom{n}{k}$. There are other notations for the same numbers, for example ${}^nC_k$, and variants. One formula for $\binom{n}{k}$ is $$\binom{n}{k}=\frac{n!}{k!(n-k)!}.$$ Here $m!$ denotes the product of all the integers from $m$ down to $1$. So for example $5!=5\cdot 4\cdot 3\cdot 2\cdot 1=120$.
Example: We do the calculation for the number of ways to choose $3$ objects from $7$. By definition, this is $\binom{7}{3}$, which is $\frac{7!}{3!4!}$. We could calculate $7!$ (it is $5040$), but there is a shortcut.
Note that $7!=7\cdot 6\cdot 5\cdot 4!$. Thus $\frac{7!}{3!4!}=\frac{7\cdot 6\cdot 5\cdot 4!}{3!4!}$. By cancellation, this is $\frac{7\cdot 6\cdot 5}{3!}$. But $3!=6$, so we get $35$.
For more information, please google Binomial Coefficients, and Pascal Triangle. Wikipedia has good writeups.