Формула ввода-вывода. Методы и правила, которые часто используются в комбинаторике

Формула ввода-вывода.
Методы и правила, которые часто используются в комбинаторике.
В комбинаторике и теории графов часто используется метод математической индукции, который является одним из эффективных методов доказательства утверждений. Это две последовательно выполняемые части метода, которые основаны на следующей общей идее.
Предположим, утверждение, которое необходимо доказать, верно для некоторого собственного значения (например, ) (эта часть метода называется базой или базой). Если из того, что это утверждение верно для любого , следует, что оно верно для него, то утверждение верно для любого натурального числа (индукционный переход).
Пример 2. Для любого натурального числа :

докажем с помощью метода математической индукции, что равенство уместно.
База: пусть , тогда очевидно, что приведенное выше равенство верно: .
Индукционный переход: верно для равенства, которое должно быть доказано, т. е.

Это делается путем добавления выражения к левой и правой сторонам равенства

Справа от последнего равенства выполняем преобразование следующим образом:


.
Значит:
.
Последнее отношение-это случай равенства, которое необходимо доказать.
Важно отметить, что когда для доказательства утверждения используется метод математической индукции, важно проверить обе части этого метода, то есть базовый и индукционный переходы обязательно должны быть проверены. Неправильные результаты также могут быть получены, если один из них не проверен. Кроме того, даже когда база проверяется на наличие более чем одного частного значения, даже для очень многих частных случаев, и получен положительный результат, итоговое утверждение, обобщающее эти случаи, может оказаться неверным. Приведенные ниже примеры показывают, что эти соображения уместны.
3- misol. “Ixtiyoriy natural son uchun son 2ga qoldiqsiz bo‘linadi” degan tasdiqni tekshirishda matematik induksiya usulining baza qismi talabini bajarmasdan faqat induksion o‘tishni tekshiramiz.
Bu tasdiq uchun to‘g‘ri bo‘lsin, ja’ni son 2ga qoldiqsiz bo‘linsin deb faraz qilamiz. U holda son ham, qo‘shiuvchilarining har biri 2ga qoldiqsiz bo‘linganligi sababli, 2ga qoldiqsiz bo‘linadi. Shuning uchun tenglik asosida son 2ga qoldiqsiz bo‘linadi degan xulosa kelib chiqadi. Demak, yuqoridagi tasdiq uchun to‘g‘ri, ya’ni induksion o‘tish bajarildi deb hisoblash mumkin.
Shunday qilib, matematik induksiya usulining baza qismini tekshirmasdan “ixtiyoriy natural son uchun son 2ga qoldiqsiz bo‘linadi” degan xulosa qilish noto‘g‘ridir, chunki ixtiyoriy natural son uchun sonni 2ga bo‘lganda 1 qoldiq qoladi.
4- misol. “Ixtiyoriy natural son uchun ifodaning qiymati tub sondir” degan tasdiqni tekshirish maqsadida matematik induksiya usulining faqat baza qismi talabini dastlabki 15ta natural sonlar uchun bajaramiz.
bo‘lganda tub son hosil bo‘ladi. bo‘lganda ham ifodaning qiymati sifatida 23, 29, 37, 47, 59, 73, 89, 107, 127, 149, 173, 199, 227 va 257 tub sonlarni hosil qilamiz.
Induksion o‘tishni tekshirmasdan “ixtiyoriy natural son uchun ifodaning qiymati tub sondir” degan xulosa qilish noto‘g‘ridir, chunki, masalan, agar bo‘lsa, u holda bu ifodaning qiymati murakkab sondir: .
5- misol. Biror natural son uchun son butun sonning kvadrati bo‘ladimi? Bu savolga javob berish uchun, ning dastlabki o‘n, yuz, ming, million, milliard, hattoki, trillionta qiymatlari uchun ifoda tekshirilganda, uning qiymatlaridan birortasi ham butun son kvadrati bo‘lmasligi qayd etilgan. Shunday bo‘lishiga qaramasdan bu tasdiq asosida, induksion o‘tishni bajarmasdan, “ixtiyoriy natural son uchun ifodaning qiymati butun sonning kvadrati bo‘lmaydi” degan xulosa qilish mumkin emas. ifodaning qiymati butun sonning kvadrati bo‘ladigan natural sonning borligi va bunday sonning eng kichigini o‘nli sanoq sistemasida yozganda 29ta (!) raqam bilan ifodala-nishi komp’yuter yordamida aniqlangan ([34]ga qarang).
В качестве другого примера применения метода математической индукции докажем следующую теорему.
1-теорема. Для любого конечного множества справедливо равенство .
Доказательство. Применяем метод математической индукции к мощности данного множества.
База. Сначала мы покажем, что доказательство теоремы выполняется, когда количество элементов множества равно нулю, т. е. когда. пусть будет . Тогда для, и будет. Следовательно, это верно для случая , , когда есть подтверждение теоремы.
Induksion o‘tish. Chekli elementli ixtiyoriy to‘plam uchun teoremaning tasdig‘i to‘g‘ri bo‘lsin, ya’ni bo‘lganda tenglik bajarilsin. elementli to‘plamni qaraymiz. Ravshanki, uchun bo‘ladi. Qaralayotgan to‘plamning ixtiyoriy elementi uchun bulean to‘plamni o‘zaro kesishmaydigan ikkita va to‘plamlar birlashmasi sifatida yozish mumkin. Demak, .
Tuzilishiga ko‘ra, to‘plam elementli to‘plamning buleanidan iborat. Shuning uchun, induksion o‘tish faraziga ko‘ra bo‘ladi. to‘plam esa to‘plamning har bir element-to‘plamiga elementni kiritish yordamida hosil qilingan. Bundan kelib chiqadi. Demak, bo‘lgan hol uchun
.
Berilgan chekli to‘plamning buleani uning barcha qism to‘lamlaridan tuzilgan toplam bo‘lgani sababli 1- teoremada isbotlangan tenglik to‘plamning buleanini ko‘rinishda belgilashga asos bo‘la oladi.
В комбинаторике есть простые, самоочевидные, но важные правила. В качестве таких правил можно указать правила сложения, умножения, а также так называемые правила вставки и вычитания.
Дано множество состоящая из элементов и множество состоящая из элементов, пусть они не пересекаются. Согласно правилу сложения, или количество вариантов выбора одного элемента, который будет принадлежать набору, равно ( ). Содержание этого правила, также известного как правило "или", также может быть выражено с помощью следующей теоремы.
2- теорема. Если для конечных множеств и , тогда .
Следовательно, согласно правилу сложения, мощность объединения двух непересекающихся множеств равна сумме мощностьи этих множеств.
По правилу умножения, множество состоящая из элементов и множество состоящая из элементов, пусть они не пересекаются, количество всех ( , ) кортежей (пар), которые могут быть составлены из элементов множеств, равно . Это правило также известно как правило "и". Его также можно выразить в виде следующей теоремы.
3-теорема. Для любых конечных и множеств справедливо равенство .
Следовательно, согласно правилу умножения, мощность декартова любых двух конечных множеств равна произведению мощностьи этих множеств.
В общем случае, если конечные и множества имеют хотя бы один общий элемент, то при определении значения суммы приходится учитывать некоторые элементы множества, а точнее, элементы множества дважды. На основании этого рассуждения мы приходим к следующему утверждению.
4-теорема. Для любых конечных и множеств справедливо равенство .
Доказательство. Легко увидеть, что:
a) и ;
b) и .
Bu munosabatlarga 2- teoremani qo‘llasak, mos ravishda va tengliklarni hosil qilamiz. Bu tengliklardan isbotlanishi kerak bo‘lgan tenglikni hosil qilish qiyin emas.
4- teoremaning tasdig‘ini umumiy holda ikkita chekli to‘plamlar birlashmasining quvvatini hisoblash qoidasi deyish mumkin. Bu qoidaning ma’nosidan kelib chiqqan holda, uni kiritish va chiqarish qoidasi deb atash qabul qilingan.
Ravshanki, 4- teoremada keltirilgan tenglikdan foydalanib , , va miqdorlarning ixtiyoriy uchtasi ma‘lum bo‘lganda to‘rtinchisini hisoblash formulasini hosil qilish mumkin.
Yuqorida bayon qilingan ikkita to‘plam uchun qo‘shish, ko‘paytirish hamda kiritish va chiqarish qoidalarini chekli sondagi istalgan chekli to‘plamlar uchun umumlashtirish mumkin.
Avvalo, kiritish va chiqarish qoidasining umumlasmasi sifatida quyidagi teoremani keltiramiz.
5- teorema (umumlashgan kiritish va chiqarish qoidasi). Ixtiyoriy chekli to‘plamlar uchun

