Intereting Posts

Solution of Differential equation $\frac{xdx-ydy}{xdy-ydx} = \sqrt{\frac{1+x^2-y^2}{x^2-y^2}}$
How to derive the formula for the sum of the first $n$ perfect squares?
Finding all the numbers that fit $x! + y! = z!$
$R/M$ is a division ring
Last few digits of $n^{n^{n^{\cdot^{\cdot^{\cdot^n}}}}}$
Why do bell curves appear everywhere?
A group of order 30 has a normal 5-Sylow subgroup.
Solving a sum of exponentials
Finding the closed form for a sequence
Proving $\sum_{k=0}^n\binom{2n}{2k} = 2^{2n-1}$
Demonstrate another way to solve the Inclusionâ€“exclusion principle?
$|\mathbb{Q}(e^{2\pi i/n}) : \mathbb{Q}(\cos(2\pi/n)| = 1 \text{ or } 2$
If $f'$ tends to a positive limit as $x$ approaches infinity, then $f$ approaches infinity
If $p,q$ are prime, solve $p^3-q^5=(p+q)^2$.
Determining a limit of parametrized, recursively defined sequence $a_{n+1}=1+\frac{(a_n-1)^2}{17}$

Given the set $N:=\{1,\cdots,n\}$, let $\pi$ be a permutation on $N$. We say $i \in \{1,\cdots,n\}$ is fixed by $g$ iff $\pi(i)=i.$

Denote the set of all permuations on $N$ by $S_n$.

Define $f :~N \cup \{0\} \to \mathbb{N}_{\geq 0}$ by

$f(m):=$The number of permutations in $S_n$ which has exactly $m$ fixed points.

Prove that $$\sum_{m=0}^{n} f(m) m^2=2n!$$

- How to justify unicyclic connected graphs formula?
- Number of Unique Sequences with Circular Shifts
- Show that the number or $r$ combinations of $X$ which contain no consecutive integers is given by $\binom{n-r+1}{r}$
- How many matrices in $M_n(\mathbb{F}_q)$ are nilpotent?
- How can I prove the formula for calculating successive entries in a given row of Pascal's triangle?
- Closed form for $\sum_{n=1}^\infty\frac{\psi(n+\frac{5}{4})}{(1+2n)(1+4n)^2}$

Remark: It seems $f(0)$ plays an prominent role.

- Do there exist two primes $p<q$ such that $p^n-1\mid q^n-1$ for infinitely many $n$?
- Reference for combinatorial game theory.
- How to algebraically prove $\binom{n+m}{2} = nm + \binom{n}{2} + \binom{m}{2}$?
- Multiples of an irrational number forming a dense subset
- Number of ways to connect sets of $k$ dots in a perfect $n$-gon
- Dissecting an equilateral triangle into equilateral triangles of pairwise different sizes
- Show that for any prime $ p $, there are integers $ x $ and $ y $ such that $ p|(x^{2} + y^{2} + 1) $.
- Solve $3x^2-y^2=2$ for Integers
- How many ways are there to divide $100$ different balls into $5$ different boxes so the last $2$ boxes contains even number of balls?
- Probability question about married couples

This solution isn’t fully combinatorial, but I think it works:

The sum we want is the number of permutations with an ordered pair $(i,j)$ such that the permutation is fixed at both $i$ and $j$. We can see this by noting that for a permutation with $m$ fixed points, we have $m^2$ choices of an ordered pair.

Now, to evaluate this number, we first choose an ordered pair. If $i \ne j$, there are $n^2-n$ choices of ordered pair and $(n-2)!$ choices of permutations. If $i = j$, there are $n$ choices of ordered pair and $(n-1)!$ choices of permutation, giving us a final answer of $(n^2-n)(n-2)! + n(n-1)! = 2n!.$

This is another question that can be addressed using the symbolic method, as seen

here. While this is not necessarily the simplest solution it does produce explicit forms of all generating functions and makes the problem amenable to automatic combinatorics, a powerful method developed by Chyzak, Salvy and Flajolet.

Permutations are sets of cycles, having combinatorial class specification

$\mathfrak P(\mathfrak C(\mathfrak Z))$. Hence the corresponding exponential generating function (EGF) is $$ \exp \log \frac{1}{1-z} = \frac{1}{1-z},$$ where $$ \log \frac{1}{1-z} $$ is the EGF of labelled cycles. (These two are easily verified as there are $n!$ permutations and $n!/n$ cycles.)

If we want to count the number of fixed points we need to mark each fixed point with a new variable, $u$, which gives the class specification $\mathfrak P(\mathfrak C(\mathcal Z) -\mathcal Z + \mathcal U \mathcal Z )$. and the mixed generating function

$$G(z, u) = \exp \left( \log \frac{1}{1-z} -z + uz \right)

= \frac{1}{1-z} e^{-z} e^{uz}. $$

A term $u^m z^n/n!$ in $G(z, u)$ represents a permutation of length $n$ with $m$ fixed points. We seek to multiply this term by $m^2$. Hence we differentiate with respect to $u$, multiply by $u$, differentiate by $u$ again and finally multiply by $u$ one more time, obtaining

$$ H(z, u) =

\frac{1}{1-u} u \left( \frac{d}{du} \left( u \frac{d}{du} G(z, u) \right)\right) =

\frac{1}{1-u} \frac{1}{1-z} e^{-z} (uz + u^2z^2) e^{uz}.$$

The factor $\frac{1}{1-u}$, when it occurs in a product with another formal power series in $u$, will produce the series for the sums of the first $n$ elements. It is included here to build a generating function for the sum, so that

$$ n! [u^n][z^n] H(z, u) = \sum_{m=0}^n f(m, n) m^2.$$

The differentiate-and-multiply is known as a so-called marking operation in symbolic combinatorics.

It remains to extract coefficients.

We have $$

\begin{align} & [z^n] \frac{1}{1-u} \frac{1}{1-z} e^{-z} \, uz \, e^{uz} =

\frac{u}{1-u} [z^{n-1}] \frac{1}{1-z} e^{(u-1)z} \\

&= \frac{u}{1-u} \sum_{k=0}^{n-1} [z^k] e^{(u-1)z}

= \frac{u}{1-u} \sum_{k=0}^{n-1} \frac{(u-1)^k}{k!} \\

&= u \left( \frac{1}{1-u} – \sum_{k=1}^{n-1} \frac{(u-1)^{k-1}}{k!}\right)

\end{align}$$

Similarly, $$

\begin{align} & [z^n] \frac{1}{1-u} \frac{1}{1-z} e^{-z} \, u^2z^2 \, e^{uz} =

\frac{u^2}{1-u} [z^{n-2}] \frac{1}{1-z} e^{(u-1)z} \\

&= \frac{u^2}{1-u} \sum_{k=0}^{n-2} [z^k] e^{(u-1)z}

= \frac{u^2}{1-u} \sum_{k=0}^{n-2} \frac{(u-1)^k}{k!} \\

&= u^2 \left( \frac{1}{1-u} – \sum_{k=1}^{n-2} \frac{(u-1)^{k-1}}{k!}\right)

\end{align}$$

It follows that

$$ n! H(z, u) = n! [u^n]

\left( u \left( \frac{1}{1-u} – \sum_{k=1}^{n-1} \frac{(u-1)^{k-1}}{k!} \right)

+ u^2 \left( \frac{1}{1-u} – \sum_{k=1}^{n-2} \frac{(u-1)^{k-1}}{k!}\right)\right)$$

which yields

$$n! \, [u^n] \left( u \frac{1}{1-u} + u^2 \frac{1}{1-u} \right)= 2n!,$$

which was to be shown.

The beauty of this method is that it is algorithmic and can be implemented in computer algebra systems as in the package mentioned above. It is actually possible to have a program calculate all the generating functions that we have seen using only the specification of the combinatorial class.

There is much more on this method at Wikipedia.

- Elementary proof of topological invariance of dimension using Brouwer's fixed point and invariance of domain theorems?
- Calculating the probability of a coin falling on its side
- Proof: A loop is null homotopic iff it can be extended to a function of the disk
- Why the zeta function?
- Proving if $\limsup x_n = \liminf x_n = c$, then $x_n \rightarrow c, n \rightarrow \infty$ using $\epsilon$
- How does Molien series describe polynomial invariants?
- Uniform convergence and differentiation proof of remark 7.17 in Rudin's mathematical analysis
- Showing that a collection of sets is a $\sigma$-algebra: either set or complement is countable
- probability of three random points inside a circle forming a right angle triangle
- Absolute value in trigonometric substitutions
- Determinant of a special $0$-$1$ matrix
- area of figure in sector of intersecting circles
- Prove that there is no integer a for which $a^2 – 3a – 19$ is divisible by 289
- Complement of a set and inverse image.
- Prove Taylor expansion with mean value theorem