Intereting Posts

Why does finding the $x$ that maximizes $\ln(f(x))$ is the same as finding the $x$ that maximizes $f(x)$?
Solving Cubic Equations (With Origami)
If $d>1$ is a squarefree integer, show that $x^2 – dy^2 = c$ gives some bounds in terms of a fundamental solution.
How do I show that two groups are not isomorphic?
geodesics on a surface of revolution
Show that the sum $\frac {1}{p_1} + \frac {1}{p_2} +\frac {1}{p_3} +…+\frac {1}{p_n}$ is never an integer,where $p_i$'s are primes,$ 1\le i \le n$.
What in Mathematics cannot be described within set theory?
Methods to see if a polynomial is irreducible
Minimum period of function such that $f\left(x+\frac{13}{42}\right)+f(x)=f\left(x+\frac{1}{6}\right)+f\left(x+\frac{1}{7}\right) $
How to solve this first-order differential equation?
What does $\ll$ mean?
Prove that $L = \frac{(pX')' – qX}{r}$ is a formally self-adjoint operator for continuous $p, q,r$ functions.
Constructive proof of Euler's formula
Prove $\sum_{n=1}^\infty(e-\sum_{k=0}^n\frac1{k!})=1$
What is the math notation for this type of function?

Show that $$ \sum_{r=1}^{n-1}\binom{n-2}{r-1}r^{r-1}(n-r)^{n-r-2}= n^{n-2} $$

I don’t know whether such identity already exists, or has been posted here before. I discovered this identity while solving a problem but nor able to prove. And if the problem is correct then this must have to be true. Its coming out to be true for $n$ upto $10$. So please prove or disprove.( I am quite sure it is true)

- An interesting property of binomial coefficients that I couldn't prove
- Convexity of Binomial Term
- Find $v_p\left(\binom{ap}{bp}-\binom{a}{b}\right)$, where $p>a>b>1$ and $p$ odd prime.
- A strange combinatorial identity: $\sum\limits_{j=1}^k(-1)^{k-j}j^k\binom{k}{j}=k!$
- Algebraic proof of $\sum_{i=0}^k{{n \choose i}{m \choose {k-i}}}= {{m+n}\choose k}$
- Combinatorial proof for two identities

- How to understand the combination formula?
- Proof related to Fibonacci sequence
- Number of relations that are both symmetric and reflexive
- What structure does the alternating group preserve?
- Combinatorial interpretation of Fermat's Last Theorem
- Why is $S_5$ generated by any combination of a transposition and a 5-cycle?
- $\sum_{k=0}^n \binom{n}{k}^2 = \binom{2n}{n}?$
- How many $N$ digits binary numbers can be formed where $0$ is not repeated
- How find this sum $ \frac{1}{1999}\binom{1999}{0}-\frac{1}{1998}\binom{1998}{1}+\cdots-\frac{1}{1000}\binom{1000}{999}$
- Fibonacci combinatorial identity: $F_{2n} = {n \choose 0} F_0 + {n\choose 1} F_1 + … {n\choose n} F_n$

Count how many are there triples $(T,e,x)$ where $T$ is a tree on $\{1,2,\dots,n\}$, $e$ is an edge of $T$ and $x$ is a vertex of $T$.

**Way 1**: $n^{n-2} n (n-1)$ by Cayley’s formula.

**Way 2**:

The edge $e$ splits the tree into two parts, left $L$ and right $R$. We will say $R$ is the one that contains $x$.

First, select two endpoints of $e$: $a \in L$ and $b \in R$, this can be done in $n(n-1)$ ways.

Let $r$ be the cardinality of $R$. Select which of $r$ numbers in $\{1,2,\dots,n\}$ belong to $R$. We already committed to $a \in L$ and $b \in R$; this means $n-2 \choose r-1$.

There are $r$ ways to choose $x$, $r^{r-2}$ ways to choose $R$ and $(n-r)^{n-r-2}$ ways to choose $L$.

Therefore

$n^{n-2} n(n-1) = n(n-1) \sum_{r=1}^{n-1} {n-2 \choose r-1} r \cdot r^{r-2} (n-r)^{n-r-2}$ QED

Suppose we are trying to show that

$$\sum_{r=1}^{n-1} {n-2\choose r-1}

r^{r-1} (n-r)^{n-r-2} = n^{n-2}$$

where $n\ge 2.$

Looking to the combinatorial proof for inspiration we present the

*labelled tree function* $T(z)$ with functional equation

$$\mathcal{T} = \mathcal{Z} \times \mathfrak{P}(\mathcal{T})

\quad\text{or}\quad

T(z) = z \exp T(z)$$

which counts the number of labelled rooted trees on $n$ nodes so that

$$n! [z^n] T(z) = n^{n-1}.$$

We now re-write the equation to better match the tree function.

Start with

$$\sum_{r=0}^{n-2} {n-2\choose r}

(r+1)^r (n-r-1)^{n-r-3} = n^{n-2}$$

and continue with

$$\sum_{r=0}^{n} {n\choose r}

(r+1)^r (n+1-r)^{n-r-1} = (n+2)^n.$$

Observe that when we multiply two exponential generating functions of

the sequences $\{a_n\}$ and $\{b_n\}$ we get that

$$ A(z) B(z) = \sum_{n\ge 0} a_n \frac{z^n}{n!}

\sum_{n\ge 0} b_n \frac{z^n}{n!}

= \sum_{n\ge 0}

\sum_{k=0}^n \frac{1}{k!}\frac{1}{(n-k)!} a_k b_{n-k} z^n\\

= \sum_{n\ge 0}

\sum_{k=0}^n \frac{n!}{k!(n-k)!} a_k b_{n-k} \frac{z^n}{n!}

= \sum_{n\ge 0}

\left(\sum_{k=0}^n {n\choose k} a_k b_{n-k}\right)\frac{z^n}{n!}$$

i.e. the product of the two generating functions is the generating

function of $$\sum_{k=0}^n {n\choose k} a_k b_{n-k}.$$

In the present case we have $$A(z) = T'(z)$$ by inspection.

Note also that

$$T(z) = \sum_{n\ge 1} n\times n^{n-2} \frac{z^n}{n!}

= \sum_{n\ge 1} n^{n-2} \frac{z^n}{(n-1)!}

= z \sum_{n\ge 1} n^{n-2} \frac{z^{n-1}}{(n-1)!}.$$

It follows that

$$B(z) = \sum_{n\ge 0} (n+1)^{n-1} \frac{z^{n}}{n!}

= \frac{1}{z} T(z).$$

We thus obtain that

$$A(z) B(z) = \frac{1}{z} T(z) T'(z).$$

Observe that when we differentiate the functional equation we obtain

$$T'(z) = \exp T(z) + z \exp T(z) \times T'(z)

= \frac{1}{z} T(z) + T(z) \times T'(z)$$

and hence

$$T'(z) = \frac{1}{z} \frac{T(z)}{1-T(z)}.$$

This yields

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

Now to extract coefficients from this we have

$$n! [z^n] A(z) B(z)

= \frac{n!}{2\pi i}

\int_{|z|=\epsilon} \frac{1}{z^{n+1}}

\frac{1}{z^2} \frac{T^2(z)}{1-T(z)} \; dz

\\ = \frac{n!}{2\pi i}

\int_{|z|=\epsilon} \frac{1}{z^{n+3}}

\frac{T^2(z)}{1-T(z)} \; dz.$$

Using a type of Lagrange inversion and putting $w=T(z)$ we get from

the functional equation

$w = z \exp w$ or $z = w \exp(-w)$ and hence

$dz = (\exp(-w) – w\exp(-w)) \; dw$

or $dz = \exp(-w) ( 1 – w ) \; dw,$

yielding for the integral

$$\frac{n!}{2\pi i}

\int_{|w|=\epsilon} \frac{\exp(w(n+3))}{w^{n+3}}

\frac{w^2}{1-w} \exp(-w)(1-w) \; dw

\\ = \frac{n!}{2\pi i}

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

Extracting the residue we find

$$n! \times \frac{(n+2)^{n}}{n!}

= (n+2)^n$$

as claimed, QED.

- Equivalence of Brouwers fixed point theorem and Sperner's lemma
- How to calculate the coordinates of orthocentre.!!
- Infinite Product computation
- Image of the Euler phi function
- $A$ is skew hermitian, prove $(I-A)^{-1} (I+A)$ is unitary
- Matrices (Hermitian and Unitary)
- Definite integrals with interesting results
- If $f\circ g$ is continuous and $g$ is continuous what about $f$?
- Example of an infinite group where every element except identity has order 2
- “$n$ is even iff $n^2$ is even” and other simple statements to teach proof-writing
- Union of $2$ set $A, B$ where $ A$ is a subset of $B$
- How many ways are there to color vertexes of a $n\times n$ square that in every $1\times 1$ squares we should have $2$ blue and $2$ red vertexes?
- On the existentence of an element of a group whose order is the LCM of orders of given two elements which are commutaive
- Express Integer as Sum of Four Squares
- Topological spaces as model-theoretic structures — definitions?