Комбинаториканың математиканың әр түрлі бөлімдерімен байланысы

Мазмұны

Кіріспе 3

§1. Комбинаторикалық есептерді шығаруда Бернсайд леммасының қолданылуы 5

1.1. Алмастырулар тобының орбиталары 5

1.2. Алмастырулар тобының орбитасының ұзындығы. Бернсайд леммасы 5

1.3. Комбинаторика есептері 8

§2. «Елеу әдісі» 21

2.1. Кірістіру мен шығару формуласы 21

2.2. «Елеудің» немесе «електен өткізудің» жалпылама әдісі. Сильва-Сильвестр елегі 23

2.3. Елеудің жалпылама әдісін сандар теориясында қолдану 23

§3. Фигураларды ең кіші диаметр бойынша бөліктерге бөлу 28

§4. «Сәтті билеттер» 34

Библиографиялық тізім 39

Кіріспе

Берілген объектілерден қандай да бір шарттарға бағынатын әр түрлі қиыстырулардың санын зерттейтін математиканың бөлігі комбинаторика деп аталады. Комбинаторика XVI ғасырда пайда болды. Құмар ойындарға қатысты сұрақтар комбинаториканың дамуына түрткі болды. Қазіргі кезде комбинаториканың әдістері математиканың өзінде де, сондай-ақ математикадан тыс ғылымдарда да – кодтау теориясы, экспериментті жоспарлау, топология, шекті алгебра, математикалық логика, ойындар теориясы, кристаллография, биология, статистикалық физика, экономика, т.б. қолданылады.

Бірнеше ғасырда дамып келген комбинаторика өзіндік зерттеу әдістерін тауып, бір жағынан алгебраның, геометрияның, анализдің есептерін шығаруда қолданылса, екінші жағынан өзі де геометриялық, аналитикалық және алгебралық зерттеу әдістерін пайдаланады.

Дипломдық жұмыстың мақсаты: комбинаториканың математиканың әр түрлі бөлімдерімен байланысын көрсету.

Міндеттері:

1. Бернсайд леммасын зерттеу және лемманы пайдаланып бояуға қатысты комбинаторикалық есептерді шығару;

2. Жай және өзара жай сандарды санауда «елеу» әдісінің қолданылуын көрсету;

3. Жазық фигураларды ең кіші диаметр бойынша бөліктерге бөлу есебін шешетін Борсук теоремасын зерттеу;

4. «Сәтті билеттер» есебін шығару.

Дипломдық жұмыс төрт бөлімнен тұрады:

Бірінші бөлімде топтар теориясының комбинаторикамен байланысы, соның ішінде комбинаториканың есептерін шығаруда алмастырулар тобының қолданылуы қарастырылды.Бұл бөлімде негізгі қолданылған факт – Бернсайд леммасы.

Екінші бөлімде қайта есептеудің жалпылама әдісі (XVIII ғасырда пайда болған)көрсетіліп, оның сандар теориясындағы қолданылу мысалдары келтірілді.

Үшінші бөлім комбинаторлық геометрияға – фигураны бірнеше кіші бөліктерге бөлу сұрағына арналған. Бұл сұрақты әрі қарай өрбітуде Борсук теоремасы негіз болып табылады.

Төртінші бөлімде сәтті билеттер туралы әйгілі есепті математикалық анализдің әдістерін қолдану арқылы шығару жолы қарастырылады.

§ 1. Комбинаторикалық есептерді шығаруда Бернсайд леммасының қолданылуы

1.1. Алмастырулар тобының орбиталары

Айталық, G – жиынындағы алмастырулар тобы болсын. ішкі жиыны G тобының орбитасы деп аталады, егер: а) кез келген және кез келген үшін болса, яғни G элементтерін О элементтеріне алмастыру амалы О жиынының шегінен аспаса; ә) О жиынының кез келген екі элементін G тобынан алмастырулар арқылы бір-біріне алмастыруға болатын болса.

Кез келген алмастырулар тобының орбиталары болатынын көрсету оңай.

Бұндай түрдегі орбиталар арқылы барлық түрдегі орбиталар сарқылып қалады, яғни егер О – G тобының орбитасы және болса, онда .

Кез келген және екі орбитасы немесе беттеседі (егер ), немесе қиылысады (егер ).

Осылайша, М жиыны қиылыспайтын ішкі жиындардың – G тобының орбиталарының бірігуіне ыдырайды. М жиынының G алмастырулар тобының орбиталарына ыдырауына байланысты төмендегі екі сұрақ пайда болады:

1. G тобының М жиынында неше орбитасы болады?

2. Осы орбиталардың әрқайсысының ұзындығы қандай, яғни олар неше элементтен тұрады?

Осы сұрақтарға жауап берейік.

1.2. Алмастырулар тобының орбитасының ұзындығы. Бернсайд леммасы

Екінші сұраққа жауап берейік. кез келген элементі үшінG-дыңа нүктесі қозғалмайтын нүкте болып табылатын барлық алмастыруларының тобын қарастыруға болады. Ол а нүктесінің тұрақтандырғышы деп аталады. Келесі теореманы дәлелдеу арқылы сұраққа жауап береміз:

орбитасының ұзындығы G тобындағы тұрақтандырғышының индексіне тең болады, яғни .

Дәлелдеуі. болсын. тізбегіндегі әр түрлі элементтер санын білу үшін G тобының элементтерін қатарға жазып алу ыңғайлы болады. Ол үшін G тобын ішкі жиыны бойынша шектесетін және элементтер саны бірдей болатын оң жақты кластардың барлық қиылыспайтын бірігулер түрінде жазуға болатыны екенін қолданамыз. Яғни

(*)

қатарының барлық алмастырулары қос-қостан әр түрлі болатын және G тобын сарқитын алмастырулар болады.

Кез келген үшін а элементіне (*) кестесінің i-ші жолын құрайтын алмастыруларын қолдану элементін береді (себебі а элементін қозғалмайтын етіп қояды). барлық l элементтері қос-қостан әр түрлі. Расында да, егер де қандай да бір i, j үшін болса, онда болады, яғни алмастыруы болады. Бірақ бұл орындалады егер мен G тобының ішкі жиыны бойынша бір оң жақты класта жату керек, ал ол мүмкін емес. Осылайша, орбитасының ұзындығы l-ге, яғни (*) кестесіндегі жолдар санына тең: (яғни l топтағы ішкі топтың индексі болып табылады). Лагранж теоремасы бойынша , яғни . Теорема дәлелденді.

Енді бірінші сұраққа жауап берейік. Ол үшін Бернсайд леммасын тұжырымдап, оны дәлелдейміз.

Айталық, – α алмастыруының қозғалмайтын нүктелер саны, – жиынында жүзеге асатын алмастырулар тобының орбиталар саны болсын. Онда алмастырулардың кез келген тобы үшін төмендегі теңдік орындалады:

, мұндағы .

