Membiarkan $b_{n}$ menunjukkan jumlah komposisi $n$ ke $k$bagian, di mana setiap bagian adalah satu atau dua. Temukan seri penghasil untuk $b_{n}$

Aug 16 2020

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

4 PrabhSimranSinghBadwal Aug 16 2020 at 19:48

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.

1 GregMartin Aug 17 2020 at 05:39

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.

cr001 Aug 16 2020 at 19:37

(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}$