離散數學(1)

第一章 Fundamental Principles of Counting

Enumeration, or counting, may strike one as an obvious process that a student learns when first studying arithmetic.

Our study of discrete and combinatorial mathematics begins  with two basic principles of counting: the rules of sum and product.

The Rule of Sum: If a first task con be performed in m ways, while a second task can be performed in n ways, and the two task cannot be performed simultaneously, then performing either task can be accomplished in any one of m+n ways.

The Rule of Product: If a procedure can be broken down into first and second stages, and if there are m possible outcomes for first stage and if, for each of these outcomes, there are n possible outcomes for the second stage, then the total procedure can be carried out, in the designated order, in mn ways.

For an integer n >= 0, n factorial ( denoted n¦)
is defined by 0¦=1
                         n¦=(n)(n-1)(n-2)...(3)(2)(1) for n >= 1

Given a collection of n distinct objects, any(linear) arrangement of these objects is called a permutation of the collection.

If there are n distinct objects and r is an integer, with 1<=r<=n, then by the rule of product, the number of permutation of size r for the n objects

p(n,r)=n*(n-1)*(n-2)*...*(n-r+1)
=(n)(n-1)(n-2)...(n-r+1)*(n-r)(n-r-1)...(3)(2)(1)/((n-r+1)*(n-r)(n-r-1)...(3)(2)(1))
=n¦/(n-r)¦

If there are n objects with n1 indistinguishable objects of a first type, n2  indistinguishable objects of a second type,..., and nr  indistinguishable objects of a nth type, where n1+n2+...+nr=n
then there are n¦/(n1¦n2¦...nr¦) (linear) arrangements of the given n objects.

If we start with n distinct objects, each selection, or combination, of r of these objects, with no reference to order,corresponds to r¦ permutations of size r from the n objects. Thus the number of combinations of size r from a collection of size n is

C(n,r)=P(n,r)/r¦=n¦/(r¦(n-r)¦)  0<=r<=n

The binomial Theorem
(x+y)^n=(n,0)x^0y^n+(n,1)X^1y^n-1+(n,2)X^2y^(n-2)+...+(n,n-1)x^(n-1)y^1+(n,n)x^ny^0=form k=0 to n∑(n,k)x^ky^(n-k)