Bu məqalədə riyaziyyatın kombinatorika adlı xüsusi bölməsinə diqqət yetiriləcək. Düsturlar, qaydalar, problemin həlli nümunələri - bütün bunları məqaləni sona qədər oxumaqla burada tapa bilərsiniz.
Bəs bu bölmə nədir? Kombinatorika hər hansı obyektlərin sayılması məsələsi ilə məşğul olur. Ancaq bu vəziyyətdə obyektlər gavalı, armud və ya alma deyil, başqa bir şeydir. Kombinatorika bizə hadisənin baş vermə ehtimalını tapmağa kömək edir. Məsələn, kart oynayarkən rəqibin kozırının olması ehtimalı nə qədərdir? Və ya belə bir misal - iyirmi topdan ibarət bir çantadan tam ağ alma ehtimalınız nədir? Məhz bu cür tapşırıqlar üçün riyaziyyatın bu bölməsinin ən azı əsaslarını bilməliyik.
Kombinator konfiqurasiyaları
Kombinatorikanın əsas anlayışları və düsturları məsələsini nəzərə alsaq, kombinatorik konfiqurasiyalara diqqət yetirməyə bilmərik. Onlardan təkcə formalaşdırma üçün deyil, həm də müxtəlif kombinator məsələlərin həlli üçün istifadə olunur. Belə modellərə misal ola bilər:
- yerləşdirmə;
- permütasyon;
- birləşməsi;
- nömrə tərkibi;
- bölünmüş nömrə.
İlk üçlük haqqında daha sonra ətraflı danışacağıq, lakin bu bölmədə kompozisiyaya və parçalanmaya diqqət yetirəcəyik. Müəyyən bir ədədin (məsələn, a) tərkibi haqqında danışarkən, a ədədinin bəzi müsbət ədədlərin nizamlı cəmi kimi təqdim edilməsini nəzərdə tuturlar. Bölmə isə sırasız cəmidir.
Bölmələr
Birbaşa kombinatorikanın düsturlarına və məsələlərin nəzərdən keçirilməsinə keçməzdən əvvəl riyaziyyatın digər bölmələri kimi kombinatorikanın da öz yarımbölmələrinə malik olduğuna diqqət yetirməyə dəyər. Bunlara daxildir:
- sadalayıcı;
- struktur;
- ekstremal;
- Ramsey nəzəriyyəsi;
- ehtimal;
- topoloji;
- sonsuz.
Birinci halda, biz sadalama kombinatorikasından danışırıq, problemlər çoxluq elementləri ilə formalaşan müxtəlif konfiqurasiyaların sadalanması və ya hesablanmasından gedir. Bir qayda olaraq, bu çoxluqlara bəzi məhdudiyyətlər qoyulur (fərqlənmə, fərqlənməmək, təkrarlanma imkanı və s.). Və bu konfiqurasiyaların sayı bir az sonra danışacağımız əlavə və ya vurma qaydası ilə hesablanır. Struktur kombinatorikaya qrafiklər və matroidlər nəzəriyyələri daxildir. Ekstremal kombinatorika məsələsinə misal olaraq aşağıdakı xassələri ödəyən qrafikin ən böyük ölçüsü nədir… Dördüncü abzasda təsadüfi konfiqurasiyalarda nizamlı strukturların mövcudluğunu öyrənən Ramsey nəzəriyyəsini qeyd etdik. Ehtimalkombinatorika sualına cavab verə bilir - verilmiş çoxluğun müəyyən bir xassə olması ehtimalı nədir. Təxmin etdiyiniz kimi, topoloji kombinatorika topologiyada metodlar tətbiq edir. Və nəhayət, yeddinci nöqtə - sonsuz kombinatorika kombinatorika üsullarının sonsuz çoxluqlara tətbiqini öyrənir.
Əlavə qaydası
Kombinatorikanın düsturları arasında çoxdan tanış olduğumuz kifayət qədər sadə düsturlara rast gəlmək olar. Məsələn, cəmi qaydası. Tutaq ki, bizə iki hərəkət (C və E) verilmişdir, əgər onlar bir-birini istisna edirsə, C hərəkəti bir neçə yolla edilə bilər (məsələn, a), E hərəkəti isə b üsulları ilə edilə bilər, onda onlardan hər hansı biri (C) və ya E) a + b üsulları ilə edilə bilər.
Nəzəri cəhətdən bunu başa düşmək olduqca çətindir, biz sadə bir misalla bütün fikri çatdırmağa çalışacağıq. Bir sinifdəki şagirdlərin orta sayını götürək - tutaq ki, iyirmi beşdir. Onların arasında on beş qız və on oğlan var. Gündəlik sinifə bir növbətçi təyin olunur. Bu gün sinif növbətçisi təyin etməyin neçə yolu var? Problemin həlli olduqca sadədir, biz əlavə qaydasına müraciət edəcəyik. Tapşırıq mətnində deyilmir ki, yalnız oğlanlar və ya yalnız qızlar növbətçi ola bilər. Buna görə də, bu, on beş qızdan və ya on oğlandan hər hansı biri ola bilər. Cəmi qaydanı tətbiq edərək, ibtidai məktəb şagirdinin asanlıqla öhdəsindən gələ biləcəyi kifayət qədər sadə bir nümunə alırıq: 15 + 10. Hesabladıqdan sonra cavabı alırıq: iyirmi beş. Yəni cəmi iyirmi beş yol varbu gün üçün növbətçi sinif təyin edin.
Çarpma qaydası
Vurma qaydası da kombinatorikanın əsas düsturlarına aiddir. Nəzəriyyə ilə başlayaq. Tutaq ki, bir neçə hərəkəti yerinə yetirməliyik (a): birinci hərəkət 1 üsulla, ikincisi - 2 yolla, üçüncüsü - 3 şəkildə və s. sonuncu a-hərəkəti sa üsullarla yerinə yetirilənə qədər. Onda bütün bu hərəkətlər (onların cəmi var) N yolla yerinə yetirilə bilər. Naməlum N necə hesablanır? Formula bu işdə bizə kömək edəcək: N \u003d c1c2c3…ca.
Yenə nəzəri cəhətdən heç nə aydın deyil, keçək vurma qaydasının tətbiqinin sadə nümunəsinə. On beş qız və on oğlanın oxuduğu iyirmi beş nəfərdən ibarət eyni sinfi götürək. Yalnız bu dəfə iki xidmətçi seçməliyik. Onlar ya yalnız oğlanlar və ya qızlar, ya da bir qızla bir oğlan ola bilər. Problemin elementar həllinə müraciət edirik. İlk xidmətçini seçirik, son paraqrafda qərar verdiyimiz kimi, iyirmi beş mümkün variant alırıq. İkinci növbətçi qalan şəxslərdən hər hansı biri ola bilər. İyirmi beş tələbəmiz var idi, birini seçdik, bu o deməkdir ki, qalan iyirmi dörd nəfərdən hər hansı biri ikinci növbətçi ola bilər. Nəhayət, vurma qaydasını tətbiq edirik və tapırıq ki, iki köməkçi altı yüz yolla seçilə bilər. Bu rəqəmi iyirmi beş və iyirmi dördü vurmaqla əldə etdik.
Dəyişin
İndi biz daha bir kombinatorik düstur nəzərdən keçirəcəyik. Məqalənin bu hissəsində bizPermütasyonlar haqqında danışaq. Problemi dərhal bir nümunə ilə nəzərdən keçirin. Bilyard toplarını götürək, onlardan n-ci ədədimiz var. Hesablamalıyıq: onları ard-arda yerləşdirmək, yəni sifarişli dəst hazırlamaq üçün neçə variant var.
Başlayaq, əgər toplarımız yoxdursa, onda yerləşdirmə seçimlərimiz də sıfırdır. Bir topumuz varsa, tənzimləmə də eynidir (riyazi olaraq bunu aşağıdakı kimi yazmaq olar: Р1=1). İki top iki müxtəlif şəkildə düzülə bilər: 1, 2 və 2, 1. Buna görə də, Р2=2. Üç top altı şəkildə düzülə bilər (Р3=6): 1, 2, 3; 1, 3, 2; 2, 1, 3; 2, 3, 1; 3, 2, 1; 3, 1, 2. Bəs üç belə top yoxdursa, on və ya on beşdir? Bütün mümkün variantları sadalamaq çox uzundur, onda kombinatorika köməyimizə gəlir. Permutasiya düsturu bizə sualımızın cavabını tapmağa kömək edəcək. Pn=nP(n-1). Düsturu sadələşdirməyə çalışsaq, alırıq: Pn=n (n - 1) … 21. Və bu, ilk natural ədədlərin məhsuludur. Belə ədəd faktorial adlanır və n kimi işarələnir!
Problemi nəzərdən keçirək. Rəhbər hər səhər öz dəstəsini bir sıra (iyirmi nəfər) qurur. Dəstədə üç ən yaxşı dost var - Kostya, Saşa və Leşa. Onların bir-birinin yanında olma ehtimalı nədir? Sualın cavabını tapmaq üçün “yaxşı” nəticənin olma ehtimalını nəticələrin ümumi sayına bölmək lazımdır. Permütasyonların ümumi sayı 20-dir!=2,5 kvintilyon. "Yaxşı" nəticələrin sayını necə hesablamaq olar? Tutaq ki, Kostya, Saşa və Leşa bir supermendir. Bizdən sonraBizdə cəmi on səkkiz fənn var. Bu halda permütasyonların sayı 18=6,5 katrilyondur. Bütün bunlarla, Kostya, Saşa və Lesha öz aralarında bölünməz üçlükdə özbaşına hərəkət edə bilərlər və bu daha 3-dür!=6 seçim. Beləliklə, cəmi 18 "yaxşı" bürcümüz var!3! Sadəcə, istədiyimiz ehtimalı tapmalıyıq: (18!3!) / 20! Bu, təxminən 0,016-dır. Faza çevrildikdə, cəmi 1,6% olur.
Yerləmə
İndi biz başqa bir çox vacib və zəruri kombinatorika düsturunu nəzərdən keçirəcəyik. Yerləşdirmə məqalənin bu bölməsində nəzərdən keçirməyi təklif etdiyimiz növbəti məsələmizdir. Biz daha da mürəkkəbləşəcəyik. Tutaq ki, biz yalnız bütün çoxluqdan (n) deyil, daha kiçikdən (m) mümkün dəyişmələri nəzərdən keçirmək istəyirik. Yəni n elementin m ilə dəyişdirilməsini nəzərdən keçiririk.
Kombinatorikanın əsas düsturlarını sadəcə əzbərləmək deyil, həm də başa düşmək lazımdır. Onların daha mürəkkəb olmasına baxmayaraq, bizdə bir deyil, iki parametr var. Tutaq ki, m \u003d 1, sonra A \u003d 1, m \u003d 2, sonra A \u003d n(n - 1). Düsturu daha da sadələşdirsək və faktoriallardan istifadə edərək nota keçsək, olduqca qısa bir düstur alırıq: A \u003d n! / (n - m)!
Birləşmə
Biz kombinatorikanın demək olar ki, bütün əsas düsturlarını misallarla nəzərdən keçirdik. İndi kombinatorikanın əsas kursunu nəzərdən keçirməyin son mərhələsinə - birləşmə ilə tanışlığa keçək. İndi əlimizdə olan n-dən m element seçəcəyik, halbuki onların hamısını bütün mümkün üsullarla seçəcəyik. Bəs bu yerləşmədən nə ilə fərqlənir? etməyəcəyiknizamı nəzərdən keçirin. Bu sıralanmamış dəst kombinasiya olacaq.
Dərhal qeydi təqdim edin: C. Biz n-dən m topun yerlərini alırıq. Biz sifarişə diqqət yetirməyi dayandırırıq və təkrar kombinasiyalar alırıq. Kombinasiyaların sayını əldə etmək üçün yerləşdirmə sayını m-ə bölmək lazımdır! (m faktorial). Yəni C \u003d A / m! Beləliklə, demək olar ki, hər şeyi seçmək üçün təxminən bərabər olan n topdan seçim etməyin bir neçə yolu var. Bunun məntiqi ifadəsi var: az seçmək, demək olar ki, hər şeyi atmaqla bərabərdir. Bu məqamda onu da qeyd etmək lazımdır ki, elementlərin yarısını seçərkən maksimum kombinasiya sayı əldə edilə bilər.
Problemi həll etmək üçün düstur necə seçilməlidir?
Kombinatorikanın əsas düsturlarını ətraflı araşdırdıq: yerləşdirmə, dəyişdirmə və birləşmə. İndi bizim vəzifəmiz kombinatorikada problemin həlli üçün lazımi düsturun seçilməsini asanlaşdırmaqdır. Aşağıdakı olduqca sadə sxemdən istifadə edə bilərsiniz:
- Özünüzə sual verin: problemin mətnində elementlərin sırası nəzərə alınıbmı?
- Cavab xeyrdirsə, kombinasiya düsturundan istifadə edin (C=n! / (m!(n - m)!)).
- Cavab xeyrdirsə, o zaman daha bir suala cavab verməlisiniz: bütün elementlər kombinasiyaya daxildirmi?
- Cavab bəlidirsə, dəyişdirmə düsturundan istifadə edin (P=n!).
- Cavab xeyrdirsə, o zaman ayırma düsturundan istifadə edin (A=n! / (n - m)!).
Nümunə
Biz kombinatorikanın elementlərini, düsturları və bəzi digər məsələləri nəzərdən keçirdik. İndi isə keçəkreal problemi nəzərə alaraq. Təsəvvür edin ki, qarşınızda kivi, portağal və banan var.
Birinci sual: onları neçə yolla yenidən təşkil etmək olar? Bunun üçün biz permutasiya düsturundan istifadə edirik: P=3!=6 yol.
İkinci sual: bir meyvəni neçə yolla seçmək olar? Bu aydındır, yalnız üç seçimimiz var - kivi, portağal və ya banan seçin, lakin birləşmə düsturunu tətbiq edirik: C \u003d 3! / (2!1!)=3.
Sual üçüncü: iki meyvəni neçə yolla seçmək olar? Hansı variantlarımız var? kivi və portağal; kivi və banan; portağal və banan. Yəni üç seçim, lakin birləşmə düsturundan istifadə edərək bunu yoxlamaq asandır: C \u003d 3! / (1!2!)=3
Dördüncü sual: üç meyvəni neçə yolla seçmək olar? Gördüyünüz kimi, üç meyvə seçmək üçün yalnız bir yol var: bir kivi, bir portağal və bir banan götürün. C=3! / (0!3!)=1.
Beşinci sual: ən azı bir meyvəni neçə yolla seçə bilərsiniz? Bu şərt bir, iki və ya hər üç meyvəni götürə biləcəyimizi nəzərdə tutur. Buna görə də C1 + C2 + C3=3 + 3 + 1=7 əlavə edirik. Yəni süfrədən ən azı bir meyvə götürmək üçün yeddi yolumuz var.
