1
$\begingroup$

There is this sequence listed on OEIS - named Domb numbers. I'm curious about

QUESTION. Is there a direct combinatorial proof for the identity $$\sum_{k=0}^n\binom{n}k^2\binom{2k}k\binom{2n-2k}{n-k} =\sum_{a+b+c+d=n}\binom{n}{a,b,c,d}^2,$$ where the RHS is sum over all non-negative integers so that $a+b+c+d=n$.

$\endgroup$

2 Answers 2

4
$\begingroup$

The Richmond and Shallit paper linked from OEIS shows that both sides count the number of Abelian squares of length $2n$ on an alphabet of $4$ letters.

$\endgroup$
1
$\begingroup$

Let, we have two rows. First row has $n$ particles $A,B,C,D$ and other row has $A',B',C',D'$ particles, which are antiparticles of the previous ones. Also, they have colours$R,B,G,V$ whereas antiparticles have anti colours. Then, number of colour less arrangements are $$T=\sum_{a+b+c+d=n} \binom{n}{a,b,c,d}^2$$

The same arrangement can be thought as $2$-groups $A,B$ and $C,D$. We choose $k$ places on both rows for $A,B$ group, in $\binom{n}{k}^2$ ways. So, this can be made colour less in $$\sum_{x+y=k} \binom{n}{x,y}^2=\binom{2k}{k}$$ ways. Similarly the $C,D$ group can be made colour less in $\binom{2n-2k}{n-k}$ ways.

Hence, total $$T=\sum_{k=0}^{n} \binom{n}{k}^2\binom{2k}{k}\binom{2n-2k}{n-k}$$ ways. To be honest, I have given a combinatorial shape to the way the equality can be obtained.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.