I'm studying Stanley's Enumerative Combinatorics, Volume 1, 2nd ed., and am stuck on exercise 23 of chapter 2 (page 260).

I would appreciate it if someone can provide a solution for me as the solution in the book is just a reference to some other papers etc...

Problem: Give a sieve - theoretic proof that: $$ \sum_{n\ge0} f(n)\frac{x^n}{n!}=\frac{1}{\sum_{j\ge 0}\big(\frac{x^{3j}}{(3j)!}-\frac{x^{3j+1}}{(3j+1)!}\big)}$$

Where $f(n)$ is the number of permutations $w \in S_n$ with no proper double descents. Furthermore, if we consider $f_r(n)$ as the number of permutations $w\in S_n$ with no $r$ consecutive descents (where $n$ is not considered a descent), prove that:

$$ \sum_{n\ge0} f_r(n)\frac{x^n}{n!}=\frac{1}{\sum_{j\ge 0}\big(\frac{x^{(r+1)j}}{((r+1)j)!}-\frac{x^{(r+1)j+1}}{((r+1)j+1)!}\big)}$$

Note $S_n$ is the permutation of size $n$, and a descent for a permutation $\pi \in S_n,$ is a position $i$ such that $\pi_i>\pi_{i+1}$. Also a proper double descent is one where for a permutation $w=a_1...a_n,$ there is an index $1<i<n$ such that $a_{i-1}>a_i>a_{i+1}$

Honestly, I have no idea how to even approach this problem. Could someone really help me solve this, it would really help me alot on understanding this chapter on sieve techniques. Thanks in advance.

  • $\begingroup$ The "other papers" might be available online in PDF. Have you tried arxiv.org, citeseer.org, and Google Scholar? $\endgroup$ – Peter Taylor Apr 6 '18 at 7:22
  • $\begingroup$ Well I could not find it, even the ones I did find, the pages I want are not available. $\endgroup$ – Aurora Borealis Apr 6 '18 at 7:25
  • $\begingroup$ I would like to know which book you are studying. This book seems like the kind of thing I would love to read, although unfortunately I can't be of any help to you. $\endgroup$ – астон вілла олоф мэллбэрг Apr 6 '18 at 7:29
  • $\begingroup$ math.mit.edu/~rstan/ec/ec1.pdf#page=1 $\endgroup$ – Aurora Borealis Apr 6 '18 at 7:31
  • $\begingroup$ The solution given in the book is a lot more than "just a reference to some other papers etc.". It says "The argument is analogous to that of the previous exercise", which is already a good start; then defines $S_k$, $T_k$, $U_k$, and argues that $T_k=S_{k+2}-U_{k+2}$, $U_k=S_{k+1}-T_{k+1}$, $S_0=S_1-T_1$, giving $f(n) = \#S_0 $ $= \#(S_1-T_1) = \#S_1-\#(S_3-U_3)$ $=\#S_1-\#S_3+\#(S_4-T_4)=\#S_1-\#S_3\#S_4-\#(S_6-U_6)$, etc. Finally, "Since $\#S_k = \binom{n}{k} f(n-k)$, the proof follows". Which parts of that do you understand, and which parts don't you? $\endgroup$ – Peter Taylor Apr 6 '18 at 8:27

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.