.
munosabat o‘rinlidir.

Isboti. Teoremani isbotlash uchun matematik induksiya usulini qo‘llaymiz. bo‘lgan hol uchun teoremaning tasdig‘i trivialdir.
Induksiya usulining bazasi sifatida bo‘lgan holni qaraymiz. Bu holda teoremaning tasdig‘i 3- teoremaga asosan to‘g‘ri.
Induksion o‘tish: teoremaning tasdig‘i uchun to‘g‘ri, ya’ni




tenglik o‘rinli bo‘lsin. Tasdiqning bo‘lgan holda to‘g‘ri ekanligini ko‘rsatamiz. Avvalo, to‘plamlarning birlashmasini ko‘rinishda ifodalaymiz. So‘ngra 3- teoremani va kesishmaga nisbatan umumlashgan distributivlik qonunini qo‘llab hamda teorema tasdig‘ining uchun to‘g‘riligini hisobga olib, quyidagilarga ega bo‘lamiz:




.
Bu ifodadagi oxirgi ayriluvchi ( ) ko‘rinishdagi ta to‘plamlar birlashmasining quvvatini ifodalaydi. Shuning uchun, induksiya faraziga ko‘ra, bu ayriluvchini quyidagicha yozish mumkin:











.
Bu ifodani o‘z o‘rniga qo‘yib




