Intereting Posts

Is the formula $(\text{ker }A)^\perp=\text{im }A^T$ necessarily true?
Show that $\prod (1- P(A_n))=0$ iff $\sum P(A_n) = \infty$
Applying Central Limit Theorem to show that $E\left(\frac{|S_n|}{\sqrt{n}}\right) \to \sqrt{\frac{2}{\pi}}\sigma$
How many times are the hands of a clock at $90$ degrees.
If L is nilpotent then $K\cap L^n \not=0$
How find this integral limt
Let $R$ be a commutative ring with $1$. Suppose that every nonzero proper ideal of $R$ is maximal. Prove that there are at most two such ideals.
Matrix exponential convergence
Number of ways to put $n$ unlabeled balls in $k$ bins with a max of $m$ balls in each bin
Show that $4\frac{\partial}{\partial z}\frac{\partial}{\partial\bar{z}}=\frac{\partial^2}{\partial x^2}+\frac{\partial^2}{\partial y^2}$
$\int_{-2}^{2} \sin(x^5)e^{(x^8\sin(x^4))} dx$
Existence and uniqueness of limit of inverse function
Killing vector fields restricted to geodesics
Taylor series of a convolution
Compact, continuous embeddings of $H^s := W^{s,2} \leftrightarrow C^{(\alpha)}$

I need your help to solve this problem :

Give a generating function for planted planar trees with all degrees odd.

Show that the number of such trees with $2k+1$ non-root vertices is

$$\displaystyle \frac{\binom{3k}{k}}{(2k+1)}$$

Please help !

- Maximum independent sets of balanced bipartite graph
- How to find the number of distinct combinations of a non distinct set of elements?
- A question on primes and equal products
- organize 5 subjects in 6 periods
- Prove if there are 4 points in a unit circle then at least two are at distance less than or equal to $\sqrt2$
- The coefficient of $x^{18}$ in $(1+x^5+x^7)^{20}$
- Help me solve a combinatorial problem
- Interesting combinatoral identity
- How do I calculate these sum-of-sum expressions in terms of the generalized harmonic number?
- Derangement of n elements

Start by computing the generating function for the odd total degree

trees without the degree-one root node. There is an even number of children plus a link to the parent for a total odd degree. This has the functional

equation

$$T(z) = z + z \frac{T(z)^2}{1-T(z)^2}.$$

Now recall the Lagrange Inversion Formula as presented e.g. at this

MathWorld link

(consulted May 26 2014.)

Using their variables we have $w=z$, $\alpha=z$ and

$$\phi(w) = \frac{w^2}{1-w^2}.$$

Setting $F(v) = v$ in the above we obtain

$$T(z) = z + \frac{z}{1} \frac{z^2}{1-z^2}

+ \frac{z^2}{2!} \frac{\partial}{\partial z}

\left(\frac{z^2}{1-z^2}\right)^2

+ \frac{z^3}{3!} \frac{\partial^2}{\partial z^2}

\left(\frac{z^2}{1-z^2}\right)^3

+ \cdots.$$

Recall that

$$\left(\frac{z}{1-z}\right)^q

= \sum_{n\ge q} {n-1\choose q-1} z^n$$

so that

$$\left(\frac{z^2}{1-z^2}\right)^q

= \sum_{n\ge q} {n-1\choose q-1} z^{2n}.$$

This implies that

$$\frac{\partial^{q-1}}{\partial z^{q-1}}

\left(\frac{z^2}{1-z^2}\right)^q

= \sum_{n\ge q} (2n)^{\underline{q-1}}

{n-1\choose q-1} z^{2n-(q-1)}.$$

This in turn yields

$$[z^m] \frac{z^q}{q!}\frac{\partial^{q-1}}{\partial z^{q-1}}

\left(\frac{z^2}{1-z^2}\right)^q

\\= [z^m] \frac{z^q}{q!}

\sum_{n\ge q} (2n)^{\underline{q-1}} {n-1\choose q-1} z^{2n+1-q}

\\ = \frac{1}{q!} [z^{m-q}]

\sum_{n\ge q} (2n)^{\underline{q-1}} {n-1\choose q-1} z^{2n+1-q}.$$

If $m$ is odd this gives $2n+1=m$ and we must have $(m-1)/2\ge q$ for

a contribution of

$$\frac{1}{q!} (m-1)^{\underline{q-1}}{m/2-3/2\choose q-1}.$$

Collecting everything into one formula we obtain for $m\ge 3$ and $m$

odd the closed form

$$1 + \sum_{q=2}^{m/2-1/2} \frac{1}{q!}

(m-1)^{\underline{q-1}}{m/2-3/2\choose q-1}$$

which is

$$1 + \sum_{q=2}^{m/2-1/2} \frac{1}{q!}

\frac{(m-1)!}{(m-q)!}

{m/2-3/2\choose q-1}$$

or equivalently

$$1 + \frac{1}{m}

\sum_{q=2}^{m/2-1/2} {m\choose q} {m/2-3/2\choose q-1}.$$

Simplifying this to

$$\frac{1}{m}{3m/2-3/2\choose m/2-1/2}$$

