counting the number of permutations of n number have k places that decrease

Question

The n size list is a list of integer numbers {1,2,3,..., n}.

I will use examples to show "have k places that decrease":

{4,3,1,2} where n=4, k=2. cause 4>3,3>1

{4,1,2,3} where n=4, k=1.cause 4>1

{1,5,4,2,3} where n=5, k=2. cause 5>4,4>2

The default order of the list is increasing. First I started from k=1, here it means only one pair of numbers is decrease. From 1 to n, I take one numbers outside, and have a (n-1) list left, then I insert the chosen number back to the (n-1) list, and I have(n-1) position to insert it. Now we have n*(n-1) permutation, but for the numbers that are connected with each other, like 1 and 2, 2 and 3, they have repeated patterns which is (n-1), so we need to delete them (but I can not clearly tell the repeated pattern, I used some examples to figure it out, and not sure whether it is correct). so the number of permutation for k=1 is n*(n-1)-(n-1)=(n-1)^2

When k=2, things kindly like out of my control, I am so lost. Don't know how to connected this one to the previous one, I hope I can write in a recursive way or get a close-form for the numbers.

Hope I can have some hints here~~

Thank you!

Answer 1

With the OP asking for a hint we can provide the following recursion. Ask how we can obtain a permutation with $k$ decreases by inserting the value $n$ into a permutation of the values from $1$ to $n-1.$ We could insert $n$ between one of the $k$ decreases of a permutation on $n-1$ with $k$ decreases, which keeps the number of decreases constant. Or we could add it at the end of a permutation on $n-1$ with $k$ decreases. Lastly we could insert it in one of the $(n-1)-(k-1)$ locations where there is no decrease of a permutation on $n-1$ with $k-1$ decreases, thereby increasing the count of decreases by one. This gives the recurrence

$$X_{n,k} = (k+1) X_{n-1, k} + (n-k) X_{n-1,k-1}.$$

The base cases here are $X_{1,0} = 1, X_{1,k} = 0$ and $X_{n,0} = 1,$ for the sorted permutation. Implementing this in Maple we find (there is an enumeration routine as well to check the values for small $n$).

with(combinat);

ENUM :=
proc(n)
    option remember;
    local gf, perm, pos, decr;

    gf := 0;

    perm := firstperm(n);

    while type(perm, `list`) do
        decr := 0;

        for pos to n-1 do
            if perm[pos] > perm[pos+1] then
                decr := decr + 1;
            fi;
        od;

        gf := gf + u^decr;

        perm := nextperm(perm);
    od;

    gf;
end;


A := (n, k) -> coeff(ENUM(n), u, k);

X :=
proc(n, k)
option remember;

    if n=1 then
        if k=0 then return 1 fi;
        return 0;
    fi;

    if k=0 then return 1 fi;

    k*X(n-1, k) + X(n-1,k) + (n-k)*X(n-1, k-1)
end;

We thus obtain e.g. for $n=7$ the values

$$1, 120, 1191, 2416, 1191, 120, 1.$$

We look these up in the OEIS and find that we are dealing with Eulerian numbers, OEIS A008292. Presumably many readers could have recognized the problem statement without doing the computation. Anyway the OEIS entry lists a considerable number of references and should suffice to start the reader on whatever type of investigation they plan to do.