Lewati ke konten utama
Gambar logo

Matematika Diskret Sebuah Pengantar Terbuka, Edisi Keempat

Oscar Levin

Subbab 3.6 Pembuktian Kombinatorial

Subbagian Pratinjau Bagian

Selidiki!
Perhatikan sembarang sel di bagian dalam Segitiga Pascal beserta enam bilangan yang mengelilinginya. Sebagai contoh, Anda dapat memperhatikan sel berikut:
🔗
sebuah sel dalam Segitiga Pascal yang dikelilingi enam sel lain.
Keenam bilangan yang mengelilingi sel pilihan kita akan dibagi menjadi dua kelompok yang masing-masing terdiri atas tiga bilangan, dengan keanggotaan berselang-seling di antara kedua kelompok. Jadi, dalam contoh ini kita memiliki satu kelompok berisi 4, 10, dan 15, serta kelompok kedua berisi 5, 6, dan 20. Namun, perhatikan:
\begin{equation*} 4\cdot 10 \cdot 15 = 600 = 5\cdot 6 \cdot 20\text{.} \end{equation*}
Apakah ini berlaku untuk sel tengah mana pun yang Anda pilih? Mengapa?
🔗
🔗
Salah satu hal paling menarik dalam kombinatorika adalah bahwa pertanyaan pencacahan yang sama sering kali dapat dijawab dengan cara yang sangat berbeda. Ketika mengenali hal ini dalam suatu masalah, kita sering dapat menggeneralisasi pertanyaannya untuk memperoleh dua ekspresi berbeda yang harus merepresentasikan kuantitas yang sama. Masalah pencacahan itu sendiri menjadi pembuktian bahwa kedua ekspresi tersebut sama. Gaya pembuktian ini disebut pembuktian kombinatorial.
🔗

Lembar Kerja Kegiatan Pratinjau

Jawaban atas suatu pertanyaan pencacahan sering kali dapat ditemukan dengan dua cara berbeda. Hal ini menghasilkan dua rumus yang memberikan jawaban tersebut; keduanya mungkin tampak berbeda, tetapi harus sama (karena keduanya merupakan jawaban yang benar untuk pertanyaan yang sama). Dengan demikian diperoleh pembuktian bahwa kedua rumus itu sama, yang disebut pembuktian kombinatorial.
🔗
Mari kita telaah beberapa contoh.
🔗
1.
Perhatikan himpunan string 7-bit berbobot 3. Artinya, string 0 dan 1 yang panjangnya tujuh karakter dan memuat tepat tiga angka 1. Ada berapa string seperti itu?
🔗
(a)
Nyatakan jawabannya sebagai satu koefisien binomial.
🔗
🔗
(b)
Sekarang hitung hanya string 7-bit berbobot 3 yang diawali dengan 1. Ada berapa?
🔗
🔗
(c)
Sekarang hitung hanya string 7-bit berbobot 3 yang diawali dengan 01. Ada berapa?
🔗
🔗
(d)
Sekarang hitung hanya string 7-bit berbobot 3 yang diawali dengan 001. Ada berapa?
🔗
🔗
(e)
Lanjutkan proses ini hingga Anda telah menghitung semua string 7-bit berbobot 3 sebagai jumlah koefisien-koefisien binomial. Berapakah jumlah ini?
🔗
🔗
🔗
2.
Perhatikan pertanyaan pencacahan “Ada berapa cara untuk menyusun ulang huruf-huruf dalam kata STATISTICS?” Perhatikan bahwa ini bukan sekadar permutasi karena terdapat huruf yang berulang.
🔗
(a)
Ada berapa cara untuk memilih tiga dari sepuluh posisi dalam anagram agar ditempati oleh huruf S?
🔗
🔗
(b)
Ada berapa cara untuk memilih tiga dari tujuh posisi yang tersisa dalam anagram agar ditempati oleh huruf T?
🔗
🔗
(c)
Lanjutkan pendekatan ini hingga Anda menemukan suatu ekspresi bagi banyaknya cara menyusun ulang huruf-huruf dalam STATISTICS sebagai hasil kali koefisien-koefisien binomial. Tuliskan hasil kali tersebut.
🔗
🔗
(d)
Sekarang jawab kembali pertanyaan pencacahan tersebut, kali ini dengan terlebih dahulu menanyakan banyaknya cara memilih posisi bagi huruf A. Lanjutkan dengan cara apa pun yang Anda sukai hingga Anda menemukan ekspresi lain bagi banyaknya cara menyusun ulang huruf-huruf dalam STATISTICS sebagai hasil kali koefisien-koefisien binomial. Tuliskan hasil kali tersebut.
🔗
🔗
(e)
Cobalah pendekatan lain lagi. Apa yang salah dengan mengatakan bahwa jawabannya adalah \(10!\text{?}\) Nilai ini terlalu besar, tetapi kita dapat memperbaikinya dengan membagi untuk memperhitungkan hasil-hasil yang ekuivalen. Dengan apa Anda harus membaginya?
🔗
Tuliskan jawaban Anda sebagai hasil bagi faktorial. Apakah Anda memperoleh jawaban yang sama seperti sebelumnya?
🔗
🔗
🔗
🔗
🔗

Subbagian Pola dalam Segitiga Pascal

Perhatikan kembali Segitiga Pascal. Lupakan sejenak dari mana segitiga itu berasal. Pandang saja sebagai objek matematis. Apa yang Anda amati?
🔗
Tujuh baris pertama Segitiga Pascal. Susunan segitiga yang terdiri atas segi enam, dengan setiap baris memuat satu segi enam lebih banyak daripada baris di atasnya. Setiap segi enam memuat sebuah bilangan bulat: angka 1 berada pada batas segitiga, dan setiap bilangan bulat di bagian dalam segitiga merupakan jumlah dua bilangan bulat di atasnya. Baris terakhir memuat bilangan 1, 7, 21, 35, 35, 21, 7, dan 1.
Banyak pola tersembunyi dalam segitiga tersebut, bahkan cukup untuk memenuhi sebuah buku berukuran wajar. Berikut beberapa pola yang paling jelas:
  1. Semua entri pada batas segitiga bernilai 1.
    🔗
    🔗
  2. Setiap entri yang tidak berada pada batas merupakan jumlah dua entri di atasnya.
    🔗
    🔗
  3. Segitiga tersebut simetris. Pada setiap baris, entri-entri di sisi kiri dicerminkan di sisi kanan.
    🔗
    🔗
  4. Jumlah semua entri pada suatu baris merupakan perpangkatan 2. (Anda perlu memeriksanya!)
    🔗
    🔗
