Комбінаторика, 1) те ж, що математичний комбінаторний аналіз . 2) Розділ елементарної математики, пов'язаний з вивченням кількості комбінацій, підлеглих тим або іншим умовам, які можна скласти із заданої кінцевої безлічі об'єктів (байдуже, якої природи; це можуть бути букви, цифри, які-небудь предмети і т.п.).
Найбільш споживані формули К.:
Число розміщень. Хай є n різних предметів. Скількома способами можна вибрати з них т предметів (враховуючи порядок, в якому вибираються предмети)? Число способів рівне
A n m =
A n m називають числом розміщень з n елементів по m.
Число перестановок. Розглянемо завдання: скількома способами можна встановити порядок дотримання один за одним n різних предметів? Число способів рівне
P n = 1Ч2Ч 3.. . n= n!
(знак n! читається: « n факторіал»; виявляється зручним розглядати також 0!, вважаючи його рівним 1). P n називають числом перестановок n елементів.
Число поєднань. Хай є n різних предметів. Скількома способами можна вибрати з них т предметів (байдуже, в якому порядку вибираються предмети)? Число способів такого вибору рівне
C n m =
C n m називають числом поєднань з n елементів по m. Числа C n m виходять як коефіцієнти розкладання n-й міри двочлена (бінома, див.(дивися) Ньютона біном ) :
(a+b) n =C n 0 a n + C n 1 a n-1 b +C n 2 a n-2 b 2 +... + C n n-1 ab n-1 + C n n b n ,
і тому вони називаються також біноміальними коефіцієнтами. Основні співвідношення для біноміальних коефіцієнтів:
C n m =C n n-m , C n m + C n m+1 = C n+1 m+1
C n 0 + C n 1 + C n 2 +...+ C n n-1 + C n n = 2 n ,
C n 0 — C n 1 + C n 2 —...+ (—1) n C n n = 0.
Числа A n m , P m і C n m зв'язані співвідношенням:
A n m =P m C n m .
Розглядаються також розміщення з повторенням (тобто всілякі набори з m предметів n різних видів, порядок в наборі существен) і поєднання з повторенням (то ж, але порядок в наборі не существен). Число розміщень з повторенням дається формулою n m , число поєднань з повторенням — формулою C m n + m -1 .
Основні правила при вирішенні завдань К.: Правило суми. Хай деякий предмет А може бути вибраний з сукупності предметів m способами, а інший предмет В можна вибрати n способами. Тоді є т + n можливостей вибрати або предмет A, або предмет Ст
Правило твору. Хай предмет А можна вибрати m способами і після кожного такого вибору предмет В можна вибрати n способами; тоді вибір пари ( А, В ) в вказаному порядку можна здійснити m + n способами.
Принцип включення і виключення. Хай є N предметів, які можуть володіти n властивостями a 1 , a 2 ..., a n . Позначимо через N (a i , a j , ..., a до ) число предметів, що володіють властивостями a i , a j ..., a до і, мабуть, якими-небудь іншими властивостями. Тоді число N'' предметів, що не володіють жодним з властивостей, a 1 , a 2 ..., a n , дається формулою
= N—N (a 1 ) — N (a 2 ) —... —n (a n ) + N (a 1 , a 2 ) + N (a 1 , a 3 ) +... + N (a n-1 , a n ) — N (a 1 , a 2 , a 3 ) —... — N (a n-2 , a n-1 , a n ) +... +(—1) n N (a 1 ..., a n )
Літ.: Netto E. Lehrbuch der Combinatorik, 2 Aufl., Lpz. — B., 1927.
