I am trying to understand the formula behind generalizing the computation of the number of unique combinations possible for a vector of length n. Say x=(a,b,c) with n = 3, the number of possible combinations would be: [3 choose 1 (a,b,c) + 3 choose 2 (ab, ac, bc) + 3 choose 3 (abc) ]. While if n is 4, the number of possible combinations would be [4 choose 1 (a,b,c,d) + 4 choose 2 (ab, ac, ad, bc, bd, cd) + 4 choose 3 (abc, abd, bcd, acd) + 4 choose 1 (abcd)], and so on for increasing number of n. But what is the general formuation for these type of combinations?

Thanks for any help! Fra

  • 2
    $\begingroup$ $\sum_{k=0}^{n}{}_nC_k = 2^n$ and $\sum_{k=1}^{n}{}_nC_k = 2^n - 1$. $\endgroup$
    – Mosquite
    Apr 5 '17 at 20:20

With each of the $n$ components of the vector, you have 2 options - select it or not. So the number of combinations is $2^n$. If you want to exclude the case where none of the components are chosen, then subtract 1.

  • $\begingroup$ Thank you for both the answers and help! I still don't understand how to get the final number from n, for n=3 it should be 7 and for n=4 it should be 11, but do I need to specify each number to choose then (each number from 2 to n for example)? sorry if this seems basic... $\endgroup$
    – user971102
    Apr 5 '17 at 20:35
  • $\begingroup$ With $n=4$, there are $2^4-1=15$ combinations which are a,b,c,d,ab,ac,ad,bc,bd,cd,abc,bcd,acd,abd,abcd. $\endgroup$ Apr 5 '17 at 20:43
  • $\begingroup$ Thanks Chris. I realized my real experiment is a bit more complicated in that it includes also cases that are positives and negatives, i.e. for n=3 and choose 2, there are two ways of choosing 2 (a negative and a positive); for n=3 and choose 3, there are two ways of choosing 3. Same for n=4: for choose 2, there are two ways of choosing 2; for choose 3, there are two ways etc... But if I try all these combinations it does not add up to 2 x 2^n... $\endgroup$
    – user971102
    Apr 6 '17 at 3:05

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.