🔗
Kita ingin menyatakan pengamatan-pengamatan ini dengan lebih tepat, lalu membuktikan bahwa semuanya benar. Setiap entri dalam Segitiga Pascal sebenarnya merupakan koefisien binomial. Angka 1 di puncak segitiga adalah \(\binom{0}{0}\text{.}\) Baris berikutnya (yang akan kita sebut baris 1, meskipun bukan baris paling atas) terdiri atas \(\binom{1}{0}\) dan \(\binom{1}{1}\text{.}\) Baris 4 (baris 1, 4, 6, 4, 1) terdiri atas koefisien-koefisien binomial
\begin{equation*} \binom{4}{0} ~~ \binom{4}{1} ~~ \binom{4}{2} ~~ \binom{4}{3} ~~ \binom{4}{4}\text{.} \end{equation*}
🔗
Berdasarkan deskripsi elemen-elemen Segitiga Pascal ini, kita dapat menuliskan kembali pengamatan di atas sebagai berikut:
  1. \(\binom{n}{0} = 1\) dan \(\binom{n}{n} = 1\text{.}\)
    🔗
  2. \(\binom{n}{k} = \binom{n-1}{k-1} + \binom{n-1}{k}\text{.}\)
    🔗
  3. \(\binom{n}{k} = \binom{n}{n-k}\text{.}\)
    🔗
  4. \(\binom{n}{0} + \binom{n}{1} + \binom{n}{2} + \cdots + \binom{n}{n} = 2^n\text{.}\)
    🔗
🔗
Masing-masing merupakan contoh identitas binomial : identitas (yaitu persamaan) yang melibatkan koefisien binomial.
🔗
Tujuan kita adalah membuktikan identitas-identitas ini. Kita ingin membuktikan bahwa identitas tersebut berlaku untuk semua nilai \(n\) dan \(k\text{.}\) Pembuktian ini dapat dilakukan dengan berbagai cara. Salah satu pilihan adalah memberikan pembuktian aljabar dengan menggunakan rumus \(\binom{n}{k}\text{:}\)
\begin{equation*} \binom{n}{k} = \frac{n!}{(n-k)!\,k!}\text{.} \end{equation*}
🔗
Berikut cara melakukannya untuk identitas kedua di atas.
🔗

Contoh 3.6.1.

Berikan pembuktian aljabar untuk identitas binomial
\begin{equation*} \binom{n}{k} = \binom{n-1}{k-1} + \binom{n-1}{k}\text{.} \end{equation*}
🔗
Penyelesaian.
Bukti.
Berdasarkan definisi \(\binom{n}{k}\text{,}\) kita memiliki
\begin{equation*} \binom{n-1}{k-1} = \frac{(n-1)!}{(n-1-(k-1))!(k-1)!} = \frac{(n-1)!}{(n-k)!(k-1)!} \end{equation*}
dan
\begin{equation*} \binom{n-1}{k} = \frac{(n-1)!}{(n-1-k)!k!}\text{.} \end{equation*}
🔗
Jadi, dengan memulai dari ruas kanan persamaan:
\begin{align*} \binom{n-1}{k-1} + \binom{n-1}{k} \amp = \frac{(n-1)!}{(n-k)!(k-1)!}+ \frac{(n-1)!}{(n-1-k)!\,k!}\\ \amp = \frac{(n-1)!k}{(n-k)!\,k!} + \frac{(n-1)!(n-k)}{(n-k)!\,k!}\\ \amp = \frac{(n-1)!(k+n-k)}{(n-k)!\,k!}\\ \amp = \frac{n!}{(n-k)!\, k!}\\ \amp = \binom{n}{k}\text{.} \end{align*}
🔗
Baris kedua (ketika penyebut bersama ditemukan) berlaku karena \(k(k-1)! = k!\) dan \((n-k)(n-k-1)! = (n-k)!\text{.}\)
🔗
🔗
🔗
🔗
Pembuktian ini tentu sah, tetapi sama sekali tidak berguna untuk menjelaskan alasannya. Meskipun Anda memahami pembuktian tersebut dengan sempurna, pembuktian itu tidak menjelaskan mengapa identitasnya benar. Pendekatan yang lebih baik adalah menjelaskan apa \(\binom{n}{k}\) artinya, lalu menjelaskan mengapa hal itu juga merupakan makna \(\binom{n-1}{k-1} + \binom{n-1}{k}\text{.}\) Mari kita lihat penerapannya pada empat identitas yang kita amati di atas.
🔗

Contoh 3.6.2.

Jelaskan mengapa \(\binom{n}{0} = 1\) dan \(\binom{n}{n} = 1\text{.}\)
🔗
Penyelesaian.
Apa yang dinyatakan oleh koefisien-koefisien binomial ini? \(\binom{n}{0}\) memberikan banyaknya cara memilih 0 objek dari koleksi \(n\) objek. Hanya ada satu cara untuk melakukannya, yaitu tidak memilih objek apa pun. Jadi, \(\binom{n}{0} = 1\text{.}\) Demikian pula, \(\binom{n}{n}\) memberikan banyaknya cara memilih \(n\) objek dari koleksi \(n\) objek. Hanya ada satu cara untuk melakukannya: pilih semua \(n\) objek. Jadi, \(\binom{n}{n} = 1\text{.}\)
🔗
Sebagai alternatif, kita mengetahui bahwa \(\binom{n}{0}\) adalah banyaknya string \(n\)-bit berbobot 0. Hanya ada satu string seperti itu, yaitu string yang seluruhnya terdiri atas angka 0. Jadi, \(\binom{n}{0} = 1\text{.}\) Demikian pula, \(\binom{n}{n}\) adalah banyaknya string \(n\)-bit berbobot \(n\text{.}\) Hanya ada satu string dengan sifat ini, yaitu string yang seluruhnya terdiri atas angka 1.
🔗
Cara lain: \(\binom{n}{0}\) memberikan banyaknya subhimpunan berisi 0 elemen dari himpunan berukuran \(n\text{.}\) Hanya ada satu subhimpunan seperti itu, yaitu himpunan kosong. \(\binom{n}{n}\) memberikan banyaknya subhimpunan yang memuat \(n\) elemen. Satu-satunya subhimpunan seperti itu adalah himpunan semula (yang berisi semua elemen).
🔗
🔗
🔗

Contoh 3.6.3.

