Қосу және көбейту
Орын ауыстыру, орналастыру және теру
жүктеу/скачать 80,45 Kb.
|
10 Комбинаторика. Қосу, көбейту ережелері.
Орын ауыстыру, орналастыру және теруАқырлы жиынның элементтерінен әртүрлі комбинаторлы конфигурацияларды құру тәсілдерінің санын есептеуге байланысты есептерін қарастырамыз. Анықтама. А жиыны n элементтен тұрсын (|𝐴| = 𝑛). А жиынның элементтерінің орын ауыстыру деп осы жиынның 𝑛 элементінен тұратын кез келген кортеж (яғни реттелген жиын) айтылады. Сонымен, орын ауыстыру бір бірінен тек енетін элементтер ретімен ерекшеленеді. Кейбір оқулықтарда ([3], 87 бет) орын ауыстыруды өзара бірмәнді функция ретінде анықтайды 𝑓: 𝐴 → 𝐴. Егер |𝐴| = 𝑛, онда 𝐴 = {1,2, . . . , 𝑛} деп есептеуге болады және орын ауыстыруды кестемен берген ыңғайлы. Мысалы, 𝑓 = (1 2 3 4 5), (𝑛 = 5). Бұл кесте алмастыру (қойылым) делінеді. Мәні 4 3 1 5 2 бойынша, алмастыру және орын ауыстыру бірдей. Әрбір осындай алмастыруға сәйкес граф қоюға болады. Жоғарыда келтірілген f алмастыруына 4.2.1 суретіндегі граф сәйкес келеді. сурет 𝑛 элементтен орын алмастырулар санын былай белгілейді: 𝑃𝑛. 𝑃𝑛 = 𝑛! ( n факториал, 𝑛! = 1 ⋅ 2. . . (𝑛 − 1) ⋅ 𝑛, анықтама бойынша 0! = 1, 1! = 1). Расында, кортеждегі бірінші орынға n элементің кез келгенін қоя аламыз, екіншіге – қалған (𝑛 -1) - ден, үшіншіге – қалған (𝑛 -2) - ден кез келгенін және т.с.с. Соңғы орынға бір элемент қана қалады. Сондықтан 𝑃𝑛 = 𝑛 ⋅ (𝑛 − 1) ⋅ (𝑛 − 2). . .2 ⋅ 1 = 𝑛!. М ы с а л 4.2.1 𝐴 = {𝑎, 𝑏, 𝑐} жиынының элементтерінен әртүрлі орын ауыстыру құру керек; олардың санын есептеу керек. Шешуі: |𝐴| = 𝑛 = 3. Жоғарыда келтірген формуладан: 𝑃3 = 3! = 1 ⋅ 2 ⋅ 3 = 6. Расында, келесі орын ауыстыру орынды: (𝑎, 𝑏, 𝑐), (𝑐, 𝑎, 𝑏), (𝑏, 𝑐, 𝑎), (𝑏, 𝑎, 𝑐), (𝑐, 𝑏, 𝑎), (𝑎, 𝑐, 𝑏). Анықтама. 𝐴 жиыны n элементтен тұрсын (|𝐴| = 𝑛) және 𝑚 ≤ 𝑛. 𝑛 элементтен 𝑚 бойынша орналастыру деп 𝐴 жиынының 𝑚 қос- қостан әртүрлі элементтерінен тұратын кез келген кортежі айтылады. Сонымен, орналастыру бір бірінен элементтерімен, не олардың орналасу ретімен ерекшеленеді. 𝑛 𝑛 элементтен 𝑚 бойынша орналастыру саны былай белгіленеді: 𝐴𝑚. Дәлелденген: 𝐴𝑚 = 𝑛! = 𝑛(𝑛 − 1)(𝑛 − 2) … (𝑛 − 𝑚 + 1). 𝑛 (𝑛−𝑚)! Расында, әрбір орналастыруды құру үшін 𝑛 элементтен m элемент таңдап алып, оларды реттеу керек. Бірінші орынға 𝑛 элементтің кез келгенін қоюға болады (яғни бірінші орынды 𝑛 тәсілмен жабуға болады), екінші орынға – кез келген қалған (𝑛 -1) элементтерді және т.с.с. Бірінші орыннан (𝑚 -1) – ге дейңнгң орынды толтырғаннан кейін 𝑛 - (𝑚 -1) = 𝑛 - 𝑚 +1 элемент қалады, олардың арасынан соңғы орынға элемент таңдалынады. Сонымен, көбейту ережесі бойынша 𝑛(𝑛 − 1)(𝑛 − 2). . . (𝑛 − 𝑚 + 1), n элементтен m элемент таңдап алудың тәсілі бар екен, яғни 𝑛 𝐴𝑚 = 𝑛(𝑛 − 1)(𝑛 − 2). . . (𝑛 − 𝑚 + 1). М ы с а л 4.2.2 𝐴 = {𝑎, 𝑏, 𝑐} жиынының элементтерінен екіден әртүрлі орналастыру құру керек; олардың санын есептеу керек. Шешуі: |𝐴| = 𝑛 = 3, 𝑚 = 2. 𝐴2 = 3! = 3 ⋅ 2 = 6. Расында, мұндай 3 (3−2)! орналастырулар алтау: (𝑎, 𝑏), (𝑏, 𝑎), (𝑎, 𝑐), (𝑐, 𝑎), (𝑏, 𝑐), (𝑐, 𝑏). Анықтама. 𝐴 жиыны n элементтен тұрсын (|𝐴| = 𝑛) және 𝑚 ≤ 𝑛. 𝑛 элементтен 𝑚 бойынша теру деп 𝐴 жиынының m элементтен тұратын кез келген ішкі жиыны айтылады. Сонымен, теру бір бірінен ең болмағанда бір элементімен ерекшеленеді. 𝑛 𝑛 элементтен 𝑚 бойынша теру саны былай белгіленеді: 𝐶𝑚. Оңай дәлелденетін өрнек 𝐴 𝑚 𝑛 𝐶𝑚 = 𝑛 = 𝑃𝑚 𝑛(𝑛−1)...(𝑛−𝑚+1) = 1⋅2...𝑚 𝑛! . 𝑚!(𝑛−𝑚)! 𝑛 𝑛 Расында, 𝑛 элементтен m бойынша орналастыру санын (𝐴𝑚) былай да табуға болады: 𝐴 жиынының 𝑛 элементінен 𝑚 элементін таңдауды 𝐶𝑚 тәсілмен (анықтама бойынша теру) табуға болады; содан соң табылған 𝑚 элементтен тұратын теруде барлық мүмкін орын ауыстырулар жасау керек. Мұны 𝑃𝑚 тәсілмен табуға болады. Көбейту ережесі бойынша 𝐴𝑚 = 𝐶𝑚 ⋅ 𝑃 , 𝑛 𝑛 𝑚 𝐴 𝑚 бұдан 𝐶𝑚 = 𝑛 . 𝑛 𝑃𝑚 𝑛 𝐶𝑚сандарының кейбір қасиеттерін білген жөн: 1) 𝐶𝑚 = 𝐶𝑛−𝑚; 𝑛 𝑛 2) 𝐶𝑚 = 𝐶𝑚 + 𝐶𝑚−1; 𝑛 𝑛−1 𝑛−1 3) 𝐶0 = 𝐶0 = 𝐶𝑛 = 1, 𝐶1 = 𝑛; 0 𝑛 𝑛 𝑛 𝑛 4) 𝐶𝑚 сандарын биномдық коэффициенттер деп атайды. Расында, Ньютон биномы формуласы мынадай түрде болады (𝑎 + 𝑏)𝑛 = 𝐶0𝑎𝑛𝑏0 + 𝐶1𝑎𝑛−1𝑏1+. . . +𝐶𝑛𝑎0𝑏𝑛. 𝑛 𝑛 𝑛 𝑛 Бұл формуладан тағы бір қасиетін алуға болады 𝐶𝑚: егер 𝑎 = 𝑏 = 1 болса, Ньютон биномы формуласы теңдікке айналады 𝐶0 + 𝐶1+. . . +𝐶𝑛 = 2𝑛. 𝑛 𝑛 𝑛 М ы с а л 4.2.3 𝐴 = {𝑎, 𝑏, 𝑐} жиынының элементтерінен екіден әртүрлі теру құру керек; олардың санын есептеу керек. Шешуі: |𝐴| = 𝑛 = 3, 𝑚 = 2 . 𝐶2 = 3⋅2 = 3. 3 1⋅2 Расында, мұндай терулер үшеу: (𝑎, 𝑏), (𝑎, 𝑐), (𝑏, 𝑐). жүктеу/скачать 80,45 Kb. Достарыңызбен бөлісу:
|