counting the number of permutations of n number have k places that decrease 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!
 A: 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.