Jelaskan mengapa \(\binom{n}{k} = \binom{n-1}{k-1} + \binom{n-1}{k}\text{.}\)
🔗
Penyelesaian.
Cara termudah untuk melihatnya adalah dengan memperhatikan string bit. \(\binom{n}{k}\) adalah banyaknya string bit berpanjang \(n\) yang memuat \(k\) angka 1. Di antara semua string tersebut, sebagian diawali dengan 1 dan sisanya diawali dengan 0. Pertama, perhatikan semua string bit yang diawali dengan 1. Setelah angka 1 tersebut, masih harus ada \(n-1\) bit (agar panjang totalnya \(n\)), dan tepat \(k-1\) di antaranya harus berupa angka 1 (karena kita sudah memiliki satu dan memerlukan total \(k\)). Ada berapa string seperti itu? Terdapat tepat \(\binom{n-1}{k-1}\) string bit seperti itu. Jadi, di antara semua string bit berpanjang \(n\) yang memuat \(k\) angka 1, sebanyak \(\binom{n-1}{k-1}\) diawali dengan 1. Demikian pula, terdapat \(\binom{n-1}{k}\) string yang diawali dengan 0 (kita masih memerlukan \(n-1\) bit dan sekarang \(k\) di antaranya harus berupa angka 1). Karena terdapat \(\binom{n-1}{k}\) string bit yang terdiri atas \(n-1\) bit dengan \(k\) angka 1, itulah banyaknya string bit berpanjang \(n\) dengan \(k\) angka 1 yang diawali dengan 0. Oleh karena itu, \(\binom{n}{k} = \binom{n-1}{k-1} + \binom{n-1}{k}\text{.}\)
🔗
Cara lain: perhatikan pertanyaan berikut. Ada berapa cara untuk memilih \(k\) taburan pizza dari menu yang menyediakan \(n\) pilihan? Salah satu cara menjawabnya langsung menghasilkan \(\binom{n}{k}\text{.}\) Cara lain untuk menjawab pertanyaan yang sama adalah terlebih dahulu memutuskan apakah Anda menginginkan ikan teri. Jika menginginkan ikan teri, Anda masih perlu memilih \(k-1\) taburan, kini hanya dari \(n-1\) pilihan. Hal ini dapat dilakukan dalam \(\binom{n-1}{k-1}\) cara. Jika tidak menginginkan ikan teri, Anda masih perlu memilih \(k\) taburan dari \(n-1\) pilihan (ikan teri tidak lagi menjadi pilihan). Hal ini dapat dilakukan dalam \(\binom{n-1}{k}\) cara. Karena pilihan dengan ikan teri saling lepas dari pilihan tanpa ikan teri, jumlah seluruh pilihan adalah \(\binom{n-1}{k-1}+\binom{n-1}{k}\text{.}\) Namun, tunggu sebentar. Kita telah menjawab pertanyaan yang sama dengan dua cara berbeda, sehingga kedua jawabannya harus sama. Jadi, \(\binom{n}{k} = \binom{n-1}{k-1} + \binom{n-1}{k}\text{.}\)
🔗
Anda juga dapat menjelaskan (membuktikan) identitas ini dengan mencacah subhimpunan atau bahkan lintasan kisi.
🔗
🔗
🔗

Contoh 3.6.4.

Buktikan identitas binomial \(\binom{n}{k} = \binom{n}{n-k}\text{.}\)
🔗
Penyelesaian.
Mengapa ini benar? \(\binom{n}{k}\) menghitung banyaknya cara memilih \(k\) benda dari \(n\) pilihan. Di pihak lain, \(\binom{n}{n-k}\) menghitung banyaknya cara memilih \(n-k\) benda dari \(n\) pilihan. Apakah keduanya benar-benar sama? Bagaimana jika, alih-alih memilih \(n-k\) benda untuk disertakan, Anda memilihnya untuk dikecualikan? Ada berapa cara untuk memilih \(n-k\) benda yang akan dikecualikan dari \(n\) pilihan? Jelas jawabannya juga \(\binom{n}{n-k}\) (setelah benda-bendanya dipilih, tidak penting apakah Anda menyertakan atau mengecualikannya). Jika Anda mengecualikan \(n-k\) benda, Anda menyertakan \(k\) benda lainnya. Jadi, himpunan hasilnya sama.
🔗
Mari kita gunakan contoh pencacahan pizza seperti di atas. Ada berapa cara untuk memilih \(k\) taburan dari daftar \(n\) pilihan? Di satu pihak, jawabannya langsung \(\binom{n}{k}\text{.}\) Sebagai alternatif, Anda dapat membuat daftar semua taburan yang tidak Anda inginkan. Agar memperoleh pizza dengan tepat \(k\) taburan, Anda perlu memilih \(n-k\) taburan yang tidak akan diletakkan di atas pizza. Terdapat \(\binom{n}{n-k}\) pilihan untuk taburan yang tidak Anda inginkan. Kedua cara tersebut menghasilkan pizza dengan \(k\) taburan, bahkan mencakup semua cara memperoleh pizza dengan \(k\) taburan. Jadi, kedua jawaban ini harus sama: \(\binom{n}{k} = \binom{n}{n-k}\text{.}\)
🔗
Anda juga dapat membuktikan (menjelaskan) identitas ini dengan menggunakan string bit, subhimpunan, atau lintasan kisi. Argumen string bit cukup menarik: \(\binom{n}{k}\) menghitung banyaknya string bit berpanjang \(n\) dengan \(k\) angka 1. Ini juga merupakan banyaknya string bit berpanjang \(n\) dengan \(k\) angka 0 (cukup ganti setiap angka 1 dengan 0 dan setiap angka 0 dengan 1). Namun, jika string berpanjang \(n\) memiliki \(k\) angka 0, string itu harus memiliki \(n-k\) angka 1. Terdapat tepat \(\binom{n}{n-k}\) string berpanjang \(n\) dengan \(n-k\) angka 1.
🔗
🔗
🔗

Contoh 3.6.5.

Buktikan identitas binomial \(\binom{n}{0} + \binom{n}{1} + \binom{n}{2} + \cdots + \binom{n}{n} = 2^n\text{.}\)
🔗
Penyelesaian.
Mari kita kembali melakukan “pembuktian pizza”. Kita perlu menemukan pertanyaan tentang taburan pizza yang jawabannya \(2^n\text{.}\) Bagaimana dengan pertanyaan ini: jika sebuah kedai pizza menawarkan \(n\) taburan, ada berapa pizza yang dapat Anda buat dengan menggunakan sembarang banyak taburan, mulai dari tanpa taburan hingga semua taburan, dan menggunakan setiap taburan paling banyak sekali?
🔗
Di satu pihak, jawabannya adalah \(2^n\text{.}\) Untuk setiap taburan, Anda dapat mengatakan “ya” atau “tidak”, sehingga Anda memiliki dua pilihan untuk setiap taburan.
🔗
Di pihak lain, bagi semua pizza yang mungkin menjadi kelompok-kelompok saling lepas: pizza tanpa taburan, pizza dengan satu taburan, pizza dengan dua taburan, dan seterusnya. Jika kita tidak menginginkan taburan, hanya ada satu pizza seperti itu (pizza kosong, boleh dikatakan demikian), tetapi bilangan itu lebih baik dipandang sebagai \(\binom{n}{0}\) karena kita memilih 0 dari \(n\) taburan. Ada berapa pizza yang memiliki 1 taburan? Kita perlu memilih 1 dari \(n\) taburan, sehingga banyaknya adalah \(\binom{n}{1}\text{.}\) Kita memperoleh:
🔗
  • Pizza dengan 0 taburan: \(\binom{n}{0}\)
    🔗
  • Pizza dengan 1 taburan: \(\binom{n}{1}\)
    🔗
  • Pizza dengan 2 taburan: \(\binom{n}{2}\)
    🔗
  • \(\displaystyle \vdots\)
    🔗
  • Pizza dengan \(n\) taburan: \(\binom{n}{n}\text{.}\)
    🔗