is best done with a CAS and Zeilberger’s algorithm /

Sister Celine’s method.

This is the following sequence

$$ 1, 3, 12, 55, 273, 1428, 7752, 43263, 246675, 1430715, \ldots$$

which is OEIS A001764 where

a variety of relevant information can be found.

**Addendum Tue May 27 22:12:28 CEST 2014.**

Here is some additional material to document how to obtain the simple

closed form.

Note that we can absorb the term in front into the sum, turning

$$1 + \frac{1}{m}

\sum_{q=2}^{m/2-1/2} {m\choose q} {m/2-3/2\choose q-1}$$

into

$$\frac{1}{m}

\sum_{q=1}^{m/2-1/2} {m\choose q} {m/2-3/2\choose q-1}.$$

Now since $m$ is odd put $m=2k+1$ to get

$$\frac{1}{2k+1}

\sum_{q=1}^k {2k+1\choose q} {k-1\choose q-1}.$$

It turns out that Maple has an implementation of creative telescoping,

the method we cited above. In the present case it yields the following

data:

> restart; > with(SumTools[DefiniteSum]): > CreativeTelescoping(binomial(2*k+1,q)*binomial(k-1,q-1),q=1..k); 1/2 k 3 27 GAMMA(k + 1/3) GAMMA(k + 2/3) 1/2 -------------------------------------- Pi GAMMA(2 k + 1)

Now using the multiplication theorem of the

Gamma function

we have that

$$\Gamma(k+1/3)\Gamma(k+2/3)

=\frac{2\pi\times 3^{1/2-3k}}{\Gamma(k)} \Gamma(3k).$$

Substituting this into the closed form for the sum yields

$$\frac{1}{2\pi}

\frac{3^{1/2+3k}}{\Gamma(2k+1)}

\frac{2\pi\times 3^{1/2-3k}}{\Gamma(k)} \Gamma(3k)

= \frac{3k\Gamma(3k)}{k\Gamma(k)\Gamma(2k+1)}.$$

It follows that the closed form for the number of trees is

$$\frac{1}{2k+1}

\frac{3k\Gamma(3k)}{k\Gamma(k)\Gamma(2k+1)}

= \frac{(3k)!}{(k!)\times (2k+1)!}

= \frac{1}{2k+1} \frac{(3k)!}{(k!)\times (2k)!}

= \frac{1}{2k+1} {3k\choose k}.$$

Note that the method of creative telescoping provides sound proof of

the closed forms of the sums that it is applied to as explained e.g. by

Wilf in his book *generatingfunctionology*.

As it turns out the Mathworld formulation is not optimal here. We can do better using Wilf’s formulation as given in *generatingfunctionology*.

Re-write the functional equation like this:

$$T(z)-T(z)^3 = z – z T(z)^2 + z T(z)^2 = z.$$

Now we have

$$[z^n] T(z) = \frac{1}{2\pi i}

\int_{|z|=\epsilon} \frac{1}{z^{n+1}} T(z) dz$$

and make the substituion $w = T(z)$ so that $z=w-w^3$ and $dz = (1-3w^2) dw$ to get

$$ \frac{1}{2\pi i}

\int_{|w|=\epsilon} \frac{1}{w^{n+1} (1-w^2)^{n+1}} w (1-3w^2) dw$$

which is

$$ \frac{1}{2\pi i}

\int_{|w|=\epsilon} \frac{1}{w^n (1-w^2)^{n+1}} (1-3w^2) dw.$$

Now the Cauchy Residue Theorem gives the following two coefficients for $n=2k+1$ and odd

$$[w^{n-1}] \frac{1}{(1-w^2)^{n+1}}

= [w^{2k}] \frac{1}{(1-w^2)^{n+1}} = {k+n\choose n} = {3k+1\choose 2k+1}$$

and

$$[w^{n-1}] 3w^2 \frac{1}{(1-w^2)^{n+1}}

= 3 [w^{2k-2}] \frac{1}{(1-w^2)^{n+1}} = 3{k-1+n\choose n} = 3{3k\choose 2k+1}.$$

But $${3k+1\choose 2k+1} – 3{3k\choose 2k+1} = \frac{1}{2k+1}{3k\choose k}$$

and we are done.

- separation theorem for probability measures
- Center of $\mathfrak{sl}(n,F)$
- Open covers by simply connected sets and fundamental group
- Proving number of subsets of a set size $n$ via induction
- Does the existence of double limit at a point imply continuity of a function at that point?
- Prove Friedrichs' inequality
- Rearrangement of series in Banach space and absolute convergence
- Why is Householder computationally more stable than modified Gram-Schmidt?
- What happens if I toss a coin with decreasing probability to get a head?
- clarification asked for 'difference between convolution and crosscorrelation?'
- Mathematical induction with the Fibonacci sequence
- The sine inequality $\frac2\pi x \le \sin x \le x$ for $0<x<\frac\pi2$
- Green's Function ODE
- How find this integral $I=\int\frac{1}{\sin^5{x}+\cos^5{x}}dx$
- Why does a multiplicative subgroup of a field have to be cyclic?