2
$\begingroup$

In an enumeration problem the sequence of number of Dyck paths semilength n having no UUDD's starting at level 0 with generating function $$\frac{2}{(1+2z^2+\sqrt{1-4z})}$$ showed up, see also https://oeis.org/A114487. It is not really important but I wonder whether a nice explicit formula exists for this sequence.

Im not really experienced with such problems but I saw that sometimes very nice formulas exit for such non-rational generating functions. For example for the Motzkin numbers $M_n$ with generating function $\frac{ 1 - x - (\sqrt{1-2x-3x^2} )}{ 2x^2}$ the explicit formula $M_n=\sum\limits_{k=0}^{[\frac{n}{2}]}{\binom{n}{2k}C_k}$ exists when $C_k$ are the Catalan numbers, see https://www.ncbi.nlm.nih.gov/pmc/articles/PMC5310552/.

$\endgroup$
  • 1
    $\begingroup$ You can make a summation by applying the binomial theorem to the numerator of the rationalized version $$\frac{1+2z^2-\sqrt{1-4z}}{2z(1+z+z^3)}$$. $\endgroup$ – Brendan McKay Jun 16 '18 at 11:37
  • 1
    $\begingroup$ @BrendanMcKay... But even for $1/(1+z+z^3)$, where the coefficients satisfy a third-order recurrence, is there a nice-looking closed form? $\endgroup$ – Gerald Edgar Jun 16 '18 at 11:41
  • $\begingroup$ @GeraldEdgar That is at least one summation for even powers and one for odd powers. But, I guess "nice" is a bit strong a word. $\endgroup$ – Brendan McKay Jun 16 '18 at 11:46
  • 2
    $\begingroup$ More precisely, it is $-(1-z-z^3)$, not $1+z+z^3$; the $n$th coefficient of $\frac1{1-z-z^3}$ is ${\displaystyle\sum_{k=0}^{\left[\frac n3\right]}}\binom{n-2k}k$. $\endgroup$ – მამუკა ჯიბლაძე Jun 16 '18 at 12:42
9
$\begingroup$

The coefficient of $z^n$ is $$\sum_{0\le k\le n/2} (-1)^k \frac{k+1}{2n-3k+1}\binom{2n-3k+1}{n-2k}.$$

To see this, let $C(z)$ be the Catalan number generating function, $$C(z) = \frac{1-\sqrt{1-4z}}{2z}=\frac{2}{1+\sqrt{1-4z}}.$$ Then $$ \frac{2}{1+2z^2+\sqrt{1-4z}} = \frac{C(z)}{1+z^2 C(z)}. $$ It is well known that $$ C(z)^j = \sum_{m=0}^\infty \frac{j}{2m+j}\binom{2m+j}{m} z^m. $$ Thus $$ \begin{aligned} \frac{2}{1+2z^2+\sqrt{1-4z}}&=\sum_{k=0}^\infty (-1)^k z^{2k}C(z)^{k+1}\\ &=\sum_{k=0}^\infty (-1)^k z^{2k} \sum_m \frac{k+1}{2m+k+1}\binom{2m+k+1}{m} z^m\\ &=\sum_n z^n \sum_{0\le k\le n/2} (-1)^k \frac{k+1}{2n-3k+1}\binom{2n-3k+1}{n-2k}. \end{aligned} $$

I have added this formula to the OEIS entry.

$\endgroup$
  • 1
    $\begingroup$ It is very nice anyway, but would not $\sum(-1)^k\frac{k+1}{n-k+1}\binom{2n-3k}{n-k}$ or $\sum(-1)^k\frac{k+1}{n-k+1}\binom{2n-3k}{n-2k}$ look slightly tidier? $\endgroup$ – მამუკა ჯიბლაძე Jun 16 '18 at 15:11
  • 1
    $\begingroup$ Yes, either of these would look slightly tidier. $\endgroup$ – Ira Gessel Aug 25 '18 at 20:41
1
$\begingroup$

This can be done with help of Maple, realizing the Brendan McKay's suggestion, in such a way:

a := convert(expand(convert(-sqrt(1-4*z), FPS, z, j)+1+2*z^2), FPS, z);

$$\sum _{j=0}^{\infty }{\frac { \left( 2\,j \right) !\,{z}^{j}}{ \left( j! \right) ^{2} \left( -1+2\,j \right) }}+1+2\,{z}^{2} $$

