6
$\begingroup$

If you had 4 elements, and you wanted to find all possible combinations of those 4, you take the factorial. But, what if you also wanted to consider combinations of 3, 2, 1 and 0 (where you're still using those 4 elements)? If you have n elements, and want to find all combinations of n, (n -1), (n -2) and so on, how would you go about it?

Also, sorry if I didn't word this question correctly.

$\endgroup$
0

3 Answers 3

5
$\begingroup$

If order doesn't matter, you can use ${n \choose 0} + {n \choose 1} + {n \choose 2} + \dots + {n \choose n} = 2^n$

The intuition here is that we're simply summing up all the possible combinations of different length-ed sets. We start with the combinations of length zero (there's only one - the empty set), and then add the combinations of length one (there's $n$ of them), etc. until we get to adding the combinations of length $n$ (there's only one).

Johanna's answer gives a good intuition of the $2^n$ value. Another way to think about it, is whenever we add a new element to the set, it must cause the number of possible subsets of that set to double in size. Think about it: All the previous possible subsets are still possible, but now we can create a copy of each of them that contains the new element - in doing so we double the number of possible subsets.


If order does matter you can use: ${n \choose 0}0! + {n \choose 1}1! + {n \choose 2}2! + \dots + {n \choose n}n!$

All we do here is multiply each element in the last equation by the number of different arrangements that are possible for each length. If, for example, we're considering a set of 7 elements, there are $7!$ different ways of rearranging that set. Note that this assumes that your set elements are unique (i.e. it's a proper set). If you have duplicate elements, don't use this formula (because, for example, it will count the ordered set AAB twice, given that we can switch the positions of the As).

Perhaps an easier way to think about the ordered case it we're just summing permutations of each possible length: $^n P_0 + ^n P_1 + ^n P_2 + \dots + ^n P_n $

$\endgroup$
2
  • $\begingroup$ If I have elements [A, B, C] then I can make [A, B, C, AB, AC, BC, ABC]. I'm counting seven unique combinations, not 2^3=8 $\endgroup$ Commented Jun 26, 2020 at 14:22
  • 1
    $\begingroup$ @DanielFreeman This will include the empty set, so [, A, B, C, AB, AC, ABC] $\endgroup$ Commented Feb 24, 2021 at 17:41
3
$\begingroup$

What you are looking for is every possible subset of the set of elements (in this case $4$ of them). To find that, you can either choose or not choose every element, so you have two choices for each element. Hence there are $2^n$ subsets of a set of size $n$.

EDIT: If order matters then we have more of them: $n + n(n-1) + n(n-2) + \dots + n!$ in particular. I'm not sure what the closed form of this (if any exists) is.

$\endgroup$
7
  • $\begingroup$ I didn't even think of a power set... I feel dumb haha Can you go a bit into more detail and explain why the number is (2^n)? $\endgroup$ Commented Jan 24, 2015 at 3:53
  • $\begingroup$ @JulianJefko There is a cool identity relating power sets with combinations: ${n \choose 1} + {n \choose 2} + \dots + {n \choose n} = 2^n$. $\endgroup$
    – user141592
    Commented Jan 24, 2015 at 3:54
  • $\begingroup$ But, if I had 3 elements, A B and C, the possible combinations are A,B,C, AB, AC, BC, BA, CA, CB, ABC, ACB, and so on. So, I have more than eight. Im sorry, I should've said order matters. $\endgroup$ Commented Jan 24, 2015 at 3:59
  • 1
    $\begingroup$ Interesting! Thank you! $\endgroup$ Commented Jan 24, 2015 at 4:08
  • 2
    $\begingroup$ @Johanna I think you've forgotten ${n \choose 0}$. So it should be ${n \choose 0} + {n \choose 1} + {n \choose 2} + \dots + {n \choose n} = 2^n$ $\endgroup$
    – user270617
    Commented Nov 7, 2016 at 4:20
0
$\begingroup$

You are looking for $\binom{0}{n}\cdot n! + \binom{1}{n}\cdot(n-1)! + \binom{2}{n}\cdot(n-2)! + \cdots + \binom{n}{n}\cdot 0!$.

There is a lot of information about this function at https://oeis.org/A000522.

$\endgroup$
2
  • $\begingroup$ Thanks induktio for the edit - technically the dot for multiply goes on the base line, the central dot is for vector dot product. $\endgroup$
    – JMP
    Commented Jan 25, 2015 at 7:06
  • $\begingroup$ Central dot for multiplication is standard where a period is used as a decimal point. On this site, you will see the period used as a decimal point, almost never the comma. $\endgroup$
    – user147263
    Commented Jan 25, 2015 at 17:19

You must log in to answer this question.

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