Return to Answer

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

I was not able to simplify the expression for $F(n)$. The main obstacle is the squaring -- without it the sum can be simplified by changing the order of summation and use of the generating function: $$G(x) = \sum_{t=0}^\infty g(t)x^t = \frac{1-x}{1-2x}.$$ While this is irrelevant to the original question, I still mention how it goes just in case.

Notice that a summand is nonzero iff $s_i+s_{i+1}-m_i\geq 0$, which together with $s_i < m_i/2$ implies $2s_i < m_i \leq s_i+s_{i+1}$ and thus

$$\sum_{0<m_1<\dots<m_k<2n} \sum_{0\le s_1<\dots<s_k<n=s_{k+1}\atop s_i<m_i/2} [x^{s_1}]\ G(x)\prod_{i=1}^k [x^{s_i+s_{i+1}-m_i}]\ G(x)$$ $$=\sum_{0\le s_1<\dots<s_k<n=s_{k+1}} [x^{s_1}]\ G(x) \sum_{m_1=2s_1+1}^{s_1+s_2} [x^{s_1+s_2-m_1}]\ G(x) \cdots \sum_{m_k=2s_k+1}^{s_k+s_{k+1}} [x^{s_k+s_{k+1}-m_k}]\ G(x)$$ $$=\sum_{0\le s_1<\dots<s_k<n=s_{k+1}} [x^{s_1}]\ G(x)\cdot [x^{s_2-s_1-1}]\ \frac{G(x)}{1-x} \cdots [x^{s_{k+1}-s_{k}-1}]\ \frac{G(x)}{1-x}$$ $$=[x^{n-k}]\ (1-x)\cdot\left(\frac{G(x)}{1-x}\right)^{k+1} = \binom{-k-1}{n-k}\cdot (-2)^{n-k} - \binom{-k-1}{n-k-1}\cdot (-2)^{n-k-1},$$ where we used that $\frac{G(x)}{1-x} = (1-2x)^{-1}$.

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

$a=(1,3,2,3,4)$." />

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.

$a=(1,3,2,3,4)$." />

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

I was not able to simplify the expression for $F(n)$. The main obstacle is the squaring -- without it the sum can be simplified by changing the order of summation and use of the generating function: $$G(x) = \sum_{t=0}^\infty g(t)x^t = \frac{1-x}{1-2x}.$$ While this is irrelevant to the original question, I still mention how it goes just in case.

Notice that a summand is nonzero iff $s_i+s_{i+1}-m_i\geq 0$, which together with $s_i < m_i/2$ implies $2s_i < m_i \leq s_i+s_{i+1}$ and thus

$$\sum_{0<m_1<\dots<m_k<2n} \sum_{0\le s_1<\dots<s_k<n=s_{k+1}\atop s_i<m_i/2} [x^{s_1}]\ G(x)\prod_{i=1}^k [x^{s_i+s_{i+1}-m_i}]\ G(x)$$ $$=\sum_{0\le s_1<\dots<s_k<n=s_{k+1}} [x^{s_1}]\ G(x) \sum_{m_1=2s_1+1}^{s_1+s_2} [x^{s_1+s_2-m_1}]\ G(x) \cdots \sum_{m_k=2s_k+1}^{s_k+s_{k+1}} [x^{s_k+s_{k+1}-m_k}]\ G(x)$$ $$=\sum_{0\le s_1<\dots<s_k<n=s_{k+1}} [x^{s_1}]\ G(x)\cdot [x^{s_2-s_1-1}]\ \frac{G(x)}{1-x} \cdots [x^{s_{k+1}-s_{k}-1}]\ \frac{G(x)}{1-x}$$ $$=[x^{n-k}]\ (1-x)\cdot\left(\frac{G(x)}{1-x}\right)^{k+1} = \binom{-k-1}{n-k}\cdot (-2)^{n-k} - \binom{-k-1}{n-k-1}\cdot (-2)^{n-k-1},$$ where we used that $\frac{G(x)}{1-x} = (1-2x)^{-1}$.

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

$a=(1,3,2,3,4)$." />

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

I was not able to simplify the expression for $F(n)$. The main obstacle is the squaring -- without it the sum can be simplified by changing the order of summation and use of the generating function: $$G(x) = \sum_{t=0}^\infty g(t)x^t = \frac{1-x}{1-2x}.$$ While this is irrelevant to the original question, I still mention how it goes just in case.

Notice that a summand is nonzero iff $s_i+s_{i+1}-m_i\geq 0$, which together with $s_i < m_i/2$ implies $2s_i < m_i \leq s_i+s_{i+1}$ and thus

