14
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ I checked oeis.org and your sequence is not in the database. $\endgroup$ – Tony Huynh Feb 8 '16 at 18:01
  • $\begingroup$ @TonyHuynh Oh I should mention this, I've looked there too, also for the sequence divided by 2 (obviously all the numbers are even). I thought about adding it but first I want to learn more about it $\endgroup$ – მამუკა ჯიბლაძე Feb 8 '16 at 18:08
  • 2
    $\begingroup$ @TimothyChow In that case it is very easy to show that the sequence is $3^{n-1}$. This is one of the reasons I hope that there must be a good generating function. $\endgroup$ – მამუკა ჯიბლაძე Feb 9 '16 at 6:24
  • 1
    $\begingroup$ For what it's worth, here are some more terms: $1, 3, 12, 39, 142, 480, 1701, 5855, 20510, 71090, 247998, 861723$. Note that the numbers have huge prime factors. Eg. $861723 = 9\cdot 95747$ $\endgroup$ – Martin Rubey Feb 10 '16 at 10:10
  • 4
    $\begingroup$ @LiorSilberman No no it is as intended. "Geometrically" it is really the midpoint: a composition $(a_1,...,a_k)$ of $n$ is more or less the same as a partition of the set $\{1,...,n\}$ of points of the real line into disjoint subsets of contiguous points, $\{1,...,a_1\}$, $\{a_1+1,...,a_1+a_2\}$, $\{a_1+a_2+1,...,a_1+a_2+a_3\}$, ..., $\{a_1+a_2+...+a_{k-1}+1,...,n\}$. Then the midpoint of $\{1,...,a_1\}$ is $\frac{a_1+1}2$, the midpoint of $\{a_1+1,...,a_1+a_2\}$ is $a_1+\frac{a_2+1}2$, etc. $\endgroup$ – მამუკა ჯიბლაძე Feb 10 '16 at 16:59
10
$\begingroup$

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.

Path corresponding to $a=(1,3,2,3,4)$.

$\endgroup$
  • $\begingroup$ Yes I am very interested to hear about the connection with lattice paths, please do explain. $\endgroup$ – მამუკა ჯიბლაძე Feb 10 '16 at 17:00
  • 1
    $\begingroup$ @მამუკაჯიბლაძე: I've added the geometric interpretation. $\endgroup$ – Max Alekseyev Feb 10 '16 at 20:00
  • 1
    $\begingroup$ @მამუკაჯიბლაძე: Unmatchable pair is a pair of paths where all vertices have distinct $x$-coordinates. $\endgroup$ – Max Alekseyev Feb 10 '16 at 22:17
  • 1
    $\begingroup$ @მამუკაჯიბლაძე: paths with 45° are indeed nicer. I'll update the illustration. $\endgroup$ – Max Alekseyev Feb 10 '16 at 22:37
  • 1
    $\begingroup$ @მამუკაჯიბლაძე: I'm afraid this is not so straightforward. The residue approach seems to fail even in the simple case of $f_n=1$ and $F(t)=\frac{1}{1-t}$. $\endgroup$ – Max Alekseyev Feb 14 '16 at 22:12
4
$\begingroup$

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

$\endgroup$
  • $\begingroup$ Congratulations! Does the parameter $z=-\frac{q^2}{2(1-q)}$ have a combinatorial meaning? $\endgroup$ – Martin Rubey Mar 25 '16 at 9:35
  • $\begingroup$ @MartinRubey Thanks! No idea. In fact I am now trying to use Heine transformation to switch to a better $z$. But maybe this one is indeed significant, will think about it too. $\endgroup$ – მამუკა ჯიბლაძე Mar 25 '16 at 10:23
1
$\begingroup$

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. $$

$\endgroup$
  • $\begingroup$ I'm confused: if $\bar f=t+3t^2+10t^3+27t^4\dots$, then $1/(1-\bar f) = 1+t+4t^2+17t^3+66t^4+\dots$ which is not the series in the question. $\endgroup$ – Martin Rubey Feb 29 '16 at 9:01
  • 1
    $\begingroup$ @MartinRubey Sorry should be more clear - the sequence starts with $n=1$, and moreover it is halved, so $\bar f=2(t^2+3t^3+10t^4+27t^5+...)$. $\endgroup$ – მამუკა ჯიბლაძე Feb 29 '16 at 9:12
  • $\begingroup$ Edited that place $\endgroup$ – მამუკა ჯიბლაძე Feb 29 '16 at 9:21
  • 1
    $\begingroup$ It's very nice that $\bar f$ is much better to compute! I wonder whether one can exploit the symmetry of $f_{x,y}$ apart from the trivial observation that the summand corresponding to $x_0,\dots,x_k$ is the same as the one corresponding to $x_k,\dots, x_0$. $\endgroup$ – Martin Rubey Feb 29 '16 at 10:05
  • 1
    $\begingroup$ Did you try to compute $S_{d_1,\dots,d_k}$ for small $k$? Multiplying by $(1-t^k)$ gives a polynomial, maybe one can do something with these. $\endgroup$ – Martin Rubey Feb 29 '16 at 20:13

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.