A first course in Probability (9^th ed.)�A textbook of Sheldon Ross�

Lectured by Prof. Shun-Pin Hsu

Ver. 102625

General Approach and Mathematical Level

SPHsu's Probability Course/ch.1

2

Combinatorial Analysis

SPHsu's Probability Course/ch.1

3

• Introduction
• The basic principle of counting
• Permutations
• Combinations
• Multinomial coefficients
• The number of integer solutions of equations
• Some useful identities

​

SPHsu's Probability Course/ch.1

4

SPHsu's Probability Course/ch.1

5

Permutation

n! is read as ‘n factorial’ !

SPHsu's Probability Course/ch.1

6

Permutationn

SPHsu's Probability Course/ch.1

7

Combinations (other notations used in France, Russia, China include and so on.)

Attention !

​

SPHsu's Probability Course/ch.1

8

Combinations

SPHsu's Probability Course/ch.1

9

Combinations

SPHsu's Probability Course/ch.1

10

Combinations

1. Analytical proof (by induction)

2. Combinatorial proof

Corollary:

and

SPHsu's Probability Course/ch.1

11

Combinations

Q: What do we get as x₁=x₂=…=x_r=1 ?

SPHsu's Probability Course/ch.1

12

Combinations

SPHsu's Probability Course/ch.1

13

Some useful identities

1.

​

(1.1)

​

(1.2)

SPHsu's Probability Course/ch.1

14

More on the interpretation of

The upper bound of index i can be determined at the end without affecting the result.

SPHsu's Probability Course/ch.1

15

In conclusion, we have

Identities (a) and (b) are known as the

Chu–Vandermonde identity. They can also be proved by the binomial theorem, as shown in the following:

Fixed terms

i.e.,

SPHsu's Probability Course/ch.1

16

Fixed terms

c

Not Fixed

SPHsu's Probability Course/ch.1

17

To prove the Chu–Vandermonde identity in a pure algebraic way,……….

SPHsu's Probability Course/ch.1

18

Some useful identities

2.

​

(2.1)

​

(2.2)

k

n

p

(2.3)

Can you give combinatorial explanations for these identities ?

(2.5)

(2.4)

SPHsu's Probability Course/ch.1

19

Some useful identities

Can you give combinatorial explanations for these identities ?