Artikel ini akan fokus pada bagian khusus matematika yang disebut kombinatorik. Rumus, aturan, contoh pemecahan masalah - semua ini dapat Anda temukan di sini dengan membaca artikel sampai akhir.
Jadi, apa bagian ini? Combinatorics berkaitan dengan masalah menghitung objek apapun. Tetapi dalam kasus ini, objeknya bukanlah buah prem, pir atau apel, tetapi sesuatu yang lain. Kombinatorik membantu kita menemukan peluang suatu kejadian. Misalnya, saat bermain kartu, berapa peluang lawan memiliki kartu truf? Atau contoh seperti itu - berapa probabilitas Anda akan mendapatkan putih persis dari sekantong dua puluh bola? Untuk tugas-tugas seperti inilah kita perlu mengetahui setidaknya dasar-dasar dari bagian matematika ini.
Konfigurasi kombinatorial
Mempertimbangkan masalah konsep dasar dan rumus kombinatorik, kita tidak bisa tidak memperhatikan konfigurasi kombinatorial. Mereka digunakan tidak hanya untuk formulasi, tetapi juga untuk memecahkan berbagai masalah kombinatorial. Contoh model tersebut adalah:
- penempatan;
- permutasi;
- kombinasi;
- komposisi angka;
- bagi nomor.
Kita akan membicarakan tiga yang pertama secara lebih rinci nanti, tetapi kita akan memperhatikan komposisi dan pemisahan di bagian ini. Ketika mereka berbicara tentang komposisi bilangan tertentu (misalnya, a), yang mereka maksud adalah representasi bilangan a sebagai jumlah terurut dari beberapa bilangan positif. Dan pembagian adalah jumlah yang tidak berurutan.
Bagian
Sebelum kita langsung ke rumus kombinatorik dan pertimbangan masalah, ada baiknya memperhatikan fakta bahwa kombinatorik, seperti bagian matematika lainnya, memiliki subbagiannya sendiri. Ini termasuk:
- enumeratif;
- struktural;
- ekstrem;
- Teori Ramsey;
- probabilistik;
- topologi;
- tak terbatas.
Dalam kasus pertama, kita berbicara tentang kombinatorik enumeratif, masalah mempertimbangkan enumerasi atau penghitungan konfigurasi berbeda yang dibentuk oleh elemen himpunan. Sebagai aturan, beberapa batasan dikenakan pada set ini (dapat dibedakan, tidak dapat dibedakan, kemungkinan pengulangan, dan sebagainya). Dan jumlah konfigurasi ini dihitung menggunakan aturan penjumlahan atau perkalian, yang akan kita bicarakan nanti. Kombinatorik struktural meliputi teori graf dan matroid. Contoh masalah kombinatorik ekstrem adalah dimensi terbesar dari graf yang memenuhi sifat-sifat berikut… Pada paragraf keempat, kami menyebutkan teori Ramsey, yang mempelajari keberadaan struktur beraturan dalam konfigurasi acak. Probabilistikkombinatorika mampu menjawab pertanyaan - berapa probabilitas bahwa himpunan yang diberikan memiliki properti tertentu. Seperti yang Anda duga, kombinatorik topologi menerapkan metode dalam topologi. Dan akhirnya, poin ketujuh - kombinatorika tak hingga mempelajari penerapan metode kombinatorik pada himpunan tak hingga.
Aturan penambahan
Di antara formula kombinatorik, seseorang dapat menemukan yang cukup sederhana, yang sudah lama kita kenal. Contohnya adalah aturan penjumlahan. Misalkan kita diberikan dua tindakan (C dan E), jika keduanya saling lepas, tindakan C dapat dilakukan dengan beberapa cara (misalnya, a), dan tindakan E dapat dilakukan dengan b-cara, maka salah satu dari mereka (C atau E) dapat dilakukan dengan cara a + b.
Secara teori, ini cukup sulit untuk dipahami, kami akan mencoba menyampaikan keseluruhan poin dengan contoh sederhana. Mari kita ambil rata-rata jumlah siswa dalam satu kelas - katakanlah dua puluh lima. Di antara mereka ada lima belas perempuan dan sepuluh laki-laki. Satu petugas ditugaskan ke kelas setiap hari. Ada berapa cara untuk menugaskan seorang petugas kelas hari ini? Solusi untuk masalah ini cukup sederhana, kami akan menggunakan aturan penambahan. Teks tugas tidak mengatakan bahwa hanya anak laki-laki atau perempuan saja yang boleh bertugas. Oleh karena itu, itu bisa menjadi salah satu dari lima belas gadis atau salah satu dari sepuluh anak laki-laki. Menerapkan aturan penjumlahan, kita mendapatkan contoh yang cukup sederhana yang dapat dengan mudah diatasi oleh siswa sekolah dasar: 15 + 10. Setelah menghitung, kita mendapatkan jawabannya: dua puluh lima. Artinya, hanya ada dua puluh lima caratetapkan kelas tugas untuk hari ini.
Aturan perkalian
Aturan perkalian juga termasuk dalam rumus dasar kombinatorik. Mari kita mulai dengan teori. Misalkan kita perlu melakukan beberapa tindakan (a): tindakan pertama dilakukan dengan 1 cara, yang kedua - dengan 2 cara, yang ketiga - dengan 3 cara, dan seterusnya hingga tindakan terakhir dilakukan dengan cara yang sama. Kemudian semua tindakan ini (yang kita miliki totalnya) dapat dilakukan dalam N cara. Bagaimana cara menghitung N yang tidak diketahui? Rumusnya akan membantu kita dalam hal ini: N \u003d c1c2c3…ca.
Sekali lagi, secara teori tidak ada yang jelas, mari kita beralih ke contoh sederhana penerapan aturan perkalian. Mari kita ambil kelas yang sama yang terdiri dari dua puluh lima orang, di mana lima belas anak perempuan dan sepuluh anak laki-laki belajar. Hanya saja kali ini kita perlu memilih dua pelayan. Mereka bisa saja laki-laki atau perempuan, atau laki-laki dengan perempuan. Kami beralih ke solusi dasar dari masalah. Kami memilih petugas pertama, seperti yang kami putuskan di paragraf terakhir, kami mendapatkan dua puluh lima opsi yang memungkinkan. Orang kedua yang bertugas dapat menjadi salah satu dari orang-orang yang tersisa. Kami memiliki dua puluh lima siswa, kami memilih satu, yang berarti bahwa salah satu dari dua puluh empat orang yang tersisa dapat menjadi yang kedua yang bertugas. Akhirnya, kami menerapkan aturan perkalian dan menemukan bahwa dua petugas dapat dipilih dalam enam ratus cara. Kami mendapatkan angka ini dengan mengalikan dua puluh lima dan dua puluh empat.
Tukar
Sekarang kita akan mempertimbangkan satu lagi rumus kombinatorik. Di bagian artikel ini, kamiMari kita bicara tentang permutasi. Pertimbangkan masalahnya segera dengan sebuah contoh. Mari kita ambil bola biliar, kita memiliki nomor ke-n. Kita perlu menghitung: berapa banyak opsi yang ada untuk menyusunnya dalam satu baris, yaitu membuat himpunan terurut.
Mari kita mulai, jika kita tidak memiliki nyali, maka kita juga tidak memiliki opsi penempatan. Dan jika kita memiliki satu bola, maka susunannya juga sama (secara matematis dapat ditulis sebagai berikut: 1=1). Dua bola dapat disusun dengan dua cara yang berbeda: 1, 2 dan 2, 1. Oleh karena itu, 2=2. Tiga bola dapat disusun dengan 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 membuat daftar semua opsi yang mungkin sangat panjang, maka kombinatorik membantu kami. Rumus permutasi akan membantu kita menemukan jawaban atas pertanyaan kita. Pn=nP(n-1). Jika kita mencoba menyederhanakan rumus, kita mendapatkan: Pn=n (n - 1) … 21. Dan ini adalah produk dari bilangan asli pertama. Bilangan seperti itu disebut faktorial, dan dilambangkan sebagai n!
Mari kita pertimbangkan masalahnya. Pemimpin setiap pagi membangun detasemennya dalam barisan (dua puluh orang). Ada tiga sahabat di detasemen - Kostya, Sasha dan Lesha. Berapa peluang mereka akan bersebelahan? Untuk menemukan jawaban atas pertanyaan tersebut, Anda perlu membagi probabilitas hasil "baik" dengan jumlah total hasil. Jumlah total permutasi adalah 20!=2,5 triliun. Bagaimana cara menghitung jumlah hasil "baik"? Misalkan Kostya, Sasha dan Lesha adalah satu superman. Lalu kitaKami hanya memiliki delapan belas mata pelajaran. Banyaknya permutasi dalam hal ini adalah 18=6,5 kuadriliun. Dengan semua ini, Kostya, Sasha, dan Lesha dapat secara sewenang-wenang bergerak di antara mereka sendiri dalam rangkap tiga yang tak terpisahkan, dan ini 3 lagi!=6 pilihan. Jadi kami memiliki total 18 rasi bintang "baik"!3! Kita tinggal mencari peluang yang diinginkan: (18!3!) / 20! Yaitu kira-kira 0,016. Jika dikonversi ke persentase, ternyata hanya 1,6%.
Akomodasi
Sekarang kita akan mempertimbangkan formula kombinatorik lain yang sangat penting dan perlu. Akomodasi adalah masalah kami berikutnya, yang kami sarankan agar Anda pertimbangkan di bagian artikel ini. Kita akan menjadi lebih rumit. Mari kita asumsikan bahwa kita ingin mempertimbangkan kemungkinan permutasi, hanya tidak dari seluruh himpunan (n), tetapi dari yang lebih kecil (m). Artinya, kami menganggap permutasi dari n item oleh m.
Rumus dasar kombinatorik tidak hanya harus dihafal, tetapi juga dipahami. Meskipun faktanya mereka menjadi lebih rumit, karena kita tidak memiliki satu parameter, tetapi dua. Misalkan m \u003d 1, lalu A \u003d 1, m \u003d 2, lalu A \u003d n(n - 1). Jika kami menyederhanakan rumus lebih lanjut dan beralih ke notasi menggunakan faktorial, kami mendapatkan rumus yang cukup ringkas: A \u003d n! / (n - m)!
Kombinasi
Kami telah mempertimbangkan hampir semua rumus dasar kombinatorik dengan contoh. Sekarang mari kita beralih ke tahap akhir dari mempertimbangkan kursus dasar kombinatorik - mengenal kombinasi. Sekarang kita akan memilih m item dari n yang kita miliki, sementara kita akan memilih semuanya dengan semua cara yang mungkin. Lalu apa bedanya dengan akomodasi? Kita tidak akanpertimbangkan ketertiban. Kumpulan yang tidak berurutan ini akan menjadi kombinasi.
Segera perkenalkan notasi: C. Kami mengambil penempatan m bola dari n. Kami berhenti memperhatikan pesanan dan mendapatkan kombinasi berulang. Untuk mendapatkan jumlah kombinasi, kita perlu membagi jumlah penempatan dengan m! (m faktorial). Artinya, C \u003d A / m! Jadi, ada beberapa cara untuk memilih dari n bola, kira-kira sama dengan berapa banyak untuk memilih hampir semuanya. Ada ungkapan logis untuk ini: memilih sedikit sama dengan membuang hampir segalanya. Penting juga untuk disebutkan pada titik ini bahwa jumlah kombinasi maksimum dapat dicapai ketika mencoba memilih setengah dari item.
Bagaimana memilih rumus untuk menyelesaikan masalah?
Kami telah memeriksa secara rinci rumus dasar kombinatorik: penempatan, permutasi, dan kombinasi. Sekarang tugas kita adalah memfasilitasi pilihan formula yang diperlukan untuk menyelesaikan masalah dalam kombinatorik. Anda dapat menggunakan skema yang agak sederhana berikut:
- Tanyakan pada diri sendiri: apakah urutan elemen diperhitungkan dalam teks soal?
- Jika jawabannya tidak, maka gunakan rumus kombinasi (C=n! / (m!(n - m)!)).
- Jika jawabannya tidak, maka Anda perlu menjawab satu pertanyaan lagi: apakah semua elemen termasuk dalam kombinasi?
- Jika jawabannya ya, maka gunakan rumus permutasi (P=n!).
- Jika jawabannya tidak, maka gunakan rumus alokasi (A=n! / (n - m)!).
Contoh
Kami telah mempertimbangkan elemen kombinatorik, rumus, dan beberapa masalah lainnya. Sekarang mari kita lanjutkan kemempertimbangkan masalah nyata. Bayangkan Anda memiliki kiwi, jeruk, dan pisang di depan Anda.
Pertanyaan satu: dalam berapa cara mereka dapat diatur ulang? Untuk melakukan ini, kami menggunakan rumus permutasi: P=3!=6 cara.
Pertanyaan kedua: dalam berapa cara satu buah dapat dipilih? Ini jelas, kami hanya memiliki tiga opsi - pilih kiwi, jeruk atau pisang, tetapi kami menerapkan rumus kombinasi: C \u003d 3! / (2!1!)=3.
Pertanyaan ketiga: dalam berapa cara dua buah dapat dipilih? Pilihan apa yang kita miliki? Kiwi dan jeruk; kiwi dan pisang; jeruk dan pisang. Artinya, tiga opsi, tetapi ini mudah diperiksa menggunakan rumus kombinasi: C \u003d 3! / (1!2!)=3
Pertanyaan empat: dalam berapa cara tiga buah dapat dipilih? Seperti yang Anda lihat, hanya ada satu cara untuk memilih tiga buah: ambil kiwi, jeruk, dan pisang. C=3! / (0!3!)=1.
Pertanyaan lima: berapa banyak cara Anda dapat memilih setidaknya satu buah? Kondisi ini menyiratkan bahwa kita dapat mengambil satu, dua atau ketiga buah. Oleh karena itu, kita tambahkan C1 + C2 + C3=3 + 3 + 1=7. Artinya, kita memiliki tujuh cara untuk mengambil setidaknya satu buah dari meja.
