Latihan 8.8 Latihan

Sistem aljabar komputer dapat menjadi alat yang ampuh untuk bekerja dengan fungsi pembangkit. Namun, kecuali jika suatu latihan secara khusus menyarankan penggunaan sistem aljabar komputer, kami sangat menganjurkan Anda menyelesaikan persoalan secara manual. Hal ini akan membantu Anda memahami penggunaan fungsi pembangkit dengan lebih baik. Anda dapat menyunting isi Sel SageMath dalam Subbab 8.2 untuk membantu menyelesaikan persoalan di sini ketika sistem aljabar komputer disarankan. Dalam beberapa kasus, kami juga telah menyertakan Sel SageMath di dalam latihan untuk Anda gunakan.

Dalam semua latihan pada bagian ini, “fungsi pembangkit” harus diartikan sebagai “fungsi pembangkit biasa.” Fungsi pembangkit eksponensial hanya diperlukan dalam latihan yang menyebutkannya secara khusus.

1.

Untuk setiap barisan hingga di bawah ini, berikan fungsi pembangkitnya.

$\displaystyle 1, 4, 6, 4, 1$
$\displaystyle 1,1,1,1,1,0,0,1$
$\displaystyle 0,0,0,1,2,3,4,5$
$\displaystyle 1,1,1,1,1,1,1$
$\displaystyle 3,0,0,1,-4,7$
$\displaystyle 0,0,0,0,1,2,-3,0,1$

2.

Untuk setiap barisan tak hingga yang ditunjukkan di bawah ini, berikan fungsi pembangkitnya dalam bentuk tertutup, i.e., bukan sebagai jumlah tak hingga. (Gunakan pilihan bentuk yang paling jelas bagi suku umum setiap barisan.)

$\displaystyle 0,1,1,1,1,1,\dots$
$\displaystyle 1,0,0,1,0,0,1,0,0,1,0,0,1,\dots$
$\displaystyle 1,2,4,8,16,32,\dots$
$\displaystyle 0,0,0,0,1,1,1,1,1,1,1,1,1,1,1,\dots$
$\displaystyle 1,-1,1,-1,1,-1,1,-1,1,-1,\dots$
$\displaystyle \displaystyle 2^8,2^7\binom{8}{1}, 2^6\binom{8}{2},\dots,\binom{8}{8},0,0,0,\dots$
$\displaystyle 1,1,1,0,0,1,1,1,1,1,1,1,1,1,\dots$
$\displaystyle 0,0,0,1,2,3,4,5,6,\dots$
$\displaystyle 3,2,4,1,1,1,1,1,1,\dots$
$\displaystyle 0,2,0,0,2,0,0,2,0,0,2,0,0,2,\dots$
$\displaystyle 6,0,-6,0,6,0,-6,0,6,\dots$
$\displaystyle \displaystyle 1,3,6,10,15,\dots,\binom{n+2}{2},\dots$

3.

Untuk setiap fungsi pembangkit di bawah ini, berikan bentuk tertutup bagi suku $n^{\text{th} }$ dari barisan yang bersesuaian.

$\displaystyle (1+x)^{10}$
$\displaystyle \displaystyle \frac{1}{1-x^4}$
$\displaystyle \displaystyle \frac{x^3}{1-x^4}$
$\displaystyle \displaystyle \frac{1-x^4}{1-x}$
$\displaystyle \displaystyle \frac{1+x^2-x^4}{1-x}$
$\displaystyle \displaystyle \frac{1}{1-4x}$
$\displaystyle \displaystyle \frac{1}{1+4x}$
$\displaystyle \displaystyle \frac{x^5}{(1-x)^4}$
$\displaystyle \displaystyle \frac{x^2+x+1}{1-x^7}$
$\displaystyle \displaystyle 3x^4 + 7x^3 -x^2 + 10 + \frac{1}{1-x^3}$

4.

Tentukan koefisien $x^{10}$ dalam setiap fungsi pembangkit di bawah ini.

