01-Basic Principle of Counting

Lab 01 - Basic Principle of Counting
Trần Lương Quốc Đại

[email protected]
05/01/2021
1. Permutation
In mathematics, a permutation of a set is an ordered arrangement of its mem-
bers into a sequence. Let 𝑆 is a finite set of size 𝑛 objects. Selecting a sample of
size 𝑘 ≤ 𝑛 from a set 𝑆. There are two types of permutation:
• Permutations with Repetition: when each element in set 𝑆 may occur
once, twice, thrice, … upto 𝑘 times in any arrangement. So, the number of
permutations is 𝑛𝑘 .
• Permutations without Repetition: when each element in set 𝑆 that oc-
curred only once time in any arrangement. It can also be represented as:
𝑛!
𝑃𝑛𝑘 = 𝑛(𝑛 − 1)(𝑛 − 2) · · · (𝑛 − 𝑘 + 1) =
(𝑛 − 𝑘)!
For instance, let set 𝐸 = {𝑎, 𝑏, 𝑐, 𝑑}. How many different ordered arrangements
of three could be selected from the five elements if 𝐸? By direct enumeration we
see that there are 24 ways:
(a,b,c), (a,c,b), (b,a,c), (b,c,a), (c,a,b), (c,b,a),
(a,b,d), (a,d,b), (b,a,d), (b,d,a), (d,a,b), (d,b,a),
(a,c,d), (a,d,c), (c,a,d), (c,d,a), (d,a,c), (d,c,a),
(b,c,d), (b,d,c), (c,b,d), (c,d,b), (d,b,c), (d,c,b).
4!
The number of permutations is 𝑃43 = 4.3.2 = (4−3)! = 24.
1 import itertools
2
3 E = {'a', 'b', 'c', 'd'}

4 k = 3
5 # Print all the k- permutations of E
6 n = len(E)
7 permute_k = list( itertools . permutations (E, k))
8 print ("%i- permutations of %s: " %(k,E))
9 for i in permute_k :
10 print (i)
11 print ("Size = ", "%i!/(%i-%i)! = " %(n,n,k), len( permute_k ))
1
2. Combination
Unlike permutation, a combination is a selection of items from a collection,
such that the order of selection does not matter. A k-combination of a set 𝑆 is a
subset of 𝑘 distinct elements of 𝑆, the number of k-combinations (denoted by 𝐶𝑛𝑘 )
is equal to the binomial coefficient (𝑛𝑘):
𝑛 𝑛(𝑛 − 1) … (𝑛 − 𝑘 + 1) 𝑛!
𝐶𝑛𝑘 = ( ) = =
𝑘 𝑘(𝑘 − 1) … 1 𝑘!(𝑛 − 𝑘)!
whenever 𝑘 ≤ 𝑛, and which is zero when 𝑘 > 𝑛.
For instance, let set 𝐸 = {𝑎, 𝑏, 𝑐, 𝑑}. How many different groups of three could
be selected from these elements? By direct enumeration we see that there are 4
ways:
(a,b,c), (a,b,d), (a,c,d), (b,c,d)
4!
The number of combination is 𝐶43 = 3!(4−3)! = 4.
1 import itertools
2
3 E = {'a', 'b', 'c', 'd'}

4 k = 3
5 # Print all the k- combinations of E
6 choose_k = list( itertools . combinations (E,k))
7 print ("%i- combinations of %s: " %(k,E))
8 for i in choose_k :
9 print (i)
10 print (" Number of combinations = %i!/(%i!(%i-%i)!) = %i" %(n,
k,n,k,len( choose_k )))
3. Urn problems
A urn contains 8 white balls, 6 black balls and 9 red balls. Six balls are
“randomly draw” from the urn.
(a) How many ways 6 balls can be selected?
(b) Enumerate all possible cases of 6 balls.
(c) Enumerate all possible cases of the first and the last ball should be red.
Firstly, we will present a white ball by a sequence 𝑊 𝑖 (𝑖 ∈ 𝑁 ) with 𝑊 for

