Is there a formula for working out combinations using the factorial of the 'choice' number?

E.g.: for a group of 6, what are the total possible combinations of up to 4 selections?

I have been doing this by adding the individual combinations, so (in the above example) I would add: $$ \def\c#1#2{\binom{#1}{#2}} \c64+ \c63 + \c62 + \c61 = 15+20+15+ 6 = 56 $$

to arrive at 56, but I'm interested to know if there is a formula that I can use. I've looked at the combinations questions but didn't see one similar.

Many thanks

  • $\begingroup$ You missed "no selection", that is $\binom 60= 1$ should be added, or? $\endgroup$ – martini Oct 15 '13 at 9:23
  • $\begingroup$ No, must be at least one. The use case is number of possible valid vote combinations in a 'first past the post' election. Voters can nominate up to the number of vacancies to make a valid vote, but an empty ballot paper is considered invalid. $\endgroup$ – mcalex Oct 15 '13 at 9:28
  • 1
    $\begingroup$ See mathoverflow.net/a/17203/36426 for partial sums of binominal coefficients. $\endgroup$ – martini Oct 15 '13 at 9:32

According to WolframAlpha the result is not very simple. The only easy cases I can think of is summing over all possibilities ($2^n$) or summing over half the possibilities. This only really works if you have an odd number of total people, but can be adapted to an even number $2k$ of people if you take care what you do with the special $k$-group case. The rest are, I believe, easiest found by getting to one of these points and add / subtract as necessary.

For instance, with $6$ people there are $2^6 = 64$ ways to choose groups in total, and since you want groups with no more than $4$ people it's easier to subtract the number of $5$-groups and $6$-groups as well as the empty group to get $$ 2^6 - \binom 6 5 - \binom 6 6 - \binom 6 0 = 64 - 6 - 1 - 1 = 56 $$ which in my opinion is easier to calculate than your summing over all valid combinations. Not much easier in this case, but it might help considerably once you get to the double digits.

  • $\begingroup$ OK, so there's no simple formula, and (though not the most efficient), the method I'm following is correct. I will probably keep adding all combinations lower than 'k' as the computer can decrement through the list faster than I can determine whether that is quicker than subtracting the remaining non combinations from the (2n) total. Many thanks. $\endgroup$ – mcalex Oct 17 '13 at 8:55

Pascal's triangle:
pascal triangle

What you are looking for is the sum on a diagonal.
The diagonal 1, 6, 15, 20, 15, 6, 1 contains what you're looking for.
The array is easy to compute a[x][y]=a[x-1][y]+a[x][y-1]
Although to find the sum on diagonal N you need O(N^2) computations.
The triangle is mirrored so you could only compute N^2/4 values.


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.