A three variable binomial coefficient identity
Restating your question, you are seeking to find the generating function of the left-hand-side: $$ g(x) = \sum_{n=0}^\infty x^n \sum_{i+j+k=n}\binom{i+j}{i} \binom{j+k}{j} \binom{k+i}{k} = \sum_{i=0}^\infty \sum_{j=0}^\infty \sum_{k=0}^\infty x^{i+j+k} \frac{(i+j)! (i+k)! (j+k)!}{i!^2 j!^2 k!^2} $$ First, carry out summation over $i$: $$ g(x) = \sum_{j=0}^\infty \sum_{k=0}^\infty x^{j+k} \frac{(j+k)!}{j!\cdot k!} {}_2F_1\left(1+j, 1+k; 1; x\right) $$ Now use Euler's transformation ${}_2F_1\left(1+j, 1+k; 1; x\right) = (1-x)^{-j-k-1} \, {}_2F_1\left(-j, -k; 1, x\right)$, which gives $$ g(x) = \frac{1}{1-x} \sum_{j=0}^\infty \sum_{k=0}^\infty \left(\frac{x}{1-x}\right)^{j+k} \frac{(j+k)!}{j!\cdot k!} {}_2F_1\left(-j, -k; 1; x\right) = \\ \frac{1}{1-x} \sum_{j=0}^\infty \sum_{k=0}^\infty \left(\frac{x}{1-x}\right)^{j+k} \frac{(j+k)!}{j!\cdot k!} \sum_{r=0}^{\min(j,k)} \binom{j}{r}\binom{k}{r} x^r = \\ \frac{1}{1-x} \sum_{r=0}^\infty x^r \sum_{j=r}^\infty \sum_{k=r}^\infty \binom{k+j}{k} \binom{j}{r}\binom{k}{r} \left(\frac{x}{1-x}\right)^{j+k} $$ Using $$ \sum_{j=r}^\infty \sum_{k=r}^\infty \binom{k+j}{k} \binom{j}{r}\binom{k}{r} z^{j+k} = \sum_{j=r}^\infty \binom{j}{r} z^{j+r} \sum_{k=0}^\infty \frac{(k+j+r)!}{j! r! k!} z^k =\\ \sum_{j=r}^\infty \binom{j}{r} z^{j+r} \binom{j+r}{j} \sum_{k=0}^\infty \frac{(j+r+1)_k}{k!} z^k = \sum_{j=r}^\infty \binom{j}{r} z^{j+r} \binom{j+r}{j} \left(1-z\right)^{-j-r-1} = \\ \frac{z^{2r}}{(1-z)^{2r+1}} \frac{1}{r!^2} \sum_{j=0}^\infty \frac{(j+2r)!}{j!} \left(\frac{z}{1-z}\right)^j = \frac{z^{2r}}{(1-z)^{2r+1}} \binom{2r}{r} \left(1-\frac{z}{1-z}\right)^{-1-2r} = \binom{2r}{r} z^{2r} \left(1-2z\right)^{-2r-1} $$ we continue: $$ g(x) = \frac{1}{1-x} \sum_{r=0}^\infty x^r \binom{2r}{r} \left(\frac{x}{1-x}\right)^{2r} \left(1 - 2 \frac{x}{1-x} \right)^{-1-2r} = \\ \frac{1}{1-x} \sum_{r=0}^\infty \binom{2r}{r} \frac{1-x}{1-3x} \left(\frac{x^3}{(1-3x)^2}\right)^r = \\ \frac{1}{1-3x} \sum_{r=0}^\infty \binom{2r}{r}\left(\frac{x^3}{(1-3x)^2}\right)^r = \frac{1}{1-3x} \left(1 - 4 \frac{x^3}{(1-3x)^2}\right)^{-1/2} = \frac{1}{1-3x} \left( \frac{(1-4x)(1-x)^2}{(1-3x)^2}\right)^{-1/2} = \frac{1}{1-x} \frac{1}{\sqrt{1-4x}} $$ which is exactly the generating function of the right-hand-side: $$ \sum_{n=0}^\infty x^n \sum_{r=0}^n \binom{2r}{r} \stackrel{n=r+k}{=} \sum_{k=0}^\infty x^r \sum_{r=0}^\infty \binom{2r}{r} x^r = \frac{1}{1-x} \cdot \frac{1}{\sqrt{1-4x}} $$
Short summary: On the right we are summing the number of words of $r$ $a$s and $r$ $b$s over $0\le r\le n.$ Denote the set of words with $r$ $a$s and $r$ $b$s by $U_r.$ On the left we are computing the number of triples of words, the first with $i$ $a$s and $j$ $b$s, the second with $j$ $a$s and $k$ $b$s, the third with $k$ $a$s and $i$ $b$s, for all $i+j+k=n.$ Denote this set of triples $V_n.$
Let $(x,y,z)\in V_n.$ Define $(x,y,z)$ to be $0$-padded if $x$ does not end in $b$ or $y$ does not end in $a.$ Define $(x,y,z)$ to be $r$-padded if $(x,y,z)=(x'b^r,y'a^r,z)$ where $(x',y',z)\in V_{n-r}$ is $0$-padded.
Then any word $w\in U_r$ can be written in a unique way as $w=x'y'z$ where $(x',y',z)\in V_r$ is $0$-padded. (This is proved below.) Then $(x'b^{n-r},y'a^{n-r},z)\in V_n$ is $(n-r)-padded.$ This establishes a bijection between $V_n$ on the left, and $U_0\cup U_1\cup\ldots\cup U_n$ on the right, thereby proving the identity. The elements of $U_n$ correspond to $0$-padded elements of $V_n,$ the elements of $U_{n-1}$ correspond to $1$-padded elements of $V_n,$ and so on.
Detailed answer: The expression $\binom{2r}{r}$ counts words constructed from $r$ $a$s and $r$ $b$s. The sum on the right counts all such words of lengths ranging from $0$ to $2n.$
On the left, we have the product $\binom{i+j}{i}\binom{j+k}{j}\binom{k+i}{k},$ which counts all words constructed by concatenating a word with $i$ $a$s and $j$ $b$s to a word with $j$ $a$s and $k$ $b$s to a word with $k$ $a$s and $i$ $b$s. Such words contain $i+j+k$ $a$s and $i+j+k$ $b$s. The sum is over all $i+j+k=n,$ so these words all have $n$ $a$s and $n$ $b$s.
These observations hint at the possibility of a bijection, but a few questions arise:
- Can any word of $n$ $a$s and $n$ $b$s be constructed by concatenating a word with $i$ $a$s and $j$ $b$s to a word with $j$ $a$s and $k$ $b$s to a word with $k$ $a$s and $i$ $b$s, for suitable $i,$ $j,$ $k$?
- Is it possible for a word to be constructed in more than one way by such a procedure?
- What about words of length less than $2n$?
In answering the first question, we will actually answer all three.
Given a word $w$ of $n$ $a$s and $n$ $b$s, let's see if we can find $i+j+k=n,$ a word $x$ of $i$ $a$s and $j$ $b$s, a word $y$ of $j$ $a$s and $k$ $b$s, and a word $z$ of $k$ $a$s and $i$ $b$s such that $xyz=w.$ Observe that if such words can be found then $\lvert x\rvert=i+j\le i+j+2k=(j+k)+(k+i)=\lvert y\rvert+\lvert z\rvert.$ So $\lvert x\rvert\le n.$
We proceed by splitting $w$ into three, possibly empty, parts as follows: let $X$ consist of the first $P$ letters of $w,$ with $0\le P\le n,$ and let $I$ equal the number of $a$s in $X$ and $J$ the number of $b$s in $X$ (so that $I+J=P$). Let $K=n-I-J.$ Let $Z$ equal the string of letters from position $Q+1$ to $2n$ of $w,$ with $Q$ chosen so that $Z$ has $K$ $a$s. Note that $Q\ge P$ automatically holds: since the number of $a$s in $X$ is $I,$ the number of $a$s in the remainder of $w$ is $n-I\ge n-P=K.$ If $n-I>K,$ then there are $a$s to the right of $X$ and to the left of $Z$ and so $Q>P.$ If $n-I=K,$ then $J=0,$ and $X$ is simply a string of $I$ $a$s. So $Z$ contains all of the remaining $a$s and possibly some $b$s as well. Since $X$ contains no $b$s, we have $Q\ge P.$ So we may let $Y$ equal the string of letters from position $P+1$ to $Q$ of $w,$ giving $w=XYZ.$
So far we have that $I+J+K=n,$ that $X$ contains $I$ $a$s and $J$ $b$s, that $Z$ contains $K$ $a$s and $B:=2n-Q-K$ $b$s, and that $Y$ contains $n-I-K=J$ $a$s and $n-J-B$ $b$s. In order to obtain our desired partition of $w,$ we need $B=I.$ We claim that with suitable choices of $P$ and $Q,$ this can always be achieved.
To verify that this is so, we need to understand what happens as $P$ increases in steps of $1$ from $0$ to $n.$ To emphasize that $I,$ $J,$ and $K$ are functions of $P,$ we write $I(P),$ etc. We have already seen that there is always at least one possible value of $Q$ (and hence $B$) compatible with a given value of $P.$ There may, however, be more than one such compatible value, so we write $Q_l(P)$ and $Q_u(P)$ for the lower and upper bounds on $Q$ for a given $P.$ We have corresponding lower and upper bounds on $B,$ $$B_l(P)=2n-Q_u(P)-K(P)=n+P-Q_u(P)$$ and $$B_u(P)=2n-Q_l(P)-K(P)=n+P-Q_l(P).$$
When $P$ increases by $1,$ $K$ decreases by $1$: $K(P+1)=K(P)-1.$ If the letter of $w$ at position $P+1$ is $a$ then $I(P+1)=I(P)+1$ and $J(P+1)=J(P)$; if that letter is $b$ then $I(P+1)=I(P)$ and $J(P+1)=J(P)+1.$ Since $K(P)=n-P,$ the $K(P)^\text{th}$ $a$ from the right in $w$ is the $(P+1)^\text{st}$ $a$ from the left. Let $u$ be the position of the $P^\text{th}$ $a$ from the left in $w$ ($u=0$ if $P=0$) and let $v$ be the position of the $(P+1)^\text{st}$ $a$ from the left in $w$ ($v=2n+1$ if $P=n$). Then $Q_l(P)=u$ and and $Q_u(P)=v-1.$ In other words, if $\lvert X\rvert=P$ then $Z$ may start anywhere between the position immediately following the $P^\text{th}$ $a$ and the position of the $(P+1)^\text{st}$ $a.$ Notice that $Q_l(P+1)=v$ and therefore, that $Q_l(P+1)=Q_u(P)+1.$ This implies that $$B_u(P+1)=n+P+1-Q_l(P+1)=n+P+1-1-Q_u(P)=n+P-Q_u(P)=B_l(P).$$ Therefore, if $I(P)<B_l(P),$ then, since $I(P+1)$ is at most $I(P)+1,$ we have $I(P+1)\le B_u(P+1).$ On the other hand, $B_l(P)$ is non-increasing as $P$ increases from $0$ to $n,$ and ultimately equals $0.$ Therefore there must eventually be a $P$ such that $B_l(P)\le I(P)\le B_u(P).$ Once we find such a $P,$ we set $i=I(P),$ $j=J(P),$ $k=n-P,$ $x=X,$ $y=Y,$ $z=Z.$
Will this be the only solution? Not in general. Let there be a solution $(i,j,k,x,y,z)$ corresponding to a particular $P$ and $Q.$ If $y$ begins with $b$ and $z$ begins with $a$ then we get an additional solution by increasing both $P$ and $Q$ by $1.$ This results in the first $b$ of $y$ becoming the last letter of $x$ and the first $a$ of $z$ becoming the last letter of $y,$ which increases $j$ by $1$ and decreases $k$ by $1$ while leaving $i$ unchanged. The process obviously also works in reverse. There are no other ways to obtain additional solutions, for if the first letter of $y$ is $a,$ adding it to $x$ would force us to add a $b$ to $z,$ but $z$ cannot increase in length when $x$ increases in length.
In summary, all solutions for a particular word $w$ have the same $i.$ Equivalently, $\lvert y\rvert=j+k=n-i$ is the same for all solutions. The solution with minimum $j$ must be such that $x$ ends in $a$ or $y$ ends in $b.$ The solution with maximum $j$ must be such that $y$ begins with $a$ or $z$ begins with $b.$
Consider an example. Let $w=baabbbaaabab.$ Here $n=6.$ Then we have $$ \begin{array}{ccc|ccc} P & I(P) & J(P) & K(P) & [B_l(P),B_u(P)] & [Q_l(P),Q_u(P)]\\ \hline 0 & 0 & 0 & 6 & [5,6] & [0,1]\\ 1 & 0 & 1 & 5 & [5,5] & [2,2]\\ 2 & 1 & 1 & 4 & [2,5] & [3,6]\\ 3 & 2 & 1 & 3 & [2,2] & [7,7]\\ 4 & 2 & 2 & 2 & [2,2] & [8,8]\\ 5 & 2 & 3 & 1 & [1,2] & [9,10]\\ 6 & 2 & 4 & 0 & [0,1] & [11,12] \end{array} $$ We get three solutions, corresponding to $(P,Q)=(3,7),$ $(4,8),$ $(5,9).$ These are $$ \begin{aligned} &(i,j,k,x,y,x)=(2,1,3,baa,bbba,aabab),\\ &(i,j,k,x,y,x)=(2,2,2,baab,bbaa,abab),\\ &(i,j,k,x,y,x)=(2,3,1,baabb,baaa,bab). \end{aligned} $$
We have answered questions $1$ and $2$ in the affirmative. This suggests a way of producing a bijective proof of the identity. Let $W$ be the set of words of length at most $2n$ containing equal numbers of $a$s and $b$s. Let $S$ be the set of sextuples $(i,j,k,x,y,z)$ where $i,$ $j,$ $k$ are nonnegative integers satisfying $i+j+k=n,$ $x$ is a word consisting of $i$ $a$s and $j$ $b$s, $y$ is a word consisting of $j$ $a$s and $k$ $b$s, and $z$ is a word consisting of $k$ $a$s and $i$ $b$s. The map from $S$ to $W$ that simply concatenates $x,$ $y,$ and $z$ is not onto, since it only produces words of length $2n,$ and not one-to-one, as we have seen above. By modifying this simple concatenation map, we obtain a map that is both onto and one-to-one.
The map: Let $s=(i,j,k,x,y,z)\in S.$ If the last letter of $x$ is $b$ and the last letter of $y$ is $a,$ delete the last letter of both words. Repeat until $x$ or $y$ is empty or the last letter of $x$ is not $b$ or the last letter of $y$ is not $a.$ Denote the resulting words $x',$ $y'.$ We define $f:S\to W$ by $f(s)=x'y'z.$
The inverse map, applied to a word $w\in W$ with $N$ $a$s and $N$ $b$s, $0\le N\le n,$ is computed
- by applying the algorithm described above to write $w=x'y'z,$ where $x'$ is a word with $i$ $a$s and $j'$ $b$s, $y'$ is a word with $j'$ $a$s and $k$ $b$s, $z$ is a word with $k$ $a$s and $i$ $b$s, $i+j'+k=N,$ and $j'$ is as small as possible,
- by appending $n-N$ $b$s to $x'$ to form $x,$ appending $n-N$ $a$s to $y'$ to form $y,$ and
- by forming the sextuple $(i,j'+n-N,k,x,y,z).$
Example from original answer: I've replaced my original answer with what I hope is a more convincing presentation, but this example from that answer may be helpful, so I leave it.
Suppose that $n=3.$ The right hand side enumerates the union of the following sets $$ \begin{aligned} &\{e\},\\ &\{ab,ba\},\\ &\{aabb,abab,abba,baab,baba,bbaa\},\\ &\{aaabbb,aababb,aabbab,aabbba,abaabb,ababab,ababba,abbaab,abbaba,abbbaa,\\ &\ \ baaabb,baabab,baabba,babaab,bababa,babbaa,bbaaab,bbaaba,bbabaa,bbbaaa\}. \end{aligned} $$ Here $e$ denotes the empty word. The left hand side enumerates words constructed as follows.
- Let $A$ be the set of words containing $i$ $a$s and $j$ $b$s. ($\lvert A\rvert=\binom{i+j}{i}$)
- Let $B$ be the set of words containing $j$ $a$s and $k$ $b$s. ($\lvert B\rvert=\binom{j+k}{j}$)
- Let $C$ be the set of words containing $k$ $a$s and $i$ $b$s. ($\lvert C\rvert=\binom{k+i}{k}$)
$$ \begin{aligned} &(i,j,k)=(0,0,3),\ A=\{e\},B=\{bbb\},C=\{aaa\}:\\ &\ \longrightarrow\{bbbaaa\}\\ &(i,j,k)=(0,1,2),\ A=\{b\},B=\{abb,bab,bba\},C=\{aa\}:\\ &\ \longrightarrow\{babbaa,bbabaa,\dot{b}bb\dot{a}aa=bbaa\}\\ &(i,j,k)=(0,2,1),\ A=\{bb\},B=\{aab,aba,baa\},C=\{a\}:\\ &\ \longrightarrow\{bbaaba,b\dot{b}ab\dot{a}a=baba,\dot{b}\dot{b}b\dot{a}\dot{a}a=ba\}\\ &(i,j,k)=(0,3,0),\ A=\{bbb\},B=\{aaa\},C=\{e\}:\\ &\ \longrightarrow\{\dot{b}\dot{b}\dot{b}\dot{a}\dot{a}\dot{a}=e\}\\ &(i,j,k)=(1,0,2),\ A=\{a\},B=\{bb\},C=\{aab,aba,baa\}:\\ &\ \longrightarrow\{abbaab,abbaba,abbbaa\}\\ &(i,j,k)=(1,1,1),\ A=\{ab,ba\},B=\{ab,ba\},C=\{ab,ba\}:\\ &\ \longrightarrow\{ababab,ababba,a\dot{b}b\dot{a}ab=abab,a\dot{b}b\dot{a}ba=abba,baabab,baabba,babaab,bababa\}\\ &(i,j,k)=(1,2,0),\ A=\{abb,bab,bba\},B=\{aa\},C=\{b\}:\\ &\ \longrightarrow\{a\dot{b}\dot{b}\dot{a}\dot{a}b=ab,ba\dot{b}a\dot{a}b=baab,bbaaab\}\\ &(i,j,k)=(2,0,1),\ A=\{aa\},B=\{b\},C=\{abb,bab,bba\}:\\ &\ \longrightarrow\{aababb,aabbab,aabbba\}\\ &(i,j,k)=(2,1,0),\ A=\{aab,aba,baa\},B=\{a\},C=\{bb\}:\\ &\ \longrightarrow\{aa\dot{b}\dot{a}bb=aabb,abaabb,baaabb\}\\ &(i,j,k)=(3,0,0),\ A=\{aaa\},B=\{e\},C=\{bbb\}:\\ &\ \longrightarrow\{aaabbb\} \end{aligned} $$ A dot over a letter indicates that the letter is to be deleted.