Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

Let $E(n)$ be the number of permutations $w\in S_n$ such that the least element of the set $Des(w)\cup \{n\}$ is even, where $Des(w)$ is the descent set of $w$. I need to find the exponential generating function $\sum_{n\geq 0}E(n)\dfrac{x^n}{n!}$.

However I have no idea how to do it! I tried to use the multiplication principle for exponential generating functions but I couldn't do much.

Any help would be appreciated. Thanks in advance!

share|improve this question
    
The solution to this problem can be found on the internet. Since this is homework I am not sure I can post the link here. If you calculate these values for small $n$ that would indicate that you have made an effort and help you find the resource with the answer. –  Marko Riedel Apr 5 '13 at 22:43
add comment

2 Answers

up vote 1 down vote accepted

Just to get the question clear: The descent set of a permutation $\pi$ is defined as the points where a descent occurs, namely $\operatorname{Des}(\pi) = \{i: \pi_i > \pi_{i+1}\}$.
The first descent in a permutation of size $n$ is defined as $F(\pi) = \min (\operatorname{Des}(\pi) \cup \{n\})$. (The union with $\{n\}$ is just to cover the case of the permutation with no descents, namely $(1, 2, \dots, n)$, for which define the first descent to be at the last position $n$.)
A "desarrangement" is defined as a permutation $\pi$ for which $F(\pi)$ is even.

We want to find the exponential generating function for $E_n$, the number of desarrangements of length $n$.

Method 1.
Prove that the number of desarrangements is the same as the number of derangements, via a bijection. As this is the approach Brian M. Scott alludes to in his answer, I will not elaborate on this further. (Besides, it requires you to know / derive the EGF of the number of derangements.)

Method 2.
We'll count the number of permutations $\pi$ of size $n$ that have $F(\pi) = 2k$, for each $k$.

To have $F(\pi) = 2k$, if $2k < n$, it means that the relative order of the first $2k+1$ elements is such that they are all ascents, except for a final descent at position $2k$. The probability (over uniform permutations of size $n$) that this happens is $\dfrac{2k}{(2k+1)!}$, as of the $(2k+1)!$ possible orderings of the first $(2k+1)$ elements, only $2k$ have this property. (Essentially, arrange all $(2k+1)$ of them in increasing order, and then move any of the first $2k$ non-maximum elements to the end.)

The other way in which we can have $F(\pi) = 2k$, per our definition is if $n = 2k$ and the permutation is $(1, 2, \dots, n)$.

So the number of permutations of size $n$ with $F(\pi)$ even is $$E_n = \sum_{0 \le 2k < n} n!\frac{2k}{(2k+1)!} + [n\text{ is even}]$$

The EGF is $$ \begin{align} E(z) = \sum_{n\ge 0} E_n \frac{z^n}{n!} &= \sum_{n\ge0}\sum_{0\le 2k < n} n!\frac{2k}{(2k+1)!} \frac{z^n}{n!} + \sum_{n \ge 0} [n\text{ is even}]\frac{z^n}{n!} \\ &= \sum_{k\ge 0}\left(\frac{2k}{(2k+1)!}\sum_{n>2k} z^n \right) + \frac{e^z + e^{-z}}2 \\ &= \sum_{k\ge 0}\left(\frac{2k}{(2k+1)!}\frac{z^{2k+1}}{1-z} \right) + \frac{e^z + e^{-z}}2 \\ &= \frac{1}{1-z}\sum_{k\ge 0}\left(\frac{2k}{(2k+1)!}z^{2k+1}\right) + \frac{e^z + e^{-z}}2 \\ \end{align} $$ Now to evaluate the sum above, we start with the known $$\frac{e^z - e^{-z}}{2} = \sum_{k\ge 0} \frac{z^{2k+1}}{(2k+1)!}$$ and differentiate it: $$\frac{e^z + e^{-z}}{2} = \sum_{k \ge 0} \frac{(2k+1)z^{2k}}{(2k+1)!}$$ so $$\begin{align} \sum_{k \ge 0} \frac{2k}{(2k+1)!} z^{2k+1} &= \frac{z(e^z + e^{-z})}{2} - \sum_{k \ge 0} \frac{z^{2k+1}}{(2k+1)!} \\ &= \frac{z(e^z + e^{-z})}{2} - \frac{e^{z} - e^{-z}}{2} \\ &= \frac{e^{z}(z-1) + e^{-z}(z+1)}{2} \end{align}$$ which makes our generating function $$ \begin{align} E(z) &= \frac{1}{1-z}\frac{e^{z}(z-1) + e^{-z}(z+1)}{2} + \frac{e^z + e^{-z}}2 \\ &= \frac{e^{-z}}{2}\left(\frac{z+1}{1-z} + 1\right) \\ &= \frac{e^{-z}}{1-z} \end{align} $$ (which unsurprisingly happens to be the same as $D(z)$ the exponential generating function for derangements).


Method 3.
We can use the "symbolic method" from the book Analytic Combinatorics (available online!) by Flajolet and Sedgewick.

Let $\mathcal{H}$ denote the class of "hooks" (or "hockey sticks"), by which I mean permutations that are increasing except for the last element. So it's a set of numbers, arranged in increasing order, followed by some number that is not the maximum. In the notation of the book, $$\mathcal{H} = \operatorname{S\scriptsize ET}\left(\mathcal{Z}\right) ^\blacksquare\star \mathcal{Z}$$ immediately giving that the EGF of $\mathcal{H}$ is $$H(z) = \int_0^z (\frac{d}{dt}e^t) t \, dt = e^z(z-1) + 1$$ (You could of course get the same with actual enumeration, using $H_n = (n-1)$ (you only have choice of the last element), but we're trying to avoid explicit counting in this method.)

Let $\mathcal{E}$ be the class of desarrangements, that we want to count. A desarrangement is either a member of $\mathcal{H}$ of odd size (which therefore has its descent in an even position), followed by an arbitrary permutation (and then relabelled), or an increasing permutation (a set of numbers arranged in increasing order) of even size. In notation, $$\mathcal{E} = \mathcal{H}_{\text{odd}} \star \operatorname{S\scriptsize EQ}(\mathcal{Z}) + \operatorname{S\scriptsize ET}_{\text{even}}(\mathcal{Z})$$ which immediately translates to the EGF $$\begin{align} E(z) &= \frac{H(z) - H(-z)}{2} \frac{1}{1-z} + \frac{e^z + e^{-z}}{2} \\ &= \frac{e^z(z-1) + 1 - e^{-z}(-z-1) - 1}{2}\frac{1}{1-z} + \frac{e^z + e^{-z}}{2}\\ &= \frac{e^{-z}}{1-z} \end{align} $$ as before. Even some intermediate expressions turned out the same as in the previous approach, but the difference this time is that we argued "globally" (which correponds to multiplying generating functions etc.) instead of having to count $E_n$ separately for every $n$.

share|improve this answer
    
Although the question is tagged homework, I thought it's OK to give a full answer as it's been 9 months. –  ShreevatsaR Jan 20 at 2:12
    
Thanks for your answer. Even though I managed to solve this exercise (9 months ago) your answer is so much concrete and clear. –  Nick Papadopoulos Feb 6 at 11:12
    
@NickPapadopoulos: You're welcome! I enjoyed writing it up, too. –  ShreevatsaR Feb 6 at 11:14
add comment

HINT: A useful technique is to gather a little data and then check to see what OEIS, The On-Line Encyclopedis of Integer Sequences, can tell you.

If you actually count, you’ll find that $E(1)=0,E(2)=1$ (for the permutation $12$), $E(3)=2$ (for $132$ and $231$), and $E(4)=9$ (for $1324$, $1423$, $1432$, $2314$, $2413$, $2431$, $3412$, $3421$, and $1234$). This is a very small amount of data, but it doesn’t hurt to check OEIS, if only for ideas. The sequence $0,1,2,9$ produces $168$ matches, which is rather a lot $-$ not really surprising, with only four terms $-$ but the first, OEIS A000166, is the sequence of derangement numbers, which at least sounds as if it might be related. And if you read down through the comments, you should quickly find something of use, if you remember that descents turn into ascents when you ‘turn a permutation upside down’.

If that still doesn’t help, I’ve left a broader hint spoiler-protected hint below; mouse-over to see it.

Google on "desarrangement" (with quotes).

share|improve this answer
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.