Дәлелдеуі. G тобының алмастырулары мен М жиынының элементтері арасындағы «α алмастыруы т элементін қозғалтпай сақтайды» қатынасын қарастырайық. жұптарына тікбұрышты тордың төбелерін сәйкестікке қойып, олардың ішінен жұбы аталған қатынаста, яғни болатындарды белгілейік (1-сурет).

Б асқаша айтқанда, берілген қатынастың графигін тұрғызайық.

Белгіленген нүктелер санын (графикке тиісті нүктелер) екі тәсілмен есептеуге болады: әрбір тік сызықтағы белгіленген нүктелер санын анықтап, оларды қосу немесе әрбір көлденең сызықтағы белгіленген нүктелер санын анықтап, оларды қосу. Қатынастың анықтамасына сәйкес әрбір тік сызықта осы сызыққа сәйкес келетін α алмастыруымен сақталатын барлық нүктелер белгіленеді. Олардың саны болады. Сондықтан графиктегі барлық нүктелердің саны

мұндағы .

Басқа жағынан қарағанда, әрбір көлденең сызықта осы сызыққа сәйкес келетін элементін сақтайтын барлық алмастырулар белгіленеді. Ал мұндай алмастырулар тобын – т элементінің тұрақтандырғышын құрайды және олардың саны бұрын дәлелденген теорема бойынша болады. Сондықтан берілген қатынастың графигіндегі белгіленген нүктелер санын анықтаудың екінші тәсілі бойынша өрнегін аламыз.

Бірақ, егер элементтері бір орбитада болса, онда , сондықтан –G тобының және бұл бірігудегі қосылғыштар қиылыспайтынбарлық орбиталары болсын. қосындысын бөліктерге бөлейік және осы бөліктердің әрқайсысының ішінде қосынды қандай да бір орбитаның элементтері бойынша жүргізілсін:

.

Бұл теңдіктің оң жағындағы әрбір t қосылғышты төмендегідей түрлендіруге болады:

.

Сондықтан .

Осылайша, нүктелер санын анықтаудың екінші тәсілі бойынша графикте белгіленген нүктелер алдық. Бірінші және екінші тәсілде алынған шамаларды теңестіріп,

,

аламыз, яғни .

Лемма дәлелденді.

1.3. Комбинаторика есептері

Санауға берілген комбинаторикалық есептерді шешуде Бернсайд леммасын қолдану мүмкіндіктерін көрсететін бірнеше мысал қарастырайық.

1-Есеп. Қанша тәсілмен кубтың төбелерін үш түске (мысалы, қызыл, көк және жасыл) бояуға болады?

Шешуі. (Осы есепте қолданылған белгілеулерді басқа есептерде де қолданамыз). Кубтың сегіз төбесінің әрқайсысын басқа төбелерінің қалай боялғанына қарамастан үш тәсілмен бояуға болатындықтан, кубтың барлық төбелерінің жиынын әр түрлі тәсілмен бояуға болады ( формуласы бойынша). Алайда бұл жағдайда үнсіз келісім бойынша кубтың төбелерін бояудың алдында оның төбелерін бір-бірінен ажырата аламыз деп ұйғарылады, яғни, айталық, куб мығым орналасқан немесе оның төбелері нөмірленген. Бұл жағдайда алынған жауапты келесідей етіп түрлендіруге болады: осылайша абсолютті бірдей және мығым орналасқан кубтарды барлығы бір-біріне ұқсамайтындай етіп бояуға болады. куб үшін бұны жасай алмаймыз. Жағдай мүлдем өзгеріп шығады, егер кубтар мығым орналасқан деген болжамнан бас тартатын болсақ, себебі әр түрлі етіп боялған кубтарды басқа қалыпқа қойғанда олардың түстері сәйкес келетіндей етіп айналдырып қоюға болады (2-сурет).

Е кі куб бірдей боялған болып есептеледі, егер олардың түстері кубтардың кеңістікте орналасу тәсіліне дейін сәйкес келетін болса, яғни кубтардың біреуін айналдырғанда сәйкес келсе. Кубтардың осындай боялған тәсілдері геометриялық айырықсыз деп айтайық. Сондықтан бояу туралы есептің орынды нақтылауы төмендегі есеп болады: қанша геометриялық әр түрлі тәсілмен кубтың төбелерін үш түске бояуға болады.

Енді бұл есептің Бернсайд леммасымен байланысы түсінікті болу үшін оны басқаша тұжырымдайық. М – мүмкіндігінше әр түрлі боялған бірдей пішінді және кеңістіктегі орны белгіленген ( ) кубтардың жиыны, ал G – кубтың барлық айналу тәсілдерінің тобы болсын. G тобы М жиынындағы алмастырулар тобын айқындайды. Атап айтқанда, егер – қандай да бір айналу болса, онда М жиынының әрбір кубына осы кубты α рет айналдырғанда шығатын басқа бір кубты сәйкестікке қоюға болады. Бұл сәйкестік М жиынындағы алмастыру болып табылады, оны деп белгілейік. G тобынан алынған алмастырулармен анықталатынМ жиынының осындай барлық алмастыруларының тобын деп белгілейміз. екені түсінікті. М жиынының К₁ және К₂ екі кубы геометриялық бірдей боялған дегеніміз – олардың біреуін айналдыру арқылы екеуін де бірдей боялған қалыпқа келтіруге болады дегенді білдіреді. Басқаша айтқанда, болатындай алмастыруы табылады, яғни К₁ және К₂ М жиынында іске асатын тобының бір орбитасында орналасқан. Осылайша, кубтың төбелерін бояудың геометриялық әр түрлі тәсілдер санын анықтау үшін М жиынындағы тобының орбиталар санын анықтау керек. Кубтардың төбелерін 1, 2, 3, 4, 5, 6, 7, 8 сандарымен нөмірленген деп есептеп, кубтарының әрқайсысын бояуды әрқайсысы немесе қ, немесе к, немесе ж болатындай сегіз әріптен тұратын «сөзбен» сипаттауға болатыны анық. Сөздің i-ші әрпі қ (немесе к, немесе ж) болады дегеніміз – таңдалған нөмірлеудегі i-ші төбе қызыл түске (сәйкесінше немесе көкке, немесе жасылға) боялды дегенді білдіреді. тобының алмастырулары қ, к, ж әріптерінің реттілігін алмастырады. Бернсайд леммасын қолдану үшін тобының әрбір алмастыруындағы қозғалмайтын нүктелер санын анықтап алу қажет. Қ, к, ж әріптерінің реттілігі алмастыруы үшін қозғалмайтын болады сонда және тек қана сонда, егер сәйкес алмастыруын кубтың нөмірлері бір циклдің құрамына кіретін төбелерінің циклдер көбейтіндісіне жіктеу кезінде бірдей түске боялған болса. Егер алмастыруы k циклдерінің көбейтіндісіне жіктелген болса, онда оның қозғалмайтын нүктелер саны болады, мұндағы , себебі кубтың нөмірлері бір циклдің құрамына кіретін төбелерін үш тәсілмен бояуға болады. Кубтың айналуларының G тобындағы барлық алмастырулары үшін циклдердің көбейтіндісіне жіктелуін сипаттайық.

