Encontrar la función generadora del número de soluciones

Question

(a) Encuentre la función generadora del número de soluciones de

$x_1+x_2+x_3+x_4+x_5+x_6=n$ donde $x_1,x_2,x_3$ son incluso $x_4,x_5,x_6$ son impar

(b) Encuentre la función generadora del número de soluciones de

$x_1+x_2+x_3+x_4+x_5=n$

con la condición de que $0\leq x_i \leq 12$ . contesta en la forma cerrada..

Como sé que el número solución para la ecuación $x_1+x_2+x_3+x_4+...+x_k=n$ es C(n+k-1 , k)

Answer 1

Una pista: Empieza por encontrar las funciones generadoras $O(z)$ y $E(z)$ que representan $$ [z^k]O(z)=\begin{cases}1 & \text{for $k$ odd}\\0 & \text{for $k$ even}\end{cases} $$ y $$ [z^k]E(z)=\begin{cases}0 & \text{ for $k$ odd}\\1 & \text{ for $k$ even}\end{cases}. $$ ¿Cómo podrías escribir la función generadora de las sumas de dos números pares? ¿De tres? ¿Y para los números Impares? ¿Cómo puedes combinar estos resultados?

Para la segunda, intenta ver cómo podrías sustituir las condiciones pares e Impares anteriores por algo más adecuado al problema.

Answer 2

