Combinatorics and computing



Download 131,78 Kb.
bet5/9
Sana11.02.2022
Hajmi131,78 Kb.
#443224
1   2   3   4   5   6   7   8   9
Bog'liq
Diskret (maruza)

Example 9.4.1 How many anagrams (permutations of the letters) are there of the following words?


(a) ANSWER (b) PERMUTE (c) LITTLE


(a) Since ANSWER has 6 different letters, the number of anagrams is 6! = 720.
(b) There are 7! ways of arranging 7 letters; however, this assumes that all the letters are different. In the present case, the number of anagrams is only half that number, because interchanging the two Es in an anagram does not produce a new anagram. The answer is 7!/2 = 2520.
(c) There are 6! permutations of six letters, but again we need to take care to avoid double counting. In each of these 6! arrangements, we can swap the Ts or the Ls or both without obtaining new anagrams. The number of different anagrams is therefore 6! / 4 = 180.
Note that in each case the original word is counted as one of the anagrams.


A more general permutation problem arises if the elements to be arranged are chosen from a larger set. Suppose we want to select r elements from a set with n elements (where n > r), and arrange those r elements in a particular order. In how many ways can this be done?
This question can be answered in a similar manner to the previous one. The first element of the permutation can be any one of the n elements in the larger set. The second element must then be chosen from the remaining n – 1 elements, the third element from the remaining n – 2 elements, and so on, until r elements have been chosen. The last (r th) element is chosen from the n – r + 1 elements remaining at that stage. By the Multiplication principle, the total number of ways this can be done is:


n(n - 1)(n - 2) ... (n – r + 1)


This expression is denoted by n P r . It is not difficult to see that we can also write n P r in terms of factorials in the following way:

Example 9.4.2 As part of a market research survey, you are shown a list of 20 types of chocolate bar, and asked to list your five favourite bars in order of preference. How many different responses to this question are there?


Solution You are selecting five bars from a larger set of 20 bars. Since the order in which the five bars are listed is important (that is, the same selection in a different order counts as a different response), this is a problem involving permutations. The answer is:


nP5 = 20 × 19 × 18 × 17 × 16 = 1 860 480



Download 131,78 Kb.

Do'stlaringiz bilan baham:
1   2   3   4   5   6   7   8   9




Ma'lumotlar bazasi mualliflik huquqi bilan himoyalangan ©hozir.org 2024
ma'muriyatiga murojaat qiling

kiriting | ro'yxatdan o'tish
    Bosh sahifa
юртда тантана
Боғда битган
Бугун юртда
Эшитганлар жилманглар
Эшитмадим деманглар
битган бодомлар
Yangiariq tumani
qitish marakazi
Raqamli texnologiyalar
ilishida muhokamadan
tasdiqqa tavsiya
tavsiya etilgan
iqtisodiyot kafedrasi
steiermarkischen landesregierung
asarlaringizni yuboring
o'zingizning asarlaringizni
Iltimos faqat
faqat o'zingizning
steierm rkischen
landesregierung fachabteilung
rkischen landesregierung
hamshira loyihasi
loyihasi mavsum
faolyatining oqibatlari
asosiy adabiyotlar
fakulteti ahborot
ahborot havfsizligi
havfsizligi kafedrasi
fanidan bo’yicha
fakulteti iqtisodiyot
boshqaruv fakulteti
chiqarishda boshqaruv
ishlab chiqarishda
iqtisodiyot fakultet
multiservis tarmoqlari
fanidan asosiy
Uzbek fanidan
mavzulari potok
asosidagi multiservis
'aliyyil a'ziym
billahil 'aliyyil
illaa billahil
quvvata illaa
falah' deganida
Kompyuter savodxonligi
bo’yicha mustaqil
'alal falah'
Hayya 'alal
'alas soloh
Hayya 'alas
mavsum boyicha


yuklab olish