$\displaystyle (x^3+x^5+x^6)(x^4+x^5+x^7) (1+x^5+x^{10}+x^{15}+\cdots)$
$\displaystyle (1+x^3) (x^3+x^4+x^5+\cdots)(x^4+x^5+x^6+x^7+x^8+\cdots)$
$\displaystyle (1+x)^{12}$
$\displaystyle \displaystyle\frac{x^5}{1-3x^5}$
$\displaystyle \displaystyle\frac{1}{(1-x)^3}$
$\displaystyle \displaystyle\frac{1}{1-5x^4}$
$\displaystyle \displaystyle\frac{x}{1-2x^3}$
$\displaystyle \displaystyle\frac{1-x^{14}}{1-x}$

5.

Tentukan fungsi pembangkit untuk banyaknya cara membuat seikat $n$ balon yang dipilih dari balon putih, emas, dan biru sedemikian sehingga ikatan tersebut memuat sedikitnya satu balon putih, sedikitnya satu balon emas, dan paling banyak dua balon biru. Ada berapa cara untuk membuat seikat $10$ balon yang memenuhi persyaratan ini?

6.

Seorang koordinator sukarelawan memiliki $30$ kukis keping cokelat identik untuk dibagikan kepada enam sukarelawan. Gunakan fungsi pembangkit (dan sistem aljabar komputer) untuk menentukan banyaknya cara ia dapat membagikan kukis tersebut sedemikian sehingga setiap sukarelawan menerima sedikitnya dua kukis dan paling banyak tujuh kukis.

7.

Perhatikan pertidaksamaan

\begin{equation*} x_1+x_2+x_3+x_4\leq n \end{equation*}

dengan $x_1,x_2,x_3,x_4,n\geq 0$ semuanya bilangan bulat. Misalkan pula bahwa $x_2\geq 2\text{,}$ $x_3$ merupakan kelipatan $4\text{,}$ dan $0\leq x_4\leq 3\text{.}$ Misalkan $c_n$ adalah banyaknya solusi pertidaksamaan yang memenuhi pembatasan tersebut. Tentukan fungsi pembangkit bagi barisan $\{c_n\colon n\geq 0\}$ dan gunakan fungsi itu untuk menentukan rumus tertutup bagi $c_n\text{.}$

8.

Tentukan fungsi pembangkit untuk banyaknya cara membagikan kertas buram kosong kepada Alice, Bob, Carlos, dan Dave sedemikian sehingga Alice memperoleh sedikitnya dua lembar, Bob memperoleh paling banyak tiga lembar, banyaknya lembar yang diterima Carlos merupakan kelipatan tiga, dan Dave memperoleh sedikitnya satu lembar tetapi paling banyak enam lembar kertas buram. Tanpa mencari penjabaran deret pangkat fungsi pembangkit ini (atau menggunakan sistem aljabar komputer!), tentukan koefisien $x^2$ dan $x^3$ dalam fungsi pembangkit tersebut.

9.

Berapakah fungsi pembangkit untuk banyaknya cara memilih sekelompok $n$ siswa dari kelas yang beranggotakan $p$ siswa?

10.

Dengan menggunakan fungsi pembangkit, tentukan rumus untuk banyaknya jenis keranjang buah berbeda yang berisi $n$ buah pilihan dari delima, pisang, apel, jeruk, pir, dan buah ara serta memenuhi pembatasan berikut:

terdapat tepat $0$ atau $2$ delima,
terdapat sedikitnya $1$ pisang,
banyaknya buah ara merupakan kelipatan $5\text{,}$
terdapat paling banyak $4$ pir, dan
banyaknya apel dan jeruk tidak dibatasi.

Ada berapa cara untuk membentuk keranjang buah seperti itu dengan $n=25$ buah?

11.

Dengan menggunakan fungsi pembangkit, tentukan banyaknya cara menukar selembar uang $100$ dolar dengan hanya menggunakan koin satu dolar serta uang kertas $$1\text{,}$ $$2\text{,}$ dan $$5\text{.}$

Petunjuk.

