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$
8
  • $\begingroup$ I checked oeis.org and your sequence is not in the database. $\endgroup$
    – Tony Huynh
    Feb 8, 2016 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, 2016 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, 2016 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$ Feb 10, 2016 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, 2016 at 16:59

3 Answers 3

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$
17
  • $\begingroup$ Yes I am very interested to hear about the connection with lattice paths, please do explain. $\endgroup$ Feb 10, 2016 at 17:00
  • 1
    $\begingroup$ @მამუკაჯიბლაძე: I've added the geometric interpretation. $\endgroup$ Feb 10, 2016 at 20:00
  • 1
    $\begingroup$ @მამუკაჯიბლაძე: Unmatchable pair is a pair of paths where all vertices have distinct $x$-coordinates. $\endgroup$ Feb 10, 2016 at 22:17
  • 1
    $\begingroup$ @მამუკაჯიბლაძე: paths with 45° are indeed nicer. I'll update the illustration. $\endgroup$ Feb 10, 2016 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$ Feb 14, 2016 at 22:12
5
$\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$
2
  • $\begingroup$ Congratulations! Does the parameter $z=-\frac{q^2}{2(1-q)}$ have a combinatorial meaning? $\endgroup$ Mar 25, 2016 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, 2016 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$
7
  • $\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$ Feb 29, 2016 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, 2016 at 9:12
  • $\begingroup$ Edited that place $\endgroup$ Feb 29, 2016 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$ Feb 29, 2016 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$ Feb 29, 2016 at 20:13

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.