Айталанбалы орналастырулар
a1,…, an – элементтері берілсін. Олардан әр түрлі ұзындығы k-ға тең тізбектер құралады және элементтері қайталанады. Элементтерінің бір түрі қайталана алатын, a1,…, an элементтер жиынның ішінен ұзындығы k-ға тең тізбектерді n-нен k бойынша қайталанбалы орналастыру деп атайды.
n-нен k бойынша алынған қайталанбалы орналастырулар саны деп белгілейміз.
Осылайша, екі орналастыру бір бірінен не элементтер құрамымен, не элементтердің орналасу ретімен өзгешеленеді.
Теорема. = nk.
Дәлелдеу. X1 = … = Xk = {a1,…, an} болсын. n-нен k бойынша әрбір орналастыруды X1 ´ …´ Xk жиынның элементі деп қарастыруға болады. Көбейтінді ережесі бойынша, n(X1´ …´Xk) = nk.
Есеп. 1, 2, 3, 4, 5 цифрларынан құралатын үш таңбалы сандардың санын табу керек.
X1 = X2 = X3 = {1, 2, 3, 4, 5} болсын. 1, 2, 3, 4, 5 цифрларынан 3 таңбалы сандары декарттық көбейтінді элементтеріне сәйкес келеді X1´ X2´ X3. Сондықтан 1, 2, 3, 4, 5 сандарынан құралатын 3 таңбалы сандар саны 53 тең.
Айталанбалы терулер
{a1,…, an} жиыны берілсін. Элементтердің орналасу ретін ескермей, кейбір элементтері қайталана алатын, n элементтен тұратын жиынның ішінен ұзындығы k болатын тізбекті n-нен k бойынша қайталанбалы терулер деп аталады.
n -нен k бойынша қайталанбалы терулер санын деп белгіленеді.
Теорема. = .
Дәлелдеу. Қайталанбалы терулерде элементтердің орналасу реті өзгермейтін болғандықтан, бірдей элементтер тобын тік сызықшамен бөлінетін әрбір теруді a1…a1 | a2…a2 |…| an…an тізбек түрінде жазуға болады. Осындай тік сызықшалар саны n – 1. Онда a1…a1 | a2…a2 |…| an…an тізбектің ұзындығы n + k – 1. Барлық n + k – 1 орындардың ішінен тік сызықшалар n – 1 орынды алады. Мұндай орналасуды тәсілмен жасауға болады. Өйткені = болса, онда = .
Есеп 1. Гастрономда 3 түрлі кәмпит бар. Оларды 3 түрлі қорапқа қаптайды. Әр түрдің өзінің қорабы бар. Неше әдіспен 5 қорапқа сұраныс жасауға болады?
A = {a, b, c} – кәмпит түрлерінің жиыны болсын. Әрбір сұранысты 3-тен 5 бойынша алынған қайталанбалы терулер ретінде қарастыруға болады. Осыдан 5 қорапқа сұраныс жасаудың әдістер саны = = тең.
Есеп 2. 3 бала 63 алма жинады. Оларды балалар өзара қанша тәсілмен бөле алады?
A = {a, b, c} – балалар жиыны. Әрбіреуіне 3-тен 63 бойынша теруін сәйкес қоюға болады. Сондықтан жауабы = = .
Есеп 3. k = 0, 1,… үшін x1 +…+ xn = k теңдеуінің оң бүтін шешімдер санын табу керек.
A = {11, 12,…, 1n} – әртүрлі бірліктер жиыны болсын. Белгісіз xi-дің әрбір мәні 1i бірліктердің қосындысы түрінде аламыз: xi = 1i +…+ 1i, i = 1,…, n. Онда А жиынның ішінен таңдап алынған k бірліктер қосындысы теңдеудің шешімі болады. Бірдей индекстері бар 1i бірліктерін қосып белгісіз xi –белгісіздің мәнін табамыз. Осылайша, теңдеудің әрбір оң бүтін шешіміне n-нен k бойынша қайталанбалы теруі сәйкес келеді.
Осыдан, берілген теңдеудің шешімдер саны .
Есеп 4. n бірдей заттардың m ыдыстарға орналастыру санын табу керек.
Шешімі: Ыдыстарды қайта нөмірлейміз. Заттардың әрбір орналасуына сәйкес ыдыстарға нөлдер мен бірліктерден тұратын тізбекті келесі әдіспен қоюға болады. Алдымен бірінші ыдыстағы заттар санына тең болатындай нөлдерді, одан кейін бірді жазамыз. Содан кейін екінші ыдыстағы заттар қанша болса, сонша нөлдерді жазамыз, содан кейін тағы да бірді жазамыз, үшінші ыдыста қанша зат болса, сонша нөлдер жазып, тағы да бірді жазамыз. Осылай жалғаса береді. Қатарда n нөл мен m – 1 бірліктер бар, барлығы m + n – 1 сандар бар.
Мысалы, n = 10, m = 4 болғанда 1011000000000 тізбекте бірінші ыдыста зат жоқ, екінші ыдыста 1 зат үшіншіде зат жоқ, төртіншіде 9 зат бар; ал 0010010000001 тізбекке келесі орналасу сәйкес келеді: 1-ші ыдыста 2 зат бар, 2-ші ыдыста 2 зат бар, 3-ші ыдыста 6 зат бар төртіншісінде жоқ. Осыдан жауабы: .