Warning: session_start() [function.session-start]: open(/var/www/nelvin/data/mod-tmp/sess_25d91b0f323f94993ddbadec0ea02eae, O_RDWR) failed: Permission denied (13) in /var/www/nelvin/data/www/ebooktime.net/index.php on line 7

Warning: session_start() [function.session-start]: Cannot send session cookie - headers already sent by (output started at /var/www/nelvin/data/www/ebooktime.net/index.php:6) in /var/www/nelvin/data/www/ebooktime.net/index.php on line 7

Warning: session_start() [function.session-start]: Cannot send session cache limiter - headers already sent (output started at /var/www/nelvin/data/www/ebooktime.net/index.php:6) in /var/www/nelvin/data/www/ebooktime.net/index.php on line 7

Warning: file_get_contents(files/survey) [function.file-get-contents]: failed to open stream: No such file or directory in /var/www/nelvin/data/www/ebooktime.net/index.php on line 82
1.3. Елементи комбінаторики : Теорія ймовірностей та математична статистика : Бібліотека для студентів

1.3. Елементи комбінаторики


Повернутися на початок книги
1 2 3 4 5 6 7 8 9 10 11 12 13 14 
15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 
30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 
45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 
60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 

Загрузка...

Правило суми. Якщо деякий об’єкт а можна вибрати т способами, а об’єкт Ь п способами, причому ніякий вибір а не збігається з жодним з виборів Ь, то один з об’єктів а або Ь можна вибрати т + п способами (1.3.1).

Правило добутку. Якщо об’єкт а можна вибрати т способами і при кожному виборі об’єкта а об’єкт Ь можна вибрати п способами, то вибір пари (а, Ь) можна здійснити т-п способами.

Узагальнене правило добутку. Якщо об’єкт а1 можна вибрати т1 способами, об’єкт а2 - т2 способами ,…, об’єктаr - тr способами, то вибір впорядкованої системи об’єктів (ах,... ,аг) можна здійснити т 1 .т2 ... тг способами (1.3.2).

Перестановками називають сполуки або групи, що скла-даються з п елементів, що розрізняються між собою і відріз-няються між собою тільки порядком їх розташування. Число всіх можливих перестановок рівне Рп = п!, де п! = 1 • 2 • 3 •... • п (1.3.3).

Наприклад, з трьох букв абв можна скласти Р3 = 3!  =

= 1-2-3 = 6 таких перестановок: абв, авб, бав, бва, ваб, вба.

Нехай є сукупність з п різних елементів. З цієї сукупності утворимо групи або сполуки зк(к< п) різних елементів.

Розміщеннями називають сполуки або сукупності з п різ-них елементів по к елементів, які відрізняються або складом елементів, або порядком їх розташування у групі.

Число всіх можливих розміщень рівне:

Аkп = п(п - 1)(п - 2) ...(п - т+1) (1.3.4). Наприклад,    з   чотирьох   букв   абвг   можна   скласти А2Л =4-3 = 12 розміщень з чотирьох елементів по два: аб, ба, ав, ва, аг, га, бв, вб, бг, гб, вг, гв.

Якщо п = k, то Аkп = Апп = п(п - l)(п - 2J...1 = п! = Рп

(1.3.5).

Комбінаціями називаються сполуки або групи, складені з п різних елементів по k елементів, які відрізняються одна від одної    хоча    б     одним     елементом.     Число     комбінацій

^k        п\         п(п-l)(п-2)...(п-k + l)

Сп=     =             (1.3.6 ).

{п-к)\к\           к\

При цьому: 0! = 1; С°п = Спп  = 1; Сп  = Сп~1 = п; Скп  =

Аk     Аk

= Сп~к; С°п + Сп + С2п + ... Спп = 2п . Число розміщень, пере-

к          к

становок і комбінацій зв’язані рівнянням: С kп =   n =   n   або

k!    Рk

А kп =РkС kп (1.3.7).

кНаприклад,    з    чотирьох   букв    абвг   можна    скласти

2    4-3

С, =     = 6 комбінацій по дві букви в кожній.

1-2

Сполуки 1) аб і ба; 2) ав і ва; 3) аг і га; 4) бв і вб; 5) бг і гб; 6) вг і гв є однією комбінацією, оскільки набір букв в кожній з шести комбінацій однаковий, а порядок їх розташування не має значення.

Перестановки з повтореннями. Якщо серед п елементів є однакові, то перестановки, які утворюються одна з одної переставлянням однакових елементів, нічим не відрізняються, тому кількість різних перестановок буде менша, ніж п\. Якщо серед елементів множини, що має п елементів є «і елементів 1-го типу, «2 елементів 2-го типу, ... щ елементів £-го типу («! + «2 + • • • + Щ = п), то число всіх перестановок такої множини позначається Р„(nu...nk) і рівне

п\

P(n,,n2,...nk) =                        (1.3.8).

nx\n2\..nk\

Розміщення з повтореннями. Розміщенням з повторен-нями з п елементів по k називається будь-яка впорядкована к-множина виду (ah...cik), де а\,...ак - елементи множини (не обов’язково  різні).  Число  всіх розміщень  з  повтореннями

позначається   Акп    (тут  можливе  к > п)  і  рівне   Акп = пк.

Розміщення з повтореннями з п елементів по к називають також впорядкованими £-вибірками з поверненням з «-мно-жини.

Приклад. Код замка складається з шести цифр. Загальна кількість усіх можливих наборів з шести цифр рівна числу

розміщень з повтореннями з 10 елементів по 6:  До =10б =

=1000000.

Комбінації з повтореннями. Комбінацією з повторен-нями з п елементів по k називається будь-яка ^-множина виду |а1,а2,...а4.},   де   аь   а2,   ...   ак  -   елементи   множини   (необов’язково різні). Число всіх комбінацій з повтореннями з п елементів по к позначається Скп   (тут можливе к>п) і рівне

Tfr       ^k        (n + k-1)!

С =с ,_1 =         (1.3.10).

к!(п-1)!

Приклад. Кількість способів, якими можна вибрати: а) шість цифр з десяти цифр дорівнює кількості комбіна-цій з повтореннями з 10 елементів по 6:

С 1 0 = Q610+6-1 = — =            = 5005;

15!     9!-10-11-12-13 -1415

10        10+6-1

6!-9!    1-2-3-4-5-6-9!

б) десять цифр з шести цифр дорівнює кількості комбіна-

цій з повтореннями з 36 елементів по 10:

С 10    ^10      15!      10!11-12-13-14-15

С  =С10 1 =    =          = 3003.

10!-5!        10!1-2-3-4-5



Warning: Unknown: open(/var/www/nelvin/data/mod-tmp/sess_25d91b0f323f94993ddbadec0ea02eae, O_RDWR) failed: Permission denied (13) in Unknown on line 0

Warning: Unknown: Failed to write session data (files). Please verify that the current setting of session.save_path is correct (/var/www/nelvin/data/mod-tmp) in Unknown on line 0