n - 1 + n! <= P(n) < n * n! The lower bound is achieved when the permutations overlap perfectly, e.g. when n = 2: 1, 2, 1 The upper bound is simply the conca

n - 1 + n! <= P(n) < n * n! The lower bound is achieved when the permutations overlap perfectly, e.g. when n = 2: 1, 2, 1 The upper bound is simply the concatenation of all permutations. You can get lower than this by exploiting the fact that some permutations' suffixes are other permutations' prefixes.