Головна

Різні комбінаторні співвідношення

  1. Аналіз співвідношення витрат, обсягу виробництва і прибутку (CVP-аналіз)
  2. Безробіття зумовлене негнучкістю, характерною для ринку праці; така негнучкість ускладнює встановлення необхідного співвідношення між попитом і пропозицією.
  3. У законі виділяються різні форми підприємництва. Найбільш поширені - індивідуальне, партнерське та корпоративне підприємництво.
  4. У процесі поетапного здійснення злочину злодії даної групи використовують різні способи для вирішення локальних завдань. Розглянемо їх більш детально.
  5. Хвильові передачі. Геометричні і кінематичні співвідношення.
  6. Питання 2. ФІЛОСОФСЬКІ І КОНКРЕТНО-НАУКОВІ АСПЕКТИ проблемму СПІВВІДНОШЕННЯ БІОЛОГІЧНОГО І СОЦІАЛЬНОГО В ЛЮДИНІ.
  7. Виховання в різні вікові періоди розвитку дітей

Правило суми. Якщо є кінцеві безлічі А і В, причому
A ? B = O, тоді | A U B | = | A | + | B | (Число елементів в об'єднанні множин є сума чисел елементів у величезних кількостях).

правило твори. Нехай A'B = {( ,  ) /  A,  B} - декартовій твір множин A і B, тоді | A'B | = | A | · | B | (Потужність безлічі АxВ є твір потужностей множин А і В).

Приклад 1. нехай A={1,2}, B = {a, b, c}. тоді
 A'B = {(1, a), (1, b), (1, c), (2, a), (2, b), (2, c)}. | A'B | = | A | · | B | = 2 · 3 = 6.

Правило можна узагальнити на n множин: Нехай А1, ..., Аn - Різні безлічі, тоді А1'...'Аn = {(?1, ?2, ..., ?n) | ?1 А1, ?2 А2, ..., ?n Аn}
 і | А1'...'Аn| = | А1| - | А2| --- | Аn|.

Приклад 2. Знайти число двійкових наборів довжини n.

Рішення: Нехай А1 = {0,1}, ..., Аn = {0,1}. тоді

 , Де E2 = {0,1}.

Нехай нам дано деякий кінцеве безліч X = {x1, ..., Xn}. Розглянемо деякий його підмножина {  }. Надалі таке підмножина назвемо r-вибіркою.

R-вибірки бувають двох видів:

1. Якщо в r-вибірці важливий порядок елементів, тоді ми будемо називати її r-перестановкою з n елементів.

2. Якщо в r-вибірці порядок елементів не важливий, тоді будемо називати її r-поєднанням з n елементів.

У кожному з видів можливі 2 випадки:

а)Допускається повторення елементів, тоді це r-перестановки з повтореннями (або r-поєднання з повтореннями).

b)Всі елементи різні, тоді це r-перестановки без повторень (або r-поєднання без повторень).

Затвердження 1. Число r-перестановок з повтореннями з n елементів П (n, r) = nr.

Доведення: Так як ми на кожне місце можемо поставити будь-який з n елементів, а таких місць r, значить все можливостей за правилом твори nr. Дійсно, А1 = X, ..., Аr = X, тоді .

Приклад 3. X = {1,2,3}. Скільки двозначних чисел ми можемо скласти з елементів безлічі X?

Рішення: Їх всього nr, Де n = 3, r = 2. Тоді 32 = 9 чисел, а саме числа 11, 21, 31, 12, 22, 32, 13, 23, 33.

затвердження 2. Число r-перестановок без повторень з n елементів  , де .

Доведення: ,  ; А2 = Х1, де ,  , ...,

 , де ,  . Іншими словами, на перше місце можна поставити n штук елементів, на друге -  елементів і так далі, на останній r-е місце можна поставити
 n - r + 1 елементів. Тоді за правилом твори

r| = .

Зауваження. Дуже часто r-перестановки без повторень з n елементів в літературі називають розміщенням з n елементів по r. Прийнято наступні позначення P (n, r) = Arn = (N)r (Число розміщень з n елементів по r).