а) Қарама-қарсы жақтардың центрлерін қосатын үш осьтің әрқайсысы болатын бұрыштарға үш рет айнала алады. Оларға мына алмастырулар сәйкес келеді:

1) (1, 5, 8, 4) (2, 6, 7, 3)

2) (1, 8) (2, 7) (3, 6) (4, 5)

3) (1, 4, 8, 5) (2, 3, 7, 6)

4) (1, 4, 3, 2) (5, 8, 7, 6)

5) (1, 3) (2, 4) (5, 7) (6, 8)

6) (1, 2, 3, 4) (5, 6, 7, 8)

7) (1, 5, 6, 2) (3, 4, 8, 7)

8) (1, 6) (2, 5) (3, 8) (4, 7)

9) (1, 2, 6, 5) (3, 7, 8, 4)

ә) Кубтың төрт диагоналінің әрқайсысы екі рет айнала алады. Оларға мына алмастырулар сәйкес келеді:

10) (1) (2, 5, 4) (3, 6, 8) (7)

11) (2) (1, 3, 6) (4, 7, 5) (8)

12) (3) (1, 6, 8) (2, 7, 4) (5)

13) (4) (1, 3, 8) (2, 7, 5) (6)

14) (1) (2, 4, 5) (3, 8, 6) (7)

15) (2) (1, 6, 3) (4, 5, 7) (8)

16) (3) (1, 8, 6) (2, 4, 7) (5)

17) (4) (1, 8, 3) (2, 5, 7) (6)

б) Кубтың қарама-қарсы қырларының орталарын қосатын алты осьтің әрқайсысы бір рет айнала алады. Оларға мына алмастырулар сәйкес келеді:

18) (1, 5) (2, 8) (3, 7) (4, 6)

19) (1, 2) (3, 5) (4, 6) (7, 8)

20) (1, 7) (2, 3) (4, 6) (5, 8)

21) (1, 7) (2, 6) (3, 5) (4, 8)

22) (1, 7) (2, 8) (3, 4) (5, 6)

23) (1, 4) (2, 8) (3, 5) (6, 7)

(1)(2)(3)(4)(5)(6)(7)(8) түріндегі тепе-тең алмастырумен бірге 24 алмастыруды – G тобының барлық элементін аламыз. Сонымен, кубтың айналу G тобында мыналар бар:

<1, 1, 1, 1, 1, 1, 1, 1> түріндегі 1 алмастыру,

<4, 4> түріндегі 6 алмастыру,

<2, 2, 2, 2> түріндегі 9 алмастыру,

<1, 1, 3, 3> түріндегі 8алмастыру.

Онда бірінші түрдегі алмастыруда қозғалмайтын нүкте бар, екінші түрдегі кез келген алмастыруда – , үшінші және төртінші түрде – қозғалмайтын нүктелер бар ( формуласы бойынша). Сондықтан, Бернсайд леммасына сәйкес, шығады.

Осылайша, кубтың төбелерін үш түске бояудың геометриялық әр түрлі тәсілдерінің саны 333-ке тең.

2-Есеп. Екі түсті – қызыл және көк моншақтардан жеті моншақтан тұратын әр түрлі қанша алқа жасауға болады?

Шешуі. Бұл есепті өзімен тең күшті болатын басқаша тұжырымдап жасайық: дұрыс жетібұрыштың төбелерін екі түске бояудың қанша геометриялық әр түрлі тәсілдері бар? М – кеңістіктегі орны бекітілген өлшемдері бірдей барынша әр түрлі боялған дұрыс жетібұрыштардыңжиыны болсын. Онда жетібұрыштың төбелерін бояудың әр түрлі нұсқалары бар, себебі жетібұрыштың әрбір төбесін басқаларынан тыс екі түрлі тәсілмен бояуға болады. Мұндағы бояудың екі түрлі тәсілі бір-бірінен ажыратылмайды, егер жетібұрышқа айналу түрлендіруін немесе осьтерге қатысты симметрияны қолданып біреуін екіншісінен алуға болатын болса. Бояу тәсілдерін қ (төбесі қызыл түске боялған) және к (төбесі көк түске боялған) әріптерінен құралған ұзындығы 7-ге тең «сөздермен» сипаттаймыз. Бернсайд леммасын қолдану үшін 1-есептегі әрекеттерді қайталаймыз. G тобының барлық алмастырулары үшін циклдердің көбейтіндісіне жіктелуін сипаттайық.

а) Тепе-тең түрлендіруге төмендегі алмастыру сәйкес келеді:

1) (1)(2)(3)(4)(5)(6)(7)

ә) бұрыштарына бұруға төмендегі алмастырулар сәйкес келеді

2) (1,2,3,4,5,6,7)

3) (1,3,5,7,2,4,6)

4) (1,4,7,3,6,2,5)

5) (1,5,2,6,3,7,4)

6) (1,6,4,2,7,5,3)

7) (1,7,6,5,4,3,2)

б) Жетібұрыштың төбелеріне қарсы жатқан қабырғаларының центрлерімен қосатын осьтерге қатысты симметрияларға төмендегі алмастырулар сәйкес келеді:

8) (1) (2,7) (3,6) (4,5)

9) (2) (1,3) (7,4) (5,6)

10) (3) (2,4) (1,5) (6,7)

11) (4) (3,5) (2,6) (7,1)

12) (5) (4,6) (3,7) (2,1)

13) (6) (5,7) (4,1) (2,3)

14) (7) (1,6) (2,5) (3,4),

мұндағы 1, 2, 3, 4, 5, 6, 7 – жетібұрыштың төбелері нөмірленген сандар.

Сонымен, G тобында мыналар бар:

<1, 1, 1, 1, 1, 1, 1> түріндегі 1 алмастыру,

<7> түріндегі 6 алмастыру,

<1, 2, 2, 2> түріндегі 7 алмастыру.

Сөз алмастыруына қатысты қозғалмайды сонда және тек қана сонда, егерорналасу нөмірлері α алмастырудағы бір циклде жататын әріптер сәйкес келсе. Сондықтан М жиынында тепе-тең алмастырудың , екінші түрдегі алмастырудың – 2, үшінші түрдегі алмастырудың – қозғалмайтын нүктелері бар. Бернсайд леммасын қолданып,

аламыз.

Осылайша, екі түсті моншақтардан 7 моншақтан тұратын 18 алқа жасауға болады.

3-Есеп. Кубтың жақтарын бояуға болады: а) барлығын ақ түске; ә) барлығын қара түске; б) кейбірін ақ түске, ал кейбірі қара түске. Әр түрлі етіп бояудың неше тәсілі бар?

Шешуі.

(1' 4' 5' 8') жағы– 1

