Greetings, folks. Yes, I'm still alive and I still love writing blogs. Last year (2020) has been a very rough year for me, you know, depression and stuff, but I finally got myself together. I'll be doing a bachelor thesis on pattern-avoid permutations, particularly trying to prove some equidistributions of some pairs of statistics on two set of PAP. I'm using this blog to take notes of my progress. On the off chance that someone would steal my ideas, I have two things to tell you: 1. I would be very flattered, 2. please don't do so.

Anyway, when we study Math, it's important to ask questions and verify what we study. We're often taught to prove a theorem before going with it. I'm doing the same today: As I was reading Amini's paper [1], I encountered a very beautiful distribution formula of the inversion statistic, and Dr. Huong Tran, my advisor, told me to prove it. I will present some introductory terminologies first, then present the proof. My proof isn't very elegant and formal, but it's pretty intuitive, visual, and intelligible. Hope you'll like it. :)

A statistic is essentially a map: . The distribution of is the coefficients of the generating function:

Given and :

Then the said generating function for is:

By looking at the term , we know that there are two occurrences of 1 in the second row of the table above.

Let be the set of permutations over the set . Denote .

The inversion set of a permutation is the set of pairs such that and .

We define the inversion statistic to be:

The distribution of is given by the generating function:

where and where .

First, we need to see if this is true with .

From the table, we have:

From the formula, we have:

thus it's indeed

Assume that the formula is true with :

Now, we need to prove that

We know that we can construct by inserting to every possible place of every string in .

Constructing : Insert 3 into 12, being the first position (312), middle position (132), last position (123). Insert 3 into 21, being the first position (321), middle position (231), last position (213). Thus .

Let be the coefficient of in .

By inserting to every possible place in a permutation, the inversion value can be increased by 0 (inserting to the last position), 1, 2, ..., up to (inserting to the first position).

where .

In conclusion: