第35页

2.2 Permutations of Sets

Theorem 2.2.1
For n and r positive integers with r <= n,
P(n, r)=n*(n-1)* ……*(n-r-1)=n!/(n-r)!

Theorem 2.2.2
The number of circular r-permutations of a set of n elements is given by
P(n,r)/r=n!/r(n-r)!
In particular, the number of circular permutations of n elements is (n-1)!

2.3 Combinations (Subsets) of Sets

Theorem 2.3.1
For 0 <= r <= n,
P(n,r) = r!C(n,r)
Hence
C(n,r) = n!/r!(n-r)!

Corollary 2.3.2
For 0 <= r <= n,
C(n,r)=C(n, n-r)

Theorem 2.3.3 (Pascal's Formula)
For all integers n and k with 1 <= k <= n,
C(n,k) = C(n-1,k) + C(n-1,k-1)
Theorem 2.3.4
For n >= 0
C(n,0)+C(n,1)+C(n,2)+...+C(n,n)=2^n,
and the common value equals the number of subsets of an n-element set.