Комбинаторикалық үйлесімді кескіндерді (конфигурацияларды) қайта есептеу формулалары

Жоспар
Кіріспе

1 Комбинаторикалық үйлесімді кескіндерді (конфигурацияларды) қайта есептеу формулалары
2 Алмастыруды санап шығу
3 Ұластыруға негізделген үйлесімді кескіндер
4 Алмастыруды санап шығу

Пән: Математика, Геометрия
Жұмыс түрі: Материал
Тегін: Антиплагиат
Көлемі: 13 бет
Таңдаулыға:

Комбинаторикалық үйлесімді кескіндерді (конфигурацияларды) қайта есептеу формулалары

қайталанбайтын орналастырулардың саны көбейтіндінің ережесінің көмегімен анықталуы мүмкін. m элементтердің біріншісінің орналастырулары n тәсілмен алынуы мүмкін, екіншісі (n-1) тәсілмен. Онда бірінші алынған элемент қайталанбайтын болғандықтан, осыған ұқсас үшінші үшін (егер m2) (n-2) тәсіл қалады, т.б.
Барлық m элементтерінің алынуы тәсілдерімен n-нен басталып 1-ге келіп отыратын көбейтінділерден тұрады. Басқаша формуланы пайдаланып былай жазады

Мысалы,
1)
2)
3)
4)
Егер m=1,онда
Егер m=n-1,онда
Мұнда 0!=1, 1!=1
екі сандардың теңдігі табиғи: егер n элементтен (n-1)-і алынса, онда қалған бір элемент бір тәсілмен алынуы мүмкін және бұл санын санымен салыстырғанда өзгеріссіз қалады. Сондықтан, n алмастыру Рn =n! (n,m) қайталанбалы орналастырулар - кортеждер, басқаша айтқанда n элементті алфавиттегі ұзындығы m-ге тең деген сөз. Көбейтінді ережесін қолдана отырып, қайталанбалы орналастырудың (n,m) әр түрлі саны екендігін оңай көрсетуге болады. Шынында, басқаларына байланысты емес әрбір n мүшелердің ретті тізбектен алынуы мүмкін, ал олардың саны m-ге тең болады. Мысалдар:
- {0,1} алфавитіндегі m ұзындықты сөздердің саны 2m-ге тең m элементті барлық бөліктерінің саны осындай, сондықтан жиын бір мәнді характеристикалық функция арқылы беріледі. m-мәнді екілік сандардың саны 2m-1 тең, себебі бірінші сан 1-ге тең болуы керек.
- Қайталанбайтын терудің (n,m) саны не символымен белгіленеді де, оны биномдық коэффициенттер деп атайды, себебі х+у екі мүшесінің n дәрежесіндегі Ньютон биномы туралы коэффициенттеріне тең болады.
(1.4.1)
Шынында, мүшесінің коэффициенті (х+у)(х+у)...(х+у), бірдей n көбейткіштердің х-тің алынуы m рет, у-тің алынуы (n-m) рет көбейткіштермен бірігіп көбейтіндіге тең болады. (n,m) қайталанбайтын теруді қайта есептеу үшін (n,m) қайталанбайтын орналастырудың құрамы бірдей элементтер эквиваленттік класс қатынаста болуы тиіс, ал өзгешелігі бар элементтер құрамын теру әр түрлі класқа тиеді. Кластардың әрбіреуіне бірдей m әр түрлі элементтерден тұратын үйлесімді кескіндер кіреді, яғни олар m алмастыруды көрсетеді және әрбір класта олардың саныm!. Осыдан қайталанбайтын (n,m) терудің саны

(1.4.2)
m-ның аз мәні үшін соңғы өрнекке болуы қолайлы, себебі алымы да, бөлімі де m көбейткіштер алымында n-нен басталып бірге азайып отыратын натурал қатар, бөлімінде бірден басталып бірге отыратын натурал қатар [1,k] кездейсоқ түрі
, ,

Егер mn болса, онда деген қолайлы.
Мысалы: , .

1.5 Биномдық коэффициенттердің қасиеттері