Tentukan penjabaran pecahan parsial bagi fungsi pembangkit Anda. Berhati-hatilah karena Anda menginginkan penjabaran pecahan parsial yang semua polinom penyebutnya memiliki koefisien bilangan bulat. Metode partial_fraction() dalam SageMath akan berguna, dan pretty_print akan membuat hasilnya lebih mudah dibaca. Setelah memperoleh penjabaran pecahan parsial yang tepat, identitas berikut mungkin berguna

\begin{equation*} \frac{p(x)}{1+x+x^2+\cdots + x^k} = \frac{p(x)(1-x)}{1-x^{k+1}}, \end{equation*}

dengan $p(x)$ berupa polinom dalam kasus ini.

12.

Seorang pebisnis sedang bepergian di Belgia dan ingin membeli cokelat untuk dirinya, suaminya, dan kedua putri mereka. Sebuah toko menyediakan trufel cokelat hitam (€10/kotak), trufel cokelat susu (€8/kotak), cokelat isi nougat (€5/kotak), batang cokelat susu (€7/batang), dan batang cokelat kakao 75% (€11/batang). Pembeliannya harus memenuhi ketentuan berikut:

Hanya kedua putrinya yang menyukai trufel cokelat hitam, dan pembelian tersebut harus memastikan bahwa setiap putri memperoleh jumlah kotak yang sama (jika mereka mendapatkannya).
Sedikitnya dua kotak trufel cokelat susu harus dibeli.
Jika ia membeli cokelat isi nougat, jumlahnya harus tepat cukup agar setiap anggota keluarga memperoleh satu kotak.
Paling banyak tiga batang cokelat susu boleh dibeli.
Banyaknya batang cokelat kakao 75% tidak dibatasi.

Misalkan $s_n$ adalah banyaknya cara pebisnis tersebut dapat membelanjakan tepat €$n$ (bukan membeli $n$ barang!) di toko cokelat ini. Tentukan fungsi pembangkit bagi barisan $\{s_n\colon n\geq 0\}\text{.}$ Dengan berapa cara ia dapat membelanjakan tepat €100 di toko cokelat tersebut? (Sistem aljabar komputer akan berguna untuk menentukan koefisien.)

13.

Kantong-kantong permen sedang disiapkan untuk dibagikan kepada anak-anak di sebuah sekolah. Jenis permen yang tersedia adalah gigitan cokelat, cangkir selai kacang, permen pepermin, dan permen kenyal buah. Setiap kantong harus memuat sedikitnya dua gigitan cokelat, sejumlah genap cangkir selai kacang, dan paling banyak enam permen pepermin. Permen kenyal buah tersedia dalam empat rasa berbeda—lemon, jeruk, stroberi, dan ceri. Sebuah kantong boleh memuat paling banyak dua permen kenyal buah, yang rasanya boleh sama atau berbeda. Selain dibedakan berdasarkan banyaknya setiap jenis permen, kantong-kantong tersebut juga dibedakan berdasarkan rasa permen kenyal buah yang disertakan, bukan hanya jumlahnya. Sebagai contoh, kantong yang memuat dua permen kenyal rasa jeruk berbeda dari kantong yang memuat satu permen kenyal rasa ceri dan satu rasa stroberi, meskipun banyaknya setiap jenis permen lainnya sama.

Misalkan $b_n$ adalah banyaknya kantong permen berbeda berisi $n$ butir permen yang dapat dibentuk dengan memenuhi pembatasan ini. Tentukan fungsi pembangkit bagi barisan $\{b_n\colon n\geq 0\}\text{.}$
Misalkan sekolah tersebut memiliki $400$ siswa dan para guru ingin memastikan bahwa setiap siswa memperoleh kantong permen yang berbeda. Namun, mereka tahu akan terjadi pertengkaran jika semua kantong tidak memuat jumlah butir permen yang sama. Berapakah jumlah butir permen terkecil yang dapat mereka masukkan ke dalam setiap kantong sehingga setiap siswa memperoleh kantong berbeda dengan jumlah butir permen yang sama?

14.

