Intereting Posts

Dividing the linear congruence equations
Order of $\mathrm{GL}_n(\mathbb F_p)$ for $p$ prime
Euclidean Geometry Intersection of Circles
Greatest prime factor of $n$ is less than square root of $n$, proof
Question about a problem on the argument principle
How to prove $\lim_{x\to \infty} {x \over \sin(x) + x} = 1$?
If $ f(x) = \frac{\sin^2 x+\sin x-1}{\sin^2 x-\sin x+2},$ then value of $f(x)$ lies in the interval
Are there any decompositions of a symmetric matrix that allow for the inversion of any submatrix?
How many matrices in $M_n(\mathbb{F}_q)$ are nilpotent?
Open Sets Boundary question
Intermediate fields between $\mathbb{Z}_2 (\sqrt{x},\sqrt{y})$ and $\mathbb{Z}_2 (x,y)$
basis for hermitian matrices
Combinatorics – How many numbers between 1 and 10000 are not squared or cubed?
The set of all sets of the universe?
Minimal polynomial of an algebraic number expressed in terms of another algebraic number

I’m trying to find the closed form for the following formula

$$\sum_{i=0}^n {n \choose i} D(i)$$

where $D(i)$ is the number of derangement for $i$ elements. A derangement is a permutation in which none of the objects appear in their “natural” (i.e., ordered) place. For example, the only derangements of $\{1,2,3\}$ are $\{2,3,1\}$ and $\{3,1,2\}$, so $!3=2$.

- Proving Nicomachus's theorem without induction
- On an expansion of $(1+a+a^2+\cdots+a^n)^2$
- If $\frac{1}{a}+\frac{1}{b}+\frac{1}{c}=\frac{1}{a+b+c}$ then $\frac{1}{a^5}+\frac{1}{b^5}+\frac{1}{c^5}=\frac{1}{a^5+b^5+c^5}.$
- Finding range of $\frac{x}{(1-x)^2}$
- Calculation of $\sum_{m=1}^{\infty}\sum_{n=1}^{\infty}\frac{m^2n}{3^n\left(m\cdot 3^n+n\cdot 3^m\right)}$
- Prove that the expression is a perfect square

- Determine the exact value of equations involving more two trig variables
- Is there a memorable solution to Kirkman's School Girl Problem?
- Solving the complex polynomial
- Solving $x\; \leq \; \sqrt{20\; -\; x}$
- Prove nth root of n! is less than n+1 th root of ((n+1) !): $\sqrt{n!}\lt \sqrt{(n+1)!}$?
- Generalisation of alternating functions
- Combinatorial proof of a Stirling number identity.
- Arrangement of word MISSISSIPPI in which no three S occur together
- Uses of the incidence matrix of a graph
- Closed form for $\sum_{k=0}^{n} \binom{n}{k}\frac{(-1)^k}{(k+1)^2}$

**Hint:** Any permutation on $[n]$ splits $[n]$ in to two sets of points: the set of points which are fixed, and the set of points which are not. To count the number of permutations with $i$ points not fixed and $n-i$ fixed, you would choose which $i$ points are going to be permuted; fix the other points; and put any permutation on the permuted points which has no fixed points. (That last bit sounds like a derangement of $i$ elements!)

For the sake of completeness we present an algebraic proof. 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}.$$

Now derangements are represented by the combinatorial species $\mathcal{D}$ with specification

$$\mathcal{D} =

\mathfrak{P}(\mathfrak{C}_2(\mathcal{Z})+\mathfrak{C}_3(\mathcal{Z})+

\mathfrak{C}_4(\mathcal{Z})+\cdots).$$

This means that they have exponential generating function

$$D(z) = \exp\left(\frac{z^2}{2}+\frac{z^3}{3}+\frac{z^4}{4}+\cdots\right)

= \exp\left(-z + \log\frac{1}{1-z}\right)

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

This is our $A(z)$ as described in the introduction. Our $B(z)$ is determined by the sum that we want to calculate to be the exponential generating function of the constant sequence with value one.

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

It follows that

$$ A(z) B(z) = \frac{1}{1-z}$$

and therefore the sum is

$$n! [z^n] A(z) B(z) = n![z^n] \frac{1}{1-z} = n!$$

which is the closed form that we were trying to compute.

- multiplicative group of infinite fields
- Polar equation of a circle
- What is the minimal isoperimetric ratio of a polyhedron with $5$ vertices?
- Prime, followed by the cube of a prime, followed by the square of a prime. Other examples?
- Rolling dice such that they add up to 13 — is there a more elegant way to solve this type of problem?
- deriving formula for series?
- Assume that A is a subset of some underlying universal set U.
- Proof related to Harmonic Progression
- How to maximize (baking) surface area?
- Prove $e^x=1+\frac{1}{\sqrt{\pi }}{\int_0^x \frac{e^t \text{erf}\left(\sqrt{t}\right)}{\sqrt{x-t}} \, dt}$
- A formula for the roots of a solvable polynomial
- If $\left| f'(x) \right| \leq A |f(x)|^\beta $ then f is a constant function
- Congruence Class $_5$ (Equivalence class of n wrt congruence mod 5) when n = $-3$, 2, 3, 6
- Area of a parallelogram, vertices $(-1,-1), (4,1), (5,3), (10,5)$.
- A question on Jacobi sums