🔗
Jumlah seluruh pizza yang mungkin adalah penjumlahan bilangan-bilangan ini, yang tepat sama dengan ruas kiri identitas yang sedang kita buktikan.
🔗
Sekali lagi, kita dapat membuktikan identitas ini dengan menggunakan subhimpunan, string bit, atau lintasan kisi (meskipun argumen lintasan kisi sedikit rumit).
🔗
🔗
🔗
Semoga uraian ini memberi gambaran tentang cara menyusun pembuktian yang menjelaskan identitas binomial. Perlu ditekankan bahwa pembuktian yang lebih tradisional juga dapat indah.
 4 
Hampir setiap identitas binomial dapat dibuktikan dengan induksi matematika menggunakan definisi rekursif \(\binom{n}{k}\text{.}\) Kita akan membahas induksi dalam Subbab 4.5.
Sebagai contoh, perhatikan pembuktian ringkas berikut untuk identitas terakhir.
🔗
Jabarkan binomial \((x+y)^n\text{:}\)
\begin{equation*} (x + y)^n = \binom{n}{0}x^n + \binom{n}{1}x^{n-1}y + \binom{n}{2}x^{n-2}y^2 + \cdots + \binom{n}{n-1}x\cdot y^{n-1} + \binom{n}{n}y^n\text{.} \end{equation*}
🔗
Ambil \(x = 1\) dan \(y = 1\text{.}\) Kita memperoleh:
\begin{equation*} (1 + 1)^n = \binom{n}{0}1^n + \binom{n}{1}1^{n-1}1 + \binom{n}{2}1^{n-2}1^2 + \cdots + \binom{n}{n-1}1\cdot 1^{n-1} + \binom{n}{n}1^n\text{.} \end{equation*}
🔗
Tentu saja, ini menyederhana menjadi:
\begin{equation*} (2)^n = \binom{n}{0} + \binom{n}{1} + \binom{n}{2} + \cdots + \binom{n}{n-1} + \binom{n}{n}\text{.} \end{equation*}
🔗
Hal menarik untuk dicoba: ambil \(x = 1\) dan \(y = 2\text{.}\) Menarik, bukan?
🔗
🔗

Subbagian Pembuktian Lainnya

Pembuktian yang bersifat menjelaskan dalam contoh-contoh di atas biasanya disebut pembuktian kombinatorial. Secara umum, untuk memberikan pembuktian kombinatorial bagi identitas binomial, misalnya \(A = B\text{,}\) lakukan langkah-langkah berikut:
🔗
  1. Temukan masalah pencacahan yang dapat Anda jawab dengan dua cara.
    🔗
    🔗
  2. Jelaskan mengapa salah satu jawaban untuk masalah pencacahan tersebut adalah \(A\text{.}\)
    🔗
    🔗
  3. Jelaskan mengapa jawaban lain untuk masalah pencacahan tersebut adalah \(B\text{.}\)
    🔗
    🔗
🔗
Karena \(A\) dan \(B\) sama-sama merupakan jawaban untuk pertanyaan yang sama, haruslah \(A = B\text{.}\)
🔗
Bagian yang rumit adalah menemukan pertanyaannya. Hal ini tidak selalu jelas, tetapi akan semakin mudah seiring bertambahnya masalah pencacahan yang Anda selesaikan. Anda akan mulai mengenali jenis jawaban sebagai jawaban bagi jenis pertanyaan tertentu. Yang lebih sering terjadi adalah Anda sedang menyelesaikan suatu masalah pencacahan dan kebetulan memikirkan dua cara berbeda untuk menemukan jawabannya. Kini Anda memiliki identitas binomial, dan pembuktiannya sudah tersedia. Pembuktian tersebut adalah masalah yang baru saja Anda selesaikan beserta kedua solusinya.
🔗
Sebagai contoh, perhatikan pertanyaan pencacahan berikut:
🔗
Ada berapa kata 10 huruf yang menggunakan tepat empat A, tiga B, dua C, dan satu D?
🔗
🔗
Mari kita mencoba menyelesaikan masalah ini. Kita memiliki 10 posisi untuk ditempati huruf. Empat di antaranya harus ditempati A. Kita dapat memilih empat posisi A dalam \(\binom{10}{4}\) cara. Sekarang, di mana kita dapat menempatkan B? Hanya tersisa 6 posisi, dan kita perlu memilih \(3\) di antaranya. Hal ini dapat dilakukan dalam \(\binom{6}{3}\) cara. Kedua C harus ditempatkan pada dua dari 3 posisi yang tersisa, sehingga kita memiliki \(\binom{3}{2}\) cara untuk melakukannya. Dengan demikian, hanya tersisa satu posisi untuk D, tetapi pilihan tunggal itu dapat kita tuliskan sebagai \(\binom{1}{1}\text{.}\) Jadi, jawabannya adalah:
\begin{equation*} \binom{10}{4}\binom{6}{3}\binom{3}{2}\binom{1}{1}\text{.} \end{equation*}
🔗
Namun, mengapa berhenti sampai di situ? Kita juga dapat menemukan jawabannya dengan cara lain. Pertama, mari kita tentukan tempat untuk satu D: kita memiliki 10 posisi dan perlu memilih 1 di antaranya, sehingga hal ini dapat dilakukan dalam \(\binom{10}{1}\) cara. Berikutnya, pilih salah satu dari \(\binom{9}{2}\) cara menempatkan kedua C. Kini tersisa \(7\) posisi, dan tiga di antaranya harus diisi dengan B. Terdapat \(\binom{7}{3}\) cara untuk melakukannya. Terakhir, A dapat ditempatkan dalam \(\binom{4}{4}\) cara (yaitu hanya satu cara). Jadi, jawaban lain untuk pertanyaan tersebut adalah
\begin{equation*} \binom{10}{1}\binom{9}{2}\binom{7}{3}\binom{4}{4}\text{.} \end{equation*}
🔗
Menarik. Hal ini memberi kita identitas binomial:
\begin{equation*} \binom{10}{4}\binom{6}{3}\binom{3}{2}\binom{1}{1} = \binom{10}{1}\binom{9}{2}\binom{7}{3}\binom{4}{4}\text{.} \end{equation*}
🔗
Berikut beberapa identitas binomial lain beserta pembuktian kombinatorialnya.
🔗

Contoh 3.6.6.

