Intereting Posts

Explicitly proving invariance of curvatures under isometry
On the greatest norm element of weakly compact set
Find a plane that passes through a point and is perpendicular to 2 planes
Power series representation/calculation
Sharper Lower Bounds for Binomial/Chernoff Tails
Must a Hermitian/Kähler Manifold have a complex structure?
Derive recursion formula for an integral
Intuitive explanation for integration
Proving inequality $\sqrt{\frac{2a}{b+c}}+\sqrt{\frac{2b}{c+a}}+\sqrt{\frac{2c}{a+b}} \leq \sqrt{3 \left(\frac{a}{b}+\frac{b}{c}+\frac{c}{a}\right)}$
Lattice Walk on Diagonally Overlapping Square Lattices
please solve a 2013 th derivative question?
Can't find the demonstration of a theorem about recursion
Choose a random number between 0 and 1 and record its value. Keep doing it until the sum of the numbers exceeds 1. How many tries do we have to do?
An example that the supremum of a family of measurable functions need not to be measurable.
Is following contradictory? Can you give an example?

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!$$

- Find the number of permutations in $S_n$ containing fixed elements in one cycle
- Smallest integer $k$ so that no Sudoku grid has exactly $k$ solutions
- $m$ balls into $n$ urns
- Product of binomial coefficient as a basis
- Distributing $k$ objects in $n$ containers - Probability distribution for Combinatorial problems
- How many arrangements of MATHEMATICS are there in which each consonant is adjacent to a vowel?

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

- A strange combinatorial identity: $\sum\limits_{j=1}^k(-1)^{k-j}j^k\binom{k}{j}=k!$
- Coloring 5 Largest Numbers in Each Row and Column Yields at Least 25 Double-Colored Numbers
- Triples of positive integers $a,b,c$ with rational $\sqrt{\frac{c-a}{c+b}},\sqrt{\frac{c+a}{c-b}}$
- How to show that $\gcd(ab,n)=1$?
- Find a solution: $3(x^2+y^2+z^2)=10(xy+yz+zx)$
- Conditions under which $a+b+c$ divides $1-abc$
- Social Golfer Problem - Quintets
- Proof related to Fibonacci sequence
- How many different ways can the signs be chosen so that $\pm 1\pm 2\pm 3 … \pm (n-1) \pm n = n+1$?
- Integer solutions of $xy+9(x+y)=2006$

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.

- A tensor calculus problem
- Find the limit $\displaystyle\lim_{n\rightarrow\infty}{(1+1/n)^{n^2}e^{-n}}$?
- Find the least number b for divisibility
- 3D Perspective projection
- Prove that $(0,1) \subseteq\mathbb R$ and $(4,10) \subseteq\mathbb R$ have the same cardinality.
- matrix representations and polynomials
- If $f(\frac{x+y}{2})=\frac{f(x)+f(y)}{2}$, then find $f(2)$
- Generating functions of partition numbers
- Need a hint to evaluate $\lim_{x \to 0} {\sin(x)+\sin(3x)+\sin(5x) \over \tan(2x)+\tan(4x)+\tan(6x)}$
- How many cycles, $C_{4}$, does the graph $Q_{n}$ contain?
- ∅ ⊆ { ∅ } Is this true or false?
- Can different tetrations have the same value?
- Define $L(A) = A^T,$ for $A \in M_n(\mathbb{C}).$ Prove $L$ is diagonalizable and find eigenvalues
- Why do we categorize all other (iso.) singularities as “essential”?
- Iterated Integrals – “Counterexample” to Fubini's Theorem