Permettere $b_{n}$ denotano il numero di composizioni di $n$ in $k$parti, dove ogni parte è una o due. Trova la serie generatrice per $b_{n}$
Sono bloccato con questi problemi di calcolo combinatorio -
Permettere $n$ essere un numero intero positivo e lascia $b_{n}$ denotano il numero di composizioni di $n$ in $k$parti, dove ogni parte è una o due. Per esempio,$(1, 2, 1, 2, 1)$ e $(2, 2, 1, 1, 1)$ sono due composizioni di $n = 7$ in $k = 5$ parti.
In primo luogo, dobbiamo trovare la serie di generazione per $b_{n}$
In secondo luogo, provalo $b_{n} = {k \choose n-k}$ per $k\le n \le2k$ e $b_{n} = 0$ altrimenti.
Risposte
Per calcolare la serie generatrice -
Lascia {1,2}$^{𝑘}$ essere l'insieme delle composizioni con k parti, ciascuna delle quali è 1 o 2.
Quindi, applicando il "Product Lemma" $$\varphi_{s}(x) = (\varphi_{(1,2)} (x))^{k} = (x+x^{2})^{k} $$
Lievitazione -
Avrà una composizione di n con k parti $i$ parti uguali a 2, per alcuni $0\le i\le k$. Notare che il numero di parti uguale a 1 è$k-i$, e $n = (k-i) + 2i$, dando $i = n-k$. Ci sono$k$ posizioni per il $n-k$ parti uguali a 2, quindi ci sono un totale di {k \ scegli nk} composizioni di $n$ in $k$ parti, ciascuna $1$ o $2$. Nota che$0\le i\le k$ implica $k\le n\le 2k$e il numero di composizioni è altrimenti zero.
C'è una bella prova combinatoria per la seconda domanda:
Il numero di composizioni di $n$ in $k$ parti ciascuna uguale a $1$ o $2$ è uguale al numero di composizioni di $n-k$ in $k$ parti ciascuna uguale a $0$ o $1$. Chiaramente ci deve essere$n-k$ $1$s in una tale composizione, e ci sono $\binom k{n-k}$ modi per organizzarli $1$s tra i $k$ parti.
(1) Lo è $(x+x^2)^k=x^k(1+x)^k$
(2) Il coefficiente di $x^n$ è dentro $x^k(1+x)^k$ uguale a $x^{n-k}$ in $(1+x)^k$. Quindi per teorema binomiale è${k\choose n-k}$