Transcript Chapter 3. Introductory Combinatorics

3.3 The Characteristic function of the set
 function
from universal set to {0,1}
 Definition 3.6: Let U be the universal set, and
let AU. The characteristic function of A is
defined as a function from U to {0,1} by the
following:
1
 A ( x)  
0
x A
x A
 Theorem
3.12: Let A and B be subsets of the
universal set. Then, for any xU, we have
 (1)A(x)0 if only if A=
 (2)A(x)  1 if only if A=U;
 (3)A(x)≦B(x) if only if AB;
 (4)A(x)  B(x) if only if A=B;
 (5)A∩B(x)=A(x)B(x);
 (6)A∪B(x)=A(x)+B(x)-A∩B(x);
(7) A ( x )  1   A ( x );
(8) A B ( x )   A B ( x )   A ( x )  A B ( x )
3.4 Cardinality
 Definition
3.7: The empty set is a finite set
of cardinality 0. If there is a one-to-one
correspondence between A and the set
{0,1,2,3,…, n-1}, then A is a finite set of
cardinality n.
 Definition 3.8: A set A is countably infinite
if there is a one-to-one correspondence
between A and the set N of natural number.
We write |A|=|N|=0. A set is countable if it
is finite or countably infinite.
 Example:
The set Z is countably infinite
 Proof: f:N→Z,for any nN,
 1
 2 n
f ( n)  
1
 (n  1)
2
n is even number
n is odd number
 The
set Q of rational number is
countably infinite, i.e. |Q|=|N|=0.
 |[0，1]| 0.
 Theorem 3.13: The R of real numbers is
not countably infinite. And |R|=|[0，1]|.
 Theorem 3.14: The power set P(N) of the
set N of natural number is not countably
infinite. And |P(N)|=|R|=1.
 Theorem 3.15(Cantor’s Theorem): For
any set, the power set of X is cardinally
larger than X.
 N, P (N),P (P (N)),…
3.5 Paradox
 1.Russell’s
paradox
 AA, AA。
 Russell’s paradox: Let S={A|AA}. The
question is, does SS?
 i.e. SS or SS?
 If SS,
 If SS,
 The statements " SS " and " SS "
cannot both be true, thus the
contradiction.
 2.Cantor’s
paradox
 1899,Cantor's paradox, sometimes called
the paradox of the greatest cardinal,
expresses what its second name would
imply--that there is no cardinal larger
than every other cardinal.
 Let S be the set of all sets. |S|?|P (S)| or
|P (S)|?|(S)|
 The Third Crisis in Mathematics
II Introductory Combinatorics
Chapter 4
Introductory Combinatorics
Counting
 Combinatorics,
is an important part of
discrete mathematics.
 Techniques for counting are important in
computer science, especially in the analysis of
algorithm.
 sorting,searching
 combinatorial algorithms
 Combinatorics
 existence
 counting
 construction
 optimization
 existence
:Pigeonhole principle
 Counting techniques for permutation and
combinations
 Generating function
 Recurrence relations
4.1 Pigeonhole principle
 Dirichlet,1805-1859
 shoebox
principle
4.1.1 Pigeonhole principle :Simple Form
 If
n pigeons are assigned to m pigeonholes,
and m<n, then at least one pigeonhole
contains two or more pigeons.
 Theorem 4.1: If n+1 objects are put into n
boxes, then at least one box contain tow or
more of the objects.
 Example
1: Among 13 people there are two
who have their birthdays in the same month.
 Example 2: Among 70 people there are six
who have their birthdays in the same month.
 Example 3:From the integers 1,2,…,2n, we
choose n+1 intergers. Show that among the
integers chosen there are two such that one of
them is divisible by the other.
 2ka
 2ra and 2sa
Example 4:Given n integers a1,a2,…,an, there exist
integers k and l with 0k<ln such that
ak+1+ak+2+…+al is divisible by n.
 a1, a1+a2, a1+a2+a3,…,a1+a2+…+an.
 Example 5:A chess master who has 11 weeks to
prepare for a tournament decides to play at least one
game every day but, in order not to tire himself, he
decides not to play more than 12 games during any
calendar week. Show that there exists a succession of
(consecutive) days during which the chess master
will have played exactly 21 games.

 Concerning Application
5, Show that there
exists a succession of (consecutive) days
during which the chess master will have
played exactly 22 games.
 (1)The chess master plays few than 12 games
at least one week
 (2)The chess master plays exactly 12 games
each week
4.1.2 Pigeonhole principle:Strong Form
 Theorem
4.2: Let q1,q2,…,qn be positive
integers. If q1+q2+…+qn-n+1 objects are put
into n boxes, then either the first box contains
at least q1 objects, or the second box contains
at least q2 objects, … , or the nth box contains
at least qn objects.
 Proof:Suppose
that
we
distribute
q1+q2+…+qn-n+1 objects among n boxes.






(1)If n(r-1)+1 objects are put into n boxes, then at
least one of the boxes contains r or more of the
objects. Equivalently,
(2)If the average of n non-negative integers
m1,m2,…,mn is greater than r-1:
(m1+m2+…+mn)/n>r-1, then at least one of the
integers is greater than or equal to r.
Proof:(1)q1=q2=…=qn=r
q1+q2+…+qn-n+1=rn-n+1=(r-1)n+1, then at least
one of the boxes contains r or more of the objects。
(2)(m1+m2+…+mn)>(r-1)n，
(m1+m2+…+mn)≥(r-1)n +1






Example 6:Two disks, one smaller than the other, are each
divided into 200 congruent sectors. In the larger disk 100
of the sectors are chosen arbitrarily and painted red; the
other 100 of the sectors are painted blue. In the smaller
disk each sector is painted either red or blue with no
stipulation on the number of red and blue sectors. The
small disk is then placed on the larger disk so that their
centers coincide. Show that it is possible to align the two
disks so that the number of sectors of the small disk whose
color matches the corresponding sector of the large disk is
at least 100.
if the large disk is fixed in place
there are 200 possible positions for the small disk such that
each sector of the small disk is contained in a sector of the
large disk.
color matches the corresponding
20000/200=100>100-1
Position with at least 100 color matches
Example 7:Show that every sequence a1,a2,…,an2+1 of
n2+1 real numbers contains either an increasing
subsequence of length n+1 or a decreasing
subsequence of length n+1.
 Proof:We suppose that there is no increasing
subsequence of length n+1 and show that there must
be a decreasing subsequence of length n+1.
 For each k=1,2, …, n2+1 let mk be the length of the
longest increasing subsequence which begins with ak.
 Let mk1=mk2=…=mk(n+1)(1k1<k2<…<kn+1n2+1).
 mk1 ak1, mk2 ak2, … mk(n+1) ak(n+1),
 ak1,ak2,…,ak(n+1)(1k1<k2<…<kn+1n2+1)
 Now show that is a decreasing subsequence

 Permutations
of sets, 3.1 P79-81
 Combinations of sets,3.2 P83-84
 Permutations and Combinations of multisets
3.1 3.2 P82,P85-86
 Exercise
P181 4, P90 3,7
 1.From the integers 1,2,…,2n, we choose n+1
intergers. Show that among the integers chosen
there are two which are relatively prime.
 2.A computer network consists of six computers.
Each computer is directly connected to at least
one of the other computers. Show that there are
at least two computers in the network that are
directly connected to the same number of other
computers.
 3.Show that for any given n+2 integers there
exist two of them whose sum, or else whose
difference is divisible by 2n.