Question of Counting Methods

2007-10-23 10:41 am
Suppose the we have n objects, r distinct adn n-r identical. Give another derivation of the formula: P(n,r) = r! C(n,r)
By counting the number of orderings of the n objects in two ways:
* Count the orderings by first choosing positions for the r distinct object
* Count the orderings by first choosing positions for the n-r identical object

回答 (1)

2007-10-23 12:29 pm
✔ 最佳答案
Suppose the we have n objects, r distinct adn n-r identical. Give another derivation of the formula: P(n,r) = r! C(n,r)
By counting the number of orderings of the n objects in two ways:
* Count the orderings by first choosing positions for the r distinct object
* Count the orderings by first choosing positions for the n-r identical object
ANSWER
First, since both this two method are make the ordering of the same n objects. The counting number of this two method should be the same.
First method: Count the orderings by first choosing positions for the r distinct object
Since the objects are distinct. The first object has n choice, second object has (n-1) choice. The r object has n-r+1 choice.
Number of orderings is n(n-1)...(n-r+1)=P(n,r)
Then we order the remaining n-r identical object into n-r places , but since they are identical, the number of orderings is equal to 1
So the number of orderings of first method is P(n,r)
Second method: Count the orderings by first choosing positions for the n-r identical object
Since the objects are identical. The number of orderings is equal to the combination of choosing n-r positions from n positions.That is C(n,r)
Then we order the remaining r distinct object into r places,similarly to (a). The first object has r choice, second object has (r-1) choice. The r object has 1 choice.
Number of orderings is r!
So the number of orderings of second method is r!C(n,r)
We have argued that the number of orderings of this two methods are equal. So we get the result
P(n,r) = r! C(n,r)


收錄日期: 2021-04-25 16:58:46
原文連結 [永久失效]:
https://hk.answers.yahoo.com/question/index?qid=20071023000051KK00339

檢視 Wayback Machine 備份