b := b := allvalues(convert(1/(2*z*(-z^3-z+1)), FPS, z));

$$1/2\,{z}^{-1}+\sum _{k=0}^{\infty } \left( {\frac {4\, \left( 1/6\, \sqrt [3]{108+12\,\sqrt {93}}-2\,{\frac {1}{\sqrt [3]{108+12\,\sqrt { 93}}}} \right) ^{2}+\sqrt [3]{108+12\,\sqrt {93}}-12\,{\frac {1}{ \sqrt [3]{108+12\,\sqrt {93}}}}+13}{62\, \left( 1/6\,\sqrt [3]{108+12 \,\sqrt {93}}-2\,{\frac {1}{\sqrt [3]{108+12\,\sqrt {93}}}} \right) ^{ k+1}}}+{\frac {4\, \left( -1/12\,\sqrt [3]{108+12\,\sqrt {93}}+{\frac {1}{\sqrt [3]{108+12\,\sqrt {93}}}}+i/2\sqrt {3} \left( 1/6\,\sqrt [3] {108+12\,\sqrt {93}}+2\,{\frac {1}{\sqrt [3]{108+12\,\sqrt {93}}}} \right) \right) ^{2}-1/2\,\sqrt [3]{108+12\,\sqrt {93}}+6\,{\frac {1 }{\sqrt [3]{108+12\,\sqrt {93}}}}+3\,i\sqrt {3} \left( 1/6\,\sqrt [3]{ 108+12\,\sqrt {93}}+2\,{\frac {1}{\sqrt [3]{108+12\,\sqrt {93}}}} \right) +13}{62\, \left( -1/12\,\sqrt [3]{108+12\,\sqrt {93}}+{\frac {1}{\sqrt [3]{108+12\,\sqrt {93}}}}+i/2\sqrt {3} \left( 1/6\,\sqrt [3] {108+12\,\sqrt {93}}+2\,{\frac {1}{\sqrt [3]{108+12\,\sqrt {93}}}} \right) \right) ^{k+1}}}+{\frac {4\, \left( -1/12\,\sqrt [3]{108+12 \,\sqrt {93}}+{\frac {1}{\sqrt [3]{108+12\,\sqrt {93}}}}-i/2\sqrt {3} \left( 1/6\,\sqrt [3]{108+12\,\sqrt {93}}+2\,{\frac {1}{\sqrt [3]{108 +12\,\sqrt {93}}}} \right) \right) ^{2}-1/2\,\sqrt [3]{108+12\,\sqrt {93}}+6\,{\frac {1}{\sqrt [3]{108+12\,\sqrt {93}}}}-3\,i\sqrt {3} \left( 1/6\,\sqrt [3]{108+12\,\sqrt {93}}+2\,{\frac {1}{\sqrt [3]{108 +12\,\sqrt {93}}}} \right) +13}{62\, \left( -1/12\,\sqrt [3]{108+12\, \sqrt {93}}+{\frac {1}{\sqrt [3]{108+12\,\sqrt {93}}}}-i/2\sqrt {3} \left( 1/6\,\sqrt [3]{108+12\,\sqrt {93}}+2\,{\frac {1}{\sqrt [3]{108 +12\,\sqrt {93}}}} \right) \right) ^{k+1}}} \right) {z}^{k} $$

It remains to multiply these series.

$\endgroup$
  • 1
    $\begingroup$ I think there is a wrong exponent in the denominator of b. As GeraldEdgar says, the coefficients have a third order linear recursion, and they are linear combinations of powers of roots of $1+z+z^{\bf 3}.$ $\endgroup$ – Pietro Majer Jun 16 '18 at 12:55
  • $\begingroup$ @Pietro Majer: Thank you for your valuable comment. In this case Maple performs the expansion too, but the formulas are somewhat longer. $\endgroup$ – user64494 Jun 16 '18 at 13:02
  • 1
    $\begingroup$ Thanks, but Im not sure whether this qualifies as a nice formula. $\endgroup$ – Mare Jun 16 '18 at 13:09
  • 1
    $\begingroup$ @Mare: An explicit closed-form expression is asked in the title of your question. $\endgroup$ – user64494 Jun 16 '18 at 13:12
  • 1
    $\begingroup$ Yes so it is good to see it here, but there might be a much nicer closed form (see the example with the Motzkin numbers, where such a direct approach probably also would end up uglier than the formula given). $\endgroup$ – Mare Jun 16 '18 at 13:15

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.