Buktikan identitas
\begin{equation*} 1 n + 2(n-1) + 3 (n-2) + \cdots + (n-1) 2 + n 1 = \binom{n+2}{3}\text{.} \end{equation*}
🔗
Penyelesaian.
Untuk memberikan pembuktian kombinatorial, kita perlu memikirkan pertanyaan yang dapat dijawab dengan dua cara: satu cara harus menghasilkan ruas kiri identitas, sedangkan cara lainnya harus menghasilkan ruas kanannya. Petunjuk untuk menentukan pertanyaan berasal dari ruas kanan: \(\binom{n+2}{3}\) menghitung banyaknya cara memilih 3 benda dari kelompok \(n+2\) benda. Mari namai benda-benda itu \(1, 2, 3, \ldots, n+2\text{.}\) Dengan kata lain, kita ingin menemukan subhimpunan 3-elemen dari bilangan-bilangan tersebut (karena urutan tidak penting, subhimpunan merupakan objek yang tepat untuk dipertimbangkan). Kita perlu sedikit cerdik untuk menjelaskan mengapa ruas kiri juga memberikan banyaknya subhimpunan ini. Berikut pembuktiannya.
🔗
Bukti.
Perhatikan pertanyaan “Ada berapa subhimpunan 3-elemen dari himpunan \(\{1,2,3,\ldots, n+2\}\text{?}\)” Kita menjawabnya dengan dua cara:
🔗
Jawaban 1: Kita harus memilih 3 elemen dari koleksi \(n+2\) elemen. Hal ini dapat dilakukan dalam \(\binom{n+2}{3}\) cara.
🔗
Jawaban 2: Bagi masalah ini menjadi kasus-kasus berdasarkan bilangan tengah dalam subhimpunan. Misalkan setiap subhimpunan ditulis sebagai \(\{a,b,c\}\) dalam urutan menaik. Kita menghitung banyaknya subhimpunan untuk setiap nilai \(b\) yang berbeda. Nilai terkecil yang mungkin bagi \(b\) adalah \(2\text{,}\) sedangkan yang terbesar adalah \(n+1\text{.}\)
🔗
Ketika \(b = 2\text{,}\) terdapat \(1 \cdot n\) subhimpunan: 1 pilihan untuk \(a\) dan \(n\) pilihan (3 hingga \(n+2\)) untuk \(c\text{.}\)
🔗
Ketika \(b = 3\text{,}\) terdapat \(2 \cdot (n-1)\) subhimpunan: 2 pilihan untuk \(a\) dan \(n-1\) pilihan untuk \(c\text{.}\)
🔗
Ketika \(b = 4\text{,}\) terdapat \(3 \cdot (n-2)\) subhimpunan: 3 pilihan untuk \(a\) dan \(n-2\) pilihan untuk \(c\text{.}\)
🔗
Demikian seterusnya. Ketika \(b = n+1\text{,}\) terdapat \(n\) pilihan untuk \(a\) dan hanya 1 pilihan untuk \(c\text{,}\) sehingga terdapat \(n \cdot 1\) subhimpunan.
🔗
Oleh karena itu, jumlah seluruh subhimpunan adalah
\begin{equation*} 1 n + 2 (n-1) + 3 (n-2) + \cdots + (n-1)2 + n 1\text{.} \end{equation*}
🔗
Karena Jawaban 1 dan Jawaban 2 menjawab pertanyaan yang sama, keduanya harus sama. Oleh karena itu,
\begin{equation*} 1 n + 2 (n-1) + 3 (n-2) + \cdots + (n-1) 2 + n 1 = \binom{n+2}{3}\text{.} \end{equation*}
🔗
🔗
🔗
🔗

Contoh 3.6.7.

