number of integer solutions to $2x_1 + x_2 + x_3 = n$

Question

I'm working on a problem for which I need to efficiently compute the number of integer solutions to equations of the form $x_1 + \cdots + x_k = n$ with some subset of $\{x_1, \dots, x_n\}$ equivalent.

For example, the problem stated in the title: $x_1 + x_2 + x_3 + x_4 = n$ with $x_1 = x_2$

I know how to find the number of integer solutions to such an equation without the added restraint of equivalent variables. I'm also familiar with adding restraints of the form $x_i \geq m$. But I don't see how to adapt that method here.

In my combinatorics book, similar problems are tackled using generating functions. I believe that the generating function for my equation would be:

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

But unless there is a way to put this into the form $\sum_{n=0}^{\infty} a_n x^n$ and thus recover $a_n$ I don't see how to make use of it.

Ideally, I would like to find a method that works for $2x_1 + x_2 + x_3 = n$ and which can also be extended to cases with more variables and different subsets of equivalent variables.

Answer 1

Use partial fractions: $$\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}$$ where we have differentiated $$\frac1{1-x}=\sum_{n=0}^\infty x^n$$ to get $$\frac1{(1-x)^2}=\sum_{n=0}^\infty nx^{n-1}=\sum_{n=0}^\infty (n+1)x^n$$ and then $$\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{\angles}[1]{\left\langle\, #1 \,\right\rangle} \newcommand{\braces}[1]{\left\lbrace\, #1 \,\right\rbrace} \newcommand{\bracks}[1]{\left\lbrack\, #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{\half}{{1 \over 2}} \newcommand{\ic}{{\rm i}} \newcommand{\imp}{\Longrightarrow} \newcommand{\Li}[1]{\,{\rm Li}_{#1}} \newcommand{\pars}[1]{\left(\, #1 \,\right)} \newcommand{\partiald}[3][]{\frac{\partial^{#1} #2}{\partial #3^{#1}}} \newcommand{\root}[2][]{\,\sqrt[#1]{\vphantom{\large A}\,#2\,}\,} \newcommand{\totald}[3][]{\frac{{\rm d}^{#1} #2}{{\rm d} #3^{#1}}} \newcommand{\verts}[1]{\left\vert\, #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}