Daxiletmə və Xaricetmə Prinsipi — Onlayn dərslik

Qeyd. Bu dərsdə nə öyrənəcəyik? Dərs 1-də belə bir qayda müəyyən etmişdik: kəsişən hallar üçün toplama qaydası keçərli deyil. O zaman yeganə çıxış yolumuz halları yenidən strukturlaşdırıb kəsişməyən formaya salmaq idi. İndi isə ikinci — və daha güclü — bir metodu öyrənirik: kəsişməni hesablamaq və çıxmaq. Bu prinsip daxiletmə və xaricetmə prinsipi (qısaca DXP) adlanır.Bu dərs iki və üç çoxluq üçün intuisiyanın formalaşdırılması ilə başlayır, daha sonra isə ümumi hala keçir (orada Dərs 3-dəki binomial eynilik bizə lazım olacaq). Sonda iki klassik tətbiqə baxacağıq: deranjman (tam yerdəyişmə) — «heç bir element öz yerində qalmasın» məsələsi — və Eyler funksiyası

\varphi(n)

-in kombinatorik isbatı. Sonuncu tətbiq bu dərsi ədədlər nəzəriyyəsi kursu ilə əlaqələndirən mühüm bir körpüdür.

Əvvəlki dərslərdən nələri bilməliyik: Toplama və vurma qaydası, hallara ayırma, tamamlayıcı çoxluq vasitəsilə sayma (Dərs 1);

n!

və

C(n,k)

(Dərs 2);

\sum_k(-1)^k\binom{m}{k}=0

eyniliyi (Dərs 3).1İki çoxluq: kəsişməni bir dəfə çıxmaq

Teorem 1.1 (İki çoxluq üçün DXP). İxtiyari sonlu

A

və

B

çoxluqları üçün

|A\cup B| = |A|+|B|-|A\cap B| .

İsbat. Birləşmənin hər bir elementinin sağ tərəfə neçə vahid töhfə verdiyini hesablayaq — doğru düsturda hər bir element dəqiq olaraq bir dəfə sayılmalıdır (Dərs 1-in qızıl qaydası).

• Əgər element yalnız $A$ -ya aiddirsə: $|A|$ -nın tərkibində bir dəfə sayılır, digər iki həddə isə sayılmır. Töhfə $1$ -dir. dəqiqdir
• Əgər element yalnız $B$ -yə aiddirsə: analoji olaraq töhfə $1$ -dir. dəqiqdir
• Əgər element hər iki çoxluğa aiddirsə: həm $|A|$ -da, həm də $|B|$ -də bir dəfə, yəni cəmi iki dəfə sayılır, sonra isə $|A\cap B|$ -də bir dəfə çıxılır. Yekun töhfə $2-1=1$ olur. dəqiqdir

Deməli, sağ tərəf doğrudan da birləşməyə aid olan hər bir elementi dəqiq bir dəfə sayır.

Qeyd. Adın mənası. Əvvəlcə

|A|

və

|B|

-nin elementlər sayını «daxil edirik», sonra isə iki dəfə sayılmış kəsişməni «xaric edirik». Prinsipin ümumi forması da məhz bu ritmə əsaslanır: daxil et, xaric et, yenidən daxil et, …

Nümunə 1.1 (izah).

30

nəfərlik sinifdə

18

şagird futbol,

15

şagird basketbol oynayır;

8

nəfər isə hər ikisini oynayır. (a) Neçə nəfər ən azı bir idman növü ilə məşğuldur? (b) Neçə nəfər heç biri ilə məşğul deyil?(a)

18+15-8=25

. (b)

30-25=5

Nümunə 1.2 (izah).

1

-dən

100

-ə qədər neçə natural ədəd

2

-yə və ya

3

-ə qalıqsız bölünür?

A

—

2

-yə bölünənlər,

|A|=\lfloor 100/2\rfloor=50

;

B

—

3

-ə bölünənlər,

|B|=\lfloor 100/3\rfloor=33

;

A\cap B

—

6

-ya bölünənlər,

\lfloor 100/6\rfloor=16

|A\cup B|=50+33-16=67 .

Deməli, nə

2

-yə, nə də

3

-ə bölünənlərin sayı:

100-67=33

Qeyd. Dərs 1 ilə müqayisə. Həmin məsələni Dərs 1-də kəsişməyən üç hala ayıraraq həll etmişdik: «yalnız

2

-yə»

+

«yalnız

3

-ə»

+

«hər ikisinə». İndi isə bunu bir sətirdə həll etdik. İki çoxluq üçün bu fərq az görünə bilər — lakin dörd-beş çoxluq olduqda hallara ayırma üsulu praktiki olaraq işləmir, DXP isə eyni asanlıqla tətbiq olunur.

2Üç çoxluq: qanunauyğunluğu müşahidə edirik

Teorem 2.1 (Üç çoxluq üçün DXP).

|A\cup B\cup C| = |A|+|B|+|C| -|A\cap B|-|A\cap C|-|B\cap C| +|A\cap B\cap C| .

İsbat. Yenə də hər elementi ayrılıqda yoxlayaq. Bir element

A

B

C

çoxluqlarından neçəsinə aiddirsə, ona uyğun olaraq hallara ayıraq.

Neçə çoxluğa aiddir	Tək kəsişmələrdə	Cüt kəsişmələrdə	Üçlü kəsişmədə	Ümumi töhfə
$1$	$+1$	$0$	$0$	$1$
$2$	$+2$	$-1$	$0$	$1$
$3$	$+3$	$-3$	$+1$	$1$

Məsələn, element düz iki çoxluğa (tutaq ki,

A

və

B

-yə) aiddirsə:

|A|

və

|B|

-də cəmi iki dəfə sayılır,

|A\cap B|

-də bir dəfə çıxılır, digər kəsişmələrdə isə iştirak etmir — yekun töhfə

2-1=1

olur.Bütün hallarda töhfə

1

oldu, deməli, düstur birləşməyə aid olan hər bir elementi dəqiq olaraq bir dəfə sayır.

Nümunə 2.1 (izah).

1

-dən

100

-ə qədər neçə natural ədəd nə

2

-yə, nə

3

-ə, nə də

5

-ə bölünür?Əvvəlcə bölünənləri sayaq:

\left\lfloor\tfrac{100}{2}\right\rfloor +\left\lfloor\tfrac{100}{3}\right\rfloor +\left\lfloor\tfrac{100}{5}\right\rfloor -\left\lfloor\tfrac{100}{6}\right\rfloor -\left\lfloor\tfrac{100}{10}\right\rfloor -\left\lfloor\tfrac{100}{15}\right\rfloor +\left\lfloor\tfrac{100}{30}\right\rfloor

= 50+33+20-16-10-6+3 = 74 .

Cavab (bölünməyənlərin sayı):

100-74=26

Qeyd. Bölünmə məsələlərində kəsişmə həmişə ƏKOB-dur. «Həm

a

-ya, həm də

b

-yə bölünən» ifadəsi məhz «

\operatorname{ƏKOB}(a,b)

-yə bölünən» deməkdir.

2

və

3

üçün bu ədəd

6

-dır,

4

və

6

üçün isə

24

yox, məhz

12

-dir — burada çox vaxt diqqətsizlikdən səhvə yol verilir.

3Ümumi halİndi qanunauyğunluq (ritm) tam aydındır: tək sayda çoxluğun kəsişmələri müsbət, cüt sayda çoxluğun kəsişmələri isə mənfi işarə ilə düstura daxil edilir.

Teorem 3.1 (Daxiletmə və xaricetmə prinsipi). Tutaq ki,

A_1,A_2,\dots,A_n

sonlu çoxluqlardır. Onda

\left|\bigcup_{i=1}^{n}A_i\right| = \sum_{i}|A_i| - \sum_{i<j}|A_i\cap A_j| + \sum_{i<j<k}|A_i\cap A_j\cap A_k| - \dots + (-1)^{n-1}|A_1\cap\dots\cap A_n| .

İsbat. Birləşmənin ixtiyari bir

x

elementini götürək və onun sağ tərəfə verdiyi ümumi töhfəni hesablayaq. Fərz edək ki,

x

dəqiq

m

sayda çoxluğa aiddir (

m\ge 1

).Sağ tərəfdəki

k

-lı kəsişmələr cəmində

x

elementi hansı hədlərdə iştirak edir? Yalnız o kəsişmələrdə ki, seçilmiş

k

çoxluğun hər biri

x

-i özündə saxlayır — yəni həmin

k

çoxluq məhz

x

-i saxlayan

m

çoxluğun içərisindən seçilməlidir. Belə seçimlərin ümumi sayı

\binom{m}{k}

