Intereting Posts

Maps – question about $f(A \cup B)=f(A) \cup f(B)$ and $ f(A \cap B)=f(A) \cap f(B)$
Is the unit circle $S^1$ a retract of $\mathbb{R}^2$?
Why, historically, do we multiply matrices as we do?
Is formal truth in mathematical logic a generalization of everyday, intuitive truth?
Prove that $A=B$ considering: $(A \cap C = B \cap C) \land (A \cup C = B \cup C)$
What is the shortest string that contains all permutations of an alphabet?
How do I count the subsets of a set whose number of elements is divisible by 3? 4?
Does the Frattini subgroup $\Phi(G)$ contain the intersection $Z(G)\cap $.
How do we identify $\mathfrak{R}$-automorphisms of a group?
Invertibility of $BA$
Mathematical expression to form a vector from diagonal elements
Number of subfields of finite field
Change of basis
Existence of $\{\omega, \omega+1,…\}$ via the axiom of replacement
Counting the number of 4 letter words that can be made from a given multiset of 11 letters

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

- Is $\sqrt{x^2}=|x|$ or $=x$? Isn't $(x^2)^\frac12=x?$
- Continued fraction for $\tan(nx)$
- If this is a telescoping series then how does it collapse? $\frac{3r+1}{r(r-1)(r+1)}$
- What are the Laws of Rational Exponents?
- About finding the period of a function which satisfies $f(x-2)+f(x+2)=f(x)$.
- Filling the gap in knowledge of algebra

- Show that $a^x+b^x+c^x>(a+b+c)^x$ for all $a,b,c>0$ and $0<x<1$
- Partitioning Integers into Equal Sets to Guarantee Arithmetic Progression
- If there are 200 students in the library, how many ways are there for them to be split among the floors of the library if there are 6 floors?
- How to simplify $\frac{\sqrt{4+h}-2}{h}$
- what is the best book for Pre-Calculus?
- A Curious Binomial Sum Identity without Calculus of Finite Differences
- About rationalizing expressions
- 6-letter permutations in MISSISSIPPI
- Sum of a Hyper-geometric series. (NBHM 2011)
- Not lifting your pen on the $n\times n$ grid

**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.

- Nilradical of polynomial ring
- A convex subset of a Hilbert space
- $f:\mathbb R\to\mathbb R$ continuous function. Which of the following sets can not be image of $(0,1]$ under $f$?
- $\lim_{n\rightarrow \infty}\int_0^1f_nhdm=\int_0^1fhdm$, prove $f\in L^p(m)$ , where $1\le p<\infty$.
- Does taking the direct limit of chain complexes commute with taking homology?
- Showing that a CCC with a zero object is the trivial category
- Prove $\det(kA)=k^n\det A$
- Dirac $\delta\left( \left^2 -k^2-m^2 \right)$
- Chance of selecting the last k pages in correct order from a set of n pages
- Prove any orthogonal 2-by-2 can be written in one of these forms…
- What sort of algebraic structure describes the “tensor algebra” of tensors of mixed variance in differential geometry?
- Simply formulated but very hard problem about certain polynomial
- Another chain of six circles
- Uniform boundedness principle for norm convergence
- Bounds on the gaps in a variant of polylog-smooth numbers.