Биномдық коэффициенттердің кейбір қасиеттерін келтірейік.
1) . Бұл (1.4.2)-формуладан шығады, себебі n элементтен m элемент алынуы бір мәнді толықтауышты анықтайды, яғни n элементтен (n-m) алынуы, қалған элементтің алынуын көрсетеді. Сондықтан бұрыңғы теңдіктерден мынау шығады:
, .
2) - бұл (1.4.1)-формула х=у=1 қойсақ, осы қасиет шығады. Мысалы,
1+5+10+10+5+1=32=25,
1+6+15+20+15+6+1=64=26
3) (1.4.1)-формулаға х=1, у=-1 қойсақ, осы шығады: мысалы, n=6 үшін:
1-6+15-20+15-6+1=0
4)
Теңдіктің дұрыстығын тексеруге n элементтен {а1,а2,...аn} алынған әрбір теру үшін жеке карточкаға символдар жазылған сәйкес элементтерге осы m элементінің теруі көрсетіледі, екінші қасиет бойынша барлық карточкалар саны 2n болады. Сондықтан, барлық карточкалардағы символдардың қосындысын екі түрлі есептелуі мүмкін:
а) m символдарды ұстайтын карточкасының саны -ға тең; қарастырылған теңдіктің сол жағы барлық карточкалардағы символдардың жалпы саны үшін k=0,1,...,n.
б) Егер барлық карточкалардағы жазылған кейбір символын сызып тастасақ, онда олардың әр түрлі теруі қалған (n-1) элементтерінің саны 2n-1, демек жазылған карточка 2n-1 тең. Теңдіктің оң жағындағы символдардың жалпы саны n∙ 2n-1.
Мысалы, n=5 үшін: 0∙1+1∙5+2∙10+3∙10+4∙5+5∙1=80=5∙16=5 ∙24.
n=6 үшін: 0∙1+1∙6+2∙15+3∙20+4∙15+5∙6+6∙1=192= 6∙32=6∙25
5)
Теңдік мынадай пікірден шығады: n элементті жиынның кейбір х элементін жазып қоямыз. m элементті соңғы жиынның бөлігінің бәрі (олардың саны - теңдіктің сол жағы) екі қиылыспайтын кластарға бөлінеді: х элементін ұстайтын және ұстамайтын.
Бірінші класта жиын бөліктері. Олар х-ті (n-1) элементтердің қалғандарынан (m-1) элементтерді ұстайды. Екінші класта элементтердің болуы айқын. Соңғы тепе-теңдік (сурет 1) Паскаль үшбұрышы1 деп аталатын схемамен байланысты.
Егер үшбұрыштың жолдарын рет бойынша 0,1,2,... сандармен нөмірлесек, онда і-жолда құратын сандар болады. 5-ші қасиет бойынша бірге тең. Шеткісінен басқа әрбір жолдағы сан тұрған сандардың қосындысы болуы мүмкін. Бұл Паскаль үшбұрышының жабайы (канондық) құрамын көрсетеді және одан берілген n-ші жолдағы бином (х+у)n коэффициенттерін оңай табуға болады.
Ескерту. 5-ші қасиет рекуренттік қайталанбалы ара қатынас мысалын көрсетеді: шамасы (n,m) екі аргументтен құралған функция ретінде қарастырылады да, басқа кіші мәндеріндей аргументтері де осы функцияның мәні арқылы өрнектеледі.
Сурет 1 Паскаль үшбұрышы

1
1 1
1 2 1
1 3 3 1
1 4 6 4 1
1 5 10 10 5 1
1 6 15 20 15 6 1
1 7 21 35 35 21 7 1
1 8 28 56 70 56 28 8 1
1 9 36 84 126 126 84 36 9 1
... ... ... ... ... ... ... ... ... ... ... ... ... ..
6) (Коши тепе-теңдігі)
Дәлелдеу үшін мынадай түсініктемені қарастырған қолайлы. n еркектер және k әйелдерден құралған топтардан m адамды делегацияға алады. Ол тәсілдерімен орындалуы мүмкін. (n+k) жиынының m-элементі жиынның бөліктерінің бәрін өрнектердің саны бойынша делегацияға m элементті делегацияны S еркектерді ұстайтын тәсілдермен S еркектер алынуы мүмкін, ал одан кейін m-s әйелдерді тәсілдердің бірі арқылы жүйеленуі мүмкін. Көбейтінді ережесі бойынша осындай делегациялардың саны тең, ал қосынды ережесі бойынша m элементті делегациялардың осындай теңдіктің оң жағындағы сияқты.
Мысалы, (, себебі m=4, n=3 43)
қайталанбалы терудің (n,m) санын алу үшін әрбір осындай теруге, яғни ретсіз n элементтік жиыннан m алынуын екі әріпті алфавиттегі {0,1} кортеждің мынандай тәсілмен алынуын сәйкес қоямыз. Алдымен n натурал саны арқылы {ai} кортежін құрамыз да, і-ші элементтердің n-жиынынан m осы сұрыптауға кіретін санға тең аі болады.
аі - дің кейбіреулері өзара тең болуы мүмкін, n компонентті осындай кортеждің қосындысы m-ге тең. Одан әрі ноль мен бірден кортеж құрамыз да, әрбір аі санын аі бірлігімен өзгертеміз, оларды нольдермен кезектестіреміз .
Егер кейбір аі =0, онда сәйкес нольдердің арасында ешқандай бірліктер болмайды. Басқаша айтқанда, кортеж (n-1) нольдерден n орынды анықтайды: барлық кортеждің сан жағына және әрбір нольдерден оңға қарай і-дің орнына аі бірлік қоямыз (аі-дің кейбіреулері бұрыңғы айтқан бойынша 0-ге тең).
Мысалы, (4,7) теруге (1,1,3,4,4,4,4) сәйкес (2,0,1,4), ал оған кортеж 1100010111; (4,7) теруге (1,2,2,2,3,3,3) сәйкес алдымен кортеж (1,3,3,0), ал кейін кортеж 1011101110. Нәтижесі (n-1) нольдерден және m бірліктерден тұратын теруді аламыз, яғни вектордың ұзындығы (n+m-1) болады.
Керісінше, осындай әрбір векторға (n,m) теруі сәйкес келеді де, серия болып, біртіндеген тәртіппен келетін бірліктер аі санын анықтайды, олардың қосындысы m-ге тең. Сондықтан
(1.4.3)
(1.4.3) теңдікті басқаша жолмен алынуы мүмкін. (с1,с2,...,сm) қайталанбалы (n,m) теруі болсын және де Оған (d1,d2,...,dm) бұл (n+m-1,m) қайталанбайтын теру берілуі мүмкін. Керісінше, әрбір (n+m-1,m) қайталанбайтын теруге (n,m) қайталанбалы теру сәйкес келуі мүмкін, осыдан (1,10) теңдік шығады.
Мысалы,
1-ші кестедегі барлық қайталанбалы 15 (3,4) теру 3 элементтің 4-тен жасалуы сәйкес кортеждермен түгенделген және сәйкес (6,4) қайталанбайтын терулермен көрсетілген.

