Ешбір элементі жоқ қатынас, яғни бос қатынас иррефлексивті, симметриялы, антисимметриялы және транзитивті қатынас болады.
Жиын элементтерiнiң теңдiгi және жазықтықтағы немесе кеңiстiктегi түзулердiң параллелдiк қатынастары рефлексивтi, симметриялы және транзитивті қатынастар болады.
Үшбұрыштар арасындағы теңдiк немесе ұқсастық қатынастары рефлексивтi, симметриялы және транзитивтi қатынастар болады.
Жиындар арасындағы iшкi жиын болу қатынасы мен нақты сандар арасындағы кiшi немесе тең қатынастары рефлексивтi, антисимметриялы және транзитивтi қатынастар мысалдары. Ал кiшi қатынасы иррефлексивтi, транзитивтi, бiрақ симметриялы да, антисимметриялы да емес қатынас болады.
1
№ 4-5
дәріс
Қарастырылатын сұрақтар (дәріс жоспары):
Қосу және көбейту ережесі.
Комбинаториканың негізгі принципі.
Дәрістің қысқаша мазмұны:
Комбинаториканың негізгі есебі – қайта санау және ақырлы жиын элементтерін тізбектеу.
Егер берілген ақырлы жиын элементтерінің қаншасының берілген бір қасиетке ие екендігін анықтау қажет болса бұл қайта санау есебі, ал берілген қасиетке ие барлық элементтерді анықтау керек болса, бұл тізімдеу есебі Комбиторика есебін дәлелдеуде екі ереже жиі қолданылады. Олар: қосу және көбейту ережелері.
Егер Х n элементтерден тұратын ақырлы жиын болса, Х объектісін Х тен n тәсілмен алуға болады дейді және Х=n болып белгіленеді.
Егер Х1,…,Хn – қос қостан қиылыспайтын жиындар болса, яғни Хi Хj= (ij), онда
-қосу ережесі. (1)
Бұл ережені k=2 үшін былай жазуға болады: Егер х объектісі m тәсілмен таңдалса, ал у басқа n тәсілмен таңдалса, онда "не х, не у" таңдау m+n тәсілмен іске асырылады (х және у элементтерін бір уақытта таңдау болмайды).
Көбейту ережесі. Егер х объектісін m тәсілмен таңдауға болса, және осындай таңдаудан кейін у объектісін өз кезегінде n тәсілмен таңдауға болса, онда реттелген (х, у) жұбын mn тәсілмен таңдауға болады.(х, у – таңдаулары тәуелсіз).
Х={х1, …, хn} жиынынан алынған хi1, …, хir элементтерінің жиынтығы n элементтен алынған r көлемді таңдама деп аталады.
Егер элементтердің орналасу тәртібі берілген болса, таңдама реттеген деп, ал орналасу тәртібіне белгілі бір шарт қойылмаса, таңдама реттелмеген деп аталады.
Таңдамаларда элементтердің қайталануы да, қайталанбауы да мүмкін.
Элементтері қайталануы мүмкін (n, r) - таңдамасы (n, r) - қайталама таңдамасы деп аталады. Ал егер реттелген (n, r) таңдаманың элементтері қос қостап әр түрлі болса, (n, r) қайталанбайтын таңдама немесе жай ғана (n, r)-орналасу деп аталады.
(n, n) - қайталанбайтын орналасу Х жиынын алмастыру деп аталады.
Элементтері қайталануы мүмкін реттелмеген (n, r) - таңдама, қайталанба (n, r) - теру деп аталады. Егер реттелмеген (n, r) таңдаманың элементтері қос қостан әр түрлі болса, онда ол қайталанбайтын (n, r) - теруі немесе жай ғана (n, r) теруі деп аталады. Кез келген (n, r) - теруін n-элементті жиынның r-элементті ішкі жиыны деп қарауға болады.
Қайталама теру саны (n, r)-ді , қайталанбайтын теру- . n-элементті теру саны Pn (яғни Pn= ) болып белгіленеді. Қайталама теру (n, r) - саны , ал қайталанбайтын теру - .
1-тұжырым. =nr.
Шынында әрбір (n, r) - қайталама теру ұзындығы r-ға тең реттелген тізбек, ал оның әр мүшесі n тәсілдің бірімен таңдалады, бұдан көбейту ережесінен =nn…n=nr.
(Дербес жағдайда бұл өрнек негізі n санау жүйесінде r позицияда жазылған әр түрлі сандардың нешеу екендігін анықтайды.).
2-тұжырым. =n(n-1)(n-2)…(n-r+1)= , rn және =0, r>n болғанда.
Шынында, r элементтен тұратын реттелген тізбектің бірінші мүшесі n тәсілмен таңдалады, екіншісі - (n-1) тәсілмен, соңғысы - (n–r+1) тәсілмен. Жалпыланған көбейту ережесінен ізделінді формуланы аламыз.
Салдар =Pn=n(n-1) … (n–n+1)=n!
3-тұжырым., егер rn, =0 егер r>n.
Шышында да, әр (n, r)-теруін r! әдіспен реттеуге болады, яғни -ді r! рет -ге қарағанда r! рет аз. Бұл формуладан = .
4-тұжырым. .
Дәрістің қысқаша мазмұны:
3. r-терулер А-дан:
Соңғы формула есептеуге ыңғайлы, факториалдар арқылы формула – жаттауға жеңіл. - симметрия қасиеті.
- Ньютон биномы.
Салдарлар: а)
б)
в)
г) - мына тепе-теңдіктің геометриялық образы Паскальдың үшбұрышы болады.
д)
Қысқаша дәлелдеу үшін -дің келесі эквиваленттік формасын қолданамыз: .
Онда
1
№ 7
дәріс
Қарастырылатын сұрақтар (дәріс жоспары):
1. Граф және оның түрлері.
2. Графтардың берілу тәсілдері.
Дәрістің қысқаша мазмұны:
Граф ұғымы. Көптеген қолданбалы есептерде айналамызды қоршаған ортаның әртүрлі объектілер арасындағы байланыстар жүйесі зерттеледі. Объектілер төбелер деп аталып, нүктелер арқылы белгіленеді, ал төбелер арасындағы байланыстар доғалар деп аталып, сәйкес нүктелерді қосатын бағытталған түзулермен белгіленеді. Қала көшелерін граф арқылы кескіндеуге болады: көше қиылысуларын графтардың төбесі деп, ал көшелерді доғалар деп алуға болады;
Блок-схемаларды да граф түрінде кескіндеуге болады: блоктар — граф төбелері, ал операцияның орындалу кезегін көрсететін стрелкалар доғалар.
