The puzzle is as follows: $$ \newcommand{\empty}{\phantom{1}} \newcommand{\boxes}[2]{\boxed{#1}\hspace{-0.04cm}\boxed{#2}} $$ At iteration (1) you start out with a pair of boxes, one empty and one with a 1: $$ \boxes{1}{\empty} $$ At iteration $i$ do the following:
- Fill each empty box, creating a new term for each box you fill
- Then, add new terms corresponding to all of the terms from iteration $i - 1$, but with a $\boxes{i}{\empty}$ box tacked onto the end.
Examples: Iteration (2) would look like: $$ \boxes{1}{2} + \boxes{1}{\empty}\:\boxes{2}{\empty} $$ where we've added one term for the one empty box, and then tacked on $\boxes{2}{\empty}$ to the term from iteration (1). Iteration (3) would look like: $$ \boxes{1}{3} \boxes{2}{\empty} + \boxes{1}{\empty} \boxes{2}{3} + \boxes{1}{2} \boxes{3}{\empty} + \boxes{1}{\empty} \boxes{2}{\empty} \boxes{3}{\empty} $$ Here the first two terms come from filling the two empty boxes, and the last two terms come from tacking on a $\boxes{3}{\empty}$ to the end of the previous terms. Iteration (4) would look like: \begin{multline} \boxes{1}{3} \boxes{2}{4} + \boxes{1}{4} \boxes{2}{3} + \boxes{1}{2} \boxes{3}{4} + \boxes{1}{4} \boxes{2}{\empty} \boxes{3}{\empty} + \boxes{1}{\empty} \boxes{2}{4} \boxes{3}{\empty} \\ + \boxes{1}{\empty} \boxes{2}{\empty} \boxes{3}{4} +\boxes{1}{3} \boxes{2}{\empty} \boxes{4}{\empty} + \boxes{1}{\empty} \boxes{2}{3} \boxes{4}{\empty} + \boxes{1}{2} \boxes{3}{\empty} \boxes{4}{\empty} + \boxes{1}{\empty} \boxes{2}{\empty} \boxes{3}{\empty} \boxes{4}{\empty} \end{multline}
Once you have done $n$ iterations get rid of any terms which have an empty box. Here, iterations (1) and (3) would just give nothing, while (2) would give $\boxes{1}{2}$ and (4) would give: $$ \boxes{1}{3} \: \boxes{2}{4} + \boxes{1}{4} \: \boxes{2}{3} + \boxes{1}{2} \: \boxes{3}{4} $$ How do you describe what you're left with at the end?
I think this should end up being identical to Isserlis' Theorem, but I'm hoping to come up with a slick combinatorial proof given this formulation. I haven't been successful so far, and all of the proofs that I have found use results from statistics that I am not familiar with.