Buatlah suatu persoalan kombinatorial (serupa dengan yang terdapat dalam bab ini) yang menghasilkan fungsi pembangkit

\begin{equation*} \frac{(1+x^2+x^4)x^2}{(1-x)^3(1-x^3)(1-x^{10})}. \end{equation*}

15.

Gerbang tol di Illinois menerima semua koin Amerika Serikat, termasuk koin satu sen. Carlos membawa sangat banyak koin satu sen, lima sen, sepuluh sen, dan dua puluh lima sen di mobilnya saat berkendara di jalan tol. Ia menghadapi tarif tol sebesar $$0.95$ dan bertanya-tanya ada berapa cara berbeda untuk menggunakan persediaan koinnya guna membayar tol tanpa menerima uang kembalian. (Setelah memperoleh fungsi pembangkit, sistem aljabar komputer mungkin merupakan cara terbaik untuk mendapatkan koefisien yang diperlukan karena Anda tidak diminta mencari koefisien $x^n\text{.}$)

Gunakan fungsi pembangkit dan sistem aljabar komputer untuk menentukan banyaknya cara Carlos dapat membayar tol $$0.95$ dengan menjatuhkan koin secara bersama-sama ke dalam wadah tol. (Anggaplah koin dengan denominasi yang sama tidak dapat dibedakan.)
Misalkan tidak tersedia wadah tempat pengendara menjatuhkan koin untuk membayar tol; sebagai gantinya, koin harus dimasukkan satu per satu ke dalam celah koin. Dalam skenario ini, Carlos bertanya-tanya ada berapa cara ia dapat membayar tol $$0.95$ ketika urutan pemasukan koin diperhitungkan. Sebagai contoh, pada bagian sebelumnya, penggunaan tiga koin dua puluh lima sen dan dua koin sepuluh sen hanya dihitung satu kali. Namun, ketika koin harus dimasukkan satu per satu ke dalam celah, terdapat $10=C(5,2)$ urutan untuk memasukkan kombinasi ini. Gunakan fungsi pembangkit dan sistem aljabar komputer untuk menentukan banyaknya cara Carlos dapat membayar tol $$0.95$ dengan memperhitungkan urutan pemasukan koin.

Petunjuk.

Untuk bagian b, Anda benar-benar memerlukan fungsi pembangkit biasa, bukan fungsi pembangkit eksponensial, meskipun urutan diperhitungkan. Setelah merasa telah memperoleh fungsi pembangkit yang tepat, Anda dapat memeriksa koefisien $x^5,\dots,x^{10}$ secara manual untuk memastikan bahwa langkah Anda sudah benar.

16.

Daftarkan semua partisi dari $9\text{.}$ Tuliskan B di samping setiap partisi menjadi bagian-bagian berbeda dan G di samping setiap partisi menjadi bagian-bagian ganjil.

17.

Gunakan fungsi pembangkit untuk menentukan banyaknya cara mempartisi $10$ menjadi bagian-bagian ganjil.

18.

Berapakah bilangan bulat terkecil yang dapat dipartisi dengan sedikitnya $1000$ cara? Ada berapa cara bilangan tersebut dapat dipartisi? Berapa banyak di antaranya yang terdiri atas bagian-bagian berbeda? (Sistem aljabar komputer akan berguna untuk latihan ini.)

19.

Berapakah fungsi pembangkit untuk banyaknya partisi suatu bilangan bulat menjadi bagian-bagian genap?

20.

Tentukan fungsi pembangkit eksponensial (dalam bentuk tertutup, bukan sebagai jumlah tak hingga) bagi setiap barisan tak hingga $\{a_n\colon n\geq 0\}$ yang suku umumnya diberikan di bawah ini.

$\displaystyle a_n = 5^n$
$\displaystyle a_n = (-1)^n2^n$
$\displaystyle a_n = 3^{n+2}$
$\displaystyle a_n = n!$
$\displaystyle a_n = n$
$\displaystyle a_n = 1/(n+1)$

21.

Untuk setiap fungsi pembangkit eksponensial di bawah ini, berikan rumus bentuk tertutup bagi barisan $\{a_n\colon n\geq 0\}$ yang dinyatakannya.