$$\sum_{0<m_1<\dots<m_k<2n} \sum_{0\le s_1<\dots<s_k<n=s_{k+1}\atop s_i<m_i/2} [x^{s_1}]\ G(x)\prod_{i=1}^k [x^{s_i+s_{i+1}-m_i}]\ G(x)$$ $$=\sum_{0\le s_1<\dots<s_k<n=s_{k+1}} [x^{s_1}]\ G(x) \sum_{m_1=2s_1+1}^{s_1+s_2} [x^{s_1+s_2-m_1}]\ G(x) \cdots \sum_{m_k=2s_k+1}^{s_k+s_{k+1}} [x^{s_k+s_{k+1}-m_k}]\ G(x)$$ $$=\sum_{0\le s_1<\dots<s_k<n=s_{k+1}} [x^{s_1}]\ G(x)\cdot [x^{s_2-s_1-1}]\ \frac{G(x)}{1-x} \cdots [x^{s_{k+1}-s_{k}-1}]\ \frac{G(x)}{1-x}$$ $$=[x^{n-k}]\ (1-x)\cdot\left(\frac{G(x)}{1-x}\right)^{k+1} = \binom{-k-1}{n-k}\cdot (-2)^{n-k} - \binom{-k-1}{n-k-1}\cdot (-2)^{n-k-1},$$ where we used that $\frac{G(x)}{1-x} = (1-2x)^{-1}$.

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

$a=(1,3,2,3,4)$." />

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

I was not able to simplify the expression for $F(n)$. The main obstacle is the squaring -- without it the sum can be simplified by changing the order of summation and use of the generating function: $$G(x) = \sum_{t=0}^\infty g(t)x^t = \frac{1-x}{1-2x}.$$ While this is irrelevant to the original question, I still mention how it goes just in case.

Notice that a summand is nonzero iff $s_i+s_{i+1}-m_i\geq 0$, which together with $s_i < m_i/2$ implies $2s_i < m_i \leq s_i+s_{i+1}$ and thus

$$\sum_{0<m_1<\dots<m_k<2n} \sum_{0\le s_1<\dots<s_k<n=s_{k+1}\atop s_i<m_i/2} [x^{s_1}]\ G(x)\prod_{i=1}^k [x^{s_i+s_{i+1}-m_i}]\ G(x)$$ $$=\sum_{0\le s_1<\dots<s_k<n=s_{k+1}} [x^{s_1}]\ G(x) \sum_{m_1=2s_1+1}^{s_1+s_2} [x^{s_1+s_2-m_1}]\ G(x) \cdots \sum_{m_k=2s_k+1}^{s_k+s_{k+1}} [x^{s_k+s_{k+1}-m_k}]\ G(x)$$ $$=\sum_{0\le s_1<\dots<s_k<n=s_{k+1}} [x^{s_1}]\ G(x)\cdot [x^{s_2-s_1-1}]\ \frac{G(x)}{1-x} \cdots [x^{s_{k+1}-s_{k}-1}]\ \frac{G(x)}{1-x}$$ $$=[x^{n-k}]\ (1-x)\cdot\left(\frac{G(x)}{1-x}\right)^{k+1} = \binom{-k-1}{n-k}\cdot (-2)^{n-k} - \binom{-k-1}{n-k-1}\cdot (-2)^{n-k-1},$$ where we used that $\frac{G(x)}{1-x} = (1-2x)^{-1}$.

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 (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 (n,0).$$ It can be seen that this path consists of alternating diagonal -45° and +45° steps, each of which crosses the $y$-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 $y$-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.

$a=(1,3,2,3,4)$." />

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

I was not able to simplify the expression for $F(n)$. The main obstacle is the squaring -- without it the sum can be simplified by changing the order of summation and use of the generating function: $$G(x) = \sum_{t=0}^\infty g(t)x^t = \frac{1-x}{1-2x}.$$ While this is irrelevant to the original question, I still mention how it goes just in case.

Notice that a summand is nonzero iff $s_i+s_{i+1}-m_i\geq 0$, which together with $s_i < m_i/2$ implies $2s_i < m_i \leq s_i+s_{i+1}$ and thus

$$\sum_{0<m_1<\dots<m_k<2n} \sum_{0\le s_1<\dots<s_k<n=s_{k+1}\atop s_i<m_i/2} [x^{s_1}]\ G(x)\prod_{i=1}^k [x^{s_i+s_{i+1}-m_i}]\ G(x)$$ $$=\sum_{0\le s_1<\dots<s_k<n=s_{k+1}} [x^{s_1}]\ G(x) \sum_{m_1=2s_1+1}^{s_1+s_2} [x^{s_1+s_2-m_1}]\ G(x) \cdots \sum_{m_k=2s_k+1}^{s_k+s_{k+1}} [x^{s_k+s_{k+1}-m_k}]\ G(x)$$ $$=\sum_{0\le s_1<\dots<s_k<n=s_{k+1}} [x^{s_1}]\ G(x)\cdot [x^{s_2-s_1-1}]\ \frac{G(x)}{1-x} \cdots [x^{s_{k+1}-s_{k}-1}]\ \frac{G(x)}{1-x}$$ $$=[x^{n-k}]\ (1-x)\cdot\left(\frac{G(x)}{1-x}\right)^{k+1} = \binom{-k-1}{n-k}\cdot (-2)^{n-k} - \binom{-k-1}{n-k-1}\cdot (-2)^{n-k-1},$$ where we used that $\frac{G(x)}{1-x} = (1-2x)^{-1}$.

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

$a=(1,3,2,3,4)$." />