2
$\begingroup$
  • Let $a(n)$ be A143017 i.e. number of $\{2-1-3, 2'^e-31\}$-avoiding permutations of size $n$ (see definition in the Elizalde paper). Here $$ a(n) = \frac{1}{n}\sum\limits_{k=0}^{\left\lfloor\frac{n}{2}\right\rfloor} 2\binom{n}{2k}\binom{n-k}{k-1} + \frac{n}{n-k}\binom{n}{2k+1}\binom{n-k}{k}. $$
  • Let $$ R(n, q) = R(n-1, q+2) + \sum\limits_{j=0}^{q}(-1)^jR(n-1,j), \\ R(0, q) = 1. $$

I conjecture that $$R(n-1, 0) = a(n).$$

Here is the PARI/GR program to check it numerically:

a(n) = (1 / n) * sum(k = 0, n \ 2, 2 * binomial(n, 2*k) * binomial(n-k, k-1) + n * binomial(n, 2*k+1) * binomial(n-k, k) / (n-k))
R_upto(n) = my(v1, v2, v3); v1 = vector(2*n + 1, i, 1); v2 = v1; v3 = vector(n + 1, i, 0); v3[1] = 1; for(i = 1, n, for(q = 0, 2*(n - i), v2[q + 1] = v1[q + 3] + sum(j = 0, q, (-1) ^ j * v1[j + 1])); v1 = v2; v3[i + 1] = v1[1]); v3
test(n) = R_upto(n) == vector(n+1, i, a(i))

Is there a way to prove it?

$\endgroup$

1 Answer 1

7
$\begingroup$

We proceed by "guessing" a generating function for $R(n,q)$ and verifying that it has the right properties.

According to https://oeis.org/A143017, the generating function $G= \sum_{n=1}^\infty a(n) x^n$ satisfies \begin{equation} xG^3 + (4x-2)G^2 + (4x-1)G + x = 0 \tag{1} \end{equation} and it is easy to see that $G$ is uniquely determined as a formal power series by this equation and the condition that $G$ has no constant term.

Let $F$ be the compositional inverse of $x(1-x^2)/(1+x-x^2)$ so $$\frac{F(1-F^2)}{1+F-F^2} =x.$$

We note that we may rewrite the functional equation for $F$ as $$F = x\left(1+\frac{F}{1-F^2}\right),$$ and $F/x$ is the generating function for sequence A101785.

First we show that $G = F/(1-F)$. By (1) it is sufficient to show that \begin{equation*} x\left(\frac{F}{1-F}\right)^3 + (4x-2)\left(\frac{F}{1-F}\right)^2 + (4x-1)\frac{F}{1-F}+ x = 0. \end{equation*} We have \begin{align*} x\left(\frac{F}{1-F}\right)^3 + (4x-2)&\left(\frac{F}{1-F}\right)^2 + (4x-1)\frac{F}{1-F}+ x\\ &=x\frac{1+F-F^2}{(1-F)^3} - \frac{F(1+F)}{(1-F)^2} \\ &=\frac{F(1-F^2)}{1+F-F^2}\frac{1+F-F^2}{(1-F)^3} - \frac{F(1+F)}{(1-F)^2}=0. \end{align*}

Now let \begin{equation*} S_q(x) =\sum_{n=0}^\infty R(n,q) x^{n+1}. \end{equation*} The recurrence for $R(n,q)$ is equivalent to the identity \begin{equation} S_q(x) =x+ xS_{q+2}(x) + x\sum_{j=0}^q (-1)^j S_j(x). \tag{2} \end{equation} and the $S_q(x)$ are determined by (2) and the condition that each $S_q(x)$ is a power series in $x$ starting with $x$. Now let $$U(z) = \sum_{q=0}^\infty S_q(x) z^q.$$ Multiplying (2) by $z^{q+2}$ and summing on $q\ge0$ gives \begin{equation} z^2 U(z) = \frac{xz^2}{1-z} +x \bigl(U(z) -S_0(x) -S_1(x)z\bigr) + \frac{xz^2}{1-z}U(-z)\tag{3} \end{equation} and $U(z)$ is the unique solution of (3).

I claim that \begin{equation} S_q(x) = \frac{F}{(1-F)^{\lfloor q/2\rfloor+1}(1+F)^{\lceil q/2\rceil}},\tag{4} \end{equation} which is equivalent to \begin{equation} U(z) = \frac{F(1+F+z)}{1-F^2-z^2}.\tag{5} \end{equation} To verify this, we use (4) and (5) to express (3) in terms of $x$, $z$, and $F$, and then replace $x$ with $F(1-F^2)/(1+F-F^2)$. We obtain an easily verified identity of rational function in $z$ and $F$. In particular, $$\sum_{n=1}^\infty R(n-1,0) x^{n}=S_0(x) = \frac{F}{1-F} = G = \sum_{n=1}^\infty a(n) x^n.$$

$\endgroup$

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.