Подякувати Студентському архіву довільною сумою
Admin
26.02.2023 12:38
Дякуємо, що користуєтесь нашим архівом!
Знаходження числа впорядкованих і невпорядкованих вибірок з повторенням
Інформація про навчальний заклад
ВУЗ:
Національний університет Львівська політехніка
Інститут:
Не вказано
Факультет:
Не вказано
Кафедра:
Кафедра прикладної математики
Інформація про роботу
Рік:
2006
Тип роботи:
Інші
Предмет:
Дискретна математика
Група:
ПМ-31
Частина тексту файла (без зображень, графіків і формул):
Міністерство освіти та науки України
Національний університет „Львівська політехніка”
кафедра прикладної математики
з курсу „Дискретна математика”
на тему:
„Знаходження числа впорядкованих і невпорядкованих вибірок з повторенням”
Зміст
Вступ…………...................................................................................3
1. Перестановки…………......................................................................4
2. Розміщення………..........................................................................7
3. Комбінації……………………………...……...............................14
4. Список використаної літератури ................................................17
Вступ
Вибірка, вибір… Це явище знайоме, мабуть, кожній дорослій людині. Воно для нас швидще психологічного характеру, адже в житті кожного приходиться ставити перед собою певний вибір. Але в даній роботі йтиметься не про вищезгаданий „страшний фатум”, а про математичний вибір. Саме з таких, на перший погляд, простих речей розпочинався розвиток математичних наук. Дуже важливим є поняття вибірок для сучасного програмування, що є прийнятним і цікавим для мене особисто.
Як відомо, існує кілька різновидів вибірок (сукупності елементів або речей, які не обов’язково повинні мати спільні властивості), таких як вибірка із поверненням, вибірка без повернення, число комбінацій, число перестановок і навіть частково сюди можна віднести поняття „факторіалу”. Дана праця несе досить таки непогано висвітлені (як на мою думку) приклади із застосуванням даних понять і окремих задач, в основі яких всюди присутня одна спільна тема – вибірка.
1. Перестановки
Означення 1.1. Нехай впорядковується (задається порядок елементів) множина М* потужності п, яка не є різноелементною і містить k1 елементів 1-го типу, k2 елементів 2-го типу, ..., ks елементів s-го типу (k1+k2+…+ks=n) причому елементи однакового типу вважаються невідрізнимими.
Одержану при цьому впорядковану множину називають перестановкою з п елементів з повторенням.
Через наявність однакових елементів не всі перестановки з повторенням будуть різними (відрізнимими), тому виникає питання про визначення кількості лише відрізнимих перестановок.
Потужність множини всіх відрізнимих перестановок з повторенням з n елементів, про які йдеться в означенні 1.1, позначається символом Сn (k1,k2,…,k).
Надалі слово "відрізнимі" будемо опускати, розуміючи, що саме такі перестановки з повторенням і маються на увазі.
За допомогою ОПК (основного правила комбінаторики), доведемо формулу обчислення Сn (k1, ,k2,...,ks).
Розглянемо скінченну множину М * , яка не є різноелементною і має k1, однакових елементів 1-го типу, k2 однакових елементів 2-го типу, ..., ks однакових елементів s-го типу (k1+k2+…+ks=n). Скільки відрізнимих перестановок має множина М*?
Якби множина М * була різноелементною, то вона мала б п! відрізнимих перестановок. Насправді внаслідок наявності однакових елементів деякі перестановки будуть невідрізнимими, тому їх треба об'єднувати в один клас і рахувати як одну перестановку. Обчислимо потужність такого класу.
Нехай - довільна фіксована перестановка множини М *. Якщо в перестановці довільно поміняти місцями лише елементи 1-го типу (перша дія D1, число способів її виконання ), потім - лише елементи 2-го типу (друга дія D2, число способів її виконання )…, лише елементи s-гo типу (s-та дія Ds, число способів її виконання ), то
отримаємо невідрізниму від неї перестановку. Їх загальна кількість за ОПК становитиме число k1!∙k2! ∙ ∙ ∙ ks! (у це число включається і ).
Для іншої перестановки відрізнимої від , також буде
k1!∙k2! ∙ ∙ ∙ ks! невідрізнимих від неї перестановок і т.д.
Отже, сукупність з n! перестановок множини M* розкладається на класи невідрізнимих перестановок, ці класи попарно не перетинаються і мають однакову потужність, яка дорівнює k1!∙k2! ∙ ∙ ∙ ks!
Отже, відрізнимих перестановок множини М* буде стільки, скільки є класів, тобто
(1.1)
Числа Сn (k1,k2,…,k) (kj>0, kl+k2+…+ ks =п) назив аються поліноміальними коефіцієнтами, оскільки вони фігурують у поліноміальній формулі для обчислення степеня з натуральним показником п від суми s чисел:
(1.2)
Поліноміальна формула (1.2) у випадку s = 2 збігається з відомою вже формулою бінома Ньютона.
Покажемо, що у випадку s = 2 поліноміальний коефіцієнт збігається з біномінальними, тобто:
, (k1+k2=n). (1.3)
Зауваження 1.1. Задача про число Сn (k1,k2,…,k) всіх перестановок з п елементів за наявності s типів однакових в кіль кості k1, k2, ..., ks (kl +k2 +… + ks =n ) еквівалентна задачі про такі розташування п відрізнимих кульок по 5 урнах, коли в першу урну потрапляє рівно k1 кульок, у другу – рівно k2 кульок, ..., у s-my — рівно ks, кульок (рис. 1.1).
рис 1.1.
Кожному типу однакових елементів відповідає урна (s типів - s урн), а відрізнимі кульки символізують собою номери (можна вважати, що кульки пронумеровані від 1 до n), які надаються елементам множини M*, після чого одержується певна перестановка цієї множини. Розташовуючи кульки-номери по урнах, ми начебто розігруємо порядок (номери місць у перестановці) серед елементів множини М*. Номери тих ki кульок, що потрапляють в i-ту урну, якраз і визначать місця, на яких стоятимуть у перестановці множини М* ki однакових елементів і-го типу (). У випадку , ki ≡1 і, значить, s = n, а формула (1.1) - у формулу (1.2).
2. Розміщення
Означення 2.1. Нехай маємо елементи п типів, причому елементи кожного однакового типу вважаються нєвідрізнимими, а їх запас — невичерпним. Якщо з них вибрати будь-які k елементів (k = 0,1,2,...), не обов'язково різних типів і додатково довільним чином впорядкувати, то одержана при цьому впорядкована множина потужності k називається розміщенням з повторенням з п елементів по k.
Потужність множини всіх розміщень з повторенням з п елементів по k у комбінаториці позначається символом .
Зауваження 2.1
а) оскільки елементи вибираються з повторенням, то на відміну від символу , де завжди k < п, в може бути k > п (наприклад, );
б) розміщення з повторенням з п елементів по k є узагальненням відповідного розміщення без повторення, оскільки у разі, коли запас елементів кожного з типів вичерпується одним елементом, ці поняття збігаються і тоді, звичайно, k <п .
Приклад 2.1 Добрим наочним прикладом розміщень з повторенням є телефонні номери. Запишемо такі чотири 6-значні телефонні номери:
t1: 21-55-12, t 2 : 12-55-21, t 3 :76-66-67, t 4 : 41-26-79.
Телефонний номер - це впорядкований набір цифр (наприклад, t1≠t2), в якого цифри можуть повторюватись(t1,t 2,t 3), тому 6-значний телефонний номер - розміщення з повторенням з n = 10 елементів (цифри 0, 1, 2, ..., 9) по k=6.
Подані нижче таблиці ілюструють означення 2.1 на прикладах утворення телефонних номерів t1,t 3. Маємо елементи n = 10 типів - нулі (1-й тип), одиниці (2-й тип), ..., дев'ятки (10-й тип); вибір з них та подальше впорядкування k = 6 елементів покажемо за допомогою таких таблиць.
t1
Вибір k=6 елементів
Їх порядок
2 елементи 2-го типу
2-й, 5-й
2 елементи 3-го типу
1-й, 6-й
2 елементи 6-го типу
3-й, 4-й
t 3
Вибір k=6 елементів
Їх порядок
4 елементи 7-го типу
2-й, 3-й, 4-й, 5-й
2 елементи 8-го типу
1-й, 6-й
Зауваження 2.2. Задача про обчислення числа всіх розміщень з повторенням з п елементів по k () еквівалентна задачі про знаходження числа всіх способів розташування k відрізнимих кульок по п урнах без обмеження на сам спосіб розташування (рис. 2.1).
Урни символізують типи елементів (скільки урн – це стільки типів), а відрізнимі кульки (вважаємо, що вони пронумеровані і номер кульки ідентифікує її) - впорядковані елементи, що вибираються. Якщо в урну з номером i потрапило ki, кульок, то це означає, що взято ki, елементів i -го типу, а номери (порядок) цих елементів відповідають номерам цих кульок.
Так, задача про число всіх 6-значних телефонних номерів еквівалентна задачі про число всіх способів розташування k = 6 відрізнимих кульок по n = 10 урнах. Нижче на рис. 2.1 показано таке розташування кульок для телефонних номерів t1,, t3, t4 з прикладу 2.1.
Рис.2.1
Отже, якщо комбінаторну задачу можна абстрактно сформулювати як задачу про довільне розташування k відрізнимих кульок по п урнах, то це означатиме, що це задача про число розміщень з п елементів по k з повторенням ( ).
Відомо, що число всіх розташувань k відрізнимих кульок по n урнах (без обмежень на спосіб розташування) дорівнює nk ).
Отже, на основі зауваження 2.2 можемо записати формулу
(2.1)
Приклад 2.2 Скільки цілих чисел десяткової системи числення можна закодувати s-розрядними числами двійкової системи?
1 спосіб
Будь-яке s-розрядне двійкове число - це впорядкована послідовність довжини s, складена з нулів та одиниць, які можуть повторюватися. Наприклад, s-розрядному двійковому числу 11010 у десятковій системі числення відповідає число 1∙24 + 1∙23 +0∙22 +1∙21 +0∙20 = 26.
Отже, s-розрядне двійкове число можна розглядати як певне розміщення з повторенням з п = 2 елементів (0, 1) по s (кількість розрядів). Тому за допомогою s-розрядних двійкових чисел можна закодувати А2* =2s цілих чисел десяткової системи, тобто числа 0, 1,2, ..., 2і -1. При s = 5 матимемо 0, 1, 2, 30, 31.
2 спосіб
Задача має таке абстрактне формулювання: скількома способами можна розташувати k = s відрізнимих кульок (розряди числа) по п = 2 урнах (цифри 0, 1)?
Виходячи із зауваження 2.2, робимо висновок про те, що маємо задачу на обчислення числа розміщень з повторенням з п = 2 елементів по k = s.
За формулою (2.1):
.
Приклад 2.3 Урна містить V відрізнимих кульок (генеральна сукупність обсягу V). З урни послідовно одна за однією вилучають v кульок, повертаючи кожного разу вилучену кульку назад в урну, при цьому контролюється не тільки те, які кульки вилучаються, але й порядок їх появи. Кожна така зареєстрована впорядкована послідовність з v кульок називається впорядкованою вибіркою обсягу v з поверненням, або впорядкованою повторною вибіркою обсягу v.
Яка потужність множини впорядкованих повторних вибірок обсягу v з генеральної сукупності обсягу V?
Очевидно, що кожна така вибірка є певним розміщенням з V елементів по v з повторенням, а тому шукана потужність визначається числом
Ця задача еквівалентна задачі про визначення потужності множини всіх функцій
F:A={l,2,...,v}(B = {l,2,...,V},
де аргумент - номер кульки згідно з порядком її вилучення, значення функції - власний номер кульки (вважаємо, що кульки в урнах занумеровані і таким чином ідентифікуються).
Приклад 2.4 Далі розглянемо задачу про розміщення з повторенням з п елементів по k за наявності одного обмеження, яке виникає в багатьох практичних задачах комбінаторного характеру.
Постановка задачі. Нехай k≥n. Яка потужність множини таких розміщень з повторенням з елементів п типів по k, які містять хоча б один елемент кожного типу?
Абстрактне формулювання задачі. Нехай k≥n. Скільки існує таких розташувань k відрізнимих кульок по п урнах, за яких всі урни заповнені (немає порожніх урн)?
Число, яке є розв'язком поставленої задачі, позначається через s(k,n) і називається в комбінаториці числом Стірлінга 1-го роду.
Це число визначається за формулою
(2.2)
Приклад 2.5 Обчислимо число Стірлінга 1 -го роду s(5,3), тобто знайдемо число всіх таких розташувань k =5 відріз-нимих кульок по п = 3 урнах, за яких відсутні порожні урні.
Приклад 2.6 Розглянемо задачу про розміщення з п елементів по k з повторенням в її абстрактній постановці.
Нехай k відрізиимих кульок розташовують по п урнах. Розглянемо такі три обмеження, які можуть виникнути для цієї задачі.
а) кульками заповнюються рівно r фіксованих урн з п (r≤n, k≥r).
Потужність множини таких розташувань кульок визначається числом Стірлінга 1-го роду
s(k,r). (2.3)
б) кульками заповнюються рівно r урн з п, які саме, не важливо (тобто r урн не фіксуються). У цьому випадку потужністю відповідної множини розташувань є число
(2.4)
в) кульки заповнюють не менше r урн з п (r≤n, k≥r). Множина таких розташувань кульок має потужність, якаї дорівнює числу
(2.5)
Узагальнення формули (2.2).
Формула (2.2) (число Стірлінга 1-го роду) визначає потужність розміщень з повторенням з елементів n різних типів по k за умови, що в цих розміщеннях наведені елементи всіх п типів.
Можна розглянути більш загальну задачу, а саме задачу про обчислення потужності таких розміщень з повтореннями з п елементів по k, які обов'язково містять елементи r фіксованих типів (r≤n, k≥r).
В абстрактній постановці ця задача звучить так: k відрізнимих кульок розташовують по п урнах так, щоб r фіксованих урн не були порожніми.
Яка потужність множини таких розташувань кульок?
Зауважимо, що й інші урни при цьому можуть бути заповнені кульками, а r фіксованих (наперед вказаних) повинні бути гарантовано заповнені.
Позначається потужність такої множини через і обчислюється за формулою
(2.6)
Зауважимо, що при r = n отримаємо
тобто формула (2.6) переходить у формулу (2.2) (або: число при r = п збігається з числом Стірлінга 1-го роду s(k,n)).
3. Комбінації
Означення 3.1. Нехай маємо елементи п типів (елементи кожного однакового типу вважаються не відрізнимими, а їхній запас -- невичерпним). Якщо з них вибирають будь-які k елементів (k = 0,1,2,...) не обов'язково різних типів, причому порядок самих елементів ігнорується, то одержана при цьому невпорядкована множина потужності k називається комбінацією з п елементів по k з повторенням.
Потужність множини всіх комбінацій з повторенням з п елементів по k позначається символом .
Усі ті зауваження, які були зроблені в попередньому розділі для розміщень з повторенням з п елементів по k (див.зауваження до означення 2.1), стосуються і відповідних комбінацій.
Приклад 3.1. Кості доміно можна розглядати як один з найпростіших прикладів комбінацій з повторенням, а саме комбінацій з елементів п = 7 типів по k = 2 .
Рис. 3.1
Роль елементів різних типів тут відіграють різні кількості очок 0, 1, 2, ..., 6 (всього n= 7 типів), а вибирається k =2 елементи (не обов'язково різних типів) - це кількості очок, які зображаються на половинках поверхні кості. Оскільки кості доміно симетричні (половинки не різняться ні за розміром, ні за кольором тощо), то порядок цих елементів не є суттєвим.
Математично кості доміно можна задати невпорядкованими парами (i,j)=(j,i) (i,j=0,1,2,...,6), де i - кількість очок на одній половині поверхні кості, j — на другій половині поверхні кості (на рис. 3.1 зображено 4 кості доміно).
Зауваження 3.3. Задача про обчислення числа всіх комбінацій з п елементів по k з повторенням () еквівалентна задачі про знаходження числа всіх способів розташування k невідрізнимих кульок по п урнах без обмежень на спосіб розташування (рис. 3.2).
Рис. 3.2
Кожне таке розташування визначається лише тим, скільки кульок (кульки відповідають елементам, що вибираються) потрапило в кожну з урн (урни відповідають різним типам елементів), а те, які саме кульки потрапили, не враховується через неможливість це зареєструвати (адже кульки невідрізнимі).
Наприклад, задача про число всіх костей доміно еквівалентна задачі про число всіх способів розташування k = 2 невідрізнимих кульк по n=7 урнах без обмежень на спосіб розташування. На рис. 3.3 показано розташування кульок, що відповідають костям k1=(0,0) k2=(1,2) k3=(5,5) k4=(4,6) з прикладу 3.1.
Висновок 1. Якщо комбінаторна задача може бути абстрактно сформульована як задача про довільне розташування k невідрізнимих кульок по п урнах, то це означатиме, що маємо задачу на комбінації з п елементів по k з повторенням.
Рис.3.3
Виявляється, що задачу про комбінації з повторенням можна також звести до вже відомої задачі про перестановки з повторенням і звідси одержати формулу для обчислення числа .
Дійсно, кожна комбінація повністю визначається, якщо вказати, скільки елементів кожного з п типів до неї входть. Зашифруємо кожну комбінацію за допомогою послідовності одиниць та нулів, складеної за таким правилом: для кожного типу, починаючи з першого, записуємо стільки одиниць, скільки елементів цього типу входить в комбінацію, а різні типи відділяємо один від одного нулями (при цьому, якщо елементи якого-небудь типу зовсім не увійшли до комбінації, то потрібно писати підряд два чи більше нулів). У результаті цього отримаємо послідовність, яка містить стільки одиниць, скільки елементів входить у комбіцацію, тобто k, а число нулів буде на один менше, ніж число типів тобто n-1. Іншими словами, отримаємо перестановку з повторенням потужності n+k-1, яка містить елементи двох типів: k одиниць та n-1 нулів.
Наприклад, розглянутим у прикладі 3.1 костям доміно, як комбінаціям з n=7 елементів по k - 2 з повторенням, відповідають такі перестановки з n+k-1=7+2-1=8 елементів з повторенням, представлені двома типами: k1=k=2 одиниць і k2 =n - l = 7-l = 6 нулів (3-й стовпчик табл. 3.1).
Таблиця 3.1
Кості доміно
Вибір k=2 елементів
Відповідні перестановки з повторенням
k1=(0,0)
Взято 2елементи 1-го типу
11000000
k2=(1,2)
Взято по одному елементу 2-го і 3-го типів
01010000
k3=(5,5)
Взято 2 елементи 6-го тиу
00000110
k4=(4,6)
Взято по одному елементу 5-го і 7-го типів
00001001
Висновок 2. Задача про число комбінацій з повторенням з п елементів по k еквівалентна задачі про число перестановок з повторенням з n + k-1 елементів, які містять елементи двох типів: k одиниць та n-1 нулів.
З формули (1.3), враховуючи висновок 2 маємо формулу
(3.1)
Приклад 3.2 Урна містить V відрізнимих кульок (генеральна сукупність обсягу V). З урни одна за одною вилучають v кульок, повертаючи кожного разу кульку назад в урну. При цьому важливим є лише те, які кульки вилучаються, а порядок їхньої появи не має ніякого значення. Кожна така зареєстрована невпорядкована послідовність з v кульок називається невпорядкованою вибіркою обсягу v з поверненням, або невпорядкованою повторною вибіркою обсягу v.
Яка потужність множини невпорядкованих повторних вибірок обсягу v з генеральної сукупності обсягу V?
Цю задачу, очевидно, можна сформулювати так: маємо елементи V типів (V відрізнимих кульок), вибираємо v елементів, не обов'язково різних типів (оскільки кульки повертаються в урну), порядок вибору не враховується. Скількома способами можна здійснити такий вибір?
Очевидно, що маємо задачу про число комбінацій з повторенням з V елементів по v, і, отже, потужність розглядуваної множини невпорядкованих повторних вибірок визначається числом
Розглядувана задача зводиться також до задачі про число монотонних функцій. Усі кульки в урні (елементи генеральної сукупності) пронумеровані числами від 1 до V (власні номери кульок), а вилучені v кульок (елементи вибірки) впорядкуємо числами 1, 2, ..., v за неспаданням їхніх власних номерів (це можна зробити, оскільки порядок вилучених кульок не береться до уваги). Тоді невпорядкованих повторних вибірок обсягу v з генеральної сукупності обсягу V буде стільки, скільки буде різних неспадних функцій
F:A={l,2,...,v}(B = {l,2,...,V},
де аргумент - номер вилученої кульки згідно з впорядкуванням за неспаданням власних номерів, значення функції - власний номер кульки.
Таких функцій є:
Список використаної літератури
1.Виленкин Н.Я Комбинаторика – М.: Наука, 1969. – 161 с.
2.Капітонова Ю.В., Кривий С.Л., Летичевський О.А. та ін. Основи дискретної математики. – К.: Наукова думка, 2002. – 560 с.
3.Бушмакін В.М., Гануліч В.К., Мохонько А.З. та ін. Комбінаторика – Л.: В-во НУ “ЛП”, 2002. – 196 с.
Ділись своїми роботами та отримуй миттєві бонуси!
0%
Оголошення від адміністратора