Mo logo [home] [lexicon] [problems] [tests] [courses] [auxiliaries] [notes] [staff] german flag
Mathematics-Online course: Prepcourse Mathematics - Basics - Combinatorics

Combinatorics on Sets

[previous page] [next page] [table of contents][page overview]
The following table shows the number of possibilities to select $ k$ elements from a set containing $ n$ elements. To this end, it is essential to distinguish whether the order is to be taken into account or not (that is whether one considers ordered or unordered combinations) as well as whether repetitions are allowed or not (that is whether one element can be picked several times).

  ordered unordered
with repetitions $ n^k$ $ \displaystyle \binom{n+k-1}{k}$
without repetitions $ n(n-1)\cdots(n-k+1)$ $ \displaystyle \binom{n}{k}$
(Authors: Höllig/Knesch/Abele)
i)
unordered selection without repetitions:

Given that no element can be picked more than once, there are $ n$ possibilities for the first pick, $ (n-1)$ possibilities for the second pick, and finally $ (n-k+1)$ possibilities for the $ k$-th pick, that is a total of

$\displaystyle n(n-1)\cdots(n-k+1) $

possibilities. This number then has to be divided by

$\displaystyle k! $

which is the number of permutations on a set of $ k$ elements.

ii)
unordered selection with repetitions:

Equivalently, we can determine how many possibilities exist to distribute $ n-1$ markers between $ n+k$ points.

$ \bullet$ | $ \bullet$ | $ \bullet$ | $ \bullet$ | $ \bullet$ | $ \bullet$ | $ \bullet$ | $ \bullet$
          $ \vartriangle$   $ \vartriangle$       $ \vartriangle$   $ \vartriangle$  
The number of points between the $ (i-1)$-th and $ i$-th marker minus one corresponds to the repetitions of the $ i$-th element. According to i), the number of possible markers is then equal to

$\displaystyle \binom{n+k-1}{n-1}\, , $

which matches the number given in the table.

iii)
The formulae for ordered selection are straightforward.
(Authors: Höllig/Knesch/Abele)
An urn contains one red, one green and one blue ball. The following table shows the number of possible outcomes when selecting two balls ($ n=3$, $ k=2$).

  ordered unordered
with repetitions
(replacing balls into urn)
$ n^k$ $ \displaystyle \binom{n+k-1}{k}$
  \includegraphics[width=.21\linewidth]{moeglichkeit1} \includegraphics[width=.21\linewidth]{moeglichkeit3}
  $ 3^2=9$ $ \displaystyle \binom{3+2-1}{2}=6$
without repetitions
(no replacing)
$ n(n-1)\cdots(n-k+1)$ $ \displaystyle \binom{n}{k}$
  \includegraphics[width=.21\linewidth]{moeglichkeit2} \includegraphics[width=.135\linewidth]{moeglichkeit4}
  $ 3\cdot 2 = 6$ $ \displaystyle \binom{3}{2}=3$
(Authors: Höllig/Knesch/Abele)
[previous page] [next page] [table of contents][page overview]
  automatically generated 9/18/2007