文档介绍：Chapter 1 Fundamental Principles of Counting
Wen-Hsiang Lu (盧文祥)
Department puter Science and Information Engineering,
National Cheng Kung University
2007/02/26
Counting
Capable of solving difficult problems.
Coding theory, probability and statistics
Help the analysis and design of efficient algorithms.
.
The Rules of Sum and Product
The Rule of Sum
If a first task can be performed in m ways, while a second task can be performed in n ways, and the two tasks cannot be performed simultaneously, then performing either task can be plished 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 es for the first stage and if, for each of these es, there are n possible es for the second stage, then the total procedure can be carried out, in the designated order, in mn ways.
Ex. : If a license plate consists of two letters followed by four digits, how many different plates are there?
The Rules of Sum and Product
The Rule of Sum
If a first task can be performed in m ways, while a second task can be performed in n ways, and the two tasks cannot be performed simultaneously, then performing either task can be plished 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 es for the first stage and if, for each of these es, there are n possible es for the second stage, then the total procedure can be carried out, in the designated order, in mn ways.
Ex. : If a license plate consists of two letters followed by four digits, how many different plates are there? 262610101010
Permutations
Permutation: counting linear arrangements of distinct objects
If there are n distinct objects and r is an integer, with 1 r n, then by the rule of product,
The number of permutations of size r for the n objects is
Example
Given 10 students, three are to be chosen and seated in a row. How man