next up previous
Next: About this document ...

Some counting situations

  1. The number of ways to choose k items from a set of n:

    Order matters?

    Repetition allowed?

    count

    Yes

    Yes

    nk

    Yes

    No

    (n)k=$\displaystyle {\frac{{n!}}{{(n-k)!}}}$

    No

    No

    $\displaystyle \left(\vphantom{\begin{array}{c} n \ k \end{array} }\right.$$\displaystyle \begin{array}{c} n \ k \end{array}$$\displaystyle \left.\vphantom{\begin{array}{c} n \ k \end{array} }\right)$=$\displaystyle {\frac{{n!}}{{(n-k)!k!}}}$

    No

    Yes

    $\displaystyle \left(\vphantom{\begin{array}{c} n+k-1 \ k \end{array} }\right.$$\displaystyle \begin{array}{c} n+k-1 \ k \end{array}$$\displaystyle \left.\vphantom{\begin{array}{c} n+k-1 \ k \end{array} }\right)$

  2. The number of functions from a set with k items to a set with n items:

    1. All functions: nk

    2. One to one functions (n)k if n $ \geq$ k; 0 otherwise.

    3. onto functions: 0 if n > k; otherwise, n!S(k, n) where S(p, q) is the number of partitions of an p-element set into q nonempty equivalence classes. These are Stirling numbers of the second kind. They satisfy a recurrance

      S(p + 1, q) = S(p, q - 1) + qS(p, q)

      obtained by observing that the last of the p+1 items is either in a class by itself (giving S(p, q - 1) for the remaining equivalence classes) or it is added to one of the q classes of a partition of the remaining p items into q classes. Note that S(p, p) = 1 and S(p, 1) = 1 and that S(p, q) = 0 if p < q r q < 1.

    4. one to one onto functions: 0 unless n = k in which case n!

  3. The number of relations on an n element set:

    1. All relations: 2n2

    2. Reflexive relations: 2(n2-n)

    3. Irreflexive relations: 2(n2-n)

    4. Symmetric relations: 2$\scriptstyle {\frac{{n(n+1)}}{2}}$

    5. Antisymmetric relations: 2n3$\scriptstyle {\frac{{n(n-1)}}{2}}$

    6. Transitive relations: hard

    7. Equivalence relations: $ \sum_{{k=1}}^{n}$S(n, k)

  4. The number of elements of the union of n subsets

    $\displaystyle \sum_{{i=1}}^{n}$| Ai| - $\displaystyle \sum_{{i,j \mbox{ distinct }}}^{}$| Ai $\displaystyle \cap$ Aj| + $\displaystyle \sum_{{i,j,k\mbox{ distinct}}}^{}$| Ai $\displaystyle \cap$ Aj $\displaystyle \cap$ Ak| -...

    + (- 1)(m+1)$\displaystyle \sum_{{i_1,\ldots, i_m \mbox{ distinct }}}^{}$|$\displaystyle \bigcap_{{k=1}}^{m}$Aik|...

    This is the principle of inclusion-exclusion.

  5. The number of derangements of an n-element set is

    dn = n!$\displaystyle \left(\vphantom{1-\frac1{2!}+\frac1{3!} +...+\frac{(-1)^n}{n!}}\right.$1 - $\displaystyle {\frac{1}{{2!}}}$ + $\displaystyle {\frac{1}{{3!}}}$ + ... + $\displaystyle {\frac{{(-1)^n}}{{n!}}}$$\displaystyle \left.\vphantom{1-\frac1{2!}+\frac1{3!} +...+\frac{(-1)^n}{n!}}\right)$

    This is obtained by inclusion-exclusion.

  6. Distributions of n items into m containers:

items

Containers

 

 

distinguishable?

distinguishable?

empties allowed?

count

Yes

Yes

Yes

mn

Yes

Yes

No

m!S(n, m)

Yes

No

Yes

$\displaystyle \sum_{{k=1}}^{m}$S(n, k)

Yes

No

No

S(n, m)

No

Yes

Yes

$\displaystyle \left(\vphantom{\begin{array}{c} n+m-1 \ m-1 \end{array}}\right.$$\displaystyle \begin{array}{c} n+m-1 \ m-1 \end{array}$$\displaystyle \left.\vphantom{\begin{array}{c} n+m-1 \ m-1 \end{array}}\right)$

No

Yes

No

$\displaystyle \left(\vphantom{\begin{array}{c} n-1 \ m-1 \end{array}}\right.$$\displaystyle \begin{array}{c} n-1 \ m-1 \end{array}$$\displaystyle \left.\vphantom{\begin{array}{c} n-1 \ m-1 \end{array}}\right)$

No

No

Yes

coefficient of xn

 

 

 

in (1 + x +...xn)m

No

No

No

coefficient of xn

 

 

 

in (x +...xn)m


next up previous
Next: About this document ...

Larry Stout 2001-03-04