Why are braid numbers of the form $Q_h^2$ or $2 \times Q_h^2$?

Consider two piles of $h$ playing cards each, all distinct. Repeatedly take one of the cards on top of one of these two piles and move it on top of one of two new piles, until both of the new piles are of height $h$.

How many different configurations can you end up with? I did some computing and found the values in the table below. I noticed that the number of possible configurations seems to be either a square or twice a square, depending on $h$ modulo $2$. I don't see why however, and I haven't been able to spot a pattern in the $Q_h$ values either.

$$\begin{array}{lrr} h & {\frak B}((h,h)\rightarrow(h,h)) & 2^{h \pmod{2}} \times Q_h^2\\ 0 & 1 & 1^2\\ 1 & 2 & 2 \times 1^2\\ 2 & 16 & 4^2\\ 3 & 128 & 2 \times 8^2\\ 4 & 1,\!156 & 34^2\\ 5 & 10,\!952 & 2 \times 74^2\\ 6 & 107,\!584 & 328^2\\ 7 & 1,\!083,\!392 & 2 \times 736^2\\ 8 & 11,\!115,\!556 & 3,\!334^2\\ 9 & 115,\!702,\!472 & 2 \times 7,\!606^2\\ 10 & 1,\!218,\!289,\!216 & 34,\!904^2\\ 11 & 12,\!948,\!910,\!592 & 2 \times 80,\!464^2\\ 12 & 138,\!708,\!574,\!096 & 372,\!436^2\\ 13 & 1,\!495,\!661,\!223,\!968 & 2 \times 864,\!772^2\\ 14 & 16,\!218,\!468,\!710,\!656 & 4,\!027,\!216^2\\ 15 & 176,\!727,\!219,\!273,\!728 & 2 \times 9,\!400,\!192^2\\ 16 & 1,\!933,\!956,\!651,\!447,\!076 & 43,\!976,\!774^2\\ 17 & 21,\!243,\!204,\!576,\!601,\!928 & 2 \times 103,\!061,\!158^2\\ 18 & 234,\!121,\!111,\!199,\!439,\!424 & 483,\!860,\!632^2\\ 19 & 2,\!587,\!943,\!032,\!046,\!002,\!688 & 2 \times 1,\!137,\!528,\!688^2\\ \end{array}$$

Does anyone have an insight? Most people whom I've asked to give the problem some thought, have answered $\sum_{i=0}^h\binom{h}{i}^4$ in a reflex, but this is only an upper bound.

(As a side note, when considering the case where you go from $k$ piles of height $2$ to $k$ new piles of height $2$, I found the formula $\frac{3k-2}{4k-2}(2k)!$. Cute, but seemingly entirely different.)

Solution 1:

I have analyzed the braid numbers ${\frak{B}}((i,j)\rightarrow(k,l))$; as described below, calculating them can be done by enumerating a class of lattice walks.

Basic formulation

Let $T_{a}^{b}$ be the operation of moving a card from source pile $a$ to destination pile $b$, where $a,b=1,2$. A legal "game" of the type contributing to ${\frak{B}}((h,h)\rightarrow(h,h))$ consists of a sequence of $2h$ operations, exactly $h$ of which have subscript $1$ (take a card from source pile $1$), and exactly $h$ of which have superscript $1$ (put a card on destination pile $1$). Since we can choose the subscripts and the superscripts independently, the total number of games is ${{2h}\choose{h}}^2$. More generally, the games contributing to ${\frak{B}}((i,n-i)\rightarrow(j,n-j))$ have $n$ operations, of which $i$ have subscript $1$ and $j$ have superscript $1$; these games number ${{n}\choose{i}}{{n}\choose{j}}$.

However, not all games lead to different configurations. In particular, the operations $T_{1}^{1}$ and $T_{2}^{2}$ commute: whenever they occur next to each other, the final configuration is not changed by swapping their order. When enumerating possible configurations, we need to count each set of equivalent games only once. We may therefore restrict our enumeration to games where every string of $T_{1}^{1}$'s and $T_{2}^{2}$'s is of the form $(T_{1}^{1})^a (T_{2}^{2})^b$; that is, $T_2^{2}T_1^{1}$ is forbidden. Similarly, the operations $T_{1}^{2}$ and $T_{2}^{1}$ also commute, and so we will forbid $T_2^{1}T_1^{2}$. It is not hard to see that no other pair of operations commutes. In this way we arrive at a set of restricted games with a one-to-one mapping to final configurations.

Lattice walks

The counting constraints for ${\frak{B}}((i,n-i)\rightarrow(j,n-j))$ are the following: $$ \begin{eqnarray} \#(T_1^{1})+\#(T_1^{2})&=&i \\ \#(T_2^{1})+\#(T_2^{2})&=&n-i \\ \#(T_1^{1})+\#(T_2^{1})&=&j \\ \#(T_1^{2})+\#(T_2^{2})&=&n-j. \end{eqnarray} $$ A little algebra shows that this is equivalent to $$ \begin{eqnarray} \#(T_1^{1})-\#(T_2^{2})&=&(i+j)-n \\ \#(T_1^{2})-\#(T_2^{1})&=&i-j \\ \sum_{a,b}\#(T_a^{b})&=&n. \end{eqnarray} $$ If we identify the operations with moves on $\mathbb{Z}^2$ (say, $T_1^{1}/T_2^{2}$ are east/west moves, and $T_1^{2}/T_2^{1}$ are north/south), we see that there is an isomorphism between games and walks on $\mathbb{Z}^2$: the games contributing to ${\frak{B}}((i,n-i)\rightarrow(j,n-j))$ correspond to walks from $(0,0)$ to $((i+j)-n,i-j)$ in exactly $n$ steps. In particular, the symmetric numbers in the question (where $i=j=h$ and $n=2h$) correspond to closed walks. More importantly, the restricted games correspond to restricted walks on $\mathbb{Z}^2$: the walks are those in which west-east and south-north switchbacks never occur. We can evaluate the braid numbers by counting these restricted closed walks.

Counting lattice walks

Let's denote the number of walks to $x\in\mathbb{Z}^2$ in $n$ steps by $G_{n}(x)$, and the number of restricted walks by $H_{n}(x)$. Each $n$-step walk is either a restricted walk already, or else takes its first forbidden switchback at $x'$ and $m \le n-2$ steps, after which it has to cover the remaining displacement $x-x'$ in $n-m-2$ steps. That is, $$ G_{n}(x) = H_{n}(x) + 2\sum_{m=0}^{n-2}\sum_{x'\in\mathbb{Z}^2}H_{m}(x')G_{n-m-2}(x-x'), $$ where the factor of $2$ accounts for the two types of forbidden switchback. In order to solve this for $H$, we introduce the Fourier-transformed generating function $$\tilde{G}(k,z)\equiv\sum_{x\in\mathbb{Z}^2}\sum_{n}z^n\exp(ik\cdot x)G_{n}(x),$$ and similarly $\tilde{H}(k,z)$. We find that $\tilde{G}(k,z)=\tilde{H}(k,z) + 2 z^2 \tilde{H}(k,z) \tilde{G}(k,z)$, or $$ \tilde{H}(k,z) = \frac{\tilde{G}(k,z)}{1 + 2z^2 \tilde{G}(k,z)} = \frac{1}{1 - 2(\cos k_x + \cos k_y)z + 2z^2}, $$ where I'm omitting the proof that $\tilde{G}^{-1}=1-2(\cos k_x+\cos k_y)z$. Expanding out the fraction, we have $$ \begin{eqnarray} \tilde{H}(k,z) &=& \sum_{n}(2z)^n\left(\cos k_x + \cos k_y - z\right)^n \\ &=& \sum_{n}(2z)^{n}\sum_{i=0}^{n}{{n}\choose{i}}\left(\cos k_x + \cos k_y\right)^{n-i} (-z)^{i} \\ &=& \sum_{n, i\le n} z^{n+i} 2^{n} {{n}\choose{i}}\left(\cos k_x + \cos k_y\right)^{n-i} (-1)^{i} \\ &=& \sum_{j, 2i\le j}z^{j} 2^{j-i} {{j-i}\choose{i}}\left(\cos k_x + \cos k_y\right)^{j-2i} (-1)^{i}; \end{eqnarray} $$ we identify the coefficient of $z^{j}$ and integrate over $k$ to obtain $$ H_{n}(x) = \sum_{i \le \lfloor n/2 \rfloor} (-2)^{i}{{n-i}\choose{i}}G_{n-2i}(x), $$ and for the closed restricted walks in particular, $$ \begin{eqnarray} {\frak{B}}((h,h)\rightarrow(h,h)) &=& H_{2h}(0) \\ &=& \sum_{k=0}^{h} (-2)^{k}{{2h-k}\choose{k}}{{2h-2k}\choose{h-k}}^2 \\ &=& (-2)^{h}\sum_{k=0}^{h} \left(-\frac{1}{2}\right)^{k}{{h+k}\choose{2k}}{{2k}\choose{k}}^2. \end{eqnarray} $$ You will find that this gives the result tabulated in the question. Why it is a perfect square or twice a perfect square is described below, in the...

