Membiarkan $b_{n}$ menunjukkan jumlah komposisi $n$ ke $k$bagian, di mana setiap bagian adalah satu atau dua. Temukan seri penghasil untuk $b_{n}$
Saya terjebak dengan masalah kombinatorik ini -
Membiarkan $n$ menjadi bilangan bulat positif dan biarkan $b_{n}$ menunjukkan jumlah komposisi $n$ ke $k$bagian, di mana setiap bagian adalah satu atau dua. Sebagai contoh,$(1, 2, 1, 2, 1)$ dan $(2, 2, 1, 1, 1)$ adalah dua komposisi $n = 7$ ke $k = 5$ bagian.
Pertama, kita perlu mencari seri pembangkit untuk $b_{n}$
Kedua, Buktikan itu $b_{n} = {k \choose n-k}$ untuk $k\le n \le2k$ dan $b_{n} = 0$ jika tidak.
Jawaban
Untuk menghitung seri pembangkit -
Biarkan {1,2}$^{𝑘}$ menjadi himpunan komposisi dengan k bagian, masing-masing adalah 1 atau 2.
Kemudian, terapkan "Lemma Produk" $$\varphi_{s}(x) = (\varphi_{(1,2)} (x))^{k} = (x+x^{2})^{k} $$
Membuktikan -
Komposisi n dengan k bagian akan memiliki $i$ bagian sama dengan 2, untuk beberapa $0\le i\le k$. Perhatikan bahwa jumlah bagian yang sama dengan 1 adalah$k-i$, dan $n = (k-i) + 2i$, memberi $i = n-k$. Ada$k$ posisi untuk $n-k$ bagian sama dengan 2, jadi ada total {k \ pilih nk} komposisi $n$ ke $k$ bagian, masing-masing $1$ atau $2$. Catat itu$0\le i\le k$ menyiratkan $k\le n\le 2k$, dan jumlah komposisi adalah nol.
Ada bukti kombinatorial yang bagus untuk pertanyaan kedua:
Jumlah komposisi $n$ ke $k$ bagian masing-masing sama dengan $1$ atau $2$ sama dengan jumlah komposisi $n-k$ ke $k$ bagian masing-masing sama dengan $0$ atau $1$. Jelas pasti ada$n-k$ $1$s dalam komposisi seperti itu, dan ada $\binom k{n-k}$ cara mengaturnya $1$s di antara $k$ bagian.
(1) Benar $(x+x^2)^k=x^k(1+x)^k$
(2) Koefisien $x^n$ masuk $x^k(1+x)^k$ sama dengan $x^{n-k}$ di $(1+x)^k$. Oleh karena itu dengan teorema binomial${k\choose n-k}$