(2' 3' 6' 7') жағы – 2

(3' 4' 7' 8') жағы – 3

3-сурет (1' 2' 5' 6') жағы – 4

(1' 2' 3' 4') жағы – 5

(5' 6' 7' 8') жағы – 6

а) Қарама-қарсы жақтардың центрлерін қосатын үш осьтің әрқайсысы болатын бұрыштарға үш рет айнала алады. Оларға мына алмастырулар сәйкес келеді:

1) (1) (2) (5, 4, 6, 3)

2) (1) (2) (4, 3) (6, 5)

3) (1) (2) (5, 3, 6, 4)

4) (3) (4) (1, 6, 2, 5)

5) (3) (4) (1, 2) (6, 5)

6) (3) (4) (5, 2, 6, 1)

7) (5) (6) (1, 3, 2, 4)

8) (5) (6) (1, 2) (3, 4)

9) (5) (6) (4, 2, 3, 1)

ә) Кубтың төрт диагоналінің әрқайсысы екі рет айнала алады. Оларға мына алмастырулар сәйкес келеді:

10) (2, 6, 3) (1, 5, 4)

11) (3, 6, 2) (4, 5, 1)

12) (6, 4, 2) (1, 5, 3)

13) (2, 4, 6) (3, 5, 1)

14) (1, 3, 6) (2, 4, 5)

15) (6, 3, 1) (5, 4, 2)

16) (1, 4, 6) (2, 3, 5)

17) (6, 4, 1) (5, 3, 2)

б) Кубтың қарама-қарсы қырларының орталарын қосатын алты осьтің әрқайсысы бір рет айнала алады. Оларға мына алмастырулар сәйкес келеді:

18) (2, 3) (1, 4) (5, 6)

19) (1, 3) (4, 2) (5, 6)

20) (1, 6) (5, 2) (3, 4)

21) (1, 5) (6, 2) (3, 4)

22) (4, 6) (3, 5) (1, 2)

23) (6, 3) (5, 4) (1, 2)

(1)(2)(3)(4)(5)(6)(7)(8) түріндегі тепе-тең алмастырумен бірге 24 алмастыруды – G тобының барлық элементін аламыз. Сонымен, кубтың айналу G тобында мыналар бар:

<1, 1, 1, 1, 1, 1> түріндегі 1 алмастыру,

<1, 1, 4> түріндегі 6 алмастыру,

<1, 1, 2, 2> түріндегі 3 алмастыру,

<3, 3> түріндегі 8 алмастыру,

<2, 2, 2> түріндегі 6 алмастыру.

Сондықтан бірінші түрдегі алмастыруда қозғалмайтын нүкте бар, екінші және бесінші түрдегі алмастыруда – , үшінші түрдегі алмастыруда – , ал төртінші түрдегі алмастыруда қозғалмайтын нүктелер бар Онда, Бернсайд леммасына сәйкес, шығады.

Осылайша, кубтың жақтарын екі түске бояудың геометриялық әр түрлі тәсілдерінің саны 10-ға тең.

4-Есеп. Екі көк, екі ақ және екі қызыл моншақтан әр түрлі қанша алқа жасауға болады?

Шешуі. Есепті басқаша тұжырымдайық: дұрыс алтыбұрыштың төбелерін екеуі көк түсті, екеуі ақ түсті, екеуі қызыл түсті етіп қанша геометриялық әр түрлі тәсілмен бояуға болады?

а) Алтыбұрыштың центрі бұрыштарға бес рет бұрыла алады. Оларға мына алмастырулар сәйкес келеді:

1) (1, 2, 3, 4, 5, 6)

2) (1, 3, 5) (2, 4, 6)

3) (1, 4) (2, 5) (3, 6)

4) (1, 5, 3) (2, 6, 4)

5) (1, 6, 5, 4, 3, 2)

ә) Дұрыс алтыбұрыштың қарама-қарсы төбелерін қосатын осьтерге қатысты үш симметрия болады. Оларға мына алмастырулар сәйкес келеді:

6) (1) (4) (2, 6) (3, 5)

7) (2) (5) (3, 1) (4, 6)

8) (3) (6) (2, 4) (1, 5)

б) Дұрыс алтыбұрыштың төбелерін қарама-қарсы қабырғаларының орталарымен қосатын осьтерге қатысты үш симметрия болады. Оларға мына алмастырулар сәйкес келеді:

9) (1, 2) (6, 3) (5, 4)

10) (1, 6) (2, 5) (3, 4)

11) (2, 3) (1, 4) (6, 5)

(1)(2)(3)(4)(5)(6) түріндегі тепе-тең алмастырумен бірге 12 алмастыруды – G тобының барлық элементін аламыз. Сонымен, G тобында мыналар бар:

<1, 1, 1, 1, 1, 1> түріндегі 1 алмастыру,

<6> түріндегі 2 алмастыру,

<3, 3> түріндегі 2 алмастыру,

<2, 2, 2> түріндегі 4 алмастыру,

<1, 1, 2, 2> түріндегі 3 алмастыру.

Әрбір түрге қатысты алмастырулар үшін қозғалмайтын нүктелер санын анықтайық. Алтыбұрышты бояйтын әр түрлі түстердің саны үшке тең болғандықтан, алмастырудағы циклдердің минималды саны үшке тең болу керек. Демек, 1), 2), 4), 5) алмастырулардың қозғалмайтын нүктелері жоқ. Бірінші түрдегі алмастыру үшін қозғалмайтын нүкте аламыз. <2, 2, 2> түріндегі әрбір алмастыру үшін көбейту принципі бойынша қозғалмайтын нүкте аламыз. <1, 1, 2, 2> түріндегі әрбір алмастыру үшін көбейту принципі бойынша қозғалмайтын нүкте аламыз. Бернсайд леммасын қолданамыз: .

Сонымен, екі көк, екі ақ, екі қызыл моншақтан 11 әр түрлі алқа жасауға болады.

5-есеп. Үш бірдей шыбын дұрыс бесбұрыштың төбелеріне геометриялық әр түрлі қанша тәсілмен орналаса алады?

Шешуі. М – үш бірдей шыбынның төбелері нөмірленген бесбұрыштың төбелерінде орналасуының әр түрлі тәсілдерінің жиыны болсын. Онда шыбындардың орналасу тәсілі бар, мұндағы 2 – (мұндағы ш – шыбын, б – бос төбе) жиынының элементтерінің саны.

а) Бесбұрыштың центрі бұрыштарға төрт рет бұрыла алады. Оларға мына алмастырулар сәйкес келеді:

1) (1, 2, 3, 4, 5)

2) (1, 3, 5, 2, 4)

3) (1, 4, 2, 5, 3)

4) (1, 5, 4, 3, 2)

ә) Дұрыс алтыбұрыштың төбелерін қарама-қарсы қабырғаларының орталарымен қосатын осьтерге қатысты бес симметрия болады. Оларға мына алмастырулар сәйкес келеді:

