Next: About this
document ...
Some counting situations
The number of ways to choose k items from a set of n:
Order matters? 
Repetition allowed? 
count 
Yes 
Yes 
n^{k} 
Yes 
No 
(n)_{k}= 
No 
No 
= 
No 
Yes 
The number of functions from a set with k items to a set with n items:
All functions: n^{k}
One to one functions (n)_{k} if n k; 0 otherwise.
onto functions: 0 if n > k; otherwise, n!S(k, n) where S(p, q) is the number of partitions of an pelement 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.
one to one onto functions: 0 unless n = k in which case n!
The number of relations on an n element set:
All relations: 2^{n2}
Reflexive relations: 2^{(n2n)}
Irreflexive relations: 2^{(n2n)}
Symmetric relations: 2^{}
Antisymmetric relations: 2^{n}3^{}
Transitive relations: hard
Equivalence relations: S(n, k)
The number of elements of the union of n subsets
 A_{i}   A_{i} A_{j} +  A_{i} A_{j} A_{k} ...
+ ( 1)^{(m+1)}A_{ik}...
This is the principle of inclusionexclusion.
The number of derangements of an nelement set is
d_{n} = n!1  + + ... +
This is obtained by inclusionexclusion.
Distributions of n items into m containers:
items 
Containers 


distinguishable? 
distinguishable? 
empties allowed? 
count 
Yes 
Yes 
Yes 
m^{n} 
Yes 
Yes 
No 
m!S(n, m) 
Yes 
No 
Yes 
S(n, k) 
Yes 
No 
No 
S(n, m) 
No 
Yes 
Yes 

No 
Yes 
No 

No 
No 
Yes 
coefficient of x^{n} 



in (1 + x +...x^{n})^{m} 
No 
No 
No 
coefficient of x^{n} 



in (x +...x^{n})^{m} 
Next: About this
document ...