1-teorema. Takrorli o‘rin almashtirishlar soni uchun formula o’rinlidir, bu yerda – elementlar soni, k – turlar soni. Isboti

elementlar bo’lsin, bu yerda , ,… – hech bo’lmaganda bittasi 1dan farqli natural sonlar. Bu n ta elementlarning o’rinlarini imkoniyati boricha almashtirishlar natijasida hosil bo’lgan kortejlar (kombinatsiyalar) takrorlanuvchi elementlar qatnashgan o‘rin almashtirishlar (qisqacha, takrorli o‘rin almashtirishlar) deb ataladi.

n ta elementlari orasida ta birinchi tur, ta ikkinchi tur, va hokazo, ta k-tur bir xil elementlar bo’lgan takrorli o’rin almashtirishlar sonini bilan belgilaymiz.

1-teorema. Takrorli o‘rin almashtirishlar soni uchun

formula o’rinlidir, bu yerda – elementlar soni, k – turlar soni.

Isboti . Har bir o’rin almashtirishdagi elementlar soni ga teng. Bu n ta elementlarni quyidagi tartibda joylashtirib, o’rin almashtirishlardan birini qaraymiz: birinchi bo’lib barcha ta birinchi tur, ulardan keyin barcha ta ikkinchi tur, va
asos bo’ldi.
Kyonisberg shaxridagi Pregel daryosi ustiga qurilgan ettita ko’prik o’sha vaqtda shaxarni to’rtta qismga ajratgan. Shaxarning ixtiyoriy qismida joylashgan uydan chiqib ettita ko’rikdan faqat bir martadan o’tib, yana o’sha uyga qaytib kelish mumkinmi? Kyonisberg ko’priklari haqidagi bu masalani hal qilish jarayonida graflarda maxsus marshrut (hozirgi vaqtda graflar nazariyasida bu marshrut Eyler tsikli nomi bilan yuritiladi) mavjudligi shartlari ham topildi. L.Eyler tomonidan e’lon qilingan tarixiy ilmiy ish yuz yildan kshproq vaqt mobaynida graflar nazariyasi bo’yicha yagona ilmiy ish bo’lib keldi.
XIX asrning o’rtalarida graflar nazariyasi bilan bog’liq tadqiqotlar G.Kirxgof (1924–1887, olmon fizigi) va A.Keli (1821–1895, ingliz matematigi) ishlaarida paydo bo’ldi.
“Graf” iborasi D.Kyonig (1884–1944, venger matematigi) tomonidan 1936– yilda graflar nazariyasiga bag’ishlangan dastlabki darsliklarda uchraydi.
Graflar nazariyasi bo’yicha tadqiqotlar natijalari inson faoliyatining turli sohalarida qo’llaniladi. Ulardan ba’zilari quyidagilar: boshqotirmalarni hal qilish; qiziqarli o’yinlar; yo’llar, elektr zanjirlari, integral sxemalari va boshqarish sistemalarini loyihalashtirishva hakazo.