Proving that $\sum_{i=0}^{n}\binom{n}{i}i^{n-i}(n-i)^{i}\le\frac{1}{2}n^n$ How can we prove that
$$\displaystyle\sum_{i=0}^{n}\binom{n}{i}i^{n-i}(n-i)^{i}\le\dfrac{1}{2}n^n$$
where $\displaystyle\binom{n}{i}=\dfrac{n!}{i!(n-i)!}$.
This inequality is very interesting. I think this problem has nice methods, but my method is very ugly.
 A: Since the full result has not yet been shown, I post this.
Here is a proof that
$$
\limsup_{n\to\infty}\frac1{n^n}\sum_{k=0}^n\binom{n}{k}k^{n-k}(n-k)^k\le\frac12\tag{1}
$$
Using the bound
$$
\binom{n}{k}\le\frac1{\sqrt{2\pi}}\frac{n^{n+1/2}}{k^{k+1/2}(n-k)^{n-k+1/2}}\tag{2}
$$
we get
$$
\begin{align}
&\frac1{n^n}\sum_{k=0}^n\binom{n}{k}k^{n-k}(n-k)^k\\
&\le\frac1{\sqrt{2\pi}}\sum_{k=0}^n\sqrt{\frac{n\vphantom{k}}{k(n-k)}}\left(\frac{k}{n-k}\right)^{n-2k}\\
&=\frac1{\sqrt{2\pi}}\sum_{k=-n/2}^{n/2}\sqrt{\frac{4n^2}{n^2-4k^2}}\left(\frac{n+2k}{n-2k}\right)^{-2k}\frac1{\sqrt{n}}\tag{$k\mapsto k+n/2$}\\
&=\frac1{\sqrt{2\pi}}\sum_{k=-n/2}^{n/2}\frac2{\sqrt{1-4k^2/n^2}}\left(\frac{1+2k/n}{1-2k/n}\right)^{-2k}\frac1{\sqrt{n}}\tag{3}
\end{align}
$$
The sum on the right hand side of $(3)$ is a Riemann Sum ($x=k/\sqrt{n}$) for
$$
\frac1{\sqrt{2\pi}}\int_{-\infty}^\infty 2\,e^{-8x^2}\,\mathrm{d}x=\frac12\tag{4}
$$

Towards a full solution
Since we are using $x=k/\sqrt{n}$, we have that $(3)$ approximates
$$
\frac1{\sqrt{2\pi}}\int_{-\sqrt{n}/2}^{\sqrt{n}/2}\frac2{\sqrt{1-4x^2/n}}\left(\frac{1+2x/\sqrt{n}}{1-2x/\sqrt{n}}\right)^{-2x\sqrt{n}}\,\mathrm{d}x\tag{5}
$$
As $n$ increases to $\infty$, $\displaystyle\frac2{\sqrt{1-4x^2/n}}$ increases to $2$ and $\displaystyle\left(\frac{1+2x/\sqrt{n}}{1-2x/\sqrt{n}}\right)^{-2x\sqrt{n}}$ increases to $e^{-8x^2}$. Thus, it is not unreasonable to infer that $(3)$ increases to $\frac12$,

