we find the number of such permutation and subset in order of subset: for each subset with $ k$ elements we should pick these $ k$ elements and put them in $ n - k$ place and fill other blanks with other elements so the nimber is: $ \sum_{k = 0}^n\binom{n}{k} \binom{n - k}{k}k!(n - k)!$=$ n!\sum_{k = 0}^n\frac {(n - k)!}{(n - 2k)!k!}$=$ n!\sum_{k}\binom{n - k}{k}$=$ n!f_{n + 1}$ as we know that $ f_{n + 1} = \sum_{k}\binom{n - k}{k}$