tenglikni hosil qilamiz.
6- teorema (umumlashgan qo‘shish qoidasi). Juft-jufti bilan kesishmaydigan ixtiyoriy chekli to‘plamlar uchun

tenglik o‘rinlidir.
Isboti. Teorema shartiga ko‘ra barcha , , indekslar uchun bo‘lgani sababli 5- teorema asosida kerakli tenglikni hosil qilamiz.
7- teorema. Ixtiyoriy chekli to‘plamlar uchun



.
munosabat o‘rinlidir.
Isboti o‘quvchiga havola qilinadi.
8- teorema (umumlashgan ko‘paytirish qoidasi). Elementlari soni mos ravishda bo‘lgan to‘plamlardan faqat bittadan element olib tuzilgan uzunlikka ega kortejlar soni ga tengdir.
Isboti. Teoremani isbotlash uchun matematik induksiya usulini qo‘llaymiz. bo‘lgan hol uchun teoremaning tasdig‘i trivialdir.
Induksiya usulining bazasi sifatida bo‘lgan holni qaraymiz. Bu holda teoremaning tasdig‘i yuqorida keltirilgan ikkita to‘plam uchun ko‘paytirish qoidasidan kelib chiqadi.
Induksion o‘tish: teoremaning tasdig‘i ( ) uchun to‘g‘ri bo‘lsin, ya’ni, to‘plamlardan faqat bittadan element olib tuzilgan uzunlikdagi kortejlar soni bo‘lsin deb faraz qilamiz. Teorema tasdig‘ining uchun ham to‘g‘ri ekanligini ko‘rsatamiz.
to‘plamlardan faqat bittadan element olib uzunligi ( )ga teng bo‘lgan kortejlar sonini aniqlash uchun turlicha usullardan foydalanish mumkin. Bu yerda quyidagi usul bilan kerakli natijani olsa bo‘ladi. Dastlab uzunligi birga teng bo‘lgan kortejlarni tuzamiz. Uzunligi birga teng bo‘lgan kortejlar berilgan to‘plamlarning ixtiyoriy biridan faqat bitta elementni tanlash yordamida tuzilishi ravshan. Tabiiyki, agar uzunligi birga teng kortejlar to‘plamning elementlaridan tuzilsa, bunday kortejlar soni ga tengdir.
Uzunligi birga teng kortejlardan ixtiyoriy birini, masalan, ni olib, uning o‘ng tomoniga to‘plamdan boshqa biror to‘plamning, masalan, to‘plamning elementlaridan birini joylashtirib, birinchi koordinatasi bo‘lgan uzunligi ikkiga teng ta kortejlar hosil qilamiz. Uzunligi birga teng kortej sifatida ta kortejlardan ixtiyoriy birini olish mumkinligini hisobga olib, hammasi bo‘lib uzunligi ikkiga teng ta kortejlarga ega bo‘lamiz.
Uzunligi ikkiga teng kortejlarning har biriga o‘ng tomondan va to‘plamlardan boshqa biror to‘plamning, masalan, to‘plamning ta elementlaridan birini joylashtirib, uzunligi uchga teng ta kortejlar hosil qilamiz. Bu yerda uzunligi ikkiga teng kortej sifatida ta kortejlardan ixtiyoriy birini olish mumkinligini e’tiborga olib, uzunligi uchga teng ta kortejlarni hosil qilamiz.
Kortejlar hosil qilish jarayonini yuqoridagiga o‘xshash mulohazalar bilan davom ettirib, bu kortejlarning har biriga o‘ng tomondan to‘plamlardan boshqa to‘plamning ta elementlaridan birini joylashtirib, uzunligi ga teng bo‘lgan ta kortejlar hosil qilamiz. Bu yerda ham uzunligi ga teng kortej sifatida ta kortejlardan ixtiyoriy birini olish mumkinligini e’tiborga olamiz. Shunday qilib, marta ta kortej hosil bo‘ldi. Demak, uzunligi ga teng bo‘lgan kortejlar tadir.