Abel's Identity
As i707107 mentions, Abel's identity is very useful here. In fact,
$$
\begin{align}
&\sum_{k=0}^n\binom{n}{k}(a+tk)^{k-1}(b-tk)^{n-k}\\
&=\sum_{k=0}^n\sum_{j=0}^{n-k}\binom{n}{k}(a+tk)^{k-1}\binom{n-k}{j}(-1)^{n-k-j}(a+b)^j(a+tk)^{n-k-j}\\
&=\sum_{k=0}^n\sum_{j=0}^{n-k}\binom{n}{n-k}\binom{n-k}{j}(a+tk)^{n-j-1}(-1)^{n-k-j}(a+b)^j\\
&=\sum_{j=0}^n\sum_{k=0}^{n-j}\binom{n}{j}\binom{n-j}{k}(a+tk)^{n-j-1}(-1)^{n-k-j}(a+b)^j\\[6pt]
&=a^{-1}(a+b)^n\tag{6}
\end{align}
$$
where the last equality is because for $j\lt n$, the sum in $k$ is an $n-j$ repeated difference of an $n-j-1$ degree polynomial in $k$, hence $0$, and for $j=n$, the sum in $k$ is a single term.
Set $a=n$, $b=0$, and $t=-1$ in $(6)$ to get
$$
\sum_{k=0}^n\binom{n}{k}(n-k)^{k-1}k^{n-k}=n^{n-1}\tag{7}
$$
The inequality is true for $n=1$, i.e. $0\le\frac12$, but false for $n=0$. Let's assume that $n\ge2$ so that we can leave out the $k=0$ and $k=n$ terms of Abel's identity since they are $0$.
Then
$$
\begin{align}
&\sum_{k=0}^n\binom{n}{k}(n-k)^kk^{n-k}\\
&=\sum_{k=1}^{n-1}\binom{n}{k}(n-k)^kk^{n-k}\\
&=\sum_{k=1}^{n-1}\binom{n}{k}(n-k)^{k-1}(n-k)k^{n-k}\\
&=n\sum_{k=1}^{n-1}\binom{n}{k}(n-k)^{k-1}k^{n-k}
-\sum_{k=1}^{n-1}\binom{n}{k}(n-k)^kk^{n-k}\frac{k}{n-k}\\
&=n\sum_{k=1}^{n-1}\binom{n}{k}(n-k)^{k-1}k^{n-k}
-\sum_{k=1}^{n-1}\binom{n}{k}(n-k)^kk^{n-k}\frac{n-k}{k}\\
&=n^n-\sum_{k=1}^{n-1}\binom{n}{k}(n-k)^kk^{n-k}\frac12\left(\frac{k}{n-k}+\frac{n-k}{k}\right)\\
&\le n^n-\sum_{k=1}^{n-1}\binom{n}{k}(n-k)^kk^{n-k}\\
&=n^n-\sum_{k=0}^n\binom{n}{k}(n-k)^kk^{n-k}\tag{8}
\end{align}
$$
The last inequality is because $\frac12\left(x+\frac1x\right)\ge1$ for $x\gt0$.
Adding the left side of $(8)$ to both sides and dividing by $2$ yields
$$
\sum_{k=0}^n\binom{n}{k}(n-k)^kk^{n-k}\le\frac12n^n\tag{9}
$$
A: One can use Abel's identity: 
How to prove $\sum\limits_{k=0}^n{n \choose k}(k-1)^k(n-k+1)^{n-k-1}= n^n$?
Abel's identity is:
$$\sum_k\binom{n}{k}(k+s-n)^{k}(r+n-k)^{n-k-1}=\frac{(r+s)^n}{r}$$
We use this with $s=0$ and $r=-n$, we have
$$\sum_k\binom{n}{k}(k-n)^k(-k)^{n-k-1}=\frac{(-n)^n}{-n}$$
It follows that 
$$\sum_k\binom{n}{k}(n-k)^kk^{n-k}\frac{n}{k}=n^n$$
Substitution $k$->$n-k$ gives 
$$\sum_k\binom{n}{k}(n-k)^kk^{n-k}\frac{n}{n-k}=n^n$$
On the other hand, 
$\frac{n}{k}+\frac{n}{n-k}=\frac{n^2}{(n-k)k}\geq 4$ for $1\leq k\leq n-1$. 
Hence 
$$4\sum_k\binom{n}{k}(n-k)^kk^{n-k}\leq \sum_k\binom{n}{k}(n-k)^kk^{n-k}\left(\frac{n}{k}+\frac{n}{n-k}\right)=2n^n.$$
A: I was hoping that by interpreting the left-hand side as an enumeration problem, there would be a relatively simple combinatorial proof.  So far this hasn't panned out.  I had thought it possible to obtain a strong partial result, but this turned out to be mistaken.  (See below.)  Perhaps someone can figure out how to turn these ideas into something that acually works.
The left-hand side of the OP's inequality can be interpreted as the enumeration of what I have called "balanced sequences".  If anyone knows the proper name for these, please let me know.  Let $\Sigma$ equal $\{1,2,\ldots,n\}^n,$ that is, the set of sequences of length $n$ of numbers from the set $\{1,2,\ldots,n\}.$  For $r\in\mathbf{Z}$ we say that $\sigma\in\Sigma$ is $r$-balanced if the number of elements greater than $r$ in $\sigma$ equals $r.$  You can see that there are no $0$-balanced or $n$-balanced sequences.  Some examples: if $n=4,$ then the sequences $2111,$ $1211,$ $1114$ are $1$-balanced; the sequences $2234,$ $4321,$ $4411$ are $2$-balanced; the sequences $1444$ and $4443$ are $3$-balanced.  Define a sequence to be balanced if it is $r$-balanced for some $r,$ and unbalanced otherwise.
In general, the number of $r$-balanced sequences is
$$\binom{n}{r}r^{n-r}(n-r)^r$$
since there are $\binom{n}{r}$ ways to choose the positions for the low elements in the sequence, $r^{n-r}$ ways of assigning low elements to those positions, and $(n-r)^r$ ways of assigning high elements to the remaining positions.  (Here "low" means less than or equal to $r;$ "high" means greater than $r.)$
Observe that if $\sigma$ is both $r$-balanced and $s$-balanced, then $r=s$.  For if $s<r,$ then $\sigma$  has $r$ elements greater than $r,$ which means that it has at least $r$ elements greater than $s.$  This contradicts that $\sigma$ has exactly $s$ elements greater than $s.$  Since a balanced sequence is therefore $r$-balanced for exactly one $r,$ the number of balanced sequences is
$$\sum_{r=0}^n\binom{n}{r}r^{n-r}(n-r)^r,$$
which must therefore be less than or equal to $\lvert\Sigma\rvert=n^n.$
To obtain the factor $1/2$ on the right, it would suffice to find an injective map from the set of balanced sequences to the set of unbalanced sequences.  Unfortunately, I have been unable to devise such a map.  robjohn's result shows that this may be delicate: as $n$ approaches infinity, $\Sigma$ will be roughly evenly split between balanced and unbalanced sequences.
Some incorrect material here: I had thought there was a simple argument leading to the   inequality
$$\sum_{r=0}^n\binom{n}{r}r^{n-r}(n-r)^r\le n^n-(n-1)^n=[1-(1-1/n)^n]n^n.$$
For large $n,$ the right-hand side is approximately $(1-1/e)n^n\approx 0.632n^n.$  Unfortunately, the argument was flawed.  I quote it here for future reference.