Buktikan identitas binomial
\begin{equation*} \binom{n}{0}^2 + \binom{n}{1}^2 + \binom{n}{2}^2 + \cdots + \binom{n}{n}^2 = \binom{2n}{n}\text{.} \end{equation*}
🔗
Penyelesaian.
Kita akan memberikan dua pembuktian berbeda untuk fakta ini. Pembuktian pertama sangat mirip dengan contoh sebelumnya (mencacah subhimpunan). Pembuktian kedua sedikit lebih ringkas dan menggunakan lintasan kisi.
🔗
Bukti.
Perhatikan pertanyaan berikut: “Ada berapa pizza yang dapat Anda buat dengan menggunakan \(n\) taburan jika tersedia \(2n\) taburan untuk dipilih?”
🔗
Jawaban 1: Terdapat \(2n\) taburan, dan Anda harus memilih \(n\) di antaranya. Hal ini dapat dilakukan dalam \(\binom{2n}{n}\) cara.
🔗
Jawaban 2: Bagi taburan menjadi dua kelompok yang masing-masing berisi \(n\) taburan (misalnya \(n\) daging dan \(n\) sayuran). Setiap pilihan \(n\) taburan harus mencakup sejumlah taburan dari kelompok pertama dan sejumlah taburan dari kelompok kedua. Perhatikan setiap kemungkinan banyaknya taburan daging secara terpisah:
🔗
0 daging: \(\binom{n}{0}\binom{n}{n}\text{,}\) karena Anda perlu memilih 0 dari \(n\) daging dan \(n\) dari \(n\) sayuran.
🔗
1 daging: \(\binom{n}{1}\binom{n}{n-1}\text{,}\) karena Anda memerlukan 1 dari \(n\) daging sehingga perlu memilih \(n-1\) dari \(n\) sayuran.
🔗
2 daging: \(\binom{n}{2}\binom{n}{n-2}\text{.}\) Pilih 2 daging dan \(n-2\) taburan sisanya dari \(n\) sayuran.
🔗
Demikian seterusnya. Kasus terakhir adalah \(n\) daging, yang dapat dipilih dalam \(\binom{n}{n}\binom{n}{0}\) cara.
🔗
Jadi, jumlah seluruh pizza yang mungkin adalah
\begin{equation*} \binom{n}{0}\binom{n}{n} + \binom{n}{1}\binom{n}{n-1} + \binom{n}{2}\binom{n}{n-2} + \cdots + \binom{n}{n}\binom{n}{0}\text{.} \end{equation*}
🔗
Bentuk ini belum tepat sama dengan ruas kiri …. Perhatikan bahwa \(\binom{n}{n} = \binom{n}{0}\) dan \(\binom{n}{n-1} = \binom{n}{1}\text{,}\) dan seterusnya, berdasarkan identitas dalam Contoh 3.6.4. Jadi, kita memang memperoleh
\begin{equation*} \binom{n}{0}^2 + \binom{n}{1}^2 + \binom{n}{2}^2 + \cdots + \binom{n}{n}^2\text{.} \end{equation*}
🔗
Karena kedua jawaban ini menjawab pertanyaan yang sama, keduanya harus sama, sehingga
\begin{equation*} \binom{n}{0}^2 + \binom{n}{1}^2 + \binom{n}{2}^2 + \cdots + \binom{n}{n}^2 = \binom{2n}{n}\text{.} \end{equation*}
🔗
🔗
Untuk pembuktian alternatif, kita menggunakan lintasan kisi. Hal ini wajar dipertimbangkan karena ruas kanan identitas mengingatkan kita pada banyaknya lintasan dari \((0,0)\) ke \((n,n)\text{.}\)
🔗
Bukti.
Perhatikan pertanyaan: ada berapa lintasan kisi dari \((0,0)\) ke \((n,n)\text{?}\)
🔗
Jawaban 1: Kita harus menempuh \(2n\) langkah, dan \(n\) di antaranya harus mengarah ke atas. Jadi, terdapat \(\binom{2n}{n}\) lintasan.
🔗
Jawaban 2: Perhatikan bahwa setiap lintasan dari \((0,0)\) ke \((n,n)\) harus memotong garis \(x + y = n\text{.}\) Artinya, setiap lintasan harus melalui tepat satu di antara titik-titik berikut: \((0,n)\text{,}\) \((1,n-1)\text{,}\) \((2,n-2)\text{,}\) …, \((n, 0)\text{.}\) Sebagai contoh, berikut yang terjadi pada kasus \(n = 4\text{:}\)
🔗
Kisi abu-abu muda dengan titik (0,0) dan (4,4) yang masing-masing ditandai di sudut kiri bawah dan kanan atas. Garis x + y = 4 ditampilkan memanjang dari sudut kiri atas ke sudut kanan bawah. Garis tersebut memotong titik-titik berlabel (0,4), (1,3), (2,2), (3,1), dan (4,0).
Ada berapa lintasan yang melalui \((0,n)\text{?}\) Untuk mencapai titik tersebut, Anda harus menempuh \(n\) satuan, dan \(0\) di antaranya mengarah ke kanan, sehingga terdapat \(\binom{n}{0}\) cara untuk mencapai \((0,n)\text{.}\) Perjalanan dari \((0,n)\) ke \((n,n)\) memerlukan \(n\) langkah, dan \(0\) di antaranya mengarah ke atas. Jadi, terdapat \(\binom{n}{0}\) cara untuk bergerak dari \((0,n)\) ke \((n,n)\text{.}\) Oleh karena itu, terdapat \(\binom{n}{0}\binom{n}{0}\) lintasan dari \((0,0)\) ke \((n,n)\) yang melalui titik \((0,n)\text{.}\)
🔗
Bagaimana dengan lintasan yang melalui \((1,n-1)\text{?}\) Terdapat \(\binom{n}{1}\) lintasan untuk mencapai titik tersebut (\(n\) langkah, 1 ke kanan) dan \(\binom{n}{1}\) lintasan untuk menyelesaikan perjalanan ke \((n,n)\) (\(n\) langkah, \(1\) ke atas). Jadi, terdapat \(\binom{n}{1}\binom{n}{1}\) lintasan dari \((0,0)\) ke \((n,n)\) yang melalui \((1,n-1)\text{.}\)
🔗
Secara umum, untuk mencapai \((n,n)\) melalui titik \((k,n-k)\text{,}\) kita memiliki \(\binom{n}{k}\) lintasan menuju titik tengah tersebut, lalu \(\binom{n}{k}\) lintasan dari titik tengah ke \((n,n)\text{.}\) Jadi, terdapat \(\binom{n}{k}\binom{n}{k}\) lintasan dari \((0,0)\) ke \((n,n)\) yang melalui \((k, n-k)\text{.}\)
🔗
Dengan demikian, jumlah seluruh lintasan dari \((0,0)\) ke \((n,n)\) yang melalui tepat satu dari titik-titik tengah ini adalah
\begin{equation*} \binom{n}{0}^2 + \binom{n}{1}^2 + \binom{n}{2}^2 + \cdots + \binom{n}{n}^2\text{.} \end{equation*}
🔗
Karena kedua jawaban ini menjawab pertanyaan yang sama, keduanya harus sama, sehingga
\begin{equation*} \binom{n}{0}^2 + \binom{n}{1}^2 + \binom{n}{2}^2 + \cdots + \binom{n}{n}^2 = \binom{2n}{n}\text{.} \end{equation*}
🔗
🔗
🔗
🔗
🔗

Pertanyaan Bacaan Pertanyaan Bacaan

1.

Manakah di antara pilihan berikut yang mendeskripsikan strategi umum pembuktian kombinatorial?
🔗
  • Ajukan pertanyaan pencacahan yang dapat dijawab dengan dua cara (dan jawablah pertanyaan itu).
    🔗
  • Benar. Setiap cara menjawab pertanyaan harus menghasilkan salah satu ruas identitas.
  • Ajukan dua pertanyaan pencacahan yang keduanya dapat dijawab dengan cara yang sama (dan jawablah kedua pertanyaan itu).
    🔗
  • Belum tepat. Anda menggunakan pembuktian kombinatorial untuk membuktikan identitas yang memiliki dua “ruas” berbeda.
  • Sederhanakan ekspresi aljabar pada setiap ruas identitas kombinatorial.
    🔗
  • Meskipun beberapa identitas dapat dibuktikan secara aljabar, cara ini bukan yang digunakan dalam pembuktian kombinatorial.
  • Anggap identitas gagal berlaku untuk suatu nilai terkecil, lalu peroleh kontradiksi dengan memperhatikan nilai yang lebih kecil.
    🔗
  • Ini merupakan argumen bergaya contoh penyangkal minimal, yang mungkin juga menjadi pembuktian yang sah, tetapi bukan yang kita maksud dengan pembuktian kombinatorial.
🔗

2.

Tuliskan pertanyaan pencacahan yang dapat Anda gunakan untuk membuktikan identitas:
\begin{equation*} \binom{x+y}{x} = \binom{x+y}{y}\text{.} \end{equation*}
🔗
🔗

3.

Pertanyaan apa yang Anda miliki setelah membaca bagian ini? Tuliskan sedikitnya satu pertanyaan tentang isi bagian ini yang membuat Anda ingin tahu.
🔗
🔗
🔗

Latihan Soal Latihan

1.

Buatlah pembuktian kombinatorial untuk identitas \(10+10 = 2\cdot 10\text{.}\)
🔗
🔗

2.

Jika Anda diminta memberikan pembuktian kombinatorial untuk identitas \(\binom{n}{2}\binom{n-2}{k} = \binom{n}{k}\binom{n-k}{2}\text{,}\) manakah di antara pertanyaan berikut yang layak digunakan?
🔗
  • Ada berapa cara untuk memilih \(2\) rasa es krim dari \(n\) pilihan dan \(k\) taburan untuk sundae Anda?
    🔗
  • Ini tidak akan membantu karena ketika kita berpindah dari satu ruas persamaan ke ruas lainnya, kita tidak menghitung hal yang sama. Kita memerlukan pertanyaan yang membuat \(k\) benda dan \(2\) benda berasal dari himpunan yang sama, yang terdiri atas \(n\) benda.
  • Ada berapa cara untuk memilih \(k\) dasi kupu-kupu yang akan dimasukkan ke bagasi tercatat dan 2 dasi kupu-kupu lainnya yang akan dimasukkan ke bagasi kabin, dari koleksi \(n\) dasi kupu-kupu?
    🔗
  • Ada \(n\) siswa dalam Klub Matematika. Ada berapa cara untuk memilih suatu subhimpunan berukuran \(2\) atau \(k\) yang akan menjalankan penggalangan dana musim gugur?
    🔗
  • Jika kita menginginkan \(2\) atau \(k\) orang, kita harus menjumlahkan banyaknya hasil dari masing-masing pilihan.
  • Dari kelas yang terdiri atas \(n\) siswa, ada berapa cara untuk memilih 2 siswa sebagai pengawas dan \(k\) siswa lainnya sebagai anggota panitia perencana pesta?
    🔗