Кесте 1
1 1 1 1
4 0 0
1 1 1 1 0 0
1 2 3 4
1 1 1 2
3 1 0
1 1 1 0 1 0
1 2 3 5
1 1 1 3
3 0 1
1 1 1 0 0 1
1 2 3 6
1 1 2 2
2 2 0
1 1 0 1 1 0
1 2 4 5
1 1 2 3
2 1 1
1 1 0 1 0 1
1 2 4 6
1 1 3 3
2 0 2
1 1 0 0 1 1
1 2 5 6
1 2 2 2
1 3 0
1 0 1 1 1 0
1 3 4 5
1 2 2 3
1 2 1
1 0 1 1 0 1
1 3 4 6
1 2 3 3
1 1 2
1 0 1 0 1 1
1 3 5 6
1 3 3 3
1 0 3
1 0 0 1 1 1
1 4 5 6
2 2 2 2
0 4 0
0 1 1 1 1 0
2 3 4 5
2 2 2 3
0 3 1
0 1 1 1 0 1
2 3 4 6
2 2 3 3
0 2 2
0 1 1 0 1 1
2 3 5 6
2 3 3 3
0 1 3
0 1 0 1 1 1
2 4 5 6
3 3 3 3
0 0 4
0 0 1 1 1 1
3 4 5 6

- Толықтауыш шарты бар n элементтерден а1а2...аn тұратын қайталанбалы орналастырудың мүмкіншіліктерінің бәрін қарастырамыз. Олардың әрбіреуінде m1 - элементтердің бірінші түрі, m2 - элементтердің екінші түрі, және жалпы айтқанда bi - элементтердің і-ші түрі, .
Әрине, b1+b2+...+br=n теңдігі орындалады. Mi элементтердің і-ші түрін өзгешеліктегі элементтерінің барлығы әр түрлі болады да және одан n! алмастыру шығады.
Сондықтан, орналастырудың негізгі бастапқы саны шығады, ол тең де, мұнда болады. Бұл сан полиномдық (көпмүшеліктік) коэффициент деп аталады, ол (х1+х2+...+хr)nполиномының айнымалы шамалары дәрежелер бойынша жіктелген көбейтіндінің коэффициентіне тең болады. r=2 болғанда, биномдық коэффициенттің жеке түрін көрсетеді.
- Кіретін және шығатын негізінің қолдануына тағы бір мысал ретінде тәртіпсіздік есебі беріледі, оның басқаша аты кездесу туралы есеп.
Кез келген осындай 1,2,3,...,n сандардан а1а2...аn үшін қанша алмастыру жасауға болады?
Бұл санды Dn арқылы белгілейміз және
(*)
формуланы қолданамыз. Мұнда N элементтердің а1а2...аn алмастырулары, бұл n!-ге тең, ал Р(с) қасиеті теңдігімен өрнектеледі. Онда орында белгілі символ қалдыратын алмастырулардың саны.
Одан әрі қосылғыштары бар тәсілдердің санымен 1,2,...n-нен таңдалып алынған . (*) формуланы қолданып, N(0) табамыз.
Сондықтан , N(0)=Dn
- Бірнеше көптеген заттарды қандай да бір саны бар жәшіктерге орналастыру тәсілдерінің санын анықтау үшін, берілген шектеулі шарттардың орындалуы тиіс.
Егер екі жиын Х,Ү берілсе және де X=m, Y=n, Х - заттар жиыны, Ү - жәшіктерден тұратын жиын, yi=f(xi), xi - заттардың уі жәшіктерге орналастыруы, онда әрбір функция осындай орналастыруды көрсетеді.
Ескерту. Жалпы мағынасын кетірмес үшін, әрдайым Х={1,2,...,m}, ал Y={1,2,...,n} мүмкіндігі болсын дейік. Егер орналастыруларға ешқандай шектеулер қойылмаса, онда барлық функцияның саны ... жалғасы

Сіз бұл жұмысты біздің қосымшамыз арқылы толығымен тегін көре аласыз.