número entero de soluciones a $2x_1 + x_2 + x_3 = n$

Question

Estoy trabajando en un problema para el cual necesito de manera eficiente calcular el número de entero de las soluciones de las ecuaciones de la forma $x_1 + \cdots + x_k = n$ con algún subconjunto de $\{x_1, \dots, x_n\}$ equivalente.

Por ejemplo, el problema señalado en el título: $x_1 + x_2 + x_3 + x_4 = n$ $x_1 = x_2$

Sé cómo encontrar el número de enteros soluciones a esta ecuación, sin el agregado de retención de equivalente variables. También estoy familiarizado con la adición de restricciones de la forma $x_i \geq m$. Pero no veo cómo adaptar el método aquí.

En mi combinatoria libro, similares problemas son abordados mediante la generación de funciones. Creo que la generación de la función de mi ecuación sería:

$$(1+x^2 + x^4 + \cdots)(1+x + x^2 + \cdots)^2 = \dfrac{1}{1-x^2} \dfrac{1}{(1-x)^2}$$

Pero si no hay una manera de poner esto en la forma $\sum_{n=0}^{\infty} a_n x^n$ y por lo tanto recuperar $a_n$ no veo la manera de hacer uso de ella.

Idealmente, me gustaría encontrar un método que funcione para $2x_1 + x_2 + x_3 = n$, y que también puede extenderse a los casos con más variables y diferentes subconjuntos de equivalente variables.

Answer 1

El uso de fracciones parciales: $$\eqalign{ \frac1{1-x^2}\frac{1}{(1-x)^2} &=\frac1{(1+x)(1-x)^3}\cr &=\frac18\Bigl(\frac{1}{1+x}+\frac{7-4x+x^2}{(1-x)^3}\Bigr)\cr &=\frac18\Bigl(\frac{1}{1+x}+\frac1{(1-x)}+\frac2{(1-x)^2} +\frac{4}{(1-x)^3}\Bigr)\cr &=\frac18\sum_{n=0}^\infty\bigl((-1)^n+1+2(n+1)+2(n+1)(n+2)\bigr)x^n\cr &=\frac18\sum_{n=0}^\infty\bigl((-1)^n+7+8n+2n^2\bigr)x^n\ ,\cr}$$ donde hemos diferenciado $$\frac1{1-x}=\sum_{n=0}^\infty x^n$$ para obtener $$\frac1{(1-x)^2}=\sum_{n=0}^\infty nx^{n-1}=\sum_{n=0}^\infty (n+1)x^n$$ y entonces $$\frac2{(1-x)^3}=\sum_{n=0}^\infty n(n+1)x^{n-1}=\sum_{n=0}^\infty (n+1)(n+2)x^n\ .$$

Answer 2

$\newcommand{\ángulos}[1]{\left\langle\, nº 1 \,\right\rangle} \newcommand{\llaves}[1]{\left\lbrace\, nº 1 \,\right\rbrace} \newcommand{\bracks}[1]{\left\lbrack\, nº 1 \,\right\rbrack} \newcommand{\dd}{{\rm d}} \newcommand{\ds}[1]{\displaystyle{#1}} \newcommand{\dsc}[1]{\displaystyle{\color{red}{#1}}} \newcommand{\expo}[1]{\,{\rm e}^{#1}\,} \newcommand{\mitad}{{1 \over 2}} \newcommand{\ic}{{\rm i}} \newcommand{\imp}{\Longrightarrow} \newcommand{\Li}[1]{\,{\rm Li}_{#1}} \newcommand{\pars}[1]{\left (\, nº 1 \,\right)} \newcommand{\partiald}[3][]{\frac{\partial^{#1} #2}{\parcial #3^{#1}}} \newcommand{\raíz}[2][]{\,\sqrt[#1]{\vphantom{\large Un}\,#2\,}\,} \newcommand{\totald}[3][]{\frac{{\rm d}^{#1} #2}{{\rm d} #3^{#1}}} \newcommand{\verts}[1]{\left\vert\, nº 1 \,\right\vert}$ \begin{align} \sum_{x_{1} = 0}^{\infty}\sum_{x_{2} = 0}^{\infty}\sum_{x_{3} = 0}^{\infty} \delta_{2x_{1}\ +\ x_{2}\ +\ x_{3},\ n} & = \sum_{x_{1} = 0}^{\infty}\sum_{x_{2} = 0}^{\infty}\sum_{x_{3} = 0}^{\infty}\ \overbrace{% \oint_{\verts{z} = 1^{-}}{1 \over z^{n + 1 - 2x_{1} - x_{2} - x_{3}}} \,{\dd z \over 2\pi\ic}}^{\ds{\delta_{2x_{1}\ +\ x_{2}\ +\ x_{3},\ n}}} \\[3mm] & = \oint_{\verts{z} = 1^{-}}{1 \over z^{n + 1}} \sum_{x_{1} = 0}^{\infty}\pars{z^{2}}^{x_{1}} \sum_{x_{2} = 0}^{\infty}z^{x_{2}}\sum_{x_{3} = 0}^{\infty}z^{x_{3}} \,{\dd z \over 2\pi\ic} \\[3mm] & = \oint_{\verts{z} = 1^{-}}{1 \over z^{n + 1}}\,{1 \over 1 - z^{2}}\, {1 \over 1 - z}\,{1 \over 1 - z}\,{\dd z \over 2\pi\ic} \\[3mm] & = \oint_{\verts{z} = 1^{-}}{1 \over z^{n + 1}}\,{1 \over \pars{1 - z}^{3}} {1 \over 1 + z}\,{\dd z \over 2\pi\ic} \\[3mm] &= \oint_{\verts{z} = 1^{-}}{1 \over z^{n + 1}} \sum_{\ell = 0}^{\infty}{-3 \choose \ell}\pars{-1}^{\ell}z^{\ell} \sum_{\ell' = 0}^{\infty}\pars{-1}^{\ell'}z^{\ell'}\,{\dd z \over 2\pi\ic} \\[3mm] &= \sum_{\ell = 0}^{\infty}{-3 \choose \ell}\pars{-1}^{\ell} \sum_{\ell' = 0}^{\infty}\pars{-1}^{\ell'}\ \overbrace{\oint_{\verts{z} = 1^{-}} {1 \over z^{n - \ell - \ell' + 1}}\,{\dd z \over 2\pi\ic}} ^{\ds{\delta_{\ell',n - \ell}}} \\[3mm] & = \pars{-1}^{n}\sum_{\ell = 0}^{n}{-3 \choose \ell} = \pars{-1}^{n}\sum_{\ell = 0}^{n}{\ell + 2 \choose \ell}\pars{-1}^{\ell} \\[3mm] & = \half\,\pars{-1}^{n} \sum_{\ell = 0}^{n}\pars{-1}^{\ell}\pars{\ell + 2}\pars{\ell + 1} = {1 \over 8}\bracks{2n^{2} + 8n + 7 + \pars{-1}^{n}} \\[3mm] & = \color{#f00}{\left\lbrace\begin{array}{lcl} {1 \over 4}\pars{n + 2}^{2} & \mbox{if} & n\ \mbox{is even} \\ {1 \over 4}\,\pars{n + 1}\pars{n + 3} & \mbox{if} & n\ \mbox{is odd} \end{array}\right.} \end{align}