Closed form of Eulerian numbers Proof

75 Views Asked by At

I was reading the proof of the closed-form formula of Eulerian numbers ($A(n,k)$) from Bona's book. I had a doubt in his classification of "removable fences" and how they eliminate the undesirable permutations. Basic setup described in the book

When we are counting the total number of desired permutations, we see that 2 things might happen which lead to undesirable permutations (| is a fence and signifies the separation of the compartments/concessions):

  • Empty compartments/concessions (eg: 234||1)
  • Neighboring compartments/concessions with no descent in between (eg: 12|3)

Bona classifies a fence $f$ as removable if it satisfies these 2 conditions:

  1. If we remove $f$, we still have a permutation whose entries increase between any two consecutive fences, and
  2. the fence $f$ is not immediately followed by another fence

He then says that any permutation that doesn't contain any removable fence has $k$ ascending runs. I do not understand why this definition of removable works (if possible, please explain through examples) and why this eliminates undesirable permutations. For instance, say we are counting $A(6,3)$, it still counts permutations of type 124||356, which isn't a desirable permutation as it only has 2 ascending runs.