Editing Combination (section)

== Number of ''k''-combinations for all ''k'' ==
{{See also|Binomial coefficient#Sum of coefficients row}}

The number of ''k''-combinations for all ''k'' is the number of subsets of a set of ''n'' elements. There are several ways to see that this number is 2<sup>''n''</sup>. In terms of combinations, <math display="inline">\sum_{0\leq{k}\leq{n}}\binom n k = 2^n</math>, which is the sum of the ''n''th row (counting from 0) of the [[Binomial coefficient#Sum of coefficients row|binomial coefficients]] in [[Pascal's triangle]]. These combinations (subsets) are enumerated by the 1 digits of the set of [[base 2]] numbers counting from 0 to 2<sup>''n''</sup>&nbsp;−&nbsp;1, where each digit position is an item from the set of ''n''.

Given 3 cards numbered 1 to 3, there are 8 distinct combinations ([[subsets]]), including the [[empty set]]:

<math display="block">| \{ \{\}  ;  \{1\}  ;  \{2\}  ;  \{1, 2\} ; \{3\}  ;  \{1, 3\}  ;  \{2, 3\}  ;  \{1, 2, 3\} \}| = 2^3 = 8</math>

Representing these subsets (in the same order) as base 2 numerals:

*0 – 000
*1 – 001
*2 – 010
*3 – 011
*4 – 100
*5 – 101
*6 – 110
*7 – 111