Kelas 11Kelas 12mathKombinatorika
x1, x2, x3 ..., x9 merupakan angka yang diambil dari {0, 1,
Pertanyaan
Berapa banyak pasangan (x1, x2, x3, ..., x9) yang memenuhi persamaan x1 + x2 + x3 + ... + x9 = 15, di mana setiap xi diambil dari {0, 1, 2, 3, 4, 5, 6, 7, 8, 9}?
Solusi
Verified
478.731
Pembahasan
Untuk menyelesaikan soal ini, kita menggunakan konsep kombinasi dengan pengulangan (stars and bars). Kita memiliki 9 variabel (x1 hingga x9) yang masing-masing dapat mengambil nilai dari 0 hingga 9, dan jumlah totalnya harus 15. Rumus kombinasi dengan pengulangan adalah C(n+k-1, k-1), di mana n adalah jumlah total dan k adalah jumlah variabel. Namun, ada batasan bahwa setiap variabel tidak boleh lebih dari 9. Pendekatan langsung dengan stars and bars akan menghasilkan jumlah solusi tanpa batasan. Kita perlu menggunakan Prinsip Inklusi-Eksklusi untuk memperhitungkan batasan tersebut. Langkah 1: Hitung total solusi tanpa batasan. Jumlah variabel (k) = 9 Jumlah total (n) = 15 Total solusi = C(15 + 9 - 1, 9 - 1) = C(23, 8) C(23, 8) = 23! / (8! * (23-8)!) = 23! / (8! * 15!) = (23 * 22 * 21 * 20 * 19 * 18 * 17 * 16) / (8 * 7 * 6 * 5 * 4 * 3 * 2 * 1) = 490314 Langkah 2: Hitung solusi di mana setidaknya satu variabel lebih dari atau sama dengan 10. Misalkan x1 >= 10. Ganti x1 dengan y1 + 10, di mana y1 >= 0. (y1 + 10) + x2 + ... + x9 = 15 y1 + x2 + ... + x9 = 5 Jumlah solusi = C(5 + 9 - 1, 9 - 1) = C(13, 8) C(13, 8) = 13! / (8! * 5!) = (13 * 12 * 11 * 10 * 9) / (5 * 4 * 3 * 2 * 1) = 1287 Karena ada 9 variabel, kita kalikan dengan 9 (karena setiap variabel bisa saja >= 10). Jumlah solusi dengan setidaknya satu variabel >= 10 = 9 * 1287 = 11583. Langkah 3: Hitung solusi di mana setidaknya dua variabel lebih dari atau sama dengan 10. Misalkan x1 >= 10 dan x2 >= 10. Ganti x1 dengan y1 + 10 dan x2 dengan y2 + 10. (y1 + 10) + (y2 + 10) + x3 + ... + x9 = 15 y1 + y2 + x3 + ... + x9 = -5 Jumlah solusi = 0 (karena tidak mungkin jumlahnya negatif). Ini berarti kita tidak perlu mempertimbangkan kasus di mana dua atau lebih variabel lebih dari atau sama dengan 10, karena jumlah totalnya hanya 15. Langkah 4: Terapkan Prinsip Inklusi-Eksklusi. Jumlah solusi yang memenuhi batasan = Total solusi - (Solusi dengan setidaknya satu variabel >= 10) Jumlah solusi = 490314 - 11583 = 478731. Jadi, banyak pasangan (x1, x2, x3, ..., x9) yang memenuhi persamaan x1 + x2 + x3 + ... + x9 = 15 adalah 478.731.
Topik: Prinsip Inklusi Eksklusi, Kombinasi Dengan Pengulangan
Section: Aplikasi Kombinasi
Apakah jawaban ini membantu?