$\displaystyle e^{7x}$
$\displaystyle x^2 e^{3x}$
$\displaystyle \displaystyle \frac{1}{1+x}$
$\displaystyle e^{x^4}$

22.

Tentukan koefisien $x^{10}/{10!}$ dalam setiap fungsi pembangkit eksponensial di bawah ini.

$\displaystyle e^{3x}$
$\displaystyle \displaystyle\frac{e^x-e^{-x}}{2}$
$\displaystyle \displaystyle\frac{e^x+e^{-x}}{2}$
$\displaystyle xe^{3x}-x^2$
$\displaystyle \displaystyle\frac{1}{1-2x}$
$\displaystyle e^{x^2}$

23.

Tentukan fungsi pembangkit eksponensial untuk banyaknya untai dengan panjang $n$ yang dibentuk dari himpunan $\{a,b,c,d\}$ jika harus terdapat sedikitnya satu $a$ dan banyaknya $c$ harus genap. Tentukan rumus tertutup bagi koefisien fungsi pembangkit eksponensial ini.

24.

Tentukan fungsi pembangkit eksponensial untuk banyaknya untai dengan panjang $n$ yang dibentuk dari himpunan $\{a,b,c,d\}$ jika harus terdapat sedikitnya satu $a$ dan banyaknya $c$ harus ganjil. Tentukan rumus tertutup bagi koefisien fungsi pembangkit eksponensial ini.

25.

Tentukan fungsi pembangkit eksponensial untuk banyaknya untai dengan panjang $n$ yang dibentuk dari himpunan $\{a,b,c,d\}$ jika harus terdapat sedikitnya satu $a\text{,}$ banyaknya $b$ harus ganjil, dan banyaknya $d$ harus $1$ atau $2\text{.}$ Tentukan rumus tertutup bagi koefisien fungsi pembangkit eksponensial ini.

26.

Tentukan fungsi pembangkit eksponensial untuk banyaknya untai alfanumerik dengan panjang $n$ yang dibentuk dari $26$ huruf kapital alfabet Inggris dan $10$ digit desimal jika

setiap huruf vokal harus muncul sedikitnya satu kali;
huruf $T$ harus muncul sedikitnya tiga kali;
huruf $Z$ boleh muncul paling banyak tiga kali;
setiap digit genap harus muncul dalam jumlah genap; dan
setiap digit ganjil harus muncul dalam jumlah ganjil.

27.

Perhatikan pertidaksamaan

\begin{equation*} x_1+x_2+x_3+x_4\leq n \end{equation*}

dengan $x_1,x_2,x_3,x_4,n\geq 0$ semuanya bilangan bulat. Misalkan pula bahwa $x_2\geq 2\text{,}$ $x_3$ merupakan kelipatan $4\text{,}$ dan $1\leq x_4\leq 3\text{.}$ Misalkan $c_n$ adalah banyaknya solusi pertidaksamaan yang memenuhi pembatasan tersebut. Tentukan fungsi pembangkit bagi barisan $\{c_n\colon n\geq 0\}$ dan gunakan fungsi itu untuk menentukan rumus tertutup bagi $c_n\text{.}$

Petunjuk.

Benar, persoalan ini sangat mirip dengan Latihan 8.8.7. Namun, batas bagi $x_4$ di sini berbeda. Anda dapat mencoba menggunakan sistem aljabar komputer untuk mempercepat pencarian penjabaran pecahan parsial, yang akan memiliki beberapa suku dengan deret pangkat yang dapat segera Anda olah. Untuk suku yang melibatkan $1/(1+x^2)\text{,}$ tentukan deretnya secara manual. Anda mungkin mendapati bahwa solusi persoalan ini terdiri atas dua bagian—satu ketika $n$ genap dan satu lagi ketika $n$ ganjil.

28.

Buktikan Proposisi 8.3 tentang koefisien dalam hasil kali dua fungsi pembangkit biasa.

Sblm Ke Atas Lnjt