Combinatorial Identity for Binomial Expression $$
\sum_{k=0}^{n} \sum_{j=0}^{\left\lfloor\frac{n-k}{2}\right\rfloor} 
3^{k+j}
\binom{n}{k}
\binom{n-k}{j}
\binom{n-k-j}{\left\lfloor\frac{n-k-2j}{2}\right\rfloor}
\binom{2}{(n-k-2 j) \bmod 3}
=\binom{
3 n+2}{n}
$$
Is there any combinatorial idea behind this identity? Having tried rigorous mathematical proof for this problem, several methods failed to give the desired result. Specifically, the smaller values for $n$ did not give any good observation for inductive hypothesis claims.
Another method of induction also failed, particularly jumping from $n$ to $n + 6$ due to parity and mod $3$ in the binomial expressions.
 A: First, the equation has a typo. It should be $\left \lfloor\frac{n-k-2j}{3}\right \rfloor$ in the binomial.
For a combinatorial proof, notice that there are three ways you can pick elements $a\cdot n+x,$ with $a\in \{0,1,2\}$ and $x\in [n]$ out of $3n$. You either:

*

*Pick $x$ in a unique way, meaning there exists a unique $\ell \in \{0,1,2\}$ such that $\ell \cdot n+x$ is in the set.

*Pick $x$ in two ways, meaning there are exactly two $\ell_i \in \{0,1,2\}$ such that $\ell_i \cdot n+x$ is in the set.

*Pick $x,n+x,2n+x$. The three of them.

Call $k$ the number of elements of the first option, so you have to choose in which of the three blocks are them in $3^k$ ways, and you have to select which of the $n$ selected elements have this property in $\binom{n}{k}$ ways. Call $j$ the number of elements on the second option, so you have to choose two blocks in $\binom{3}{2}^j=3^j$ ways, and the elements have to be selected out of $n-k$ remaining options in $\binom{n-j}{k}$ ways.

Notice then that you are choosing $n=k+2j+3s$ where $s$ is the number of elements you choose from the third option. See that $s=\left \lfloor\frac{n-k-2j}{3}\right \rfloor$ and so of the remaining $n-k-j$ options you have to select this $s$ in $\binom{n-j-k}{\left \lfloor\frac{n-k-2j}{3}\right \rfloor}$ ways. Notice, further, that there is no condition on $s$ so it may happen that you actually did not have the correct residue modulo $3$ at the end, so there are three options: either $n-k-2j$ is $0$ mod $3$ which means you have nothing left, or $1,2$ mod 3 so you need one or two more elements(choose these elements from $3n+2$ and $3n+1$ in $\binom{2}{n-k-2j \pmod 3}$ ways).

