Қосу және көбейту
Қайталанатын орналастыру, теру және орын ауыстыру
жүктеу/скачать 80,45 Kb.
|
10 Комбинаторика. Қосу, көбейту ережелері.
Қайталанатын орналастыру, теру және орын ауыстыру𝑛 элементтен 𝑚 элемент таңдағанда орналастыру мен теру құрғанда элементтер берілген жиынға қайтарылмауы да мүмкін (жоғарыда көрсетілгендей), қайтарылуы да мүмкін. Соңғы жағдайда қайталанатын орналастыру және қайталанатын теру туралы сөз болады. Анықтама. 𝐴 жиыны n элементтен тұрсын (|𝐴| = 𝑛) және 𝑚 ≤ 𝑛. 𝐴 жиынының 𝑛 элементтен 𝑚 бойынша қайталанатын орналастыру деп 𝐴 жиынының 𝑚 элементінен тұратын кортеж айтылады. Сонымен, қайталанатын орналастыру бір бірінен не элементімен, не олардың орналасу ретімен, не элементтерінің қайталану санымен айрықшалануы мүмкін. 𝑛 элементтен 𝑚 бойынша қайталанатын орналастыру саны былай белгіленеді: 𝐴𝑚 . Дәлелденген: 𝐴𝑚 = 𝑛𝑚. Расында, А жиыны n элементтен 𝑛 𝑛 тұрсын және (𝑎1, 𝑎2, . . . , 𝑎𝑚) оның кортеждерінің бірі болсын (қайталанатын орналастыру). Бұл орналастырудың әрбір элементі екі басқа орналастырларда қайталанады, яғни кортеждің әрбір орнына А жиынның n элементінің әрқайсысы үміткер. Сондықтан n элементтен m бойынша қайталанатын орналастыру саны 𝑛 𝐴𝑚 = 𝑛⏟_⋅ 𝑛_._. .¸𝑛 = 𝑛𝑚. 𝑚 М ы с а л 4.3.1 𝐴 = {𝑎, 𝑏, 𝑐} жиынының элементтерінен екіден қайталанатын орналастыру құру керек; олардың санын есептеу керек. Шешуі: |𝐴| = 𝑛 = 3, 𝑚 = 2 . 2 𝐴3 = 32 = 9. Расында, бұл келесі орналастыру: (𝑎, 𝑎), (𝑎, 𝑏), (𝑎, 𝑐), (𝑏, 𝑏), (𝑏, 𝑎), (𝑏, 𝑐), (𝑐, 𝑐), (𝑐, 𝑎), (𝑐, 𝑏). Анықтама. А жиынының n элементтен m бойынша қайталанатын теру деп А жиынының 𝑚 элементінен кез келген ішкі жиыны айтылады және де бір элемент қайталануы мүмкін. Сонымен, қайталанатын теру бір бірінен ең болмағанда бір элементімен ерекшеленеді, бірақ олардың әрбірінде кез келген элемент қайталануы мүмкін. 𝑚 𝑛 элементтен 𝑚 бойынша қайталанатын теру саны былай белгіленеді: 𝐶𝑛 . Дәлелденген: 𝐶𝑚 = 𝐶𝑚 . 𝑛 𝑛+𝑚−1 М ы с а л 4.3.2 𝐴 = {𝑎, 𝑏, 𝑐} жиынының элементтерінен екіден қайталанатын теру құру керек; олардың санын есептеу керек. Шешуі: |𝐴| = 𝑛 = 3, 𝑚 = 2. 2 2 = 𝐶2 = 4⋅3 = 6. Бұл келесі теру: 𝐶3 = 𝐶3+2−1 4 1⋅2 (𝑎, 𝑎), (𝑎, 𝑏), (𝑎, 𝑐), (𝑏, 𝑏), (𝑏, 𝑐), (𝑐, 𝑐). Анықтама. n элементті жиында m әртүрлі элементтер бар болсын. Және де бірінші элемент 𝑛1 рет, екінші - 𝑛2 рет және т.с.с, 𝑚 - ші элемент 𝑛𝑚 рет қайталанылады: 𝑛1 + 𝑛2+. . . +𝑛𝑚 = 𝑛. Берілген n элементті жиынның орын ауыстыруын n элементтен қайталанатын орын ауыстыру деп атайды. 𝑛 элементтен 𝑚 бойынша қайталанатын орын ауыстыру саны былай белгіленеді: 𝑃𝑛(𝑛1, 𝑛2, . . . , 𝑛𝑚). Дәлелденген: 𝑃𝑛(𝑛1, 𝑛2, . . . , 𝑛𝑚) = 𝑛 ! 𝑛 𝑛! !. . . 𝑛 ! . 1 2 𝑚 М ы с а л 4.3.3 1, 1, 2, 4 цифрларынан қанша әртүрлі төрт таңбалы сандар құруға болады. Шешуі: Берілген жиын төрт цифрдан тұрады (𝑛 = 4), олардың арасында 1 екі рет қайталанады: 𝑛1= 2; 2 – бір рет: 𝑛2 = 1, 4 - бір рет: 𝑛3 = 1. Жоғарыда көрсетілген формула бойынша 1,1,2,4 цифрларынан төрт таңбалы сандар саны 4! 𝑃4(2,1,1) = 2! ⋅ 1! ⋅ 1! = 1 ⋅ 2 ⋅ 3 ⋅ 4 1 ⋅ 2 = 12 . жүктеу/скачать 80,45 Kb. Достарыңызбен бөлісу:
|