1. To’plam va ular ustida amallar

10Fibonachchi sonlari. Bo’laklar kombinatorikasi
 
Fibonachchi sonlarining ta 'rifi. Elementlari haqiqiy son-
lardan iborat bo'lgan 
J/p 1*2, Wj,...,U
n
,... 
ketma-ketlikni qaraymiz. Bu ketma-ketlikdagi elementlarning 
uchinchisidan boshlab, har biri o'zidan oldingi ikkita elementning 
yig'indisiga teng, ya'ni u
n
—u
nl
+u
n2
 (n >3) bo'lsin. Ravshanki, bu 
ketma-ketlikni tashkil qilishda uning dastlabki ikkita hadi muhim 
bo'lib, keyingi barcha hadlari rekurrent
2
tenglik vositasida aniqlanadi. 
u=u
2
=l bo'lganda yuqorida keltirilgan ketma-ketlik Fibonachchi 
qatori, uning hadlari esa Fibonachchi sonlari, deb ataladi. 
Tabiiyki, Fibonachchi qatoridagi Fibonachchi sonlarini aniq-
lash jarayoni cheksizdir. Fibonachchi sonlarining dastlabki 24 tasi 
quyida keltirilgan: 
1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610, 987, 1597, 
2584, 4181, 6765, 10946, 17711, 28657, 46368. 
«Fibonachchi sonlari» iborasi birinchi bo'lib, XIX asrda Eduard 
Lyuka
3
tomonidan qiziqarli matematikaga bag'ishlab yozilganasarua 
qo'llanilgan. Fibonachchi (bu italyancha «filius Bonacci» so'zlaridan 
qisqartirilib tuzilgan bo'lib, Bonachchining o'g'li ma'nosini anglatadi) 
Italiyadagi Piza shahrida XII—XIII asrlarda yashagan Leonardo 
Pizanskiyning boshqacha ismidir (laqabidir). Bonachchi Italiya va 
Jazoirda savdo-sotiq bilan shug'ullangan.
7.
 Paskal uchburchagi. 
Paskal uchburchagi quyidagi jadval ko’rinishida bo’ladi: birinchi 
qator birinchi pozitsiyalarda ikkita birdan tashkil topadi, har bir 
navbatdagisi esa birinchi pozitsiyada bir, boshqalarida esa oldingi 
qatordagi mazkur va oldingi pozitsiyalardagi elementlar yig’indisi 
yordamida hisoblanadi. Oxirgi elementi ham bir ga teng. Shunday 
qilib quyidagi uchburchak hosil qilinadi 
Kiruvchi ma'lumotlar: 
INPUT.TXT kirish faylining yagona satrida bitta butun son, N(1 ≤ N 
≤ 109) soni kiritiladi 
Chiquvchi ma'lumotlar: 
OUTPUT.TXT chiqish faylida Paskal uchburchagining dastlabki N 
ta satrida jami nechta juft son mavjudligini chop eting. 
Ta’rif sifatida deb qabul qilinsa va bu son yuqoridagi jadvalning 
raqamli qatoridan oldin raqamli qatori sifatida joylashtirilsa, 
uchburchak figurasiga o‘xshash 1- shakldagi sonlar jadvalini hosil 
qilish mumkin. 
1- shakl 
1- shakldagi sonlar jadvali Paskal uchburchagi deb ataladi. Bu jadval 
arifmetik uchburchak nomi bilan ham yuritiladi. Uning Paskal nomi 
bilan atalishiga qaramasdan, bunday sonlar jadvali juda qadimdan 
dunyoning turli mintaqalarida, jumladan, sharq mamlakatlarida ham 
ma’lum bo‘lgan. Masalan, Erondagi Tus shahrida (hozirgi 
Mashhadda) yashab ijod qilgan Nosir at-Tusiy1 XIII asrda bu 
jadvaldan foydalanib, berilgan ikkita son yig‘indisining natural 
darajasini hisoblash usulini o‘zining ilmiy ishlarida keltirgan bo‘lsa, 
g‘arbda Al-Kashi nomi bilan mashhur Samarqandlik olim Ali 
Qushchi2 butun sonning istalgan natural ko‘rsatkichli arifmetik ildizi 
qiymatini taqribiy hisoblashda bu jadvaldan foydalana bilganligi 
haqida ma’lumotlar bor. Keyinchalik G‘arbiy Yevropada bu sonlar 
uchburchagi haqida M. Shtifel3 arifmetika bo‘yicha qo‘llanmalarida 
yozgan va u ham butun sondan istalgan natural ko‘rsatkichli 
arifmetik ildizning taqribiy qiymatini hisoblashda bu uchburchakdan 
foydalana bilgan. 1556 yilda bu sonlar jadvali bilan N. Tartalya4, 
keyinroq logarifmik lineyka ijodkori U. Otred5 (1631 yil) ham 
shug‘ullanganlar. 1654 yilga kelib B. Paskal o‘zining “Arifmetik 
uchburchak haqidagi traktat” nomli asarida bu sonlar jadvali 
haqidagi ma’lumotlarni e’lon qildi. 
Paskal uchburchagidagi qatorlar istalgancha davom ettirilishi 
mumkin. Shunisi qiziqki, Paskal uchburchagi yordamida istalgan ta 
elementdan tadan gruppalashlar sonini faqat qo‘shish amali 
yordamida hosil qilish mumkin Bu amal formulaga asoslanadi.