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

Improve this question
$\endgroup$
4
  • 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
    Commented Jun 16, 2018 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
    Commented Jun 16, 2018 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
    Commented Jun 16, 2018 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$
    – მამუკა ჯიბლაძე
    Commented Jun 16, 2018 at 12:42

2 Answers 2

Reset to default
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.

Improve this answer
$\endgroup$
2
  • 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$
    – მამუკა ჯიბლაძე
    Commented Jun 16, 2018 at 15:11
  • 1
    $\begingroup$ Yes, either of these would look slightly tidier. $\endgroup$
    – Ira Gessel
    Commented Aug 25, 2018 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.

Improve this answer
$\endgroup$
6
  • 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
    Commented Jun 16, 2018 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
    Commented Jun 16, 2018 at 13:02
  • 1
    $\begingroup$ Thanks, but Im not sure whether this qualifies as a nice formula. $\endgroup$
    – Mare
    Commented Jun 16, 2018 at 13:09
  • 1
    $\begingroup$ @Mare: An explicit closed-form expression is asked in the title of your question. $\endgroup$
    – user64494
    Commented Jun 16, 2018 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
    Commented Jun 16, 2018 at 13:15

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .