2
$\begingroup$

I am a biologist and my math skills have become a bit rusty, so any help would be appreciated. I would like to know how to calculate how many combinations there exist any given number of combinations and how many of those are unique.

I would really like to know how to calculate this for any number of combinations (not just 0-9 but like 20 or 30) and numbers in the combinations (1-1 or 1-1-1 or 1-1-1). In this scenario 1-2-2 and 2-1-1 and 2-2-1 are all identical (= 1-2) so the position number in the digit is not important and only non-redundant numbers are counted.


example data made by brute force in R for numbers 0-9:

  • 1 number in the combination (0,1,2,3,4,5,6,7,8,9):
  • 10 possibilities and 10 unique possibilities

2 numbers in the combination (0-1,0-2,0-3,0-4...):

  • 100 possibilities (10 combinations of 1 number only and 90 combinations where 2 different numbers are found)
  • 55 unique (10 combinations of 1 and 45 of 2 (because 1-2 and 2-1 are the same)

3 numbers in the combination (0-0-1,0-0-2,0-0-3...):

  • 1000 possibilities (10+270+720) and 175 unique (10+45+120)

4 numbers in combination (0-0-0-1,0-0-0-2...):

  • 10000 possibilities (10+630+4320+5040) and 385 unique (10+45+120+210)

But what would the general formula be for calculating these numbers (i.e. for the 4 digit combinations on how to calculate that it was 10,630,4320,5040 for combinations and 10,45,120,210 for unique combinations with 10 numbers per digit but what is the search space for 30 numbers per digit position and 16 digits in each combination?

$\endgroup$

4 Answers 4

1
$\begingroup$

In the first case the total is easier than the components; in the second the components are easier than the total.

Let's suppose you are choosing $m$ times from $n$ possible digits, and you are interested in cases where you end up with $k$ distinct digits.

In the first case of ordered digits, possibly with duplicates:

  • There are $n^m$ possible choices overall: for example with $n=10$ and $m=4$ you have $10^4=10000$

  • There are ${n \choose k} k! \lbrace\textstyle{m\atop k}\rbrace$ possible choices with $k$ distinct digits, where ${n \choose k}$ is a binomial coefficient and $\lbrace\textstyle{m\atop k}\rbrace$ is a Stirling number of the second kind: for example with $n=10$ and $m=4$ and $k=2$ you have $45 \times 2\times 7=630$

In the second case of unordered deduplicated digits:

  • There are $\displaystyle {n \choose k}$ possible choices with $k$ distinct digits (though you need $k \le m$: for example with $n=10$ and $m=4$ and $k=2$ you have $45$
  • The total is then $\displaystyle \sum_{k=1}^{\min (n,m)} {n \choose k}$. For example with $n=10$ and $m=4$ you have $10+45+120+210=385$. I am not aware of a simple expression for this in general, though when $m \ge n$ it is $2^n-1$
$\endgroup$
2
  • $\begingroup$ Hi Henry. Thank you for your help. That would have taken me forever to find this without your help. The R code is fac=function(n,k) { factorial(n)/(factorial(k)*factorial(n-k)) } ster=function(n,k) { for(j in 1:k){l[j]=(-1)^(k-j)*fac(k,j)*j^n} 1/factorial(k)*sum(l) } n=10;m=4;k=2 fac(n,k)*factorial(k)*ster(m,k) #630 #combinations n=10;m=4;k=2;l=0 for(j in 1:m){l[j]=fac(n,j)} sum(l) #385 $\endgroup$ Nov 10, 2016 at 11:34
  • $\begingroup$ @user2031910: you might find choose(n,k) * sum((-1)^(k-(1:k)) * choose(k, 1:k) * (1:k)^m) and sum(choose(n, 1:min(n,m))) slightly simpler versions to produce $630$ and $385$ $\endgroup$
    – Henry
    Nov 10, 2016 at 11:53
0
$\begingroup$

Suppose there are $d$ digits and we are looking at combinations of length $n\in\{1,\dots,d\}$.

Then for $k=1,\dots,n$ we find: $$\binom{d}{k}$$ combinations with $k$ distinct numbers. It is no more than a matter of choosing $k$ out of $d$.

So the total number of unique possibilities is: $$\sum_{k=1}^n\binom{d}{k}$$

In order to find all possibilities for $d,n,k$ we must multiply $\binom{d}{k}$ with the number of surjections $\{1,\dots,n\}\to\{1,\dots,k\}$ which leads to: $$\binom{d}{k}\sum_{j=0}^{k}(-1)^{j}\binom{k}{j}\left(k-j\right)^{n}$$

possibilities.

So an expression for the total number is: $$\sum_{k=1}^n\sum_{j=0}^{k}(-1)^{j}\binom{d}{k}\binom{k}{j}\left(k-j\right)^{n}$$

I don't exclude that there is a more elegant expression for this, but I don't know it.

$\endgroup$
0
$\begingroup$

Thank you for your great help. That saved me A LOT of time. The R code for calculating the question for any m,k,n (according to Henry nomenclature)

fac=function(n,k) { factorial(n)/(factorial(k)*factorial(n-k)) }

ster=function(n,k) { for(j in 1:k){l[j]=(-1)^(k-j)*fac(k,j)*j^n} 1/factorial(k)*sum(l) }

n=10;m=4;k=2

fac(n,k)*factorial(k)*ster(m,k)

Answer=630

Combinations

n=10;m=4;k=2;l=0

for(j in 1:m){l[j]=fac(n,j)};sum(l)

Answer=385

$\endgroup$
1
  • 1
    $\begingroup$ you might find choose(n,k) * sum((-1)^(k-(1:k)) * choose(k, 1:k) * (1:k)^m) and sum(choose(n, 1:min(n,m))) slightly simpler versions to produce $630$ and $385$ $\endgroup$
    – Henry
    Nov 10, 2016 at 11:55
0
$\begingroup$

If you allow the numbers to be the same and the order does matter (so $12$ is different from $21$) then I guess you already have the intuition, that the number is $n^k$, where $n$ is the length of the data (10 in your example) and $k$ is the length of your "combination" (or, as mathematicians would prefer to call it, permutation with repetitions). Why is that? As you have no restriction, for all elements, you choose one of $n$ possibilities. Overall, for $k$ numbers you multiple $n\cdot\ldots \cdot n $, $k$ times, which is $n^k$.

Then you jump to a combination, which differs in two aspects: first, repetition is not allowed, and second, order does not matter. The number of them is ${n \choose k} =\frac{n!}{k!(n-k)!}.$ The intuition is somewhat more complicated. First, assume order matters, but no repetition is allowed (these are permutations). You can then choose the first number in $n$ ways, the next in $n-1$ ways (no repetition!) etc., the last $k$-th element in $n-k+1$ ways. So you have $n\cdot(n-1)\ldots(n-k+1)=\frac{n!}{(n-k)!} $ ways.

Now, you want the order to not matter. For each of the $k$-long permuation (e.g. 123) you have $k!$ possible versions (e.g. 123,132,231,213,312,321). So you have to divide the last result by $k!$ to get what you need. Overall, you have $n \choose k$ possibilities.

The thing that you call "unique combination" is actually a sum of all combinations (in the mathematical sense) of length $\leq k$. So, for $n=10$ and $k=2$ you choose first ${10 \choose 1}=10$ combinations of size $1$ and ${10\choose 2}=45$ combinations of size $2$, in total $55$ combinations. The final result is in general: $$\sum_{i=1}^k{n \choose i}$$

R surely does have a command for $n \choose k$, you just need to sum it up.

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .