A seemingly simple combinatorial object that must have an easy generating function

Question

One more question related to my earlier "Special" meanders.

I am trying to isolate simplest problems related to it. Here is one.

For a composition (i. e. a tuple of natural numbers) $\boldsymbol a=(a_1,...,a_k)$, define the set of its midpoints by $$ \operatorname{mid}(\boldsymbol a):=\{a_1+...+a_{i-1}+\frac{a_i+1}2\mid1\leqslant i\leqslant k\}. $$ For example, $\operatorname{mid}(4,1,3)=\{\frac52,5,7\}$.

Call compositions $\boldsymbol a$ and $\boldsymbol b$ unmatchable if $\operatorname{mid}(\boldsymbol a)\cap\operatorname{mid}(\boldsymbol b)=\varnothing$.

I need any explicit information (formula, generating function, ...) for the numbers

$F(n):=$ number of unmatchable pairs $\langle\boldsymbol a,\boldsymbol b\rangle$ with $\sum a_i=\sum b_j=n$.

The sequence starts $0,2,6,24,78,284,960,3402,11710,41020,...$

My attempts so far have led to increasingly absurdly complicated approaches (like inverting infinite matrices with power series coefficients) and gave nothing in the end.

I believe a specialist can either give an answer immediately or relate it to some known difficult problem.

Answer 1

The number of unmatchable pairs can be computed with the formula: $$F(n) = \sum_{k=0}^{2n-1} (-1)^k \sum_{0<m_1<\dots<m_k<2n} \left( \sum_{0\le s_1<\dots<s_k<n=s_{k+1}\atop s_i<m_i/2} g(s_1)\prod_{i=1}^k g(s_i+s_{i+1}-m_i)\right)^2,$$ where $$g(t) = \begin{cases} 0, &\text{if}\ t<0;\\ 1, &\text{if}\ t=0;\\ 2^{t-1}, &\text{if}\ t\geq 1. \end{cases} $$

UPDATE #2 (02/14/16). The expression being squared in the formula for $F(n)$ equals the coefficient of $x_1^{m_1}x_2^{m_2-m_1}\cdots x_k^{m_k-m_{k-1}}x_{k+1}^{2n-m_k}$ in $$G(x_1^2)\cdot \prod_{i=1}^k \frac{x_i x_{i+1}}{1-x_ix_{i+1}}\cdot G(x_{i+1}^2),$$ where $G(x)$ is the generating function for $g(s)$: $$G(x) = \sum_{s=0}^\infty g(s)\cdot x^s = \frac{1-x}{1-2x}.$$ Without squaring this would lead to almost trivial summation of these coefficients, but summation with squaring remains a challenge I do not yet know how to address. Parseval's identity may be relevant here somehow.

P.S. Midpoints have also a nice geometrical interpretation in terms of certain lattice paths, which I can explain later if there is interest. see update below.

P.S. #2 Here is my PARI/GP code, which implements the above formula for $F(n)$:

{ g(t) = if(t<0, return(0)); if(t==0,1,2^(t-1)); }
{ f(n,m) = my(r=0); if(#m==0,return(g(n))); forvec(s=vector(#m,i,[0,(m[i]-1)\2]), r += prod(i=0,#m, g(if(i<#m,s[i+1],n)-if(i>0,m[i]-s[i],0));); ,2); r; }
{ F(n) = my(r=0); for(k=0,2*n-1, forvec(m=vector(k,i,[1,2*n-1]), r+=(-1)^k*f(n,m)^2; ,2); ); r; }

UPDATE #1 (adjusted per suggestion of მამუკაჯიბლაძე).

I will illustrate the path interpretation on the example of $a=(1,3,2,3,4)$ with the sum $n=13$.

I define the "modified" middle points (obtained from the original ones by multiplying by 2 and subtracting 1) as $$m_i = 2(a_1+\dots+a_{i-1})+a_i.$$ In our example, we have $m=(1,5,10,15,22)$. Let us represent these entities as a path: $$(0,0) \to (m_1,-a_1) \to (m_2,a_2) \to (m_3,-a_3) \to \dots \to (2n,0).$$ It can be seen that this path consists of alternating diagonal -45° and +45° steps, each of which crosses the $x$-axis but does not visit it, except for the start and end points. In other words, the intermediate vertices in this path alternatingly lie below and above the $x$-axis and their $x$-coordinates correspond to the modified middle points of $a$. Clearly, vectors $a$ and such paths are in one-to-one correspondence.

Here is the path for our example.

Answer 2

I've now got an explicit formula for the generating function; after several simplifications it is still quite messy. Still decided to show it (in a separate answer, adding this to the old one would make it too long I think), maybe somebody can use it for a better answer. The proof is equally messy and uninspiring, it consists in making the functional equation from the recursion which I described in my previous answer.

So let $f(q)=\sum F(n)q^n$. Then, $$ f(q)=\frac AB, $$ where $$ A=\sum_{n=0}^\infty (-1)^{n-1}\prod_{k=1}^n \frac{(1-2q^k)^2}{(1-q^k)(1-4q^{k+1})} \frac{1+q-4q^{n+1}}{1-2q^n}\left(\frac{q^2}{2(1-q)}\right)^n $$ and $$ B=\sum_{n=0}^\infty (-1)^n\prod_{k=1}^n \frac{(1-2q^k)^2}{(1-q^k)(1-4q^{k+1})} \left(\frac{1-q}{1-2q^n}+2\frac{1-2q}{(1-2q^n)^2}\right)\left(\frac{q^2}{2(1-q)}\right)^n. $$ Or, if you prefer, \begin{multline*} A=1-3 q +\frac{(1-2 q) \left(1-4 q^2+q\right) }{(1-q) \left(1-4 q^2\right)}\frac{q^2}{2 (1-q)} -\frac{(1-2 q)^2 \left(1-2 q^2\right) \left(1-4 q^3+q\right) }{(1-q) \left(1-4 q^2\right) \left(1-q^2\right) \left(1-4 q^3\right)}\left(\frac{q^2}{2 (1-q)}\right)^2 +\frac{(1-2 q)^2 \left(1-2 q^2\right)^2 \left(1-2 q^3\right) \left(1-4 q^4+q\right) }{(1-q) \left(1-4 q^2\right) \left(1-q^2\right) \left(1-4 q^3\right) \left(1-q^3\right) \left(1-4 q^4\right)}\left(\frac{q^2}{2 (1-q)}\right)^3\mp... \end{multline*} and \begin{multline*} B=1-3 q-\frac{\left(3-7 q+2 q^2\right)}{(1-q) \left(1-4 q^2\right)}\frac{q^2}{2 (1-q)} +\frac{(1-2 q)^2 \left(3-5 q-2 q^2+2 q^3\right) }{(1-q) \left(1-4 q^2\right) \left(1-q^2\right) \left(1-4 q^3\right)}\left(\frac{q^2}{2 (1-q)}\right)^2 -\frac{(1-2 q)^2 \left(1-2 q^2\right)^2 \left(3-5 q-2 q^3+2 q^4\right) }{(1-q) \left(1-4 q^2\right) \left(1-q^2\right) \left(1-4 q^3\right) \left(1-q^3\right) \left(1-4 q^4\right)}\left(\frac{q^2}{2 (1-q)}\right)^3\pm... \end{multline*} (Later)

Let me add one more version: $$ f(q)=\frac{(1-4 q) \, _2\phi _1\left(\begin{smallmatrix}2,\ 2 q\\4 q\end{smallmatrix};q,\frac{-q^2}{2 (1-q)}\right)+q \, _2\phi _1\left(\begin{smallmatrix}2,\ 2 q\\4 q^2\end{smallmatrix};q,\frac{-q^2}{2 (1-q)}\right)}{2 (1-2 q) \, _2\phi _1\left(\begin{smallmatrix}2,\ 2\\4 q^2\end{smallmatrix};q,\frac{-q^2}{2 (1-q)}\right)-(1-q) \, _2\phi _1\left(\begin{smallmatrix}2,\ 2 q\\4 q^2\end{smallmatrix};q,\frac{-q^2}{2 (1-q)}\right)} $$ where $_2\phi _1$ is the basic hypergeometric series

Answer 3

This is definitely very far from being an answer, but still.

Let $f(t)=\sum_nF(n)t^n$ be the ogf for the numbers in question.

As in the comment by Timothy Chow, call a pair $\langle\boldsymbol a,\boldsymbol b\rangle$ indecomposable if $\boldsymbol a$ and $\boldsymbol b$ do not have common partial sums, that is, $a_1+...+a_i\ne b_1+...+b_j$ except for 0 and total. Let $\bar F(n)$ be the number of indecomposable unmatchable pairs with sum $=n$. The sequence $\bar F(1)/2,\bar F(2)/2,...$ starts with $0,1,3,10,27,80,216,621,1703,4824,13350,...$

Let $\bar f(t)$ be the generating function for $\bar F(n)$.

It is clear that each pair decomposes uniquely into indecomposables, hence $f=1+\bar f+\bar f^2+\bar f^3+...=\frac1{1-\bar f}$, so it suffices to compute $\bar f$.

Next, indecomposables can be similarly uniquely "glued" from "elementary" unmatchable pairs. A pair $\langle\boldsymbol a,\boldsymbol b\rangle$ is elementary if either $\boldsymbol a$ or $\boldsymbol b$ consists of a single number.

By a gluing I mean a situation like this: $$\langle(a_1),(b_1,...,b_{j-1},x)\rangle;\langle(x,a_2,...,a_{i-1},y),(b_j)\rangle;\langle(a_i),(y,b_{j+1},...,b_{j'-1},z)\rangle;\langle(z,a_{i+1},...,a_{i'-1},t),(b_{j'})\rangle,...$$

Now it is not difficult to count elementary unmatchable pairs with given "ends". For fixed $x$ and $y$ let $F_{xy}(n)$ be the number of unmatchable pairs of the form $\langle(x+n+y),(x,...,y)\rangle$ and let $f_{xy}(t)=\sum F_{xy}(n)t^n$ be the corresponding generating function; then $$ f_{xy}(t)=\frac{1-3t^2+2t^3-2^{d-1}t^{d+1}+2^dt^{d+3}}{(1-t)(1-4t^2)}-\begin{cases}0,&x\ne y\\\frac t{2(1-t)},&x=y\end{cases} $$ where $d=|x-y|$.

Uniqueness of gluing then gives $$ \bar f(t)=\sum_{k,x_0,x_1,x_2,...,x_k>0}f_{x_0x_1}(t)f_{x_1x_2}(t)\cdots f_{x_{k-1}x_k}(t)t^{x_0+x_1+x_2+...+x_k}. $$ I had some functional equations when making a series of two variables out of this, but could not simplify it any further.

Followup

In response to comments by Martin Rubey - some modifications of the above. Since $f_{xy}(t)$ only depends on $|x-y|$, one may redefine them, denoting $f_{xy}(t)$ by $f_d(t)$, where $d=|x-y|$. Then grouping terms by powers of $f_d$ gives some additional information, but not much I'm afraid. \begin{align*} \frac12\bar f(t)=&\frac{t^2}{1-t^2}\left(f_0+2tf_1+2t^2f_2+2t^3f_3+...\right)\\ +&\frac{t^3}{1-t^3}\left(f_0^2+2t(1+t)f_0f_1+t(1+t+2t^2)f_1^2+2t^2(1+t^2)f_0f_2+...\right)\\ +&\frac{t^4}{1-t^4}\left(f_0^3+2t^2(1+t+t^2)f_0^2f_1+...\right)\\ +&... \end{align*}

Followup-2

This could actually be added on the spot, don't know why I did not do it before. Still not a full answer, though.

The above considerations can also be used to obtain a recursion for $\bar F(n)$ as follows. let $\bar F_m(n)$ be the number of indecomposable unmatchable pairs $\langle(a_1,...,a_k),(b_1,...,b_l)\rangle$ with $a_k>b_l=m$ (thus $\bar F(n)=2\sum_{0<m<n}\bar F_m(n)$). Then $$ \bar F_m(n)=\sum_{1\leqslant m'\leqslant n-m}E_{|m-m'|}(n-m-m')+\sum_{1\leqslant m'<n'\leqslant n-m}\bar F_{m'}(n')E_{|m-m'|}(n-m-n'), $$ where $E_d(n)$ is the number, for any fixed $x$, of elementary unmatchable pairs of the form $\langle(x+n+x+d),(x,...,x+d)\rangle$ (this does not depend on $x$). Explicitly, $E_d(0)=1$ while for $n>0$, $$ E_d(n)= \begin{cases} \frac13\left(\left(4+\frac{1+(-1)^n}2\right)2^{n-2}-2\right),&d=0,\\ \frac13\left(\left(4+\frac{1+(-1)^{d+n}}2\right)2^{n-2}-2^{d-1}\right),&0<d<n,\\ 2^{n-1},&n\leqslant d. \end{cases} $$

This is quite computable, I just reached $\bar F(120)/2=58911664743785612350317153163016087887141938864410257$ in several minutes. On the whole, asymptotics seems to be something like $$ \bar F(n)/2\sim (0.16532514842404...)\times(2.794251674002018...)^n. $$ By the way, the first sum in the above recursion actually seems to simplify: for $m<n$, $$ \sum_{1\leqslant m'\leqslant n-m}E_{|m-m'|}(n-m-m')=E_m(n-m), $$ although I don't have a proof of it at the moment.

Followup-3

Let me also mention that the above recursion can be turned into a matrix equation as follows. Consider the infinite matrix $M=\left(t^if_{|i-j|}(t)\right)_{i,j\geqslant1}$ and the infinite vector $v=\left(t^d(f_d(t)-1)\right)_{d\geqslant1}$ (with $f_d(t)$ as in the first followup). Then $$ \left(\sum_n\bar F_m(n)t^n\right)_{m\geqslant1}=(1-M)^{-1}v=(1+M+M^2+M^3+...)v. $$