5) (1) (2, 5) (3, 4)

6) (2) (1, 3) (5, 4)

7) (3) (2, 4) (1, 5)

8) (4) (3, 5) (2, 1)

9) (5) (1, 4) (2, 3),

мұндағы 1, 2, 3, 4, 5 – бесбұрыштың төбелерін нөмірлеген сандар. (1)(2)(3)(4)(5) түріндегі тепе-тең алмастырумен бірге G тобының 10 элементін аламыз. Сонымен, G тобында мыналар бар:

<1, 1, 1, 1, 1> түріндегі 1 алмастыру,

<5> түріндегі 4 алмастыру,

<1, 2, 2> түріндегі 5 алмастыру.

Әрбір түрге қатысты алмастырулар үшін қозғалмайтын нүктелер санын анықтайық. Алмастыруда қозғалмайтын нүктелер болу үшін алмастырудағы циклдердің минималды саны екіге тең болу керек, себебі жиыны ш және б екі элементінен тұрады. Сондықтан, 1), 2), 3), 4) алмастырулардың қозғалмайтын нүктелері жоқ. Онда <1, 1, 1, 1, 1> түріндегі алмастыру үшін формула бойынша қозғалмайтын нүкте аламыз. <1, 2, 2> түріндегі әрбір алмастыру үшін көбейту принципі бойынша қозғалмайтын нүкте аламыз. Бернсайд леммасын қолданамыз: .

Сонымен, үш бірдей шыбын дұрыс бесбұрыштың төбелеріне екі әр түрлі геометриялық тәсілмен орналаса алады.

6-Есеп. Кубтың төбелерін екі түске (қызыл мен жасыл) әрбір түске боялған төбелер саны бірдей болатындай етіп неше тәсілмен бояуға болады?

Шешуі. Бұл есепті шығару үшін 1-есепті қолданамыз. М – кеңістіктегі орны бекітілген өлшемдері бірдей барынша әр түрлі боялған кубтардың жиыны болсын. Онда формуласы бойынша әр түрлі боялған кубтар санын аламыз. Төбелерді екі түске бояу қажет болғандықтан (4 – қызылға, 4 – көкке), онда алмастырудағы циклдердің минималды саны екіге тең болу керек. Сондықтан 1) – 24) барлық алмастыруларында (1-есеп) қозғалмайтын нүктелер болады. Нәтижесінде G тобында мыналар бар:

<1, 1, 1, 1, 1, 1, 1, 1> түріндегі 1 алмастыру,

<4, 4> түріндегі 6 алмастыру,

<2, 2, 2, 2> түріндегі 9 алмастыру,

<1, 1, 3, 3> түріндегі 8 алмастыру.

Онда <1, 1, 1, 1, 1, 1, 1, 1> түріндегі алмастыруында қозғалмайтын нүкте болады. <4, 4> түріндегі әрбір алмастыруда көбейту принципі бойынша қозғалмайтын нүкте бар. <2, 2, 2, 2> түріндегі әрбір алмастыруда көбейту принципі бойынша қозғалмайтын нүкте бар. <1, 1, 3, 3> түріндегі әрбір алмастыруда көбейту принципі бойынша қозғалмайтын нүкте бар. Бернсайд леммасы бойынша: .

Сонымен, екі түске боялған төбелер саны бірдей болатындай етіп кубтың төбелерін 7 тәсілмен бояуға болады.

7-Есеп. Әрбір кубтың бояуында барлық төрт түс кездесетіндей етіп кубтың жақтарын төрт түске қанша әр түрлі тәсілмен бояуға болады?

Шешуі. Бұл есепті шешу үшін 3-есепті пайдаланамыз. М – кеңістіктегі орны бекітілген өлшемдері бірдей барынша әр түрлі боялған кубтардың жиыны болсын. Онда көбейту принципі бойынша кубтың бірінші жағын 4 тәсілмен, екіншісін – үш, үшіншісін – екі, төртіншісін – бір, бесіншісін – төрт, алтыншысын – төрт тәсілмен бояуға болады. аламыз. Бояудың геометриялық әр түрлі тәсілдерін табайық. Ол үшін 3-есепте сипатталған кубтың айналуының G тобындағы алмастырулардың циклдардың көбейтіндісіне жіктелуді қолданамыз. Кубтың боялуында төрт әр түрлі түс болу керек болғандықтан, алмастырудағы циклдердің минималды саны төртке тең болу керек. Сондықтан 3-есептегі 1), 3), 4), 6), 7), 9) – 23) алмастыруларында қозғалмайтын нүктелер болмайды. Осылайша, қозғалмайтын нүктелерде <1, 1, 2, 2> түріндегі 3 алмастыру және <1, 1, 1, 1, 1, 1> түріндегі 1 алмастыру болады.Әрбір түрдегі алмастырулар үшін қозғалмайтын нүктелер санын анықтайық. <1, 1, 1, 1, 1, 1> түріндегі алмастыру үшін көбейту принципі бойынша қозғалмайтын нүктелерді аламыз. <1, 1, 2, 2> түріндегі алмастыру үшін көбейту принципі бойынша қозғалмайтын нүктелерді аламыз. Бернсайд леммасы бойынша шығады.

Сонымен, әрбір кубтың бояуында барлық төрт түс кездесетіндей етіп кубтың жақтарын төрт түске 19 әр түрлі тәсілмен бояуға болады.

§ 2. «Елеу әдісі» [4]

Санаудың жалпылама әдісімен танысайық, оны «елеу әдісі» немесе «комбинаторикалық елеу» деп атауға болады: P-ның кез келген қасиетін оның қандай да бір А жиынындағы бөлшектенуімен байланыстыруға болады, бұл кезде А жиыны екі бөлікке бөлінеді: Р-ның қасиеттеріне ие болатын элементтері бар А₁ ішкі жиыны және Р-ның қасиеттеріне ие болмайтын, яғни қасиетіне ие болатын элементтері бар А₂ ішкі жиыны. Қажетті қасиетті таңдай отырып тізбектелген елеу арқылы белгілі бір шектеулер қойылған ішкі жиындарды санап шығуға болады.

2.1. Кірістіру мен шығару формуласы

А – шекті жиын және болсын. ретінде А-ға қатысты қосымшасын, ал ретінде А-дағы элементтер санын белгілейік.

Онда

.

Егер мен , онда

(1)

.

1. формула ішкі жиындарының п жағдайына жалпыланатынын көрсетейік:

(2)

Индукцияны қолданайық. Берілгені

(3)

(2) формула ішкі жиындардың жағдайында орындалады деп болжам жасайық:

(4)

жиынының келесідей ішкі жиындарын қарастырайық:

(4) формула мен қолданып, алатынымыз:

(5)

(5) пен (4) формулаларды (3) формулаға қойып, (2) формуланы аламыз. Осылайша, (1) формуланы ескере отырып (2) формула индукция бойынша дәлелденді. Бұл формуланы кірістіру мен шығару формуласы деп атайды. Ол көп жағдайда мына түрде беріледі:

(6)

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

2.2. «Елеудің» немесе «електен өткізудің» жалпылама әдісі. Сильва – Сильвестр елегі

(6) формула санаудың тізбектелген үрдісін сипаттайды және ол Сильва – Сильвестр елегі деп аталады.

Мысал. Төмендегі жиынды

және келесідей қасиеттерді қарастырайық:

жұп сан,

және , (7)

және .

қасиетіне ие болатын А жиынының элементтерін санайық. қасиеттеріне сәйкес келетін ішкі жиындарды деп белгілейік. Онда

Әуелі А жиынын -ден «елеп алайық»: . Одан кейін -ді мен -тен елейміз: , . -ні -тен елейміз: Сонымен,

Алайда (6) формула ізделінді жиынның элементтер санын есептеуге мүмкіндік бермейді. Оны табу үшін , , тізбектей жазып аламыз. Әрине, элементтер саны аз жиын үшін ізделінді ішкі жиынды жазып алған ыңғайлы, бірақ элементтері көп жиын үшін бұны жасау қиынға соғады.

2.3. Елеудің жалпылама әдісін сандар теориясында қолдану

Теорема 1. мен жұп-жұппен өзара жай сандар болсын. k-ны бөлмейтін k бүтін сандардың саны мынаған тең:

(8)

Дәлелдеу. белгілеуін енгізіп, (2) формуланы жазайық:

(9)

Бұдан шығады:

,

,

(10)

∙ ∙ ∙ ∙ ∙ ∙ ∙ ∙ ∙ ∙ ∙ ∙ ∙ ∙ ∙ ∙ ∙ ∙ ∙ ∙ ∙ ∙ ∙ ∙ ∙ ∙ ∙ ∙ ∙ ∙ ∙ ∙ ∙ ∙ ∙ ∙ ∙ ∙

.

(10) формуланы (9) формулаға қойып, (8) формуланы аламыз.

Мысал. болсын.

35-тен аспайтын және 3-ке де, 7-ге де, 8-ге де бөлінбейтін бүтін сандардың саны мынаған тең:

Басқа қосымшаларды қарастырайық.

болатын бүтін k сандарының санын деп белгілеп, Эйлер функциясы деп атайды.

Теорема 2. болсын. Онда

, (11)

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

Дәлелдеу. Барлық п-ды бөлетіндіктен және өзара жай болғандықтан, мынаны аламыз:

= .

(8) формула бойынша

яғни (11) формуланы аламыз.

Мысал. болсын. 84-тің жай бөлгіштері 2, 3, 7 болады; сондықтан

Мёбиус функциясы. Төмендегідей түрде анықталатын Мёбиус функциясын қолданып (11) формуланы басқа түрде көрсетейік:

;

, егер п жай санның квадратына бөлінсе;

, егер – әр түрлі жай көбейткіштер болса, .

(11) теңдікті Мёбиус функциясын қолданып түрлендірейік:

Онда

, (12)

мұнда қосынды п-ді бөлетін барлық k үшін жүргізіледі (1-ді қоса алғанда).

Мысал. Берілгені

, , ,

, , ,

, , ,

, ,

болғанда (12) формула

береді.

Эратосфен елегі. жай сандарын санаудың тағы бір тәсілі белгілі: есептеледі және 2, 3, ..., п тізбегінен 2-ге бөлінетін сандар, одан кейін 3-ке бөлінетін сандар, ..., с-ға бөлінетін сандар сызылады. Қалған сандар ізделінді сандар болады.

2-теореманы қолданып келесідей формуланы алуға болады. Егер арқылы болатындай барлық q жай сандарының санын белгілесек, онда (8) формулаға сәйкес

(13)

болады, мұндағы – -нен аспайтын жай сандар (оң жақтағы -1 қосылады, себебі 1 саны жай санға жатпайды).

(12) формулаға сәйкес

(14)

мұнда қосынды п-нің барлық жай бөлгіштері бойынша есептеледі (1-ді қоса алғанда).

Мысал. 2, 3, ..., 84 сандарының ішінде қанша жай сан бар? аламыз. 2 мен 9-дың арасындағы жай сандар 2, 3, 5, 7 болады. (13) формулаға сәйкес

Осылайша, 2, 3, ..., 84 сандарының ішінде барлығы жай сан бар. Эратосфен елегі оларды есептейді: 2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83.

Бұл тақырыптың кеңейтілуі: кейде ішкі жиындар белгіленбейді де, осы элементтер ие болатын қасиеттер саны ғана көрсетіледі. Мұндай жағдай үшін (6) формуланы қолданып қажетті формуланы шығарып алуға болады.

§3. Фигураларды ең кіші диаметр бойынша бөліктерге бөлу [1, 2]

F фигурасының диаметрі деп біріншіден, F фигурасының кез келген M және N екі нүктесінің арақашықтығы d-дан аспайтын, екіншіден, F фигурасында арақашықтығы d-ға тең болатын А мен В нүктелерінің ең болмағанда бір жұбы табылатындай d қашықтығын атаймыз.

Мысалдар:

• Егер F фигурасы шеңбердің l доғасымен және а хордасымен шектелген сегменті болса, онда l доғасы жарты шеңберден аспайтын жағдайда F фигурасының диаметрі а-ға тең болады; ал l доғасы жарты шеңберден артық болған жағдайда F фигурасының диаметрі шеңбердің диаметрімен беттеседі.

• Егер F фигурасы көпбұрыш болса, онда оның диаметрі төбелерінің арақашықтықтарының ең үлкеніне тең болады.

Фигурада арақашықтығы d-ға тең болатын бірнеше нүктелердің жұптары болуы мүмкін: эллипстің жағдайында мұндай нүктелер жұбы – біреу, квадратта – екеу, дұрыс үшбұрышта – үшеу, шеңберде – шексіз көп.

Есеп: d диаметрлі шеңберді әрқайсысының диаметрі d-дан кем болатындай екі бөлікке бөлуге болмайды, бірақ үш бөлікке бөлуге болады (4-сурет (а, ә)).

Error: Reference source not found

Дәл осындай қасиетке қабырғасы d-ға тең болатын тең қабырғалы үшбұрыш та ие болады. Бірақ кіші диаметр бойынша екі бөлікке бөлуге болатын фигуралар да кездеседі (5-сурет (а, ә)).

Error: Reference source not found

Кез келген F фигурасы үшін оны кіші диаметр бойынша бөліктерге бөлуге берілген есепті қарастыра аламыз. Бұл үшін қажетті бөліктердің ең кіші мәнін арқылы белгілейік. Егер F – шеңбер немесе тең қабырғалы үшбұрыш болса, онда , ал эллипс пен параллелограмм үшін . Мынадай сұрақ туындайды: болатындай жазық фигураны табуға болады ма, яғни оны кіші диаметр бойынша бөліктерге бөлу үшін үш бөлік емес, 4 немесе бұдан да көп бөліктер қажет болатын фигура табылады ма?