One gets a partial result as follows.  Let $\Sigma_-=\{1,2,\ldots,n-1\}^n.$  Define the right translates of $\sigma\in\Sigma_-$ to be the sequences in $\Sigma$ of the form $\sigma+c,$ where $c\ge1$ and $\sigma+c$ is the sequence obtained from $\sigma$ by adding $c$ to every one of its elements.  Clearly we must have $c\le c_\max=n-\max(\sigma).$
It is not hard to see that right translates of a balanced sequence are unbalanced.  It then follows that $\Sigma$ contains at least $(n-1)^n$ unbalanced sequences.  For every sequence $\sigma\in\Sigma_-$ is either unbalanced, or has a right translate $\sigma+c_\max$ in $\Sigma\setminus\Sigma_-$ that is unbalanced.  (The map that takes a balanced sequence in $\Sigma_-$ to its maximal right translate in $\Sigma\setminus\Sigma_-$ is invertible - merely translate leftward until the sequence becomes balanced.)  This proves that there are at most $n^n-(n-1)^n$ balanced sequences.

The flaw is that right translates of balanced sequences are not necessarily unbalanced.  A simple example is $1133$ and its right translate $2244,$ both of which are $2$-balanced.  I guess I was misled by the examination of many $r$-balanced sequences $\sigma\in\Sigma_-$ with the property that $r$ was an element of $\sigma.$  In this case, one can prove that $\sigma+1$ is unbalanced as follows.  Let $\rho_j(\sigma)$ be the number of elements of $\sigma$ that are greater than $j.$  If the table of values $\rho_l(\sigma)$ looks like
$$\begin{array}{c|cccccccccc} j & 0 & 1 & 2 & \ldots & r-1 & r & r+1 & \ldots & n-1 & n\\ \hline\rho_j(\sigma) & n & a_1 & a_2 & \ldots & a_{r-1} & r & a_{r+1} & \ldots & 0 & 0                                                                                                     \end{array},$$
then the corresponding table for $\rho_j(\sigma+1)$ looks like
$$\begin{array}{c|ccccccccccc} j & 0 & 1 & 2 & \ldots & r-1 & r & r+1 & \ldots & n-1 & n\\ \hline\rho_j(\sigma+1) & n & n & a_1 & \ldots & a_{r-2} & a_{r-1} & r & \ldots & a_{n-2} & 0                                                                                                    \end{array}.$$
The sequence $a_1,a_2,\ldots,a_{n-2}$ is nonincreasing, and, since $r$ is an element of $\sigma,$ we have $a_{r-1}>r$.  Therefore $\sigma+1$ is unbalanced.  This argument does not work if $r$ is not an element of $\sigma$ since then $a_{r-1}=r.$  It also fails for $\sigma+c$ with $c>1.$
A: This was Question 10 from the 2009 Sydney University Mathematics Society (SUMS) problem solving competition, see here. A combinatorial solution interpreting the problem in terms of trees can be found in the last section of the solutions here.