Thrilling conclusion

In fact, this very sum has been studied by Z. H. Sun (here), in the form of the polynomial $$ f_n(y)=\sum_{k=0}^{n}{{n+k}\choose{2k}}{{2k}\choose{k}}^2 y^k, $$ for which he derived the identity $$ f_n(x(x+1)) = D_n(x)^2, $$ where $$ D_{n}(x)=\sum_{k=0}^{n}{{n}\choose{k}}{{n+k}\choose{k}} x^k. $$ In our case, $y=x(x+1)=-1/2$, so $x=-\frac{1}{2}(1\pm i)$. We calculate $$ \begin{eqnarray} D_h\left(-\frac{1}{2}(1+i)\right) &=& \sum_{k=0}^{h}\left(-\frac{1}{2}(1+i)\right)^{k} {{h}\choose{k}}{{h+k}\choose{k}} \\ &=& \sum_{k=0}^{h} 2^{-k/2} \left(\cos\frac{5\pi k}{4} + i\sin\frac{5\pi k}{4}\right) {{h}\choose{k}}{{h+k}\choose{k}}. \end{eqnarray} $$ The sum turns out to be purely real for even $h$ and purely imaginary for odd $h$, leaving us with two cases. For even $h$, $$ {\frak{B}}((h,h)\rightarrow(h,h))=\left[ \sum_{k=0}^{h} 2^{(h-k)/2} {{h}\choose{k}}{{h+k}\choose{k}} \cos\frac{5\pi k}{4} \right]^2. $$ For odd $h$, $$ {\frak{B}}((h,h)\rightarrow(h,h))=2 \times \left[ \sum_{k=0}^{h} 2^{(h-k-1)/2} {{h}\choose{k}}{{h+k}\choose{k}} \sin\frac{5\pi k}{4} \right]^2. $$ The bracketed expression is an integer in both cases.

Solution 2:

This is not an answer, but just a reformulation of the problem; maybe somebody will recognise it as a know problem under this form (but I don't). The number $B(h)$ can be defined as follows.

Let a directed graph on $2h$ point be given that is a disjoint union of two chains of length $h$. The number $B(h)$ counts the number of ways a second labelled pair of chains of length $h$ can be defined on the same set of vertices such that the the graph formed by the vertices with the union of the two sets of directed edges (the union of $4$ chains in all) still has no oriented cycles: it forms a Directed Acyclic Graph. (The fact that the two chains are labelled means we distinguish a solution where the two chains interchanged; this accounts for a factor $2$ in the number of solutions whenever $h>0$.) Since the added edges are an isomorphic image of the original edges under a unique permutation of the vertices, the problem can also be stated as one of counting such permutations.