$\newcommand{\bbx}[1]{\,\bbox[8px,border:1px groove navy]{{#1}}\,} \newcommand{\braces}[1]{\left\lbrace\,{#1}\,\right\rbrace} \newcommand{\bracks}[1]{\left\lbrack\,{#1}\,\right\rbrack} \newcommand{\dd}{\mathrm{d}} \newcommand{\ds}[1]{\displaystyle{#1}} \newcommand{\expo}[1]{\,\mathrm{e}^{#1}\,} \newcommand{\ic}{\mathrm{i}} \newcommand{\mc}[1]{\mathcal{#1}} \newcommand{\mrm}[1]{\mathrm{#1}} \newcommand{\pars}[1]{\left(\,{#1}\,\right)} \newcommand{\partiald}[3][]{\frac{\partial^{#1} #2}{\partial #3^{#1}}} \newcommand{\root}[2][]{\,\sqrt[#1]{\,{#2}\,}\,} \newcommand{\totald}[3][]{\frac{\mathrm{d}^{#1} #2}{\mathrm{d} #3^{#1}}} \newcommand{\verts}[1]{\left\vert\,{#1}\,\right\vert}$

$\ds{\large\mathbf{\left. a\right)}}$

\begin{align} &\left.\sum_{x_{1} = 0}^{\infty}\sum_{x_{2} = 0}^{\infty} \sum_{x_{3} = 0}^{\infty}\sum_{x_{4} = 1}^{\infty} \sum_{x_{5} = 1}^{\infty}\sum_{x_{6} = 1}^{\infty} \bracks{\sum_{k = 1}^{6}x_{k} = n} \right\vert_{\ x_{1},x_{2},x_{3}\ \mrm{even} \atop x_{4},x_{5},x_{6}\ \mrm{odd}} \\[5mm] = &\ \left.\sum_{x_{1} = 0}^{\infty}\sum_{x_{2} = 0}^{\infty} \sum_{x_{3} = 0}^{\infty}\sum_{x_{4} = 1}^{\infty} \sum_{x_{5} = 1}^{\infty}\sum_{x_{6} = 1}^{\infty} \oint_{\verts{z}\ =\ 1^{-}}{1 \over z^{n + 1 - \sum_{k = 1}^{6}x_{k}}}\, {\dd z \over 2\pi\ic} \right\vert_{\ x_{1},x_{2},x_{3}\ \mrm{even} \atop x_{4},x_{5},x_{6}\ \mrm{odd}} \\[5mm] = &\ \oint_{\verts{z}\ =\ 1^{-}}{1 \over z^{n + 1}}\, \pars{\sum_{x = 0}^{\infty}z^{2x}}^{3}\pars{\sum_{y = 0}^{\infty}z^{2y + 1}}^{3} {\dd z \over 2\pi\ic} = \oint_{\verts{z}\ =\ 1^{-}}{1 \over z^{n + 1}}\, \pars{1 \over 1 - z^{2}}^{3}\pars{z \over 1 - z^{2}}^{3} {\dd z \over 2\pi\ic} \\[5mm] = &\ \oint_{\verts{z}\ =\ 1^{-}}{1 \over z^{n - 2}\pars{1 - z^{2}}^{6}}\, {\dd z \over 2\pi\ic} = \sum_{k = 0}^{\infty}{-6 \choose k}\pars{-1}^{k} \oint_{\verts{z}\ =\ 1^{-}}{1 \over z^{n - 2k - 2}}\, {\dd z \over 2\pi\ic} \\[5mm] = &\ \sum_{k = 0}^{\infty}{k + 5 \choose 5} \bracks{n - 2k - 2 = 1} =\ \bbox[15px,#ffe,border:1px dotted navy]{\ds{% \left\{\begin{array}{lcl} \ds{0} & \mbox{if} & \ds{n}\ \mbox{is}\ even \\[2mm] \ds{\bracks{n + 7}/2 \choose 5} & \mbox{if} & \ds{n}\ \mbox{is}\ odd \end{array}\right.}} \end{align}

$\ds{\large\mathbf{\left. b\right)}}$ es bastante similar a $\ds{\large\mathbf{\left. a\right)}}$ .

\begin{align} &\oint_{\verts{z}\ =\ 1^{-}}{1 \over z^{n + 1}} \pars{\sum_{x = 0}^{12}z^{x}}^{5}\,{\dd z \over 2\pi\ic} = \oint_{\verts{z}\ =\ 1^{-}}{\pars{1 - z^{13}}^{5} \over z^{n + 1}\pars{1 - z}^{5}} \,{\dd z \over 2\pi\ic} \\[5mm] = &\ \oint_{\verts{z}\ =\ 1^{-}}{1 \over z^{n + 1}} \sum_{k = 0}^{\infty}{k + 4 \choose 4}x^{k}\sum_{\ell = 0}^{5} {5 \choose \ell}\pars{-1}^{\ell}x^{13\ell}\,{\dd z \over 2\pi\ic} \\[5mm] = &\ \sum_{\ell = 0}^{5}{5 \choose \ell}\pars{-1}^{\ell}\sum_{k = 0}^{\infty} {k + 4 \choose 4}\bracks{k + 13\ell = n} = \sum_{\ell = 0}^{5}{5 \choose \ell}\pars{-1}^{\ell} {n - 13\ell + 4 \choose 4}\bracks{\ell \leq {n \over 13}} \\[5mm] = &\ \color{#f00}{% \sum_{\ell = 0}^{\left\lfloor n/13\right\rfloor}\pars{-1}^{\ell}{5 \choose \ell}{n - 13\ell + 4 \choose 4}} \\[5mm] = &\ \left\{\begin{array}{ll} \ds{n + 4 \choose 4} & \mbox{if} & \ds{0 \leq n \leq 12} \\[3mm] \ds{{n + 4 \choose 4} - 5{n - 9 \choose 4}} & \mbox{if} & \ds{13 \leq n \leq 25} \\[3mm] \ds{{n + 4 \choose 4} - 5{n - 9 \choose 4} + 10{n - 22 \choose 4}} & \mbox{if} & \ds{26 \leq n \leq 38} \\[3mm] \ds{{n + 4 \choose 4} - 5{n - 9 \choose 4} + 10{n - 22 \choose 4} - 10{n - 35 \choose 4}} & \mbox{if} & \ds{39 \leq n \leq 51} \\[3mm] \ds{{n + 4 \choose 4} - 5{n - 9 \choose 4} + 10{n - 22 \choose 4} - 10{n - 35 \choose 4} + 5{n - 48 \choose 4}} & \mbox{if} & \ds{52 \leq n \leq 60} \\[3mm] \ds{0} & \mbox{if} & \ds{n > 60} \end{array} \derecha. \Fin

Answer 3

Este es un enfoque ligeramente diferente.

Problema del anuncio (a):

• Ya que incluso $x_j, 1\leq j\leq 3$ puede tener valores $0,2,4,\ldots$ codificamos los candidatos a la par $x_j$ a través de $t^0+t^2+t^4+\cdots$

• Desde que impar $x_j, 4\leq j\leq 6$ puede tener valores $1,3,5,\ldots$ codificamos los candidatos a impar $x_j$ a través de $t^1+t^3+t^5+\cdots$

  La contribución de incluso $x_1,x_2,x_3$ es \begin{align*} (1+t^2+t^4+\cdots)^3=\frac{1}{\left(1-t^2\right)^3} \end{align*}

  La contribución de impar $x_4,x_5,x_6$ es \begin{align*} (t^1+t^3+t^5+\cdots)^3=t^3(1+t^2+t^4+\cdots)^3=\frac{t^3}{\left(1-t^2\right)^3} \end{align*}

  Aquí aplicamos el _expansión de la serie geométrica_ .

Es conveniente utilizar el coeficiente de operador $[t^n]$ para denotar el coeficiente de $t^n$ de una serie.

Concluimos: Una función generadora $A(t)$ proporcionando con $[t^n]A(t)$ el número de soluciones deseadas es \begin{align*} A(t)=\frac{t^3}{\left(1-t^2\right)^6} \end{align*}

$$ $$

Problema del anuncio (b):

• Desde $x_j,1\leq j\leq 5$ puede tener valores $0\leq x_j\leq 12$ codificamos la contribución de $x_j$ a través de $t^0+t^1+t^2+\cdots+t^{12}$ .

Así, la contribución de cada $x_j$ puede codificarse como \begin{align*} 1+t^1+t^2+\cdots+t^{12}=\frac{1-t^{13}}{1-t} \end{align*}

Aquí aplicamos la fórmula del _series geométricas finitas_ .

Concluimos: Una función generadora $B(t)$ proporcionando con $[t^n]B(t)$ el número de soluciones deseadas es \begin{align*} B(t)=\left(\frac{1-t^{13}}{1-t}\right)^5 \end{align*}

Una pista: Si además el número de soluciones, es decir, el coeficiente de las funciones generadoras $A(t)$ , resp. $B(t)$ es extraer, de nuevo es conveniente aplicar el coeficiente de así como el operador _Soporte Iverson_ .