🔗
🔗

Latihan Latihan Tambahan

1.

Berikan pembuktian kombinatorial untuk identitas \(2+2+2 = 3\cdot 2\text{.}\)
🔗
🔗

2.

Misalkan Anda memiliki \(x\) fez dan \(y\) dasi kupu-kupu. Tentu saja, \(x\) dan \(y\) keduanya lebih besar dari 1.
  1. Ada berapa kombinasi fez dan dasi kupu-kupu yang dapat Anda buat? Anda hanya dapat mengenakan satu fez dan satu dasi kupu-kupu pada satu waktu. Jelaskan.
    🔗
    🔗
  2. Jelaskan mengapa jawabannya juga \({x+y \choose 2} - {x \choose 2} - {y \choose 2}\text{.}\) (Jika ini adalah jawaban yang Anda berikan pada bagian (a), cobalah lagi.)
    🔗
    🔗
  3. Gunakan jawaban Anda pada bagian (a) dan (b) untuk memberikan pembuktian kombinatorial bagi identitas
    \begin{equation*} {x+y \choose 2} - {x \choose 2} - {y \choose 2} = xy\text{.} \end{equation*}
    🔗
    🔗
🔗
🔗

3.

Ada berapa segitiga yang dapat Anda gambar dengan menggunakan titik-titik di bawah ini sebagai simpul?
🔗
Dua belas titik tersusun membentuk setengah lingkaran. Tujuh titik terletak pada diameter horizontal lingkaran, sedangkan lima titik sisanya terletak pada keliling lingkaran.
  1. Temukan ekspresi untuk jawaban yang berupa jumlah tiga suku yang melibatkan koefisien binomial.
    🔗
    🔗
  2. Temukan ekspresi untuk jawaban yang berupa selisih dua koefisien binomial.
    🔗
    🔗
  3. Generalisasikan hasil di atas untuk menyatakan dan membuktikan suatu identitas binomial dengan pembuktian kombinatorial. Misalkan Anda memiliki \(x\) titik pada sumbu horizontal dan \(y\) titik pada setengah lingkaran.
    🔗
    🔗
🔗
Petunjuk.
Akan terdapat 185 segitiga. Namun, untuk menemukannya …
  1. Berapa banyak simpul segitiga yang dapat berada pada sumbu horizontal?
    🔗
    🔗
  2. Apakah sembarang tiga titik dapat menjadi simpul-simpulnya?
    🔗
    🔗
🔗
🔗
🔗

4.

Perhatikan semua segitiga yang dapat Anda buat dengan menggunakan titik-titik di bawah ini sebagai simpul. Perhatikan bahwa kita tidak mengizinkan segitiga degenerat (yang ketiga simpulnya berada pada garis yang sama), tetapi kita mengizinkan segitiga yang bukan segitiga siku-siku.
🔗
Lima titik berjarak sama pada garis vertikal dan enam titik tambahan berjarak sama yang memanjang ke kanan pada garis horizontal dari titik terendah (membentuk sudut siku-siku).
  1. Tentukan banyaknya segitiga, dan jelaskan mengapa jawaban Anda benar.
    🔗
    🔗
  2. Tentukan kembali banyaknya segitiga dengan menggunakan metode yang berbeda. Jelaskan mengapa metode baru Anda berhasil.
    🔗
    🔗
  3. Nyatakan identitas binomial yang dibuktikan oleh kedua jawaban Anda di atas (yaitu, berikan identitas binomial yang dibuktikan oleh kedua jawaban tersebut). Kemudian generalisasikan dengan menggunakan \(m\) dan \(n\text{.}\)
    🔗
    🔗
🔗
Petunjuk.
Jawabannya adalah 120.
🔗
🔗
🔗

5.

Seorang perempuan akan menikah. Ia memiliki 15 sahabat, tetapi hanya dapat memilih 6 di antaranya sebagai pengiring pengantin, dan salah seorang di antaranya harus menjadi pengiring pengantin utama. Ada berapa cara untuk melakukannya?
🔗
  1. Bagaimana jika ia terlebih dahulu memilih 6 pengiring pengantin, lalu memilih salah seorang di antaranya sebagai pengiring pengantin utama?
    🔗
    🔗
  2. Bagaimana jika ia terlebih dahulu memilih pengiring pengantin utama, lalu 5 pengiring pengantin lainnya?
    🔗
    🔗
  3. Jelaskan mengapa \(6 {15 \choose 6} = 15 {14 \choose 5}\text{.}\)
    🔗
    🔗
🔗

6.

Perhatikan identitas berikut:
\begin{equation*} k{n\choose k} = n{n-1 \choose k-1}\text{.} \end{equation*}
  1. Apakah identitas ini benar? Cobalah untuk beberapa nilai \(n\) dan \(k\text{.}\)
    🔗
    🔗
  2. Gunakan rumus \({n \choose k}\) untuk memberikan pembuktian aljabar bagi identitas tersebut.
    🔗
    🔗
  3. Berikan pembuktian kombinatorial bagi identitas tersebut.
    🔗
    🔗
🔗
Petunjuk.
Cobalah Latihan 5.
🔗
🔗
🔗

7.

Berikan pembuktian kombinatorial bagi identitas \({n \choose 2}{n-2 \choose k-2} = {n\choose k}{k \choose 2}\text{.}\)
🔗
Petunjuk.
Bagaimana jika Anda menginginkan sepasang pengiring pengantin utama bersama?
🔗
🔗
🔗

8.

Perhatikan identitas binomial
\begin{equation*} \binom{n}{1} + 2 \binom{n}{2} + 3 \binom{n}{3} + \cdots + n\binom{n}{n} = n2^{n-1}\text{.} \end{equation*}
  1. Berikan pembuktian kombinatorial bagi identitas ini. Petunjuk: Bagaimana jika sejumlah orang dari kelompok beranggotakan \(n\) orang ingin pergi ke ruang teka-teki, dan salah seorang yang pergi harus menjadi kapten tim?
    🔗
    🔗
  2. Berikan pembuktian alternatif dengan menjabarkan \((1+x)^n\) dan menurunkan kedua ruas.
    🔗
    🔗
🔗
Petunjuk.
Untuk pembuktian kombinatorial: bagaimana jika Anda belum mengetahui berapa banyak pengiring pengantin yang akan dipilih?
🔗
🔗
🔗

