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
best video best video best video best video best video best video best video best video best video best video best video best video best video best video best video best video best video best video best video best video best video best video best video best video best video best video best video best video best video best video best video best video best video best video best video best video best video best video best video best video best video best video