Transcript Basic Concepts of Discrete Probability

Elements of Combinatorics
1
Permutations
• (Weak Definition) A permutation is usually
understood to be a sequence containing each
element from a finite set once, and only once.
• The concept of sequence is distinct from that of a
set, in that the elements of a sequence appear in
some order: the sequence has a first element
(unless it is empty), a second element (unless its
length is less than 2), and so on. In contrast, the
elements in a set have no order; {1, 2, 3} and {3,
2, 1} are different ways to denote the same set.
2
Permutations
• (General Definition) A permutation is an
ordered sequence of elements selected from a
given finite set, without repetitions, and not
necessarily using all elements of the given set.
• For example, given the set of letters
{C, E, G, I, N, R}, some permutations are ICE,
RING, RICE, NICER, REIGN and CRINGE
3
Permutations
• The total number of different permutations of
n elements of a set with the cardinality n is
P(n)  n  (n  1)  (n  2)  ...  2 1  n!
P(n)  n!
4
Permutations
• The number of different (ordered)
permutations (arrangements) of r elements
selected from n is
n!
r
P(n, r )  An  n  (n  1)  ...  (n  r  1) 
(n  r )!
n!
r
P(n, r )  An 
(n  r )!
5
Combinatorics: where we need it?
• For example, if students have today Calculus
(C), Physics (P), and Discrete Mathematics (D)
classes. How we can calculate the probability
that D is the first class?
• The following 6 arrangements are possible:
CPD, CDP, PCD, PDC, DCP, DPC. Two of them
are desirable: DCP and DPC. Thus, if all events
are equiprobable, then the probability is
2/6=1/3.
6
The number of subsets of a set
• Theorem. If n is any nonnegative integer, then
a set of the cardinality n (a set with n
elements) has exactly 2n subsets.
7
Combinations
• A combination is an un-ordered collection of distinct
elements, usually of a prescribed size and taken from a
given set.
• Given a set S, a combination of elements of S is just a
subset of S, where, as always for (sub)sets the order of
the elements is not taken into account (two lists with
the same elements in different orders are considered
to be the same combination). Also, as always for
(sub)sets, no elements can be repeated more than
once in a combination; this is often referred to as a
"collection without repetition"
8
Combinations
• The number of different (not ordered)
combinations of r elements selected from n is
the number of all possible permutations
(arrangements) of r objects
r
selected from n P  n, r   An
divided by the number of all possible
permutations of r objects r!:
r
An
n!
r
C  n, r   Cn 

r ! r !(n  r )!
9
The number of subsets of a set
• Theorem. Let S be a set containing n
elements, where n is a nonnegative integer. If
r is an integer such that 0  r  n , then the
number of subsets of S containing exactly r
elements is
r
P(n, r ) An
n!
r
C (n, r )  Cn 


r!
r ! r !(n  r )!
10
Combinatorics: where we need it?
• Let students take during this semester
Calculus (C), Physics (P), and Discrete
Mathematics(D) classes, two classes/day. How
we can calculate the probability that D and P
are taken at the same day?
• There are 3 different combinations of 2
objects selected from 3: (CP=PC), (CD=DC),
(DP=PD). One of them is desirable: (DP=PD).
Thus, the probability is 1/3.
11
1st Property of Combinations
• Theorem. If r and n are integers such that
1  r  n , then
C  n, r   C  n  1, r  1  C  n  1, r 
Cnr  Cnr11  Cnr1
12
2nd Property of Combinations
• Theorem. If r and n are integers such that
1  r  n , then
C  n, r   C  n , n  r 
C C
r
n
nr
n
13
Binomial Theorem
• Binomial Theorem (I. Newton). Let x and y be
the variables, and n is a nonnegative integer.
r
Then Cn , r  0,..., n are the coefficients of
the binomial decomposition (binomial
coefficients):
0 n
1 n 1
2 n2 2
x

y

C
x

C
x
y

C
y  ...


n
n
nx
n
...  C x
r
n
nr
y  ...  C y
r
n
n
n
14
Pascal’s Triangle
C00  1
C10  1
C20  1
C30  1
C11  1
C21  2
C31  3
C22  1
C32  3
C33  1
15
Pascal’s Triangle
16
Pascal’s Triangle
0
0
0
1
0
2
0
3
0
4
C
C
C
C
C
1
1
1
2
1
3
1
4
C
C
C
C
2
2
2
3
2
4
C
C
C
3
3
3
4
C
C
C
4
4
17
Combinatorics: where we need it?
• Tournament problem. Suppose there are n
chess players and they participate in the
tournament, where everybody has to play
with all other participants exactly 1 time. How
many parties will be played in this
tournament? Cn2
• How many parties will be played if each
participant has to play with others twice? A2
n
18