Приклад 4. Х = {1,2,3}. Скільки двозначних чисел без повторюваних цифр можна скласти з елементів безлічі Х?

Рішення: Їх всього P (n, r) = n (n - 1) (n - 2) ... (n - r + 1), де n = 3, r = 2. Тоді P (3,2) = 3 · 2 = 6 чисел (12, 21, 13, 31, 23, 32).

слідство 1. Якщо в утвердженні 2 r = n, то це перестановка з n елементів, і тоді .

Приклад 5. X = {1,2,3}. Скільки тризначних чисел без повторюваних цифр можна скласти з елементів безлічі Х?

Рішення: їх всього Pn = N !, де n = 3. Тоді P3 = 3! = 1 · 2 · 3 = 6 чисел: 123, 213, 231, 321, 312, 132.

Формула Стірлінга:  (~ - Асимптотично одно).

якщо  , то .

Затвердження 3. Число r-поєднань без повторень з n елементів .

Доведення: Беремо довільну неупорядковану вибірку {  } - R-елементів. З цієї однієї невпорядкованою отримуємо r! упорядкованих. А так як все невпорядкованих вибірок  , то  - Число впорядкованих вибірок. Оскільки кожна упорядкована вибірка отримана перестановкою елементів в невпорядкованою, то

.

Приклад 6. X = {1,2,3}. знайти  : 12, 13, 23 (невпорядковані двозначні числа без цифр, що повторюються).

Приклад 7. У чемпіонаті країни з футболу беруть участь 18 команд, причому кожні дві команди зустрічаються між собою 2 рази. Скільки матчів грається протягом сезону?

Рішення: В першому колі відбудеться стільки матчів, скільки існує двоелементний підмножин у безлічі, що містить 18 елементів, тобто їх число дорівнює  = 153.

У другому колі грається стільки ж матчів, тому протягом сезону відбудеться 306 зустрічей.

числа  , Де r = 0,1, ..., n називають біноміальними коефіцієнтами.

0! = 1 (за визначенням, для зручності).

2.3. Властивості біноміальних коефіцієнтів.
 Біноміальна теорема. поліноміальна теорема

1)  - ціле число.

2) : = , =  > (  ).

3) : .

4) Біноміальна теорема.  . (1)

Доведення: >

>  елемента;

>  елементів.

Треба дізнатися, який коефіцієнт  при >  > після перемноження виходить  різних комбінацій, але деякі елементи повторюються. Тобто коефіцієнт при  дорівнює числу
 r-поєднань x з усіх n дужок, де  , тобто  . ¦

5) Слідство 2. Якщо у формулі (1) x = y = 1, то

.

6) Слідство 3. Якщо у формулі (1) x = -1, y = 1, то

.

Приклад 8. Знайти число двійкових наборів довжини n з 0 і 1, що мають r одиниць.

Рішення: Всього довічних наборів довжини n з 0 і 1 - 2n, З них, що мають r одиниць, так само

= .

Приклад 9.Для освітлення залу може бути включена кожна з 10 ламп. Скільки існує різних способів освітлення залу?

Рішення: Очевидно стільки, скільки існує підмножин у десятіелементного безлічі, тобто  . При цьому враховується і той спосіб освітлення, при якому жодна лампа не горить.

Приклад 10. Записати комплексне число  в алгебраїчній формі.

Рішення: За формулою (1) маємо

.

Значить, (2 + i)6 = -117 + 44i.

7) a) нехай  (Парне число), тоді .

b)нехай  (Непарне число), тоді

,

де [n / 2] - ціла частина числа n / 2.

Доведення:

a) Треба довести, що  , якщо  , Де r = 0, 1, ...,  - 1.

= , = , = =  <1. Так як  , то  ; n - r ? r + 1 + 1. Тоді (r + 1) / (n-r) ? (r + 1) / ((r + 1) +1) <1.

доказ для b) аналогічно.

затвердження 4. Число r-поєднань з повтореннями з n елементів

.

Доведення: Нехай {x1, ..., Xn} - Наші елементи, з них виберемо r елементів {  } Без урахування порядку, але з повторенням.

нехай x1 зустрічається ?1 раз,

x2 зустрічається ?2 рази,

...

xn зустрічається ?n раз,

де 0? ?i? r, 1? i? n; ?1 + ?2 + ... + ?n = R.

Число наших вибірок дорівнює числу рішень нашого рівняння  в цілих позитивних числах. Отже,  вибірка дає рішення  , і навпаки,  рішення дає вибірку, тобто  взаимнооднозначное відповідність між рівнянням і вибірками.

нехай ?1, ..., ?n - вирішення рівняння  . Тоді виписуємо ?1 одиниць, потім 0, потім ?2 одиниць, потім 0, і так далі:

0  0 ... 0 .

У цьому наборі одиниць r штук, нулів (n - 1) штук.

По кожному рішенню рівняння  отримаємо набори з 0 і 1 довжиною r + n - 1.

Отже, кожен такий набір дає рішення  . Тому число рішень рівняння  дорівнює числу наборів з r + n - 1 нулів і одиниць, кожен з яких має рівно r одиниць, а це число дорівнює .

Приклад 11. E = {1, 2, 3}. Скільки поєднань з повтореннями з E по 2?

Рішення: D23 = C24 = (4!) / (2! 2!) = (3-4) / 2 = 6. Усього таких поєднань 6, а саме: 11, 12, 22, 23, 13, 33.

Завдання. Якщо дано (x + y + z)4, Як знайти коефіцієнт при x2yz?

Рішення: (x + y + z) (x + y + z) (x + y + z) (x + y + z) - з кожної дужки витягуються різні змінні, таких варіантів 34.

Як виходить x2yz: x x y z

x y x z.

... ... ... ...

Як підрахувати, скільки разів зустрінеться x2yz.

Спочатку ми вибираємо x по максимальному ступені, що буде  наборів. тоді  варіантів буде для вибору y. За правилом твори  варіантів буде для вибору x2y. аналогічно,  -З12- С11 варіантів буде для вибору x2yz. Іншими словами, x2yz зустрінеться  -З1211 =  -З12 = (4!) / (2! 2!) - (2!) (1! 1!) = 3-4 = 12 разів.

Рішення подібних завдань дає наступна поліноміальна

Теорема 1. .

Доведення:(x1 + x2 + ... + Xk) ... (X1 + x2 + ... + Xk) - Всього n дужок.

Для того щоб вибрати r1 штук x1 з n дужок необхідно  варіантів. Далі у нас залишилося (n - r1) Дужок, значить, число виборів r2 штук x2 з (n - r1) Дужок буде  . Тоді загальне число виборів  буде  і т.д. Тоді число виборів rk штук xk з (n - r1 -...- rk-1) Дужок буде  , Так як r1 + ... + Rk = N.

всього виборів  буде

n!

=

r1!r2! ...rk!

Значить, коефіцієнт при  буде .

Приклад 12. Знайти коефіцієнт при x2yz в (x + y + z)4.

Рішення: За полиномиальной теоремі коефіцієнт при x2yz буде дорівнює (4!) / (2! · 1! · 1!) = 3 · 4 = 12.

Приклад 13. Скільки різних поєднань літер можна скласти з слова макака.

Рішення: Використовуємо поліноміальних теорему. Будемо оперувати з буквами як з виразами виду (М + А + К)6 .

Так як в слові макак букв >

то число шуканих слів (різних поєднань літер з слова макака) дорівнюватиме коефіцієнту при члені

МА3К2 = 60.



Попередня   5   6   7   8   9   10   11   12   13   14   15   16   17   18   19   20   Наступна

ЕДЕРАЛЬНОЕ ОСВІТИ | ББК 22.174 я73 | ВСТУП | Безлічі і операції над ними | алгебра множин | Розбиття множини на підмножини | Кортежі і декартовій твір множин | відносини | Властивості бінарних відносин | алгебра підмножин |

© 2016-2022  um.co.ua - учбові матеріали та реферати