Жауапты Борсук теоремасы береді: d диаметрлі кез келген жазық F фигурасын диаметрі d-дан кем болатын үш бөлікке бөлуге болады, яғни .

Лемма: d диаметрлі кез келген жазық фигураны параллель қабырғаларының арақашықтығы d-ға тең дұрыс алтыбұрыштың ішіне алуға болады.

Лемманың дәлелдеуі.

F фигурасына бір-біріне параллель және тіреуіш түзулерін жүргізейік. Фигура арақашықтығы d-дан аспайтын (себебі F фигурасының диаметрі d-ға тең) және түзулерінің арасында орналасады (6-сурет). F фигурасына түзуімен бұрыш жасайтын және бір-біріне параллель орналасқан және тіреуіш түзулерін жүргізейік. түзулері бұрышы болатын және биіктіктері d-дан аспайтын ABCD параллелограмын құрайды және F фигурасы осы параллелограмның ішінде орналасады. F фигурасына түзуімен бұрыш жасайтын және тіреуіш түзулерін жүргізейік және параллелограмның АС диагоналінің ұштарынан осы түзулерге перпендикулярлар жүргізіп, перпендикулярлардың табандарын M және N арқылы белгілейік (6-сурет). теңдігі орындалатындай етіп түзуінің бағытын таңдауға болатынын көрсетейік. Айталық, және болсын. Осылайша, шамасы теріс сан болады. түзуі -қа айналатындай етіп бағытын үздіксіз өзгерте берейік (F фигурасын қозғалыссыз қалдырамыз). түзуімен бірге түзулері де өздерінің бағыттарын өзгертеді (себебі олардың орналасуы түзуіне байланысты). Сондықтан, түзуі бұрылған кезде A, C, M, N нүктелері де қозғала бастайды, демек, шамасы да үздіксіз өзгеріп тұрады.

Error: Reference source not found

Бірақ түзуі -қа бұрылған кезде, ол бұрын түзуі орналасқан жерге орналасады. Сондықтан біз 6-суретте бейнеленген параллелограмды қайтадан алатын боламыз, бірақ бұл параллелограмда A мен С, сондай-ақ M мен N нүктелері «рөлдерін» ауыстыратын болады. Демек, бұл жағдайда у шамасы енді оң таңбалы болады.

Error: Reference source not found

Егер түзуінің -тан -қа дейін бұрылу кезіндегі у шамасының өзгеру графигін салсақ (7-сурет), онда у шамасы нөлге айналатындай түзуінің орналасуы табылатынын, яғни теңдігі орындалатынын көреміз (себебі теріс мәннен оң мәнге үздіксіз өзгеру барысында у шамасы қандай да бір мезгілде нөлге айналуы тиіс). Біз у шамасы нөлге айналатын кездегі барлық түзулердің орналасуын қарастырамыз (8-сурет). теңдігінен түзулерінен құралған алтыбұрыш центріне қатысты симметриялы болатыны шығады.

Error: Reference source not found

Бұл алтыбұрыштың әрбір бұрышы -қа тең, ал қарама-қарсы қабырғаларының арақашықтығы d-дан аспайды. Егер мен түзулерінің арақашықтығы d-дан кем болса, онда біз бұл түзулердің арасын арақашықтығы d-ға тең болатындай етіп ашамыз (оларды бірдей қашықтыққа ысырамыз). Дәл осылай түзулерімен, одан кейін түзулерімен жасаймыз. Нәтижесінде қарама-қарсы қабырғаларының арақашықтығы d-ға тең болатын центріне қатысты симметриялы алтыбұрыш (бұрыштары ) аламыз. Айтылғандардың бәрінен бұл алтыбұрыштың қабырғалары өзара тең екені көрініп тұр, яғни бұл алтыбұрыш – дұрыс, ал F фигурасы алтыбұрыштың ішінде орналасқан.

Борсук теоремасының дәлелдеуі. F – d диаметрі фигура болсын. Дәлелденген леммаға сәйкес F фигурасы қарама-қарсы қабырғаларының арақашықтығы d-ға тең болатын дұрыс алтыбұрыштың ішінде орналасады. Бұл дұрыс алтыбұрышты диаметрлері d-дан кем болатын үш бөлікке бөлуге болатынын көрсетейік. Бұл кезде F фигурасы да диаметрлері d-дан кем болатын үш бөлікке бөлінеді. Дұрыс алтыбұрышты үш бөлікке бөлу нәтижесі 9-суретте көрсетілген (P, Q, R нүктелері қабырғаларының ортасы, ал О – алтыбұрыштың центрі болады). Бөліктердің диаметрлері d-дан кем екеніне көз жеткізу үшін PQL үшбұрышында Q бұрышы тік бұрыш екенін, сондықтан екенін байқау жеткілікті. Осылайша, теорема дәлелденді.

Теореманың дәлелдеуінен d диаметрлі кез келген жазық фигураны диаметрлері (себебі ) (9-сурет) аспайтын үш бөлікке бөлуге болады деген қорытынды шығаруға болады. Бөліктердің диаметрлерін осылайша бағалау ең тиімді болып табылады, себебі d диаметрлі шеңберді диаметрлері -ден кем болатындай етіп үш бөлікке бөлуге мүмкін емес (диаметрі -ден кем болатын бөлік шеңберден -тан кем доғада орналасқан жиынды кесіп алады, сондықтан мұндай үш бөлік шеңберді толық жаба алмайды).

Бұл сұрақ жөнінде келесідей кеңейтулерді ұсынуға болады:

Борсук теоремасы бұл сұрақтың негізі болып табылады, бірақ ол d диаметрлі кез келген F фигурасының нешеге тең деген сұраққа толық жауап бермейді. Теорема -ке тек қана жоғарыдан баға береді: . Сонымен қатар кез келген фигура үшін екені анық. Осы жерде мәселе туындайды: қандай жазық фигуралар үшін екіге тең және қандай фигуралар үшін ол үшке тең.

Дөңес фигураларды гомотетикалық жабу туралы есепті (F фигурасын толықтай жабуға мүмкіндік беретін F фигурасының «кішірейтілген көшірмелерінің» ең аз саны туралы) және F фигурасының шекарасын сәулелейтін бағыттардың ең аз саны туралы есепті қарастыруға болады.

Осы барлық есептерді кеңістіктегі фигураларға қарастыруға болады.

§4. «Сәтті билеттер» [5]

Билетті сәтті деп атайық, егер оның нөмірінің алғашқы үш цифрының қосындысы соңғы үш цифрының қосындысына тең болса (алты таңбалы нөмірлер үшін). Осы жерде сұрақ туындайды: барлығы қанша сәтті билет бар?

