Artikel ini akan menumpukan pada bahagian khas matematik yang dipanggil kombinatorik. Formula, peraturan, contoh penyelesaian masalah - semua ini boleh anda temui di sini dengan membaca artikel hingga akhir.
Jadi, apakah bahagian ini? Kombinatorik memperkatakan isu mengira sebarang objek. Tetapi dalam kes ini, objek bukan plum, pear atau epal, tetapi sesuatu yang lain. Kombinatorik membantu kita mencari kebarangkalian sesuatu peristiwa. Contohnya, semasa bermain kad, apakah kebarangkalian pihak lawan mempunyai kad terup? Atau contoh sedemikian - apakah kebarangkalian anda akan mendapat warna putih tepat dari beg dua puluh bola? Untuk tugasan seperti ini kita perlu mengetahui sekurang-kurangnya asas bahagian matematik ini.
Konfigurasi gabungan
Memandangkan isu konsep asas dan formula kombinatorik, kita tidak boleh tidak memberi perhatian kepada konfigurasi gabungan. Mereka digunakan bukan sahaja untuk perumusan, tetapi juga untuk menyelesaikan pelbagai masalah gabungan. Contoh model sedemikian ialah:
- peletakan;
- permutasi;
- kombinasi;
- komposisi nombor;
- pecah nombor.
Kita akan bercakap tentang tiga yang pertama dengan lebih terperinci kemudian, tetapi kita akan memberi perhatian kepada gubahan dan pembahagian dalam bahagian ini. Apabila mereka bercakap tentang komposisi nombor tertentu (katakan, a), mereka bermaksud perwakilan nombor a sebagai jumlah tertib beberapa nombor positif. Dan perpecahan ialah jumlah yang tidak tertib.
Bahagian
Sebelum kita pergi terus ke formula kombinatorik dan pertimbangan masalah, adalah wajar memberi perhatian kepada fakta bahawa kombinatorik, seperti bahagian matematik yang lain, mempunyai subseksyen sendiri. Ini termasuk:
- enumeratif;
- struktur;
- melampau;
- Teori Ramsey;
- kebarangkalian;
- topologi;
- tak terhingga.
Dalam kes pertama, kita bercakap tentang kombinatorik enumeratif, masalah mempertimbangkan penghitungan atau pengiraan konfigurasi berbeza yang dibentuk oleh unsur set. Sebagai peraturan, beberapa sekatan dikenakan ke atas set ini (kebolehbezaan, tidak dapat dibezakan, kemungkinan pengulangan, dan sebagainya). Dan bilangan konfigurasi ini dikira menggunakan peraturan penambahan atau pendaraban, yang akan kita bincangkan kemudian. Kombinatorik struktur termasuk teori graf dan matroid. Contoh masalah kombinatorik ekstrem ialah apakah dimensi terbesar graf yang memenuhi sifat berikut… Dalam perenggan keempat, kami menyebut teori Ramsey, yang mengkaji kehadiran struktur biasa dalam konfigurasi rawak. Kebarangkaliankombinatorik dapat menjawab soalan - apakah kebarangkalian set tertentu mempunyai sifat tertentu. Seperti yang anda fikirkan, gabungan topologi menggunakan kaedah dalam topologi. Dan akhirnya, titik ketujuh - kombinatorik tak terhingga mengkaji penggunaan kaedah kombinatorik pada set tak terhingga.
Peraturan tambahan
Di antara formula kombinatorik, seseorang boleh menemui formula yang agak mudah, yang telah lama kita kenali. Contohnya ialah peraturan jumlah. Katakan kita diberi dua tindakan (C dan E), jika ia saling eksklusif, tindakan C boleh dilakukan dalam beberapa cara (contohnya, a), dan tindakan E boleh dilakukan dalam b-ways, maka mana-mana daripadanya (C atau E) boleh dilakukan dengan cara a + b.
Secara teori, ini agak sukar untuk difahami, kami akan cuba menyampaikan keseluruhan perkara dengan contoh mudah. Mari kita ambil purata bilangan pelajar dalam satu kelas - katakan dua puluh lima. Antaranya ialah lima belas perempuan dan sepuluh lelaki. Seorang atendan ditugaskan ke kelas setiap hari. Berapa banyak cara yang ada untuk menetapkan atendan kelas hari ini? Penyelesaian masalah ini agak mudah, kami akan menggunakan peraturan penambahan. Teks tugasan tidak mengatakan bahawa hanya lelaki atau perempuan sahaja boleh bertugas. Oleh itu, boleh jadi mana-mana daripada lima belas perempuan atau mana-mana daripada sepuluh lelaki. Menggunakan peraturan jumlah, kami mendapat contoh yang agak mudah yang boleh dihadapi oleh pelajar sekolah rendah dengan mudah: 15 + 10. Setelah mengira, kami mendapat jawapan: dua puluh lima. Iaitu, hanya ada dua puluh lima caratetapkan kelas bertugas untuk hari ini.
Peraturan pendaraban
Peraturan pendaraban juga tergolong dalam formula asas kombinatorik. Mari kita mulakan dengan teori. Katakan kita perlu melakukan beberapa tindakan (a): tindakan pertama dilakukan dalam 1 cara, yang kedua - dalam 2 cara, yang ketiga - dalam 3 cara, dan seterusnya sehingga tindakan a terakhir dilakukan dengan cara yang sama. Kemudian semua tindakan ini (yang kita ada jumlahnya) boleh dilakukan dalam N cara. Bagaimana untuk mengira N yang tidak diketahui? Formula akan membantu kami dengan ini: N \u003d c1c2c3…ca.
Sekali lagi, tiada yang jelas dalam teori, mari kita beralih kepada contoh mudah untuk menggunakan peraturan pendaraban. Mari kita ambil kelas yang sama dengan dua puluh lima orang, di mana lima belas perempuan dan sepuluh lelaki belajar. Cuma kali ini kita perlu memilih dua orang atendan. Mereka boleh sama ada lelaki atau perempuan sahaja, atau lelaki dengan perempuan. Kami beralih kepada penyelesaian asas masalah. Kami memilih atendan pertama, seperti yang kami putuskan dalam perenggan terakhir, kami mendapat dua puluh lima pilihan yang mungkin. Orang kedua yang bertugas boleh menjadi mana-mana orang yang tinggal. Kami mempunyai dua puluh lima pelajar, kami memilih seorang, yang bermaksud bahawa mana-mana daripada dua puluh empat orang yang tinggal boleh menjadi yang kedua bertugas. Akhirnya, kami menggunakan peraturan pendaraban dan mendapati bahawa dua atendan boleh dipilih dalam enam ratus cara. Kami mendapat nombor ini dengan mendarab dua puluh lima dan dua puluh empat.
Tukar
Sekarang kita akan mempertimbangkan satu lagi formula kombinatorik. Dalam bahagian artikel ini, kamiMari kita bercakap tentang pilih atur. Pertimbangkan masalah dengan segera dengan contoh. Mari kita ambil bola biliard, kita ada nombor ke-n. Kita perlu mengira: berapa banyak pilihan yang ada untuk menyusunnya dalam satu baris, iaitu, untuk membuat set tertib.
Mari kita mulakan, jika kita tidak mempunyai bola, maka kita juga mempunyai pilihan penempatan sifar. Dan jika kita mempunyai satu bola, maka susunannya juga sama (secara matematik, ini boleh ditulis seperti berikut: Р1=1). Dua bola boleh disusun dalam dua cara berbeza: 1, 2 dan 2, 1. Oleh itu, Р2=2. Tiga bola boleh disusun dalam enam cara (Р3=6): 1, 2, 3; 1, 3, 2; 2, 1, 3; 2, 3, 1; 3, 2, 1; 3, 1, 2. Dan jika tidak ada tiga bola seperti itu, tetapi sepuluh atau lima belas? Untuk menyenaraikan semua pilihan yang mungkin adalah sangat panjang, maka kombinatorik datang untuk membantu kami. Formula pilih atur akan membantu kami mencari jawapan kepada soalan kami. Pn=nP(n-1). Jika kita cuba untuk memudahkan formula, kita mendapat: Pn=n (n - 1) … 21. Dan ini adalah hasil darab nombor asli pertama. Nombor sedemikian dipanggil faktorial, dan dilambangkan sebagai n!
Mari kita pertimbangkan masalahnya. Pemimpin setiap pagi membina detasmennya dalam satu barisan (dua puluh orang). Terdapat tiga kawan baik dalam detasmen - Kostya, Sasha dan Lesha. Apakah kebarangkalian bahawa mereka akan berada di sebelah antara satu sama lain? Untuk mencari jawapan kepada soalan, anda perlu membahagikan kebarangkalian hasil "baik" dengan jumlah bilangan hasil. Jumlah bilangan pilih atur ialah 20!=2.5 quintillion. Bagaimana untuk mengira bilangan hasil "baik"? Katakan bahawa Kostya, Sasha dan Lesha adalah seorang superman. Kemudian kamiKami hanya mempunyai lapan belas mata pelajaran. Bilangan pilih atur dalam kes ini ialah 18=6.5 kuadrilion. Dengan semua ini, Kostya, Sasha dan Lesha boleh sewenang-wenangnya bergerak sesama mereka dalam rangkap tiga yang tidak boleh dibahagikan, dan ini adalah 3 lagi!=6 pilihan. Jadi kami mempunyai 18 buruj "baik" secara keseluruhan!3! Kita hanya perlu mencari kebarangkalian yang diingini: (18!3!) / 20! Iaitu kira-kira 0.016. Jika ditukar kepada peratusan, ia ternyata hanya 1.6%.
Penginapan
Sekarang kita akan mempertimbangkan satu lagi formula kombinatorik yang sangat penting dan perlu. Penginapan ialah keluaran kami yang seterusnya, yang kami cadangkan anda pertimbangkan dalam bahagian artikel ini. Kita akan menjadi lebih rumit. Mari kita anggap bahawa kita ingin mempertimbangkan pilih atur yang mungkin, hanya bukan dari keseluruhan set (n), tetapi dari yang lebih kecil (m). Iaitu, kami mempertimbangkan pilih atur bagi n item dengan m.
Formula asas kombinatorik bukan sahaja harus dihafal, tetapi difahami. Walaupun pada hakikatnya ia menjadi lebih rumit, kerana kita tidak mempunyai satu parameter, tetapi dua. Katakan bahawa m \u003d 1, kemudian A \u003d 1, m \u003d 2, kemudian A \u003d n(n - 1). Jika kita memudahkan lagi formula dan beralih kepada notasi menggunakan faktorial, kita mendapat formula yang agak ringkas: A \u003d n! / (n - m)!
Gabungan
Kami telah mempertimbangkan hampir semua formula asas kombinatorik dengan contoh. Sekarang mari kita beralih ke peringkat akhir mempertimbangkan kursus asas kombinatorik - mengenali gabungan. Sekarang kita akan memilih m item daripada n yang kita ada, manakala kita akan memilih kesemuanya dalam semua cara yang mungkin. Jadi bagaimana ini berbeza dengan penginapan? Kami tidak akanpertimbangkan perintah. Set tidak tertib ini akan menjadi gabungan.
Segera perkenalkan tatatanda: C. Kami mengambil penempatan bola m daripada n. Kami berhenti memberi perhatian kepada pesanan dan mendapat kombinasi berulang. Untuk mendapatkan bilangan gabungan, kita perlu membahagikan bilangan peletakan dengan m! (m faktorial). Iaitu, C \u003d A / m! Oleh itu, terdapat beberapa cara untuk memilih daripada n bola, lebih kurang sama dengan berapa banyak untuk memilih hampir semua. Terdapat ungkapan logik untuk ini: memilih sedikit adalah sama dengan membuang hampir segala-galanya. Ia juga penting untuk menyatakan pada ketika ini bahawa bilangan maksimum gabungan boleh dicapai apabila cuba memilih separuh daripada item.
Bagaimana untuk memilih formula untuk menyelesaikan masalah?
Kami telah meneliti secara terperinci formula asas kombinatorik: peletakan, pilih atur dan gabungan. Sekarang tugas kami adalah untuk memudahkan pilihan formula yang diperlukan untuk menyelesaikan masalah dalam kombinatorik. Anda boleh menggunakan skema yang agak mudah berikut:
- Tanya diri anda: adakah susunan elemen diambil kira dalam teks masalah?
- Jika jawapannya tidak, maka gunakan formula gabungan (C=n! / (m!(n - m)!)).
- Jika jawapannya tidak, maka anda perlu menjawab satu lagi soalan: adakah semua elemen termasuk dalam gabungan?
- Jika jawapannya ya, gunakan formula pilih atur (P=n!).
- Jika jawapannya tidak, maka gunakan formula peruntukan (A=n! / (n - m)!).
Contoh
Kami telah mempertimbangkan unsur kombinatorik, formula dan beberapa isu lain. Sekarang mari kita beralih kepadamempertimbangkan masalah sebenar. Bayangkan anda mempunyai kiwi, oren dan pisang di hadapan anda.
Soalan satu: dalam berapa banyak cara ia boleh disusun semula? Untuk melakukan ini, kami menggunakan formula pilih atur: P=3!=6 cara.
Soalan dua: dalam berapa cara satu buah boleh dipilih? Ini jelas, kami hanya mempunyai tiga pilihan - pilih kiwi, oren atau pisang, tetapi kami menggunakan formula gabungan: C \u003d 3! / (2!1!)=3.
Soalan tiga: dalam berapa cara dua buah boleh dipilih? Apakah pilihan yang kita ada? kiwi dan oren; kiwi dan pisang; oren dan pisang. Iaitu, tiga pilihan, tetapi ini mudah untuk diperiksa menggunakan formula gabungan: C \u003d 3! / (1!2!)=3
Soalan empat: dalam berapa cara tiga buah boleh dipilih? Seperti yang anda lihat, hanya ada satu cara untuk memilih tiga buah: ambil kiwi, oren dan pisang. C=3! / (0!3!)=1.
Soalan lima: berapa banyak cara anda boleh memilih sekurang-kurangnya satu buah? Keadaan ini menunjukkan bahawa kita boleh mengambil satu, dua atau ketiga-tiga buah. Oleh itu, kami menambah C1 + C2 + C3=3 + 3 + 1=7. Iaitu, kami mempunyai tujuh cara untuk mengambil sekurang-kurangnya sekeping buah dari meja.