-dır.Deməli,

x

-in ümumi töhfəsi belə hesablanır:

\binom{m}{1}-\binom{m}{2}+\binom{m}{3}-\dots = -\sum_{k=1}^{m}(-1)^{k}\binom{m}{k} = -\left(\sum_{k=0}^{m}(-1)^{k}\binom{m}{k}-1\right) = -\left(0-1\right)=1 ,

burada Dərs 3-dəki işarəli cəm eyniliyindən istifadə etdik.Beləliklə, birləşməyə aid olan hər bir element dəqiq bir dəfə sayılır; birləşməyə daxil olmayan element isə heç bir həddə iştirak etmir (töhfəsi

0

olur).

Qeyd. Bu isbata diqqət yetirin. Dərs 3-də sadəcə «binomial eynilik» kimi öyrəndiyimiz nəzəri fakt —

\sum_k(-1)^k\binom mk=0

— burada birdən-birə işə düşdü və bütün prinsipin isbatının əsas səbəbinə çevrildi. Olimpiada riyaziyyatında fərqli mövzular arasındakı belə bağlantılar istisna deyil, əsas qaydadır.

Teorem 3.2 (DXP-nin tamamlayıcı forması — praktikada ən çox istifadə olunan forma). Tutaq ki,

U

sonlu «universal» çoxluqdur və

A_1,\dots,A_n\subseteq U

. Onda

A_i

-lərin heç birinə aid olmayan elementlərin sayı aşağıdakı kimi tapılır:

\left|U\setminus\bigcup A_i\right| = |U| - \sum_i |A_i| + \sum_{i<j}|A_i\cap A_j| - \dots + (-1)^{n}|A_1\cap\dots\cap A_n| .

İsbat. Sadəcə olaraq

|U|

-dan əvvəlki teoremin sağ tərəfini çıxırıq; nəticədə bütün işarələr əksinə dəyişir.

DXP-nin tətbiqi — dörd addım.

1. Universal çoxluğu seçin. $U$ nədir? (Bütün ədədlər, bütün permutasiyalar, bütün funksiyalar …)
2. «İstənməyən» (pis) xassələri müəyyən edin. $A_i$ — $i$ -ci şərtin pozulduğu obyektlər çoxluğu olsun. Diqqət: $A_i$ həmişə «istənməyən» (pozulan) halları ifadə etməlidir, məqsədəuyğun halları yox.
3. Kəsişmələri hesablayın. Adətən $|A_{i_1}\cap\dots\cap A_{i_k}|$ qiyməti yalnız $k$ -dan asılı olur — bu, prosesi çox yüngülləşdirir. Onda düstur aşağıdakı formaya düşür:
$\sum_{k=0}^{n}(-1)^k\binom{n}{k}N_k$
burada $N_k$ — istənilən (ixtiyari seçilmiş) $k$ məhdudiyyətin eyni anda pozulduğu obyektlərin sayıdır.
4. İşarələri yoxlayın. $k=0$ həddi $|U|$ -ya bərabərdir və işarəsi müsbətdir (+).

Nümunə 3.1 (izah).

1

-dən

1000

-ə qədər neçə ədəd

2

3

5

ədədlərindən heç birinə bölünmür?

U=\{1,\dots,1000\}

|U|=1000

. İstənməyən xassələr: «

2

-yə bölünür», «

3

-ə bölünür», «

5

-ə bölünür».

1000-(500+333+200)+(166+100+66)-33 = 1000-1033+332-33=266 .

4Birinci klassik tətbiq: süryeksiyalar (örtən funksiyalar)

Nümunə 4.1 (izah).

5

müxtəlif konfet

3

uşağa paylanmalıdır. Hər uşaq ən azı bir konfet almalıdır. Konfetləri neçə fərqli üsulla paylamaq olar?

U

— bütün mümkün paylanmalar çoxluğudur: hər bir konfet üçün

3

imkan var, deməli

3^5=243

.İstənməyən hallar (xassələr):

A_1

— «birinci uşaq heç bir konfet almır»,

A_2

A_3

— analoji olaraq digər uşaqlar üçün. Onda:

• $|A_i|$ : bütün konfetlər digər $2$ uşağa paylanır — $2^5=32$ ; bu tipli cəmi üç hədd var.
• $|A_i\cap A_j|$ : bütün konfetlər yalnız bir uşağa düşür — $1^5=1$ ; bu tipli də üç hədd var.
• $|A_1\cap A_2\cap A_3|=0$ (bütün uşaqlar konfetsiz qala bilməz).

3^5-3\cdot 2^5+3\cdot 1^5-0 = 243-96+3=150 .

Teorem 4.1 (Süryeksiyaların sayı).

n

elementli çoxluqdan

k

elementli çoxluğa təyin olunmuş örtən (bütün qiymətləri alan) funksiyaların (süryeksiyaların) sayı

S(n,k)=\sum_{i=0}^{k}(-1)^i\binom{k}{i}(k-i)^{\,n}.

İsbat.

U

— bütün mümkün funksiyalar çoxluğu olsun,

|U|=k^n

(hər bir elementin obrazını

k

fərqli cür seçmək olar).

A_j

— «

j

qiyməti heç vaxt alınmır» şərtini ödəyən funksiyalar çoxluğu olsun. Onda

i

sayda məhdudiyyətin eyni anda pozulması demək —

i

sayda qiymətin heç vaxt alınmaması deməkdir; belə funksiyalar yerdə qalan

k-i

qiyməti ala bilər və onların sayı

(k-i)^n

-dir. Hansı

i

qiymətin «atılacağı» isə

\binom ki

cür seçilə bilər. DXP-nin tamamlayıcı formasını tətbiq etsək, axtarılan düstur əldə olunar.

Nümunə 4.2 (izah).

1\times 6

ölçülü zolaq

3

fərqli rənglə boyanmalıdır; hər rəngdən ən azı bir dəfə istifadə olunmalıdır. Zolağı neçə fərqli üsulla rəngləmək olar?

3^6-3\cdot 2^6+3\cdot 1^6 = 729-192+3=540 .

Qeyd. «Hər biri ən azı bir» — DXP-nin əsas açar sözü. Dərs 1-də «ən azı bir» ifadəsi bir qadağa (məhdudiyyət) üçün tamamlayıcı sayma prinsipini işə salırdı. İndi isə bir neçə belə şərt var və məhz bu, DXP-nin birbaşa tətbiq sahəsidir. Diqqətli olun: burada uşaqlar (eləcə də rənglər, qutular) bir-birindən fərqlidir. Eyni (fərqlənməyən) qutular halı isə daha mürəkkəbdir və bu dərsin mövzusu xaricindədir.

5İkinci klassik tətbiq: deranjman (tam yerdəyişmə)

Tərif 5.1 (Deranjman — tam yerdəyişmə).

\{1,2,\dots,n\}

çoxluğunun elə permutasiyasına (yerdəyişməsinə) deranjman (tam yerdəyişmə) deyilir ki, bu zaman heç bir element öz əvvəlki yerində qalmasın: yəni hər bir

i

üçün

\sigma(i)\ne i

olsun. Belə permutasiyaların sayı

D_n

ilə işarə olunur.

Klassik hekayə:

n

nəfər papağını qarderoba verir; çıxarkən isə papaqlar təsadüfi qaydada paylanılır. Heç kimin öz papağını almaması hadisəsi neçə cür ola bilər?

Teorem 5.2.

D_n = n!\left(1-\frac{1}{1!}+\frac{1}{2!}-\frac{1}{3!} +\dots+\frac{(-1)^n}{n!}\right) = \sum_{k=0}^{n}(-1)^k\frac{n!}{k!} .

İsbat.

U

— bütün permutasiyalar çoxluğu,

|U|=n!

. İstənməyən (pozulan) xassə

A_i

: «

i

obyekti öz yerindədir», yəni

\sigma(i)=i

.Müəyyən edilmiş

k

dənə konkret indeks üçün

A_{i_1}\cap\dots\cap A_{i_k}

kəsişməsi nəyi ifadə edir? Həmin

k

element öz yerində bərkidilib, qalan

n-k

element isə sərbəst düzülür: deməli,

(n-k)!

qədər permutasiya var. Bu say yalnız və yalnız

k

-dan asılıdır və sözügedən indekslər

\binom nk

cür seçilir. DXP-nin tamamlayıcı formasını yazsaq:

D_n=\sum_{k=0}^{n}(-1)^k\binom{n}{k}(n-k)! =\sum_{k=0}^{n}(-1)^k\frac{n!}{k!\,(n-k)!}(n-k)! =\sum_{k=0}^{n}(-1)^k\frac{n!}{k!} . \qquad

