Метод рекурентних співвідношень.

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

Метод включення і виключення.

Хай N(A) - число елементів безлічі A. Тоді методом математичної індукції можна довести, що

N(A1 U A2 U ... An)= N(A1)+ ... + N(An) -

- {N(A1 П A2)+ ... + N(An-1 П An)} +

+ {N(A1 П A2 П A3)+ ... + N(An-2 П An-1 П An)} - ...

... +(-1)^n-1*N(A1 П A2 П ... П An-1 П An).

Метод підрахунку числа елементів об'єднання безлічі по цій формулі, що полягає в почерговому складанні і відніманні, називається методом включення і виключення.

3. Метод траєкторій.

Для багатьох комбінаторних завдань можна вказати таку геометричну інтерпретацію, яка зводить завдання до підрахунку числа доріг (траєкторій), що володіють певною властивістю

Елементи комбінаторики. Набори: набори з повторюванням; специфікація набору

Поняття розміщень в комбінаториці

Означення. Розміщення з повтореннями по m елементів n-елементної множини A – це послідовність елементів множини A, що має довжину m.

Приклад. При A={a, b, c} розміщення з повтореннями по два елементи – це пари (a,a), (a,b), (a,c), (b,a), (b,b), (b,c), (c,a), (c,b), (c,c).

Якщо |A|=n, то за правилом добутку множина всіх розміщень з повтореннями, тобто множина A^m=A´A´…´A, містить n^m елементів. Зокрема, якщо |A|=2, то розміщень з повтореннями 2^m. Зауважимо, що ці розміщення можна взаємно однозначно поставити у відповідність послідовностям з 0 і 1 довжини m.

У багатьох комбінаторних задачах об'єкти, кількість яких треба обчислити, являють собою послідовності, у яких перший елемент належить множині A₁, другий – A₂, тощо. Але досить часто множина A₂ визначається лише після того, як зафіксовано перший член послідовності, A₃ – після того, як зафіксовано перші два і т.д. Обчислимо, наприклад, кількість 7-цифрових телефонних номерів, у яких немає двох однакових цифр поспіль. Якщо на першому місці в номері є, наприклад, 1, то на другому може бути будь-яка з 9 інших цифр. І так само на подальших сусідніх місцях. Таким чином, тут |A₁|=10, |A₂|=|A₃|=…=|A₇|=9, і загальна кількість номерів є 10×9⁶.

Означення. Розміщення без повторень по m елементів n-елементної множини A, де m£n – це послідовність елементів множини A, що має довжину m і попарно різні члени.

<== попередня сторінка	\|	наступна сторінка ==>
Види задач підрахунку числа елементів множин	\|	Приклади.

Не знайшли потрібну інформацію? Скористайтесь пошуком google:

Генерація сторінки за: 0.005 сек.