I noticed something interesting in this table. The columns can be expressed by polynomials of degree k. I toke the first $k+1$ numbers from each column and used Lagrange's interpolation. Surprisingly, I got that this extrapolation gives exact values of all other numbers in the column. I can't check this for $k=7$. $$k=0: 1$$ $$k=1: n-1$$ $$k=2: n^2-3n+2$$ $$k=3: n^3-5n^2+8n-5$$ $$k=4: n^4-\frac{15}2n^3+\frac{29}2n^2+3n-17$$ $$k=5: n^5-\frac{65}6n^4+\frac{173}6n^3+\frac{148}3n^2-\frac{862}3n+265$$ $$k=6: n^6-\frac{883}{60}n^5+\frac{157}3n^4+\frac{2155}{12}n^3-\frac{4570}3n^2+\frac{42767}{15}n-967$$ $$k=7: \frac{1679}{1680}n^7-\frac{2765}{144}n^6+\frac{21541}{240}n^5+\frac{69163}{144}n^4-\frac{717821}{120}n^3+\frac{1462277}{72}n^2-\frac{10388033}{420}n+5037$$
If I set the $n$ to one where the first positive value occurs, it is: $$k=0: 1$$ $$k=1: n$$ $$k=2: n^2+n$$ $$k=3: n^3+n^2-1$$ $$k=4: n^4+\frac92n^3+n^2-\frac92n+1$$ $$k=5: n^5+\frac{55}6n^4+\frac{31}2n^3-\frac{14}3n^2-2n+1$$ $$k=6: n^6+\frac{917}{60}n^5+\frac{713}{12}n^4+\frac{565}{12}n^3-\frac{5}{12}n^2+\frac{409}{30}n-3$$ $$k=7: \frac{1679}{1680}n^7+\frac{142}{9}n^6+\frac{192}{5}n^5-\frac{3743}{36}n^4-\frac{18917}{240}n^3+\frac{14119}{36}n^2-\frac{50761}{140}n+100$$
Questions:
Can it be proven that the colums of that table are always polynomials?
Can be the coefficients predicted in a way? There seems to be an order but I can't find it.
This is a very very very partial answer, treating only cases k = 0, 1, 2, 3. But I hope it inspires some further work on the remaining cases.
Think of the numbers as points at distance $k$ from a fixed base point in the pancake graph. We think about the basepoint as the pile of pancakes that is completely sorted in the desired way. Vertices (stacks) that are reachable in $k$ steps from this point (but not in less steps) are exactly the stacks that need $k$ steps to reach the base point - which is what the table is counting. (Of course from the pancake graph perspective, the choice of base point is not important since the group $S_n$ acts transitively on the vertices of the graph by graph isomorphisms.)
The first three columns are easy. Of course there is only point at distance 0 from the basepoint: the base point itself. Also as every vertex in the pancake graph has degree $(n-1)$ (there are at each moment $n-1$ possible flips to make) it is clear that each point has $n-1$ neighbors. This is the $k=1$ column.
Similarly: each of these $n-1$ neighbors has $n-2$ neighbors apart from the base point, so the number of points at distance $k = 2$ should be $(n-1)(n-2)$. Expanding the brackets we recover your result: $n^2 - 3n + 2$.
Alas this strategy breaks down for $k = 3$. The pancake graphs contain a lot of hexagons (isomorphic embeddings of the 3-pancake graph) which means that if we take the naive prediction of $(n-1)(n-2)(n-2)$ we count some, and perhaps many, points twice or perhaps even more often it there are multiple hexagons containing both the base point and the point of interest. So the answer will certainly be less than $(n-1)(n-2)(n-2)$, but by how much?
Well lets first rewrite this crude upper bound in the form you use, so without brackets. We get $n^3 - 5 n^2 + 8 n - 4$. This is very interesting, it is only 1 more than what you find! This means that of the $n^3 - 5 n^2 + 8 n - 4$ points at distance 3 there is only one that is double counted!
Knowing this it is not hard to see which one is it: we already mentioned the 3-pancake subgraph. It consists of moves that only move the top 3 pancakes. Apparently:
Instead of writing 'apparently' we could also just post this as a lemma, prove it and derive the formula for the $k = 3$ case from it.
Now the proof of this lemma is not so hard because 3 is a really really small number. The real question is:
I will think about that and come back to it later.