$n$	1	2	3	4	5	6	7	8	9
$n!$	1	2	6	24	120	720	5040	40 320	362 880
$D_n$	0	1	2	9	44	265	1854	14 833	133 496

Qeyd. Gözəl riyazi fakt: $D_n\approx \dfrac{n!}{e}$ . Mötərizədəki cəm

e^{-1}=0{,}3678\ldots

ədədinin Teylor sırası ayrılışıdır. Deməli, təsadüfi permutasiyada heç bir elementin öz yerində qalmaması ehtimalı

n

böyüdükcə

1/e\approx 0{,}368

-ə yaxınlaşır — və bu yaxınlaşma inanılmaz sürətlidir. Praktik nəticə:

D_n

ədədi

n!/e

ədədinə ən yaxın tam ədəddir (

n\ge 1

şərti üçün). Məsələn,

10!/e=1\,334\,960{,}9\ldots

və

D_{10}=1\,334\,961

Teorem 5.3 (İki rekurrent düstur).

n\ge 2

üçün

\text{(a)}\quad D_n=(n-1)\bigl(D_{n-1}+D_{n-2}\bigr), \qquad \text{(b)}\quad D_n=n\,D_{n-1}+(-1)^n .

(Başlanğıc şərtlər:

D_0=1

D_1=0

İsbat. (a) — kombinatorik isbat.

1

elementinin hansı mövqeyə getdiyinə baxaq:

\sigma(1)=j\ne 1

, yəni

j

üçün

n-1

sərbəst imkan var. İndi iki hala ayıraq.

• $\sigma(j)=1$ (yəni $1$ və $j$ elementləri yerlərini öz aralarında dəyişib). Bu halda yerdə qalan $n-2$ element öz aralarında tam yerdəyişmə (deranjman) əmələ gətirir: $D_{n-2}$ .
• $\sigma(j)\ne 1$ . İndi $2,3,\dots,n$ elementlərini $1,2,\dots,n$ mövqelərindən $j$ -dən başqa hamısına yerləşdirmək tələb olunur və məhdudiyyətlər belədir: hər bir $i\ne j$ elementi öz $i$ yerinə düşməməli, $j$ elementi isə $1$ yerinə düşməməlidir. Əgər $1$ yerini şərti olaraq « $j$ -nin öz yeri» kimi adlandırsaq, bu, dəqiq olaraq $n-1$ obyektin tam yerdəyişməsidir: $D_{n-1}$ .

Vurma və toplama qaydalarına əsasən:

D_n=(n-1)(D_{n-1}+D_{n-2})

.(b) — Cəbri isbat. Düsturdan birbaşa alınır:

D_n-nD_{n-1}=\sum_{k=0}^{n}(-1)^k\frac{n!}{k!} -n\sum_{k=0}^{n-1}(-1)^k\frac{(n-1)!}{k!}=(-1)^n

, çünki ilk

n

hədd tamamilə ixtisar olunur.

Nümunə 5.1 (izah).

D_6

-nı iki fərqli üsulla hesablayaq.Düsturla:

D_6=720\left(1-1+\frac12-\frac16+\frac1{24}-\frac1{120} +\frac1{720}\right)=360-120+30-6+1=265

.(a) rekurrent düsturu ilə:

D_6=5(D_5+D_4)=5(44+9)=5\cdot 53=265

. dəqiqdir

«Dəqiq

k

elementin öz yerində qalması» məsələləri.

n

obyektin permutasiyalarından dəqiq olaraq

k

-sının öz yerində qalanlarının sayı

\binom{n}{k}\,D_{n-k}

düsturu ilə hesablanır: çünki əvvəlcə yerində qalacaq

k

obyekti seçirik, sonra isə yerdə qalan

n-k

elementin heç birinin öz yerində qalmaması şərtini tətbiq edirik.

Nümunə 5.2 (izah).

6

məktub

6

fərqli zərfə təsadüfi qoyulur. Dəqiq olaraq

2

məktubun öz aid olduğu zərfə düşməsi neçə fərqli cür ola bilər?

\binom{6}{2}D_4 = 15\cdot 9 = 135 .

Qeyd. Yoxlama düsturu. Bütün mümkün permutasiyaların sayı belə hallara ayrılır:

n!=\sum_{k=0}^{n}\binom{n}{k}D_{n-k}.

n=4

üçün yoxlayaq:

\binom40 D_4+\binom41 D_3+\binom42 D_2+\binom43 D_1 +\binom44 D_0 = 9+4\cdot2+6\cdot1+0+1=24=4!

. dəqiqdir Bu eynilik apardığınız hesablamaların doğruluğunu yoxlamağın ən sürətli yoludur.

6Üçüncü tətbiq: Eyler funksiyası — iki fənni birləşdirən körpüƏdədlər nəzəriyyəsi kursundan

\varphi(n)

funksiyası sizə tanışdır: bu funksiya

1,2,\dots,n

ədədləri arasında

n

ilə qarşılıqlı sadə olan ədədlərin sayını tapır. Onun hesablanma düsturu isə əslində saf kombinatorikaya əsaslanır.

Teorem 6.1 (Eyler funksiyasının düsturu).

n>1

ədədinin kanonik ayrılışı

n=p_1^{\alpha_1}\cdots p_r^{\alpha_r}

şəklində olsun. Onda

\varphi(n)=n\left(1-\frac{1}{p_1}\right)\left(1-\frac{1}{p_2}\right) \cdots\left(1-\frac{1}{p_r}\right).

İsbat.

U=\{1,2,\dots,n\}

universal çoxluğunu götürək. İxtiyari bir

x

ədədi

n

ilə qarşılıqlı sadə deyilsə,

\iff

bu,

x

-in

n

-in sadə vuruqlarından (yəni

p_i

-lərdən) ən azı birinə bölündüyü deməkdir. Deməli, istənməyən (pis) xassələr artıq hazırdır:

A_i=\{x\in U:\ p_i\mid x\}

.Kəsişmələri hesablamaq çox asandır:

p_{i_1},\dots,p_{i_k}

sadə ədədləri cüt-cüt fərqli (qarşılıqlı sadə) olduğuna görə onların hamısına eyni anda bölünmək birbaşa onların

p_{i_1}\cdots p_{i_k}

hasilinə bölünmək deməkdir. Belə ədədlərin sayı isə məhz

\dfrac{n}{p_{i_1}\cdots p_{i_k}}

-dir (bu kəsr tam ədəd verir, çünki həmin hasil

n

-in bölənidir).DXP-nin tamamlayıcı formasını tətbiq edək:

\varphi(n)= n-\sum_i \frac{n}{p_i}+\sum_{i<j}\frac{n}{p_ip_j} -\dots+(-1)^r\frac{n}{p_1\cdots p_r}.

İndi isə diqqətlə nəzər yetirin: bu cəbri ifadə sadəcə olaraq

n\left(1-\frac{1}{p_1}\right)\cdots\left(1-\frac{1}{p_r}\right)

hasilinin açılmış formasıdır — belə ki, mötərizələri vurub açdıqda hər bir

(-1)^k/(p_{i_1}\cdots p_{i_k})

həddi dəqiq olaraq bir dəfə əmələ gəlir.

Nümunə 6.1 (izah).

\varphi(100)

100=2^2\cdot 5^2

, deməli

\varphi(100)=100\left(1-\tfrac12\right)\left(1-\tfrac15\right) =100\cdot\tfrac12\cdot\tfrac45=40 .

DXP dili ilə eyni hesablamanı aparaq:

100-50-20+10=40

. dəqiqdir

Nümunə 6.2 (izah).

\varphi(60)

60=2^2\cdot 3\cdot 5

;

60-\left(30+20+12\right)+\left(10+6+4\right)-2=60-62+20-2=16

. Düsturla:

60\cdot\frac12\cdot\frac23\cdot\frac45=16

. dəqiqdir

Qeyd. Niyə bu körpü əhəmiyyətlidir? Ədədlər nəzəriyyəsində

\varphi(n)

-in multiplikativ (zərb) xassəsi adətən Çin qalıq teoremi vasitəsilə isbat olunur. Burada isə şahidi olduq ki, həmin düstur ədədlər nəzəriyyəsinin heç bir mürəkkəb aparatına ehtiyac olmadan — sadəcə düzgün sayma qaydası ilə — əldə olunur. Bu yanaşma olimpiadaçılar üçün xarakterik bir mənzərədir: bir sahənin mürəkkəb görünən faktı digər sahənin nisbətən sadə aləti ilə asanlıqla isbat edilir.

7Tipik səhvlər və iş sxemi

Qeyd. Altı klassik səhv.

1. «İstənməyən» (pis) çoxluqlar əvəzinə «yaxşı» (məqsədəuyğun) çoxluqları götürmək. DXP-də $A_i$ çoxluqları mütləq şərtin pozulduğu (qadağan olunmuş) obyektləri ifadə etməldir. Əks halda kəsişmələri hesablamaq mümkün olmayacaq.
2. İşarələri qarışdırmaq. Yadda saxlayın: birləşmə düsturunda ilk hədd müsbətdir (+); tamamlayıcı düsturda isə $|U|$ müsbətdir (+) və birinci cəm mənfi (-) işarə ilə gəlir.
3. Kəsişməni səhv hesablamaq. Bölünmə məsələlərində kəsişmə mütləq ƏKOB ilə tapılır; permutasiya məsələlərində isə bir neçə elementi öz yerində bərkitdikdə yerdə qalanlar tam sərbəst hərəkət edir.
4. $k=0$ həddini unutmaq. $\binom n0 N_0=|U|$ həddi tamamlayıcı düsturun ayrılmaz bir hissəsidir.
5. Fərqlənməyən (eyni) obyektlərə tətbiq etmək. «Hər qutu boş qalmasın» məsələsi qutular fərqli olduqda DXP vasitəsilə həll olunur; lakin qutular eynidirsə məsələnin həll alqoritmi tamamilə fərqlidir.
6. Deranjman məsələlərində «dəqiq» ilə «ən azı» anlayışlarını qarışdırmaq. «Dəqiq olaraq $k$ element yerindədir» $=\binom nk D_{n-k}$ ; lakin «ən azı $k$ element yerindədir» deyildikdə isə müvafiq halların cəmi hesablanmalıdır.

Qeyd. Yaddaş cədvəli.

Şərtdə nə verilibsə	Hansı alətdən istifadə olunmalıdır
« $a$ -ya və ya $b$ -yə bölünən»	İki çoxluq üçün DXP, kəsişmə ƏKOB ilə tapılır
«Heç birinə bölünmür»	DXP-nin tamamlayıcı forması
«Hər qutuya/uşağa/rəngə ən azı bir»	Süryeksiya (örtən funksiya) düsturu
«Heç bir element öz yerində deyil»	$D_n$ (Tam yerdəyişmə düsturu)
«Dəqiq olaraq $k$ element öz yerindədir»	$\binom nk D_{n-k}$
« $n$ ədədi ilə qarşılıqlı sadədir»	$\varphi(n)$ , yəni sadə bölənlər üzrə DXP tətbiqi
Kəsişmələrin sayı yalnız $k$ -dan asılıdır	$\sum_k(-1)^k\binom nk N_k$

8Asan məsələlər

Məsələ 1.

|A|=20

|B|=15

|A\cap B|=6

|A\cup B|

neçəyə bərabərdir?

Həll.

20+15-6=29

. Cavab:

29

Məsələ 2.

30

nəfərlik bir sinifdə

18

nəfər futbol,

15

nəfər basketbol oynayır,

8

nəfər isə hər ikisini oynayır. (a) Neçə nəfər ən azı bir idman növü ilə məşğuldur? (b) Neçə nəfər heç bir idmanla məşğul deyil?

Həll. (a)

18+15-8=25

. (b)

30-25=5

. Cavab: (a)

25

; (b)

5

Məsələ 3.

1

-dən

100

-ə qədər neçə natural ədəd

2

-yə və ya

3

-ə bölünür?

Həll.

50+33-16=67

(kəsişmə, yəni hər ikisinə bölünənlər

6

-ya bölünənlərdir). Cavab:

67

Məsələ 4. Eyni aralıqda yerləşən neçə ədəd nə

2

-yə, nə də

3

-ə bölünür?

Həll.

100-67=33

. Cavab:

33

Məsələ 5.

1

-dən

1000

-ə qədər neçə natural ədəd

3

-ə və ya

5

-ə bölünür?

Həll.

333+200-66=467

. Cavab:

467

Məsələ 6. Eyni aralıqda neçə ədəd nə

3

-ə, nə də

5

-ə bölünür?

Həll.

1000-467=533

. Cavab:

533

Məsələ 7.

1

-dən

100

-ə qədər neçə natural ədəd

2

3

və

5

ədədlərindən heç birinə bölünmür?

Həll.

100-(50+33+20)+(16+10+6)-3=100-103+32-3=26

. Cavab:

26

Məsələ 8.

1

-dən

300

-ə qədər neçə natural ədəd

3

5

və ya

7

-yə bölünür?

Həll.

100+60+42-20-14-8+2=162

. Cavab:

162

Məsələ 9.

40

nəfərdən

25

-i ingilis,

20

-si isə alman dilini bilir.

10

nəfər hər iki dili bilir. Neçə nəfər bu dillərdən heç birini bilmir?

Həll. Ən azı bir dili bilənlər

25+20-10=35

; deməli qalanlar

40-35=5

nəfərdir. Cavab:

5

Məsələ 10.

1

-dən

1000

-ə qədər neçə natural ədəd

2

3

5

ədədlərindən heç birinə bölünmür?

Həll.

1000-(500+333+200)+(166+100+66)-33=266

. Cavab:

266

Məsələ 11. Neçə fərqli üçrəqəmli ədədin yazılışında ən azı bir

7

rəqəmi iştirak edir?

Həll. Tamamlayıcı sayma üsulu (bu, DXP-nin sadə, bir məhdudiyyətli halıdır):

7

rəqəmi iştirak etməyən üçrəqəmlilərin sayı

8\cdot 9\cdot 9=648

, deməli

900-648=252

. Cavab:

252

Məsələ 12.

D_3

və

D_4

qiymətlərini hesablayın.

Həll.

D_3=3!\left(1-1+\frac12-\frac16\right)=6\cdot\frac13=2

;

D_4=24\left(1-1+\frac12-\frac16+\frac1{24}\right)=12-4+1=9

. Cavab:

2

və

9

Məsələ 13.

4

məktub

4

fərqli zərfə təsadüfi qaydada qoyulur. Heç bir məktubun öz zərfinə düşməməsi hadisəsi neçə cür ola bilər?

Həll.

D_4=9

. Cavab:

9

Məsələ 14.

5

nəfər papaqlarını qarderoba verir və çıxarkən təsadüfi bir papaq götürür. Heç kimin öz papağını götürməməsi neçə cür mümkündür?

Həll.

D_5=120\left(1-1+\frac12-\frac16+\frac1{24}-\frac1{120}\right) =60-20+5-1=44

. Cavab:

44

Məsələ 15.

\varphi(36)

nəyə bərabərdir?

Həll.

36=2^2\cdot 3^2

;

\varphi(36)=36\cdot\frac12\cdot\frac23=12

. Cavab:

12

Məsələ 16.

\varphi(100)

nəyə bərabərdir?

Həll.

100\cdot\frac12\cdot\frac45=40

. Cavab:

40

Məsələ 17.

\varphi(60)

-ın qiymətini həm düsturla, həm də DXP tətbiq etməklə hesablayın.

Həll. Düsturla:

60\cdot\frac12\cdot\frac23\cdot\frac45=16

. DXP ilə:

60-(30+20+12)+(10+6+4)-2=16

. dəqiqdir Cavab:

16

Məsələ 18.

1

-dən

120

-yə qədər neçə natural ədəd

120

ilə qarşılıqlı sadədir?

Həll.

120=2^3\cdot 3\cdot 5

;

\varphi(120)=120\cdot\frac12\cdot\frac23\cdot\frac45=32

. Cavab:

32

Məsələ 19.

4

müxtəlif konfet

2

uşağa elə paylanmalıdır ki, hər uşaq ən azı bir konfet alsın. Bunu neçə üsulla etmək olar?

Həll.

2^4-2\cdot 1^4=16-2=14

. Cavab:

14

Məsələ 20.

5

müxtəlif konfet

3

uşağa elə paylanmalıdır ki, hər uşaq ən azı bir konfet alsın. Bunu neçə cür etmək olar?

Həll.

3^5-3\cdot 2^5+3\cdot 1^5=243-96+3=150

. Cavab:

150

Məsələ 21.

|A|=12

|B|=10

|C|=8

|A\cap B|=5

|A\cap C|=4

|B\cap C|=3

|A\cap B\cap C|=2

|A\cup B\cup C|

tapın.

Həll.

12+10+8-5-4-3+2=20

. Cavab:

20

Məsələ 22.

1

-dən

50

-yə qədər neçə natural ədəd

2

-yə və ya

7

-yə qalıqsız bölünür?

Həll.

25+7-3=29

. Cavab:

29

Məsələ 23. Neçə fərqli dördrəqəmli ədədin yazılışında

1

və ya

2

rəqəmi iştirak edir?

Həll. Tamamlayıcı sayma ilə: tərkibində nə

1

, nə də

2

olmayanlar — birinci rəqəm

\{3,\dots,9\}

çoxluğundan (

7

imkan), qalan üç rəqəm isə

\{0,3,4,\dots,9\}

çoxluğundan (

8

imkan) seçilir:

7\cdot 8^3=3584

. Cavab

9000-3584=5416

. Cavab:

5416

Məsələ 24.

1

-dən

200

-ə qədər neçə natural ədəd

4

-ə və ya

6

-ya bölünür?

Həll.

50+33-16=67

. (Kəsişmə

\operatorname{ƏKOB}(4,6)=12

-yə bölünənlərdir:

\lfloor 200/12\rfloor=16

.) Cavab:

67

Məsələ 25.

5

nəfərin təsadüfi qaydada əyləşdiyi düzülüşlərin neçəsində ən azı bir nəfər öz əvvəlki yerində əyləşib?

Həll.

5!-D_5=120-44=76

. Cavab:

76

Məsələ 26.

6

məktubdan dəqiq olaraq birinin öz zərfinə düşməsi hadisəsi neçə cür ola bilər?

Həll.

\binom{6}{1}D_5=6\cdot 44=264

. Cavab:

264

Məsələ 27.

5

məktubdan dəqiq olaraq ikisinin öz zərfinə düşməsi neçə cür ola bilər?

Həll.

\binom{5}{2}D_3=10\cdot 2=20

. Cavab:

20

Məsələ 28.

\varphi(72)

nəyə bərabərdir?

Həll.

72=2^3\cdot 3^2

;

72\cdot\frac12\cdot\frac23=24

. Cavab:

24

Məsələ 29.

1

-dən

1000

-ə qədər neçə natural ədəd

1000

ilə qarşılıqlı sadədir?

Həll.

1000=2^3\cdot 5^3

;

\varphi(1000)=1000\cdot\frac12\cdot\frac45=400

. Cavab:

400

Məsələ 30.

100

tələbədən

60

-ı riyaziyyat,

50

-si fizika dərnəyinə gedir,

30

nəfər isə hər ikisinə gedir. Neçə tələbə bu dərnəklərin heç birinə getmir?

Həll.

60+50-30=80

;

100-80=20

. Cavab:

20

9Orta və çətin məsələlər

Məsələ 31. Üç çoxluq üçün verilən DXP düsturunu isbat edin.

Həll. Birləşmənin ixtiyari bir elementini götürüb onun düsturun sağ tərəfinə verdiyi töhfəni hesablayaq; element

A,B,C

-dən neçəsinə aiddirsə, ona uyğun hallara ayıraq: əgər yalnız bir çoxluqda olarsa töhfə

1

; iki çoxluqda olarsa

2-1=1

; hər üçündə olarsa

3-3+1=1

. Bütün hallarda yekun töhfə

1

olur, deməli sağ tərəf birləşmənin hər bir elementini dəqiq olaraq bir dəfə sayır. Birləşməyə daxil olmayan element isə heç bir həddə iştirak etmir. Cavab: İsbat olundu.

Məsələ 32. Ümumi DXP düsturunu isbat edin: yəni hər bir aid olan elementin verdiyi töhfənin

1

olduğunu göstərin.

Həll. Fərz edək ki,

x

elementi dəqiq olaraq

m\ge 1

sayda çoxluğa aiddir. Düsturdakı

k

-lı kəsişmələr cəmində

x

elementi dəqiq

\binom mk

dəfə (həddə) iştirak edir (çünki kəsişən həmin

k

çoxluq

x

-i özündə saxlayan bu

m

çoxluğun içindən seçilməlidir). Deməli, ümumi töhfə belə olar:

\sum_{k=1}^{m}(-1)^{k-1}\binom mk = -\left(\sum_{k=0}^{m}(-1)^k\binom mk\right)+1 = -0+1 = 1,

burada Dərs 3-dəki işarəli cəm eyniliyindən (binom açılışından) istifadə edildi. Cavab: İsbat olundu.

Məsələ 33.

1

-dən

2000

-ə qədər neçə ədəd

2

3

5

7

-dən heç birinə bölünmür? (İzahlı həlli Dərs mətnindəki analoji məsələyə baxaraq

1000

üçün yoxlayın) Məsələ:

1

-dən

1000

-ə qədər neçə ədəd

2

3

5

7

-dən heç birinə bölünmür?

Həll. Dörd məhdudiyyət (şərt) var. Əvvəlcə bütün mümkün məxrəcləri (ƏKOB-ları) siyahı halında yazaq:

• tək sayda olanlar: $2,3,5,7$ — qismətlər: $500,\,333,\,200,\,142$ ; cəmi $1175$ ;
• cüt sayda olanlar (kəsişmələr): $6,10,14,15,21,35$ — qismətlər: $166,\,100,\,71,\,66,\,47,\,28$ ; cəmi $478$ ;
• üçlü kəsişmələr: $30,42,70,105$ — qismətlər: $33,\,23,\,14,\,9$ ; cəmi $79$ ;
• dördlü kəsişmə: $210$ — qismət: $4$ .

Tamamlayıcı DXP düsturunu tətbiq edək:

1000-1175+478-79+4 = 228 .

Yoxlama (Nəzarət). Nəzəri cəhətdən belə ədədlərin paylanma sıxlığı təxminən

\frac12\cdot\frac23\cdot\frac45\cdot\frac67=\frac{8}{35}\approx 0{,}229

-dur, yəni

1000

ədəd üçün təxminən

229

gözlənilir — bu da bizim aldığımız cavabla olduqca uyğundur. dəqiqdir Cavab:

228

Qeyd. Bu məsələdən çıxarılacaq dərs. Dörd məhdudiyyət olduqda düsturda artıq

16

hədd iştirak edir və hesablama səhvi ehtimalı olduqca yüksəkdir. Bunun qarşısını almaq üçün iki qoruyucu vərdiş lazımdır: (1) kəsişmələrin məxrəclərini (

6,10,14,15,21,35

;

30,42,70,105

;

210

) əvvəlcə səliqə ilə ayrıca siyahı halında qeyd edin; (2) aldığınız nəticəni sıxlıqların hasili ilə təqribi yoxlayın.

Məsələ 34.

6

müxtəlif topu

3

fərqli qutuya elə yerləşdirin ki, heç bir qutu boş qalmasın. Bunu neçə cür etmək olar?

Həll. Süryeksiya (örtən funksiya) düsturuna əsasən:

3^6-3\cdot 2^6+3\cdot 1^6=729-192+3=540

. Cavab:

540

Məsələ 35.

7

müxtəlif hədiyyə

3

uşağa paylanır; hər uşaq ən azı bir hədiyyə almalıdır. Neçə cür paylamaq olar?

Həll. Süryeksiya düsturu:

3^7-3\cdot 2^7+3\cdot 1^7=2187-384+3=1806

. Cavab:

1806

Məsələ 36.

D_n=(n-1)(D_{n-1}+D_{n-2})

rekurrent düsturunu isbat edin və bu vasitəsilə

D_6

-nı hesablayın.

Həll. Tutaq ki,

\sigma(1)=j

olsun; deranjman şərtinə görə

j\ne 1

, deməli

j

üçün fərqli

n-1

imkan mövcuddur. İndi qalan prosesi iki fərqli hala ayıraq:

• Əgər $\sigma(j)=1$ olarsa: yerdə qalan $n-2$ element tam sərbəst şəkildə öz aralarında deranjman (tam yerdəyişmə) əmələ gətirir — bu da $D_{n-2}$ qədər variant deməkdir;
• Əgər $\sigma(j)\ne 1$ olarsa: $2,\dots,n$ elementlərinin yerləşdirilməsi üçün qüvvədə olan məhdudiyyətlər «hər bir $i\ne j$ üçün $i$ yerinə düşməmək» və « $j$ elementinin $1$ yerinə düşməməsi»dir; bu halda, fərqli $1$ yerini asanlıqla $j$ -nin «öz qanuni yeri» kimi fərz etsək, bu proses tamamilə dəqiq olaraq $n-1$ obyektin deranjmanı olar — yəni $D_{n-1}$ .

Deməli, toplama və vurma prinsiplərini birləşdirdikdə

D_n=(n-1)(D_{n-1}+D_{n-2})

alınır.

D_6

-nın hesablanması:

D_6=5(D_5+D_4)=5(44+9)=265

. Cavab:

265

Məsələ 37.

D_n=nD_{n-1}+(-1)^n

olduğunu isbat edin.

Həll. Açıq şəkilli düsturdan istifadə edək:

D_n=\sum_{k=0}^{n}(-1)^k\frac{n!}{k!},\qquad nD_{n-1}=n\sum_{k=0}^{n-1}(-1)^k\frac{(n-1)!}{k!} =\sum_{k=0}^{n-1}(-1)^k\frac{n!}{k!}.

İki cəm arasındakı yeganə fərq məhz

k=n

həddidir: belə ki,

D_n-nD_{n-1}=(-1)^n\dfrac{n!}{n!}=(-1)^n

. Cavab: İsbat olundu.

Məsələ 38.

6

məktub

6

fərqli zərfə təsadüfi olaraq qoyulur. Dəqiq olaraq

2

-sinin öz aid olduğu zərfə düşməsi hadisəsi neçə cür ola bilər?

Həll. Əvvəlcə yerində qalacaq düz iki məktubu seçirik (

\binom62=15

), yerdə qalan dörd məktub isə mütləq heç biri öz zərfinə düşməmək şərtilə (deranjman) paylanmalıdır (

D_4=9

): beləliklə,

15\cdot 9=135

. Cavab:

135

Məsələ 39. Eyler funksiyasının düsturunu DXP vasitəsilə isbat edin.

Həll. Universal çoxluq

U=\{1,\dots,n\}

olsun, istənməyən şərtlərin cəmiyyəti isə

A_i=\{x:\ p_i\mid x\}

(burada

p_i

—

n

-in ayrılışındakı sadə bölənlərdir).

x

ədədi ilə

n

qarşılıqlı sadə deyil

\iff

x

heç olmasa bir

A_i

çoxluğuna daxildir.

k

sayda sadə ədədin hamısına eyni anda bölünmək birbaşa onların hasilinə bölünmək deməkdir, belə ədədlərin ümumi sayı isə

n/(p_{i_1}\cdots p_{i_k})

-dir. Tamamlayıcı DXP düsturunu yazsaq:

\varphi(n)=n-\sum\frac{n}{p_i}+\sum\frac{n}{p_ip_j}-\dots = n\prod_{i=1}^{r}\left(1-\frac1{p_i}\right),

çünki ən sağdakı hasili vurub açdıqda dəqiq olaraq eyni cəbri hədlər alınır. Cavab: İsbat olundu.

Məsələ 40.

1

-dən

2026

-ya qədər neçə ədəd

2

3

5

ədədlərindən heç birinə bölünmür?

Həll.

\lfloor 2026/2\rfloor=1013

\lfloor 2026/3\rfloor=675

\lfloor 2026/5\rfloor=405

;

\lfloor 2026/6\rfloor=337

\lfloor 2026/10\rfloor=202

\lfloor 2026/15\rfloor=135

;

\lfloor 2026/30\rfloor=67

. DXP tətbiqi:

2026-(1013+675+405)+(337+202+135)-67 = 2026-2093+674-67=540 .

Cavab:

540

Məsələ 41. Neçə altırəqəmli ədədin yazılışında həm

1

, həm də

2

rəqəmi iştirak edir?

Həll.

U

— bütün altırəqəmli ədədlərin çoxluğu olsun,

|U|=900\,000

. Burada istənməyən (pozulan) məhdudiyyətlər:

A

— «

1

rəqəmi yoxdur»,

B

— «

2

rəqəmi yoxdur».

• $|A|$ : birinci rəqəm $\{2,\dots,9\}$ içindən seçilir ( $8$ imkan), qalan beş mövqe isə $1$ -dən fərqli rəqəmlərlə doldurulur ( $9$ imkan): deməli $8\cdot 9^5=472\,392$ . Eyni qayda ilə $|B|=472\,392$ tapılır.
• $|A\cap B|$ : nə $1$ , nə də $2$ rəqəmi iştirak etmir — bu zaman birinci rəqəm üçün $7$ imkan, qalan mövqelər üçün isə $8$ imkan mövcuddur: $7\cdot 8^5=229\,376$ .

Ən azı bu rəqəmlərdən birinin olmadığı (çatışmadığı) ədədlərin ümumi sayı:

472\,392\cdot 2-229\,376=715\,408

. Axtarılan cavab (hər ikisinin mütləq olduğu):

900\,000-715\,408=184\,592

. Cavab:

184\,592

Məsələ 42.

8

müxtəlif kitab

3

fərqli rəfə yerləşdirilir (hər bir rəfdəki sıra, düzülüş vacib deyil). Heç bir rəf boş qalmamalıdır. Bunu neçə cür həyata keçirmək olar?

Həll. Birbaşa süryeksiya düsturu:

3^8-3\cdot 2^8+3\cdot 1^8=6561-768+3=5796

. Cavab:

5796

Məsələ 43.

\{1,2,\dots,6\}

çoxluğunun neçə fərqli permutasiyasında

\sigma(1)\ne 1

və

\sigma(2)\ne 2

-dir?

Həll. Burada cəmi iki məhdudiyyət (qadağa) var (digər dörd mövqe isə tamamilə sərbəstdir — diqqətli olun, bu tam dərəngement (deranjman) məsələsi deyil!):

6!-2\cdot 5!+4! = 720-240+24=504 .

Cavab:

504

Məsələ 44.

\{1,2,\dots,7\}

-nin neçə permutasiyasında eyni vaxtda

\sigma(1)\ne1

\sigma(2)\ne2

\sigma(3)\ne3

şərtləri ödənilir?

Həll. Cəmi üç məhdudiyyət mövcuddur, düsturu açaq:

7!-3\cdot 6!+3\cdot 5!-4! = 5040-2160+360-24=3216 .

Cavab:

3216

Məsələ 45.

1

-dən

100

-ə qədər neçə natural ədəd tam kvadrat, tam kub və ya tam beşinci qüvvətdir?

Həll. Tam kvadratlar

10

dənədir (

1^2,\dots,10^2

); tam kublar

4

dənə; tam beşinci qüvvətlər isə

2

dənədir (

1,32

). Kəsişmələri isə ƏKOB vasitəsilə tapaq: altıncı qüvvətlər

2

ədəddir (

1,64

), onuncu qüvvətlər

1

dənədir, on beşinci qüvvətlər

1

dənə, otuzuncu qüvvətlər

1

dənədir.

10+4+2-2-1-1+1=13 .

Cavab:

13

Məsələ 46.

1

-dən

1000

-ə qədər neçə natural ədəd nə tam kvadrat, nə də tam kubdur?

Həll. Kvadratlar

31

ədəd, kublar

10

ədəd, kəsişmələr yəni altıncı qüvvətlər

3

ədəddir (

1,64,729

). Ən azı biri (birləşmə):

31+10-3=38

. Tamamlayıcı çoxluq olaraq cavab:

1000-38=962

. Cavab:

962

Məsələ 47.

5

məktubdan ən azı

3

-nün öz aid olduğu zərfə düşməsi hadisəsi neçə cür ola bilər?

Həll. «Dəqiq olaraq

k

element yerindədir» hallarını bir-bir yoxlayaraq toplayaq:

\binom53 D_2+\binom54 D_1+\binom55 D_0 = 10\cdot 1+5\cdot 0+1\cdot 1=11 .

(Diqqətli olun: dəqiq olaraq

4

-ü yerində olan heç bir permutasiya yoxdur — çünki bu zaman beşinci məktub da məcburən öz yerində olar; yazılan düstur bunu

D_1=0

sayəsində asanlıqla özü kənarlaşdırır.) Cavab:

11

Məsələ 48.

4

evli cütlük (

8

nəfər) bir cərgəyə düzülür. Heç bir cütlüyün yan-yana əyləşməməsi (yanaşı gəlməməsi) hadisəsi neçə cür mümkündür?

Həll. Universal çoxluq

U

: bütün mümkün düzülüşlər,

|U|=8!=40\,320

. İstənməyən xassə

A_i

: «

i

-ci cütlük yan-yana əyləşib».

k

sayda konkret cütlüyün eyni vaxtda yan-yana olması şərtinə baxaq: həmin

k

cütü vahid bir blok (obyekt) kimi nəzərdə tuturuq — yerdə qalan elementlərlə birlikdə cəmi

8-k

obyekt olur. Onların düzülüşü

(8-k)!

qədərdir və hər bir qapalı blokun içində ər-arvadın yerlərini dəyişməsi

2

cür mümkündür, yəni yekun olaraq

2^k(8-k)!

alınır. Bu qiymət yalnız və yalnız

k

-dan asılıdır. DXP-nin düsturuna əsasən:

\sum_{k=0}^{4}(-1)^k\binom4k 2^k(8-k)! = 40\,320-4\cdot2\cdot5040+6\cdot4\cdot720-4\cdot8\cdot120+16\cdot24

= 40\,320-40\,320+17\,280-3840+384 = 13\,824 .

Cavab:

13\,824

Məsələ 49.

1

-dən

2026

-ya qədər neçə natural ədəd

6

10

və ya

15

-ə qalıqsız bölünür?

Həll. Tək-tək bölənlər:

\lfloor 2026/6\rfloor=337

\lfloor 2026/10\rfloor=202

\lfloor 2026/15\rfloor=135

. Cüt kəsişmələr (ƏKOB tapılır):

\operatorname{ƏKOB}(6,10)=30

—

\lfloor 2026/30\rfloor=67

;

\operatorname{ƏKOB}(6,15)=30

—

67

;

\operatorname{ƏKOB}(10,15)=30

—

67

; Hər üçünün ortaq kəsişməsi də elə

30

-a bərabərdir — o cümlədən

67

. DXP düsturunu tətbiq edək:

337+202+135-67-67-67+67=540 .

Cavab:

540

10Ev tapşırıqlarıA hissəsi — asan

$|A|=25$ , $|B|=18$ , $|A\cap B|=7$ . $|A\cup B|$ neçədir?
$|A\cup B|=40$ , $|A|=25$ , $|B|=22$ . $|A\cap B|$ neçədir?
$50$ nəfərdən $30$ -u çay, $25$ -i isə qəhvə içir, $12$ nəfər isə hər ikisini içir. Neçə nəfər bunlardan heç birini içmir?
$1$ -dən $100$ -ə qədər neçə ədəd $3$ -ə və ya $4$ -ə qalıqsız bölünür?
Eyni aralıqda neçə ədəd nə $3$ -ə, nə də $4$ -ə bölünür?
$1$ -dən $200$ -ə qədər neçə ədəd $5$ -ə və ya $8$ -ə bölünür?
$1$ -dən $500$ -ə qədər neçə ədəd $2$ -yə və ya $5$ -ə bölünür?
Eyni aralıqda neçə ədəd nə $2$ -yə, nə də $5$ -ə bölünür?
$1$ -dən $100$ -ə qədər neçə ədəd $2$ , $5$ , $7$ -dən heç birinə bölünmür?
$\varphi(24)$ funksiyası neçədir?
$\varphi(50)$ neçədir?
$\varphi(81)$ neçədir?
$\varphi(210)$ neçədir?
$D_2$ , $D_3$ , $D_4$ , $D_5$ qiymətlərini ardıcıl yazın.
$3$ məktub $3$ fərqli zərfə təsadüfi qoyulur; heç bir məktub öz zərfinə düşməsin. Bu hal neçə cür mümkündür?
$6$ nəfərin heç birinin öz papağını götürməməsi ehtimalı (hal sayı) neçə cür ola bilər?
$4$ müxtəlif konfet $2$ uşağa elə paylanmalıdır ki, hər uşaq ən azı bir konfet alsın. Bu, neçə cür paylana bilər?
$6$ müxtəlif kitab $2$ fərqli rəfə elə qoyulmalıdır ki, heç bir rəf boş qalmasın. Bunu neçə cür etmək olar?
$1$ -dən $1000$ -ə qədər neçə natural ədəd $7$ -yə və ya $11$ -ə qalıqsız bölünür?
$|A|=15$ , $|B|=12$ , $|C|=10$ , $|A\cap B|=6$ , $|A\cap C|=5$ , $|B\cap C|=4$ , $|A\cap B\cap C|=2$ . Bu şərtlərlə $|A\cup B\cup C|$ tapın.
Neçə fərqli üçrəqəmli ədədin yazılışında ən azı bir dənə $3$ rəqəmi iştirak edir?
Neçə fərqli dördrəqəmli ədədin yazılışında ən azı bir dənə $0$ rəqəmi var?
$1$ -dən $1000$ -ə qədər neçə ədəd $4$ , $6$ və ya $9$ -dan heç birinə bölünmür?
$5$ nəfərin təsadüfi olaraq əyləşdiyi yerlərdən neçəsində ən azı bir nəfər öz keçmiş yerində əyləşib?
$4$ məktubdan tam olaraq (dəqiq) birinin öz zərfinə düşməsi hadisəsi neçə cür ola bilər?
$1$ -dən $90$ -a qədər neçə natural ədəd $90$ ilə qarşılıqlı sadədir?
$60$ tələbədən $35$ -i riyaziyyat, $30$ -u fizika, $20$ -si isə kimya dərnəyinə gedir; $15$ nəfər riyaziyyat və fizika, $12$ nəfər riyaziyyat və kimya, $10$ nəfər fizika və kimya dərnəyinə, $5$ nəfər isə hər üçünə birdən gedir. (a) Neçə tələbə ən azı bir dərnəyə gedir? (b) Neçə nəfər dərnəklərin heç birinə getmir?
$1$ -dən $1000$ -ə qədər neçə natural ədəd $6$ -ya bölünür?
Neçə beşrəqəmli ədədin yazılışında ən azı bir dənə $9$ rəqəmi var?
$|A|=30$ , $|B|=20$ məlum olarsa, $|A\cup B|$ birləşməsi ən kiçik və ən böyük olmaqla hansı qiymətləri ala bilər?
$1$ -dən $60$ -a qədər neçə ədəd $60$ ilə qarşılıqlı sadədir?
$\varphi(2026)$ neçədir? ( $2026=2\cdot 1013$ və $1013$ sadə ədəddir.)
$5$ müxtəlif konfet $2$ uşağa elə paylanmalıdır ki, hər uşaq ən azı bir konfet alsın. Bunu neçə cür həyata keçirmək olar?
$1$ -dən $100$ -ə qədər neçə ədəd tam kvadrat və ya tam kub hesab olunur?
$4$ müxtəlif oyuncaq $3$ uşağa elə paylanmalıdır ki, hər uşaq ən azı bir oyuncaq alsın. Bu neçə cür paylana bilər?
$D_7$ deranjmanının qiyməti neçədir?

B hissəsi — orta və çətin

İki çoxluq üçün DXP-ni element-töhfə metodu ilə (hər elementin sayılma sayını hesablayaraq) isbat edin.
Üç çoxluq üçün DXP-nin isbatını verin.
$1$ -dən $2000$ -ə qədər neçə natural ədəd $2$ , $3$ , $5$ , $7$ -dən heç birinə qalıqsız bölünmür?
$\{1,\dots,7\}$ çoxluğundan $\{1,2,3,4\}$ çoxluğuna nə qədər süryeksiya (örtən funksiya) təyin etmək olar?
$8$ müxtəlif hədiyyə $4$ uşağa, hər uşaq mütləq ən azı bir hədiyyə alacaq şəkildə neçə fərqli üsulla paylanır?
$D_n=(n-1)(D_{n-1}+D_{n-2})$ rekurrent düsturunu isbat edin və bu düstur vasitəsilə $D_8$ -i hesablayın.
$D_n=nD_{n-1}+(-1)^n$ düsturunun doğruluğunu isbat edin.
$7$ məktubdan dəqiq olaraq $3$ -nün öz zərfinə düşməsi hadisəsi neçə fərqli cür ola bilər?
$8$ məktubdan ən azı $6$ -sının öz aid olduğu zərfə düşməsi hadisəsi neçə cür ola bilər?
Eyler funksiyasının açıq düsturunu, yəni $\varphi(n)=n\prod\left(1-\frac1p\right)$ bərabərliyini DXP tətbiq etməklə isbat edin.
$1$ -dən $3000$ -ə qədər neçə ədəd $3$ , $4$ , $5$ -dən heç birinə qalıqsız bölünmür?
Neçə fərqli altırəqəmli ədədin yazılışında həm $1$ , həm də $2$ rəqəmi iştirak edir?
Neçə fərqli beşrəqəmli ədədin yazılışında $1$ , $2$ , $3$ rəqəmlərinin hər üçü mütləq var?
$\{1,\dots,8\}$ çoxluğunun neçə fərqli permutasiyasında eyni vaxtda $\sigma(i)\ne i$ ( $i=1,2,3,4$ ) məhdudiyyət şərti ödənilir?
$5$ evli cütlük ( $10$ nəfər) bir cərgəyə düzülür. Heç bir cütlük yanaşı (yan-yana) əyləşməsin. Bu neçə cür mümkündür?
$1$ -dən $1000$ -ə qədər neçə natural ədəd nə tam kvadrat, nə tam kub, nə də tam beşinci qüvvətdir?
$1\times 7$ ölçülü zolağı $3$ fərqli rənglə elə boyamaq lazımdır ki, hər rəngdən ən azı bir dəfə istifadə olunsun. Neçə cür boyamaq olar?
$10$ müxtəlif kitab $3$ fərqli rəfə qoyulmalıdır, özü də heç bir rəf tam boş qalmamalıdır. Kitabları neçə cür yerləşdirmək olar?
$\varphi(1000)$ və $\varphi(2025)$ qiymətlərini hesablayın.
$1$ -dən $2026$ -ya qədər olan natural ədədlərdən neçəsi $2026$ ilə qarşılıqlı sadədir?
$9$ məktubdan tam dəqiq olaraq $4$ -nün öz zərfinə düşməsi halı neçə cür ola bilər?
$\{1,\dots,6\}$ çoxluğunun neçə permutasiyasında heç bir tək rəqəm/ədəd öz yerində deyil?
İsbat edin: $\displaystyle\sum_{k=0}^{n}(-1)^k\binom nk (n-k)^n = n!$ . (Göstəriş: Süryeksiya (örtən funksiya) düsturunu xüsusi halda, yəni $k=n$ olduqda tətbiq edin.)
$1$ -dən $1000$ -ə qədər neçə ədəd $30$ ilə qarşılıqlı sadədir?
Neçə fərqli dördrəqəmli ədədin yazılışında $1$ , $2$ və $3$ rəqəmlərindən heç biri yoxdur?
$\varphi(100)$ -ü birbaşa düsturdan istifadə etmədən, məhz DXP metodu ilə hesablayın.
$6$ müxtəlif top $3$ fərqli qutuya, heç bir qutu boş qalmayacaq şəkildə neçə cür yerləşdirilə bilər?
$D_{10}$ ilə $10!/e$ ədədini müqayisə edin və riyazi olaraq $D_n$ -in niyə məhz $n!/e$ -yə ən yaxın tam ədəd olduğunu izah edin.
$3$ evli cütlük ( $6$ nəfər) cərgəyə düzülür. Heç bir cütlük yanaşı gəlməsin. Düzülüş neçə cür mümkündür?
$\{1,\dots,6\}$ çoxluğundan $\{1,2,3,4\}$ çoxluğuna təyin olunan cəmi neçə süryeksiya var?

11Ev tapşırıqlarının cavabları

Qeyd. Necə istifadə etməli? DXP məsələlərində cavabınız verilənlərlə uyğun gəlmirsə, bunun səbəbi demək olar ki, həmişə bu ikisindən biridir: (1) kəsişmələri səhv hesablamısınız (bölünmə məsələlərində ƏKOB çox vaxt unudulur), (2) işarələrdə səhvə yol vermisiniz (+ və - sıralaması). Hesablamanı yenidən aparmazdan əvvəl sırf həmin iki zəif nöqtəni təkrar yoxlayın.

A hissəsi1.

36

7

7

50

50

60

300

200

34

10.

8

11.

20

12.

54

13.

48

14.

1,\,2,\,9,\,44

15.

2

16.

265

17.

14

18.

62

19.

220

20.

24

21.

252

22.

2439

23.

611

24.

76

25.

8

26.

24

27. (a)

53

, (b)

7

28.

166

29.

37\,512

30. ən kiçik

30

, ən böyük

50

31.

16

32.

1012

33.

30

34.

12

35.

36

36.

1854

B hissəsi — cavablar və qısa izahatlar

1. İsbat olundu. Element yalnız $A$ -da / yalnız $B$ -də / hər ikisində olduqda töhfələr $1,1,2-1=1$ olur.
2. İsbat olundu. Element $1$ , $2$ və ya $3$ çoxluğa aid olduqda töhfələr müvafiq olaraq $1$ , $2-1$ , $3-3+1$ olar.
3. $458$ . $2000-(1000+666+400+285)+(333+200+142+133+95+57) -(66+47+28+19)+9$ .
4. $8400$ . $\sum_i(-1)^i\binom4i(4-i)^7 =4^7-4\cdot 3^7+6\cdot 2^7-4$ .
5. $40\,824$ . $4^8-4\cdot 3^8+6\cdot 2^8-4$ .
6. $D_8=14\,833$ . $D_8=7(D_7+D_6)=7(1854+265)=7\cdot 2119$ .
7. İsbat olundu. Düsturdakı cəmlərin fərqində qalan yeganə hədd yalnız $k=n$ həddi olur.
8. $315$ . $\binom73 D_4=35\cdot 9$ .
9. $29$ . $\binom86 D_2+\binom87 D_1+\binom88 D_0=28+0+1$ .
10. İsbat olundu. $A_i=\{x\le n:\ p_i\mid x\}$ qəbul edilir; $k$ sayda sadə ədədin kəsişməsi $n/(p_{i_1}\cdots p_{i_k})$ verir; DXP-nin tamamlayıcı forması həqiqətən hasilin açılışını verir.
11. $1200$ . $3000-(1000+750+600)+(250+200+150)-50$ .
12. $184\,592$ . $900\,000-2\cdot 8\cdot 9^5+7\cdot 8^5$ .
13. $4146$ . $U$ : bütün beşrəqəmli ədədlər $90\,000$ -dir; istənməyən şərt $A_i$ : « $i$ rəqəmi iştirak etmir» ( $i=1,2,3$ ). Bir məhdudiyyət pozulduqda: $8\cdot 9^4=52\,488$ ; iki məhdudiyyət: $7\cdot 8^4=28\,672$ ; üç məhdudiyyət: $6\cdot 7^4=14\,406$ . Tamamlayıcı DXP ilə: $90\,000-3\cdot 52\,488+3\cdot 28\,672-14\,406=4146$ .
14. $24\,024$ . $8!-4\cdot 7!+6\cdot 6!-4\cdot 5!+4! =40\,320-20\,160+4320-480+24$ .
15. $1\,263\,360$ . $\sum_{k=0}^{5}(-1)^k\binom5k 2^k(10-k)!$ .
16. $960$ . Kvadratlar $31$ , kublar $10$ , beşinci qüvvətlər $3$ dənədir; altıncı $3$ , onuncu $1$ , on beşinci $1$ , otuzuncu $1$ dənədir: $1000-(31+10+3)+(3+1+1)-1$ .
17. $1806$ . $3^7-3\cdot 2^7+3$ .
18. $55\,980$ . $3^{10}-3\cdot 2^{10}+3$ .
19. $\varphi(1000)=400$ , $\varphi(2025)=1080$ . $2025=3^4\cdot 5^2$ , $2025\cdot\frac23\cdot\frac45$ .
20. $1012$ . $\varphi(2026)=\varphi(2)\varphi(1013)=1\cdot 1012$ .
21. $5544$ . $\binom94 D_5=126\cdot 44$ .
22. $426$ . Üç məhdudiyyət qoyulur ( $i=1,3,5$ tək mövqeləri üçün): $6!-3\cdot 5!+3\cdot 4!-3!=720-360+72-6$ .
23. İsbat olundu. Nəzərə alın ki, $\{1,\dots,n\}$ çoxluğundan özünə, yəni $\{1,\dots,n\}$ -ə təyin olunan örtən funksiyalar (süryeksiyalar) əslində dəqiq biyeksiyaları, yəni $n!$ sayda permutasiyaları ifadə edir; sadəcə süryeksiya düsturunu $k=n$ xüsusi halı üçün tətbiq edin.
24. $266$ . $30=2\cdot3\cdot5$ ; $1000-(500+333+200)+(166+100+66)-33$ .
25. $2058$ . Birinci rəqəm $\{4,\dots,9\}$ çoxluğundan seçilir — $6$ imkan; qalan üç mövqe isə $\{0,4,\dots,9\}$ çoxluğundan seçilir — $7$ imkan: yəni $6\cdot 7^3$ .
26. $40$ . $100-(50+20)+10$ .
27. $540$ . $3^6-3\cdot 2^6+3$ .
28. $D_{10}=1\,334\,961$ , $10!/e\approx 1\,334\,960{,}92$ . Aşkar edə bilərsiniz ki, $D_n$ ilə $n!/e$ ədədləri arasındakı qalıq fərq $\left|\sum_{k>n} (-1)^k n!/k!\right|<\frac{1}{n+1}\cdot\frac{n+1}{n}\le\frac12$ (istənilən $n\ge 1$ üçün) məhdudiyyətini ödəyir, deməli doğrudan da $D_n$ ən yaxın tam ədəddir.
29. $240$ . $6!-3\cdot 2\cdot 5!+3\cdot 4\cdot 4!-8\cdot 3! =720-720+288-48$ .
30. $1560$ . $4^6-4\cdot 3^6+6\cdot 2^6-4$ .