9.

Berikan pembuktian kombinatorial bagi identitas \(1 + 2 + 3 + \cdots + n = {n+1 \choose 2}\text{.}\)
🔗
Petunjuk.
Hitung jabat tangan.
🔗
🔗
🔗

10.

Perhatikan string bit dalam \(\B^6_2\) (string bit berpanjang 6 dan berbobot 2).
🔗
  1. Ada berapa string bit tersebut yang diawali dengan 1?
    🔗
    🔗
  2. Ada berapa string bit tersebut yang diawali dengan 01?
    🔗
    🔗
  3. Ada berapa string bit tersebut yang diawali dengan 001?
    🔗
    🔗
  4. Apakah ada string lain yang belum kita hitung? String mana saja, dan ada berapa?
    🔗
    🔗
  5. Berapa jumlah seluruh string bit dalam \(\B^6_2\text{?}\)
    🔗
    🔗
  6. Identitas binomial apa yang baru saja Anda buktikan secara kombinatorial?
    🔗
    🔗
🔗

11.

Mari kita menghitung string digit terner, yaitu string yang setiap digitnya dapat berupa 0, 1, atau 2.
  1. Ada berapa string digit terner yang memuat tepat \(n\) digit?
    🔗
    🔗
  2. Ada berapa string digit terner yang memuat tepat \(n\) digit dan \(n\) angka 2?
    🔗
    🔗
  3. Ada berapa string digit terner yang memuat tepat \(n\) digit dan \(n-1\) angka 2? (Petunjuk: Di mana Anda dapat menempatkan digit yang bukan 2, dan nilai apa yang dapat dimilikinya?)
    🔗
    🔗
  4. Ada berapa string digit terner yang memuat tepat \(n\) digit dan \(n-2\) angka 2? (Petunjuk: Lihat petunjuk sebelumnya.)
    🔗
    🔗
  5. Ada berapa string digit terner yang memuat tepat \(n\) digit dan \(n-k\) angka 2?
    🔗
    🔗
  6. Ada berapa string digit terner yang memuat tepat \(n\) digit dan tidak memuat angka 2? (Petunjuk: String jenis apa ini?)
    🔗
    🔗
  7. Gunakan bagian-bagian di atas untuk memberikan pembuktian kombinatorial bagi identitas
    \begin{equation*} {n \choose 0} + 2{n \choose 1} + 2^2{n \choose 2} + 2^3{n \choose 3} + \cdots + 2^n{n \choose n} = 3^n\text{.} \end{equation*}
    🔗
    🔗
🔗
🔗

12.

Ada berapa cara untuk menyusun ulang huruf-huruf dalam kata “rearrange”? Jawab pertanyaan ini dengan sedikitnya dua cara berbeda untuk membuktikan suatu identitas binomial.
🔗
🔗

13.

Buktikan identitas di bawah ini dengan pembuktian kombinatorial.
\begin{equation*} {2 \choose 2}{n \choose 2} + {3 \choose 2}{n-1 \choose 2} + {4\choose 2}{n-2 \choose 2} + \cdots + {n\choose 2}{2\choose 2} = {n+3 \choose 5}\text{.} \end{equation*}
🔗
Petunjuk.
Soal ini mungkin mengingatkan Anda pada Contoh 3.6.6
🔗
🔗
🔗

14.

Dalam Contoh 3.6.5 kita telah membuktikan bahwa jumlah sembarang baris dalam Segitiga Pascal merupakan perpangkatan dua. Secara khusus,
\begin{equation*} {n\choose 0} + {n \choose 1} + {n\choose 2} + \cdots + {n \choose n} = 2^n\text{.} \end{equation*}
Argumen yang diberikan di sana menggunakan pertanyaan pencacahan, “Ada berapa pizza yang dapat Anda buat dengan menggunakan sembarang banyak dari \(n\) taburan berbeda?” Untuk berlatih, berikan pembuktian baru bagi identitas ini dengan menggunakan pertanyaan yang berbeda.
  1. Gunakan pertanyaan tentang pencacahan subhimpunan.
    🔗
    🔗
  2. Gunakan pertanyaan tentang pencacahan string bit.
    🔗
    🔗
  3. Gunakan pertanyaan tentang pencacahan lintasan kisi.
    🔗
    🔗
🔗
Petunjuk.
Untuk lintasan kisi, pikirkan jenis lintasan yang dicacah oleh \(2^n\text{.}\) Tidak semua lintasan akan berakhir pada titik yang sama, tetapi Anda dapat mendeskripsikan himpunan titik akhirnya sebagai sebuah garis.
🔗
🔗
🔗

15.

  1. Pemenang Piala Stanley ditentukan melalui seri terbaik dari 7 pertandingan antara dua tim. Ada berapa cara tim Anda dapat menang? Mari kita jawab pertanyaan ini dengan dua cara:
    1. Berapa dari 7 pertandingan yang harus dimenangi tim Anda? Ada berapa cara hal ini dapat terjadi?
      🔗
      🔗
    2. Bagaimana jika seri berlangsung hingga seluruh 7 pertandingan? Berarti Anda memenangi pertandingan terakhir. Ada berapa kemungkinan hasil untuk 6 pertandingan pertama?
      🔗
      🔗
    3. Bagaimana jika seri hanya berlangsung 6 pertandingan? Ada berapa cara hal ini dapat terjadi? Bagaimana jika 5 pertandingan? 4 pertandingan?
      🔗
      🔗
    4. Apa dua cara berbeda untuk menghitung banyaknya cara tim Anda dapat menang? Tuliskan persamaan yang melibatkan koefisien binomial (yaitu \({n \choose k}\)). Pola apa dalam Segitiga Pascal yang dicontohkan oleh persamaan ini?
      🔗
      🔗
    🔗
    🔗
  2. Generalisasikan. Bagaimana jika aturannya berubah dan Anda memainkan seri terbaik dari \(9\) pertandingan (memerlukan 5 kemenangan)? Bagaimana jika Anda memainkan seri \(n\) pertandingan dengan \(k\) kemenangan yang diperlukan untuk menjadi juara?
    🔗
    🔗
🔗
🔗

16.

Misalkan \(k_1, k_2, \ldots, k_j\) merupakan daftar bilangan bulat positif yang jumlahnya \(n\) (yaitu, \(\sum_{i=1}^j k_i = n\)). Gunakan dua graf yang memuat \(n\) simpul untuk menjelaskan mengapa
\begin{equation*} \sum_{i = 1}^j \binom{k_i}{2} \le \binom{n}{2}\text{.} \end{equation*}
🔗
Petunjuk.
Berapa banyak sisi yang dimiliki \(K_n\text{?}\) Salah satu dari kedua graf tidak akan terhubung (kecuali \(j=1\) ).
🔗
🔗
🔗
🔗
🔗
SblmTopLnjt
Umpan Balik