This question builds off of the previous MO question Number of collinear ways to fill a grid.

Let $A(m,n)$ denote the set of binary words $\alpha=(\alpha_1,\alpha_2,\ldots,\alpha_{m+n-2})$ consisting of $m-1$ $0's$ and $n-1$ $1's$. Evidently $\#A(m,n) = \binom{m+n-2}{m-1}$.

For $\alpha \in A(m,n)$ and $1\leq i \leq m+n-2$, set $$ b^\alpha_i := \#\{1\leq j < i\colon \alpha_i\neq\alpha_j\} +1.$$ $$ c^\alpha_i := \#\{1\leq j \leq i\colon \alpha_i=\alpha_j\}=(i+1)-b^\alpha_i.$$

The resolution of the above-linked question implies that $$ \sum_{\alpha \in A(m,n)} \frac{b^\alpha_1b^\alpha_2 \cdots b^\alpha_{m+n-2}}{b^\alpha_{m+n-2} (b^\alpha_{m+n-2}+b^\alpha_{m+n-3})\cdots (b^\alpha_{m+n-2}+b^\alpha_{m+n-3}+\cdots+b^\alpha_1) } = \frac{mn}{(m+n-1)!}$$ Meanwhile, in this answer, it is explained that $$ \sum_{\alpha \in A(m,n)} \frac{1}{c^\alpha_{m+n-2} (c^\alpha_{m+n-2}+c^\alpha_{m+n-3})\cdots (c^\alpha_{m+n-2}+c^\alpha_{m+n-3}+\cdots+c^\alpha_1) } = \frac{2^{m-1}2^{n-1}}{(2m-2)! (2n-2)!}$$

Considering the similarities of these two remarkable weighted sums over binary words, we ask:

Question: Is there a more general formula which specializes to the above two formulas?


Since for any $\alpha \in A(m,n)$ we have $$ \{c_1^{\alpha},c_2^{\alpha},\ldots,c_{m+n-2}^{\alpha}\} = \{1,2,\ldots,m-1,1,2,\ldots,n-1\},$$ we can rewrite that second sum to be $$ \sum_{\alpha \in A(m,n)} \frac{c^\alpha_1 c^\alpha_2 \cdots c^\alpha_{m+n-2}}{c^\alpha_{m+n-2} (c^\alpha_{m+n-2}+c^\alpha_{m+n-3})\cdots (c^\alpha_{m+n-2}+c^\alpha_{m+n-3}+\cdots+c^\alpha_1) } = \frac{2^{m-1}(m-1)!2^{n-1}(n-1)!}{(2m-2)! (2n-2)!},$$ to be even more similar to the first sum.

If we set $$ d^{\alpha}_i = xb^{\alpha}_i+yc^{\alpha}_i,$$ then the above commentary explains that $$ \sum_{\alpha \in A(m,n)} \frac{d^\alpha_1 d^\alpha_2 \cdots d^\alpha_{m+n-2}}{d^\alpha_{m+n-2} (d^\alpha_{m+n-2}+d^\alpha_{m+n-3})\cdots (d^\alpha_{m+n-2}+d^\alpha_{m+n-3}+\cdots+d^\alpha_1)}$$ has a product formula for $x,y\in \{0,1\}$. Maybe it has a product formula for general $x,y$.


1 Answer 1


One can perhaps look at the bivariate generating functions, $$ \sum_{m,n \geq 0} \frac{x^m y^n mn}{(m+n-1)!} $$ and $$ \sum_{m,n \geq 0} \frac{x^m y^n 2^{m+n-2}}{(2m-2)!(2n-2)!}. $$ Mathematica expresses these as $$ \frac{x y \left(e^x x^3-e^x x^2 y+x e^y y^2-2 e^x x y+2 x e^y y-e^y y^3\right)}{(x-y)^3} $$ and $$ \frac{1}{2} x y \left(\cosh \left(\sqrt{2} \sqrt{x}\right) \left(\sqrt{2} \sqrt{y} \sinh \left(\sqrt{2} \sqrt{y}\right)+2 \cosh \left(\sqrt{2} \sqrt{y}\right)\right)+\sinh \left(\sqrt{2} \sqrt{x}\right) \left(\sqrt{x y} \sinh \left(\sqrt{2} \sqrt{y}\right)+\sqrt{2} \sqrt{x} \cosh \left(\sqrt{2} \sqrt{y}\right)\right)\right). $$ There is not a lot of similarities here, but maybe there is a natural interpolation...


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.