Intereting Posts

Show that if $f$ has compact support, then its Fourier transform cannot have compact support unless $f=0$.
Can I understand Egorov's theorem in this way?
$H_0(X,A) = 0 \iff A \cap X_i \neq \emptyset \forall $ path-components $X_i$
Matrix on complex field.
Approximating commuting matrices by commuting diagonalizable matrices
counting the patterns
Is there a different name for strongly Darboux functions?
Is sum of digits of $3^{1000}$ divisible by $7$?
How to show that $C=C$ is a Banach space
Lower bounds for bb(7) and bb(8) wanted
Finite abelian $p$-group with only one subgroup size $p$ is cyclic
Symmetric and wedge product in algebra and differential geometry
Is $\mathbb Z$ Euclidean under some other norm?
Finding the Limit $\lim_{x\to 0} \frac{\sin x(1 – \cos x)}{x^2}$
Formula that's only satisfiable in infinite structures

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

- What is the probability of of drawing at least 1 queen, 2 kings and 3 aces in a 9 card draw of a standard 52 card deck?
- The sum of a polynomial over a boolean affine subcube
- Applications of the Fibonacci sequence
- Partitioning Integers into Equal Sets to Guarantee Arithmetic Progression
- Expression for power of a natural number in terms of binomial coefficients
- Prove that $0^0 = 1$ using binomial theorem

Please help !

- $\tbinom{2p}{p}-2$ is divisible by $p^3$
- Sword, pizza and watermelon
- How do we show the equality of these two summations?
- An odd question about induction.
- Finding a combinatorial argument for an interesting identity: $\sum_k \binom nk \binom{m+k}n = \sum_i \binom ni \binom mi 2^i$
- Using permutation or otherwise, prove that $\frac{(n^2)!}{(n!)^n}$ is an integer,where $n$ is a positive integer.
- How many different sums of parts of a vector
- A problem regarding the proof of ${p^nk\choose p^n}\equiv k\mod p$, where $p\nmid k$.
- How to understand the combination formula?
- $n$ choose $k$ where $n$ is less than $k$

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.

- Why doesn't a simple mean give the position of a centroid in a polygon?
- Show: $f'=0\Rightarrow f=\mbox{const}$
- Evaluating $\displaystyle\int_0^1\frac{\sqrt{1-y^2}}{1+y^2}dy$ without trig substitution
- Understanding quotient groups
- Prove that if a sequence $\{a_{n}\}$ converges then $\{\sqrt a_{n}\}$ converges to the square root of the limit.
- Exercise 2.7.1 of J. Norris, “Markov Chains”
- A manifold such that its boundary is a deformation retract of the manifold itself.
- Prove that vector has normal distribution
- Does $\sum \limits_{n=1}^\infty\frac{\sin n}{n}(1+\frac{1}{2}+\cdots+\frac{1}{n})$ converge (absolutely)?
- Are the events independent?
- Is this similarity to the Fourier transform of the von Mangoldt function real?
- What is the best way to self-study GAP?
- Proving Cauchy condensation test
- Bounding this arithmetic sum
- Proof Complex positive definite => self-adjoint