Барлық сәтті билеттерді алғашқы үш цифрдың қосындысы тең болатын топтарға бөлейік. Бұл қосынды 0-ден (000 цифрларының үштігі үшін) 27-ге дейінгі (999 цифрларының үштігі үшін) мәндерді қабылдауы мүмкін. Сондықтан топтар саны 28 болады. Цифрларының қосындысы п болатын әр түрлі үштіктердің санын деп белгілейік. -нің алғашқы бірнеше мәнін табу қиын емес:

• (қосындысы 0 болатын 000 бір ғана үштігі бар);

• (қосындысы 1 болатын 001, 010, 100 үш үштік бар);

• (002, 020, 200, 011, 101, 110 үштіктері).

Алғашқы үш цифрларының қосындысы п болатын сәтті билеттер саны – (сәтті билеттің басына да, соңына да қосындысы п болатын цифрларының кез келген үштігін қоюға болады). Осылайша, сәтті билеттердің санын анықтау үшін сандарын анықтап, одан кейін осы 28 санның квадраттарының қосындысын табу жеткілікті.

мәндерін анықтау үшін цифрларының қосындысы п болатын біртаңбалы және екітаңбалы сандарды есептейік. Әрбір үшін цифрларының қосындысы п болатын бір ғана біртаңбалы сан бар (бұл санның жазылуы п санының жазылуымен бірдей болады). Біртаңбалы сандарды көпмүшесімен сипаттайық. Бұл көпмүшенің мәні мынадай: көпмүшесіндегі коэффициенті цифрларының қосындысы п болатын біртаңбалы сандардың санына тең. Басқаша айтқанда, көпмүшесіндегі коэффициенті 1-ге тең, егер және 0-ге тең, егер болса.

Екітаңбалы сандарды сипаттайтн көпмүшесін жазайық. көпмүшесіндегі коэффициенті цифрларының қосындысы п болатын екітаңбалы сандардың санына тең. (Бірінші немесе екі цифры да нөлге тең бола алатын екітаңбалы сандарды да қарастырамыз). көпмүшесінің дәрежесі 18-ге тең (бұл – екітаңбалы санның цифрларының қосындысының ең үлкен мүмкін мәні): .

Ұсыныс 1. .

Дәлелдеу. және мономдарының көбейтіндісі көпмүшесінің мономының коэффициентіне салым жасайды сонда және тек қана сонда, егер болса. Сондықтан, көпмүшесінің мономының коэффициенті п санын қосындысы түрінде көрсету тәсілдерінің саны болып табылады. Осылайша, теңдіктің оң жағындағы көпмүше көпмүшесімен сәйкес келеді.

көпмүшесін жазайық.

Ұсыныс 2. .

Дәлелдеу. көпмүшесінің мономының коэффициенті п санын үш цифрдың қосындысы түрінде көрсету санына тең.

Сонымен, сәтті билеттер саны туралы есеп мынаған әкелді: санын - көпмүшесінің коэффициенттерінің квадраттарының қосындысын есептеу керек. көпмүшесіне көбейту – өте қарапайым амал. Бірақ біз математикалық анализ аппаратын қолданамыз.

Көпмүшедегі s-тің орнына өрнегін қояйық. Онда – 27 дәрежелі тригонометриялық полином болады:

.

екенін пайдаланып,

_{аламыз.}

Геометриялық прогрессияның қосындысын тауып және

екенін пайдаланып,

аламыз, бұдан ізделінді шама

(15)

тең болады.

(15) интегралының мәнін бағалауға тырысайық. функциясының кесіндісіндегі графигі мына түрде болады:

Error: Reference source not found

Нөлде функция өзінің максимумына жетеді, ол 10-ға тең. кесіндісінің сыртында f функциясының мәні -тен аспайды. Сондықтан (15) интегралындағы кесіндісіне қосымша салым аспайды (шын мәнінде ол әлдеқайда аз). (15) интегралдың негізгі бөлігі кесіндісінде шоғырланған. Бұл кесіндінің салымын анықтау үшін тұрақты фаза әдісін қолданамыз. Бұл әдіс болғандағы интегралының мәнін анықтауға мүмкіндік береді. t-ның үлкен мәндерінде интегралдың мәні функциясының («фаза») өзінің тұрақты 0 нүктесінің ( болатын нүктесінде) аумағындағы түріне қатысты анықталады. Нөлдің аумағында , ал .

t-ның үлкен мәндерінде

аламыз.

деп алып және (15) формуланы қолданып жуық мәнін аламыз. Алынған нәтиже ізделінді мәнді жақсы дәлдікпен (ауытқушылық 3% артық емес) жақындатады.

Қарастырылған мысалдың негізінде комбинаторикалық есептер және оларды шешу әдістері туралы кейбір қорытындылар жасауға болады. Санау комбинаторикасының есептері шекті жиындардың қандай да бір тобына жататын объектілер санын есептеуден тұрады. Топтың әрбір жиынында өзіндік нөмірі бар (сәтті билеттер туралы есепте мұндай нөмір үштаңбалы санның цифрларының қосындысы болды).

Әдетте, санау комбинаторикасының есебі «түптеп келгенде» шешіледі: топтың әрбір жиыны үшін оның барлық элементін жазып шығып, осылайша олардың санын анықтауға болады. Мәселе мынада: зерттелетін жиындардың барлық элементтерін жазуды талап етпейтін «жақсы» шешім табу. Ал «жақсы» шешімнің не екенін анықтау қиынға соғады.

Санау комбинаторикасының есептерін шығару барысында жасаушы көпмүшелерді қарастырған өте тиімді болады. Біздің жағдайымызда жасаушы көпмүше пайда әкелді. Комбинаторикалық объектілермен жасалатын амалдар жасаушы функциялардың терминдерінде өте жақсы сипатталады. Осылайша, цифрларының қосындысы берілген біртаңбалы сандардан үштаңбалы сандарға өту үрдісі жай ғана жасаушы көпмүшесін кубқа шығарудан тұрды. Математиканың бір-бірімен байланысты бөлімдерінен (мысалы, анализден) әдістерді пайдалану санау есебіне басқаша қарауға және оны шешудің жаңаша, әрі тосын тәсілдерді табуға мүмкіндік береді.

Библиографиялық тізім

1. Болтянский, В.Г. Теоремы и задачи комбинаторной геометрии [Текст] / В.Г. Болтянский, И.Ц. Гохберг // – М.: Наука, 1965.

2. Болтянский, В.Г. Разбиение фигур на меньшие части [Текст] / В.Г. Болтянский, И.Ц. Гохберг // – М.: Наука, 1971.

3. Калужнин, Л.А. Преобразования и перестановки [Текст] / Л.А. Калужнин, В.И. Сущанский // – М.: Наука, 1979.

4. Кофман, А. Развитие методов пересчета [Текст] / А. Кофман // Введение в прикладную комбинаторику – М.: Наука, 1975. – с. 60–73.

5. Ландо, С.К. Счастливые билеты [Текст] // Математическое просвещение, сер. 3, вып. 2. – М.: Просвещение, 1998. – с. 127–132.