white color and 𝑖 for order of the ball. So, 8 white balls are ‘W1’, ‘W2’, ..., ‘W8’.
Similarly 6 black balls are ‘B1’ to ‘B6’ and 9 red balls are ‘R1’ to ‘R9’.
1 def cross(A, B):
2 '''The set of ways of concatenating one item from
collection A with one from B. '''
3 return {a + b for a in A for b in B}
2
4
5 urn = cross('W', '12345678 ') | cross ('B', '123456 ') | cross (

'R', '123456789 ')
6
7 print (urn)
Each event is a set of 6 balls are “randomly draw” from the urn, so the sample
space will be the set of all possible cases of 6 balls. Each of the 6 balls may be
included in any of the combinations any number of times.
6 23.22.21.20.19.18
𝑈 6 = 𝐶23 = = 100947
6!
1 import itertools
2 U6 = list( itertools . combinations (urn , 6))
Solution for (a):
1 print (len(U6))
Solution for (b):
1 for s in U6:
2 print (s)
Solution for (c):
1 for s in U6:
2 if s [0][0]== 'R' and s[ -1][0]== 'R':
3 print (s)
4. Exercises
1. Let set 𝐴 = {1, 2, 3, 4, 5}. Find all of 3-digit numbers can be formed from
the digits in set 𝐴 without repetitions. Assign list of the numbers to variable
𝑛𝑢𝑚_3_𝑑𝑖𝑔𝑖𝑡, and number of the numbers to variable 𝑛𝑢𝑚_𝑙𝑒𝑛𝑔𝑡ℎ.
2. A urn contains 8 white balls, 6 black balls and 9 red balls. Three balls are
“randomly draw” from the urn.
(a) Find a list of all possible 3 balls and assign to variable 𝑈 3. Assign number
of set 𝑈 3 to variable 𝑙𝑒𝑛_𝑈 3.
(b) Enumerate all possible cases of three balls of different colors.
(c) Enumerate all possible cases of the first ball being white and the second
ball red.
3. Mr. Holmes has 10 books consisting of 4 mathematics, 3 physics and 2 chem-

istry and 1 on language. He is going to put them on his bookshelf so that all
the books dealing with the same subject are together on the shelf. How many
different arrangements are possible? Print these arrangements to screen.
3
4. A committee of size 5 is to be selected from a group of 6 men and 9 women.
If the selection is made randomly, how many different selections can the com-
mittee consist of 3 men and 2 women? Print these selections to screen.
5. A standard deck of playing cards consists of 52 cards. All cards are divided
into 4 suits including spades (♠), clubs (♣), diamonds (♦) and hearts (♥). In
each suit there are 13 cards including a 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, J (jack), Q
(queen), K (king). A 5–card poker hand is said to be a “three of a kind” if it
consists of 3 cards of the same denomination, and 2 other cards of 2 different
denominations other than the one for the previous 3 cards.
(a) Making a list of all possible 5 card poker and assign to variable 𝑝𝑜𝑘𝑒𝑟_5.
Assign number of 5 card poker to variable 𝑙𝑒𝑛_𝑝𝑜𝑘𝑒𝑟_5.
(b) Find all of “three of a kind” and assign to variable 𝑡ℎ𝑟𝑒𝑒_𝑜𝑓_𝑎_𝑘𝑖𝑛𝑑.
Assign the number to variable 𝑙𝑒𝑛_𝑡ℎ𝑟𝑒𝑒_𝑜𝑓_𝑎_𝑘𝑖𝑛𝑑.

01-Basic Principle of Counting

Uploaded by

Copyright:

Available Formats

01-Basic Principle of Counting

Uploaded by

Document Information

Copyright

Available Formats

Share this document

Share or Embed Document

Sharing Options

Did you find this document useful?

Is this content inappropriate?

Copyright:

Available Formats

01-Basic Principle of Counting

Uploaded by

Copyright:

Available Formats

Lab 01 - Basic Principle of Counting

Trần Lương Quốc Đại

3 E = {'a', 'b', 'c', 'd'}

3 E = {'a', 'b', 'c', 'd'}

(a) How many ways 6 balls can be selected?

(b) Enumerate all possible cases of 6 balls.

Firstly, we will present a white ball by a sequence 𝑊 𝑖 (𝑖 ∈ 𝑁 ) with 𝑊 for

5 urn = cross('W', '12345678 ') | cross ('B', '123456 ') | cross (

3. Mr. Holmes has 10 books consisting of 4 mathematics, 3 physics and 2 chem-

You might also like