Види задач підрахунку числа елементів множин

Основними і типовими операціями і пов'язаними з ними завданнями комбінаторики є наступні:

1) утворення впорядкованої безлічі, що полягає у встановленні певного порядку дотримання елементів безлічі один за одним, - складання перестановок;

2) утворення підмножин, що полягає у виділенні з даної безлічі деякої частини його елементів, - складання поєднань;

3) утворення впорядкованих підмножин - складання розміщень.

ТИПИ КОМБІНАТОРНИХ ЗАВДАНЬ.

1. Магічний квадрат - квадратна таблиця (n * n) цілих чисел від 1 до n¤ така, що суми чисел уздовж будь-якого стовпця, будь-якого рядка і двох діагоналей таблиці дорівнюють одному і тому ж числу s=n(n¤+1) /2. Число n називають порядом магічного квадрата.

Доведено, що магічний квадрат можна побудувати для будь-якого n Є 3. Вже в середні віки був відомий алгоритм побудови магічних квадратів непарного порядку. Існують магічні квадрати, удоволетворяющие ряду додаткових умов, наприклад магічний квадрат з n=8, який можна розділити на чотири менші магічні квадрати 4x4. У Індії і деяких інших країнах магічні квадрати вживалися як талісмани. Проте загальної теорії магічних квадратів не існує. Невідоме навіть загальне число магічних квадратів порядку n.

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

3. Завдання розміщення- одне з класичних комбінаторних завдань, в якому потрібно визначити число способів розміщення m різних предметів в n різних вічках із заданим числом r порожніх вічок. Це число рівне

r n-r m

C (r)=C дельта O, r=0,1,2...,n,

nm n

де

до m до j j m

дельта O =сигма (-1) C (к-j)

j=0 до

4. Завдання комівояжера, завдання про бродячого торговця - комбінаторне завдання теорії графів. У простому випадку формулюється таким чином: дани n міст і відома відстань між кожними двома містами; комівояжер, що виходить з якого-небудь міста, повинен відвідати n-1 інших міст і повернутися в початковий. У якому порядку повинен він відвідувати міста (по одному разу кожен) аби загальна пройденноє відстань була мінімальною?

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

МЕТОДИ ВИРІШЕННЯ КОМБІНАТОРНИХ ЗАВДАНЬ

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

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

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