Елементи комбінаторики
Комбінаторика вивчає питання про те, скільки різних комбінацій, підпорядкованих тим чи іншим умовам, можна скласти із заданих об’єктів.Розміщенням із n елементів по m називається любий впорядкований набір із m різних елементів, вибраних із загальної сукупності в n елементів.
A(07OmjzMgzwEkAAAANDUyM2Y0NmQtNTQyYy00NGE4LWE5YTItY2EwYWNhMWEzY2M5k5da0Rm0GQ21Wmte2akTXzbqc3g1))/Images/topic7/1_1.gif)
A(07OmjzMgzwEkAAAANDUyM2Y0NmQtNTQyYy00NGE4LWE5YTItY2EwYWNhMWEzY2M5k5da0Rm0GQ21Wmte2akTXzbqc3g1))/Images/topic7/1_2.gif)
де n! = 1•2•3•...•n,
(n - m)! = 1•2•3•...•(n - m).A(07OmjzMgzwEkAAAANDUyM2Y0NmQtNTQyYy00NGE4LWE5YTItY2EwYWNhMWEzY2M5k5da0Rm0GQ21Wmte2akTXzbqc3g1))/Images/topic7/1_3.gif)
A(07OmjzMgzwEkAAAANDUyM2Y0NmQtNTQyYy00NGE4LWE5YTItY2EwYWNhMWEzY2M5k5da0Rm0GQ21Wmte2akTXzbqc3g1))/Images/topic7/1_4.gif)
Перестановками із n елементів називається любий впорядкований набір цих елементів.
A(07OmjzMgzwEkAAAANDUyM2Y0NmQtNTQyYy00NGE4LWE5YTItY2EwYWNhMWEzY2M5k5da0Rm0GQ21Wmte2akTXzbqc3g1))/Images/topic7/1_5.gif)
A(07OmjzMgzwEkAAAANDUyM2Y0NmQtNTQyYy00NGE4LWE5YTItY2EwYWNhMWEzY2M5k5da0Rm0GQ21Wmte2akTXzbqc3g1))/Images/topic7/1_6.gif)
Комбінацією із n елементів по m називається любий невпорядкований набір із m різних елементів, вибраних із загальної сукупності в n елементів.
A(07OmjzMgzwEkAAAANDUyM2Y0NmQtNTQyYy00NGE4LWE5YTItY2EwYWNhMWEzY2M5k5da0Rm0GQ21Wmte2akTXzbqc3g1))/Images/topic7/1_7.gif)
A(07OmjzMgzwEkAAAANDUyM2Y0NmQtNTQyYy00NGE4LWE5YTItY2EwYWNhMWEzY2M5k5da0Rm0GQ21Wmte2akTXzbqc3g1))/Images/topic7/1_8.gif)
Із приведених визначень видно, що результати підрахунків залежать від декількох факторів одночасно.
По-перше, від того, із якої кількості елементів можна складати набори.
По-друге, результат залежить від того, якої величини набори елементів потрібні.
Важливо також знати, чи являється суттєвий порядок елементів в наборі.
Якщо в умовах задачі є якісь особливості, то вони розв’язуються в першу чергу.
При цьому можуть бути розміщення без повторень
, коли два набори вважаються різними,якщо вони відрізняються один від одного хоча б одним елементом, або коли набори однакові по складу, - порядком розташування цих елементів в наборі.
В цьому випадку справедливе співвідношенняде n! = 1•2•3•...•n,
(n - m)! = 1•2•3•...•(n - m).
В розміщеннях з повтореннями
в набір можуть входити і однакові елементи,але набори також відрізняються один від одного або складом елементів, або порядком розміщення цих елементів в них.
Доведено, щоВ перестановках без повторень
набори містять n елементів із n і відрізняютьсяодин від одного лише порядком елементів в них.
Очевидно, щоВ комбінаціях без повторень
набори відрізняються один від одного лише складомі розраховуються по формулі
По-перше, від того, із якої кількості елементів можна складати набори.
По-друге, результат залежить від того, якої величини набори елементів потрібні.
Важливо також знати, чи являється суттєвий порядок елементів в наборі.
Якщо в умовах задачі є якісь особливості, то вони розв’язуються в першу чергу.