Елементи комбінаторики (реферат)

ЕЛЕМЕНТИ КОМБІНАТОРИКИ.

§ 1. Поняття множини. Операції над множинами Поняття множини належить до первісних понять математики, якому не дається означення Множину можна уявити собі як су­купність деяких предметів, об'єднаних за довільною характерис­тичною ознакою Наприклад, множина учнів класу, множина цифр десяткової нумерації (0, 1, 2, 3, 4, 5, 6, 7, 8, 9), множина натуральних чисел, множина зернин у даному колосі, множина букв українського алфавіту, множина точок на прямій Предмети, з яких складається множина, називаються її елементами і позначаються малими буквами латинського алфавіту. Наприклад, а = 5 — елемент множини цифр десяткової нумерації Для позначення множин використовують великі букви латинсь­кого алфавіту або фігурні дужки, всередині яких записуються елементи множини При цьому порядок запису елементів не має значення Наприклад, множину цифр десяткової нумерації мож­на позначити буквою М (чи будь-якою великою буквою латин­ського алфавіту) або записати так {1, 3, 5, 2, 4, 6, 8, 7, 9, 0}.

Належність предмета даній множині позначається символом $$$$, а неналежність — символом $$$$ (інколи $$\stackrel{}{}$$) Наприклад, число 7 $$$$ А, де, А — множина чисел першого десятка, а число 12 $$$$ A.

Множини бувають скінченні і нескінченні. У скінченній множині міститься певна кількість елементів, тобто кількість елементів скінченної множини виражається натуральним чис­лом Наприклад, множина М цифр десяткової нумерації скінчен­на і містить десять елементів. У нескінченній множині - нескін­ченна кількість елементів. Наприклад, множина натуральних чисел, множина точок прямої - нескінченні множини.

Множина, в якій немає жодного елемента, називається порож­ньою і позначається символом $$\mathrm{}$$. Наприклад, множина точок перетину двох паралельних прямих — порожня множина.

Якщо множина В складається з деяких елементів даної мно­жини, А (і тільки з них), то множина В називається підмножиною множини А. У такому разі співвідношення між множинами, А і В позначається так В $$$$ А (читається «В міститься в А» або «В — підмножина А»). Якщо В може й дорівнювати А, то вживається символ В $$$$ А. Знак $$$$ називається знаком нестрогого включення, а знак $$$$ — знаком строгого включення.

Порожня множина $$\mathrm{}$$ є підмножиною будь-якої множини, тобто $$\mathrm{}$$ $$$$ А.

Саму множину, А можна розглядати як підмножину А, тобто, А $$$$ А.

Множину задають двома основними способами:

1) переліченням всіх її елементів;

2) описанням характеристичної властивості її елементів. Наприклад: а) В = {math xmlns="http://www.w3.org/1998/Math/MathML" display="block" >, множина, задана переліченням елементівб) X — множина коренів квадратного рівняння х2 = 25. Множина X задана характеристичною властивістю елементів — бути коренем рівняння х2 = 25″. Цю саму множину можна зада­ти і переліченням її елементів: X = {-5- 5}.

Дві множини називаються рівними, якщо вони складаються з тих самих елементів. Наприклад, множини коренів рівняння х2 = 25 і |x| = 5 рівні між собою. Справді, X = {-5- 5} і Y = {-5- 5}, де Y — множина розв’язків рівняння |x|-5. Отже, X = Y.

Над множинами виконуються певні операції (дії). Зазначимо три з них.

Переріз множин. Перерізом множин, А і В називається множина С, яка складається з усіх тих і тільки тих елемен­тів, які належать коленій з даних множин, А і В.

Приклад 1. Нехай, А — множина всіх дільників числа 32, тобто, А = {І, 2, 4, 8, 16, 32), а В — множина всіх дільників чис­ла 24, тобто В = {1, 2, 3, 4, 6, 8, 12, 24}. Тоді перерізом множин, А і В є множина С = {1, 2, 4, 8}, яка складається зі спільних дільників чисел 32 і 24.

Схематично переріз множин, А і В можна зобразити за допо­могою фігур. Символічно позначається так: С = А $$$$ В і читається: «С є перерізом, А і В» .

Приклад 2. Нехай М — множина прямокутників, N — множина ромбів, тоді Р = М $$$$ N — множина квадратів.

Об'єднання множин. Об'єднанням (або сумою) двох мно­жин, А і В називається така множина С, яка складається з усіх елементів множин, А і В, і тільки з них.

Позначається це так: С = А $$$$ В і читається: «С є об'єднанням, А і В» .

Якщо множини, А і В мають спільні елементи, тобто, А $$$$ В $$$$ 0, то кожний з цих спільних елементів береться в множину С тільки один раз.

Приклад 3. А ={1,2, 3,4}, В = {3, 4, 5, 6}, тоді С = {1,2,3,4,5,6}.

Приклад 4. Q — множина раціональних чисел, І - мно­жина ірраціональних чисел. Тоді множиною R всіх дійсних чисел буде об'єднання множин Q і І, тобто R = Q $$$$ І.

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

Віднімання множин. Доповнення множини. Різницею двох множин, А і В називається така множина С, яка складається з усіх елементів множини А, що не належать множині В.

Позначається це так: С = А В і читається: «С є різницею, А і В» .

Приклад 5. а) А= {5,6, 8, 12}, В= {5, 6}, тобто В $$$$ А, тоді С = А В= {8, 12};

б) А = {5, 6, 8, 12}, В = {8, 12, 1, 2}, тоді С = А В = {5, 6};

в) А = {5, 6, 12}, В = {1, 2}, тоді С = А В = {5, 6, 12};

г) А= {5, 6}, В= {5,6, 12}, тобто В $$$$ А, тоді С = А В = $$\mathrm{}$$ .

У випадку, коли, А $$$$ В, то різниця С = А В називається доповненням множини В відносно множини, А і позначаєть­ся САВ.