Not the fastest approach for question 1, but here is a way. All permutations are produced and each is tested. There are various possibilities to achieve a tabular result. Here I just used Multicolumn.
strirlingPermutation[k_] := (
list = Riffle[Table[i, {i, 1, k}], Table[i, {i, 1, k}]];
check[x_List] := (
done = {};
n = 1;
While[n <= Length[x],
If[MemberQ[done, x[[n]]],
p = Position[done, x[[n]]][[1]][[1]];
If[Min[done[[p ;;]]] != x[[n]], Return[False]]];
AppendTo[done, x[[n]]];
n++;
];
Return[True];
);
Multicolumn[Select[Permutations[list], check[#] &], k]
)
strirlingPermutation[3]
