4. Теру
Есеп. Құрамында n элементі бар жиыннан r элементтен тұратын әртүрлі қанша жиын құруға болады?
Алдымен әрбіреуінен r
элементтен тұратын реттелген жиынтықты
құрамыз. Бұндай жиынтықтың саны
тең (бұл n
элементтің r
бойынша орналастыру болып табылады).
Енді элементтердің жазылу реті маңызды
емес екендігін ескерейік. Сонымен қатар
әр түрлі, бір бірінен тек элементтедің
реті бойынша өзгешеленетін
орналастыруынан бір теру аламыз. Мысалы,
екі элементтен тұратын, екі әр түрлі
және
оранластыруына бір
теруі сәйкес келеді. Осылайша,
теру саны
оналастыруынан
есе кіші:
Мысал. Сегіз дворниктен үшеуін таңдап алу тәсілінің саны мынаған тең
Қайталамалы теру
Есеп. n
заттан r
бойынша қайталамалы теруді
табу керек. Формуланың қорытып шығарылуын
суреттегі мысалдан қарастырайық (1.5.2
қараңыз). n
типті зат бар (
негатив). r
заттан тұратын жиынтықты құру керек (
фотосурет). Жиынтық элементтерінің реті
бойынша емес, өзінің құрамы бойынша
өзгешеленеді. Мысалы,
және
құрамды жиынтық әр түрлі болады –
біреуінде бірінші негативтен алынған
3 фотосурет, екінші және үшінші негетивтен
бір –бір фотосуреттен, ал басқасында
- бірінші негативтен біреу және үшінші
негативтен төрт фотосурет бар. Осы
жиынтықты үстелге әр түрлі титпті
фотосуреттерді каламсаппен бөлу арқылы
жайып қояйық (1.26 сурет). Бізге
қаламсап қажет болады, ал фотосуреттен
қажет. Біз осы
затты өзара ауытыру арқылы әр түрлі
қайталамалы теру аламыз, яғни n
заттан r
бойынша алынған
қайталамалы теру саны құрамы
,
ұзындығы
болатын қайталамалы алмастырулар санына
тең болады. Біздің мысалда бұл
Қайталамалы теру формуласын басқаша былай жазуға болады:
5. Ньютон биномы
Мектепте қысқаша көбейту
формуласын оқытады:
Ньютон биномы осы формулалар қатарын жалғастыруға мүмкіндік береді. Келесі өрнектегі жақшаларды ашайық:
Қосындының жалпы мүшесі
түріне ие болады. C
коэффициенті неге тең?
Ол
қосылғышын алуға болатын әдістер санына
тең (яғни а
көбейткіші бар k
жақшаны, ал қалған
жақшадан b
көбейткішті таңдап алу әдісіне тең).
Мысалы, егер
болса, онда
қосылғышын бірінші және бесінші жақшадан
а
көбейткішін таңдап алу арқылы ала
аламыз. Іріктеме типі қандай? Саналу
реті маңызды емес (алдымен біріншіні,
содан кейін бесінші жақшаны таңдаймыз
немесе керісіше алдымен бесіншіні,
содан кейін біріншіні), іріктемеде
қайталанатын элементтер жоқ (біріңғай
нөмірлі жақша). Бұл қайталамасыз теру.
Мұндай іріктеменің саны мынаған тең:
Сонымен, кез келген натурал n үшін бином формуласы мына түрге ие болады:
немесе
.
Мысал.
болғанда мына формуланы
аламыз
Себебі
Формуланың дұрыстығын
-ны
-ға
көбейту арқылы тексеріңіз. Ньютон биномы
формуласының қатаң дәлелдеуі математикалық
индукция әдісімен жүзеге асырылады.
Биноминальды коэффициенттердің қасиеттері
Биномиальды коэффициентке n элементтен k бойынша теру санын өрнектейтін
,
шамасы жатады. Бұл шамалар мынадай қасиеттерге ие болады.
Симетрия қасиеті.
.
Бином формуласында бұл
формуланың оң жақ және сол жақ ұшында
бірдей орында тұрған коэффициенттер
мысалы,
тең дегенді білдіреді.
Расында да,
-
бұл n
элементтен тұратын жиынның k
элементтен тұратын ішкі жиындарының
саны. Ал
-
бұл оларға қосымша ішкі
жиындардың саны.
Паскаль қасиеті.
Айталық
болсын.
саны – бұл Х
жиынының k элементтен
құралған ішкі жиынының саны. Барлық
ішкіжиындарды екі классқа бөлейік:
1) Құрамында
элементі жоқ ішкі жиындар, олардың саны
;
2) Құрамында
элементі бар ішкі жиындар, олардың саны
.
Б
ұл
класстар қиылыспайтындықтан, онда
қосынды ережесі бойынша Х
жиынының k
элементтен құралған барлық ішкі жиындар
саны
тең.
Осы қасиеттің негізінде
Паскаль үшбұрышы құрылады (1.28 сурет),
оның n-ші
жолында
биномдық жіктеудің коэффициенттері
жатады.
Қосындының қасиеті.
Ньютон биномы формуласына қояйық
мәні
.
Бұдан
аламыз.
Айырманың қасиеті.
Ньютон биномы формуласына
қояйық. Сол жақ бөлігінен
,
ал оң жақ бөлігінен таңбасы
ауысып отыратын биноминальдық
коэффициенттерді аламыз, ал бұл қасиеттің
дәлелдеуі болып табылады.
Соңғы қасиетті барлық теріс
таңбалы коэффициенттерді формуланың
сол жағына шығару арқылы жазу ыңғайлы
болады:
Есеп.
Құрамында х
жоқ
биномдық жәктеудің мүшелерін табу
керек, егер тақ нөмірлі биноминальдық
коэффициенттердің қосындысы 512 тең
болса.
Шешуі.
Айырманың қасиеті бойынша тақ нөмірлі
биноминальдық коэффициенттердің
қосындысы да 512 тең, ендеше,барлық
коэффициенттердің қосындысы мынаған
тең 512+512=1024. Алайда қосындының қасиеті
бойынша бұл сан мынаған тең
.
Сондықтан
.
Биномдық жіктеудің жалпы мүшесін жазып
оны түрлендірейік:
болғанда
мынаны аламыз:
Член разложения
жіктеу мұшесінің құрамында
x
жоқ, егер
,
яғни
.
Сонымен жіктеудің тоғызыншы
мүшесінің құрамында x
жоқ және ол мынаған тең
Максимум қасиеті.
Егер n
биномының дәрежесі – тақ сан болса,
онда
болғанда биноминальды коэффициенттердің
арасында бір максималдысы болады. Егер
биномның дәрежесі тақ болса, онда
максималды мәнге екі биноминальды
коэффициент үшін
және
болғанда жетеді. Сонымен
юолғанда максималды коэффициент -
,
ал
болғанда
максималды мән
тең (1.28 сурет).
Ұсынылған әдебиеттер:
1. Нұрсұлтанов Қ.Н., Дискретті математика және математикалық логика. – Семей 2002.
2. Судоплатов С.В., Овчинникова Е.В. Элементы дискретной математики. –М.: ИНФРА-М, Новосибирск: изд-во НГТУ, 2002.
3. Смыслова З.А.. Дискретная математика (Учебное пособие), Томск, 2000.
4. Қ.Жетпісов., Математикалық логика және дискретті математика. Алматы, 2011.
5. Шапорев С.Д. Математическая логика. Курс лекций и практических заниятий.- СПБ.: БХВ-Петербург 2005. - 416стр.
6. Тишин В.В. Дискретная математика в задачах и примерах. БХВ-Петербург 2008.
Дәріс 6 – 7
Дәріс сабақтың құрылымы: