Головна

Знаходження числа всіх підмножин даної множини

  1. II етап. Розподіл на двозначні і тризначні розрядні числа.
  2. Абсолютна величина числа
  3. Аксіома безперервності безлічі дійсних чисел. Точні межі числових множин.
  4. Алгебраїчна, геометрична і показові форми комплексного числа
  5. Алгебраїчні Дії з комплексними числами
  6. Альтернативні витрати будь-якого блага визначаються тим кількістю інших благ, якими треба пожертвувати, щоб отримати додаткову одиницю даного блага.
  7. аффінниє безлічі

Якщо задано деякий безліч А, То можна розглядати нове безліч М (А) - Безліч всіх його підмножин.

Приклад 1. Скільки підмножин має безліч А={E}?

За властивостями відносини включення, маємо ? А и А .

Таким чином, одноелементні безліч А={E} має 2 підмножини.

Приклад 2. Скільки всього підмножин має двоелементною безліч А=, в}?

За властивостями відносини включення, маємо ? А и А .

Одноелементні підмножини: {А}, {в}.

Таким чином, двоелементною безліч А=, в} всього має 4 підмножини.

Приклад 3. Скільки всього підмножин має Трьохелементний безліч А = {?, 0, ?}?

За властивостями відносини включення, маємо ? А и А .

Одноелементні підмножини: {?}, {0}, {?}.

Двоелементний підмножини: {?, 0}, {?, ?}, {0, ?}.

Таким чином, Трьохелементний безліч А = {?, 0, ?} всього має 8 підмножин.

Приклад 4. Скільки всього підмножин має чотирьохелементний безліч А = , в, с, d}?

За властивостями відносини включення, маємо ? А и А .

Одноелементні підмножини: {А}, {в}, {з}, {d}. Двоелементний підмножини: {А, в}, {а, з}, {a, d}, {в, з}, {в, d}, {с, d}. Трьохелементні підмножини: {А, в, с}, {a, в, d}, {а, с, d}, {в, з, d}.

Таким чином, чотирьохелементний безліч всього має 16 підмножин.

Неважко помітити, що зі збільшенням кількості елементів множини А, Число всіх його підмножин значно збільшується. Виникає питання: скільки підмножин має безліч з n - Елементів?

Відповідь на поставлене запитання дає наступне твердження.

теорема 5.Кінцеве безліч, що містить n елементів, має 2п підмножин, тобто якщо Ап = {А1, а2, ..., Aп }, то п (М (Ап)) = 2п.

? Доказательствопроведем, використовуючи метод математичної індукції.

1) Шлях п = 1, тобто А1 = 1}. значить, М (А1) = {?, {а1}}.

В цьому випадку п (М (А1)) = 21 = 2 що і доводить справедливість теореми при п = 1.

2) Нехай п = до, тобто Aк = {А1, а2, ..., Aк }.

Припустимо, що п (М (Aк)) = 2 , Тобто безліч Aк має 2 підмножин.

3) Доведемо, що тоді безліч Aдо +1, має 2 підмножин. Справді, якщо до елементів безлічі Aк, що містить к елементів, додати ще один елемент aдо + 1, То до наявних 2 підмножини додадуться ще 2 нових підмножини, і, отже, безліч Aдо +1, що містить к + 1 елементів, матиме 2 + 2  = 2 ? 2 = 2 підмножин.

Таким чином, п (М (Aдо +1)) = 2 .

На підставі методу математичної індукції можна зробити висновок, що Теорема. 5 справедлива для будь-якого натурального числа п. Теорема доведена.



Завдання для самостійного рішення | поняття факторіала

Приклади розв'язання деяких комбінаторних задач ... 97 | Поняття комбінаторної задачі | Історія виникнення і розвитку комбінаторики | кінцеві безлічі | Операції над множинами | Декартово твір множин А і В | Правила суми і твори | Завдання для самостійного рішення | Перестановки без повторень | Завдання для самостійного рішення |

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