# Number of cute permutations

A permutation of the numbers $$1,2,3,\dots,n$$ is called cute if there is exactly one number that is greater than its position. For example, $$1,4,3,2$$ is a cute permutation (when $$n=4$$) because only the number $$4$$ is greater than its position. How many cute permutations there for a fixed $$n$$?

The problem is from a local math contest. Here is my attempt in solving the problem:

I've noticed that if $$p_1,p_2,\dots,p_n$$ is a cute permutation where $$p_k>k$$ then for all $$i\neq k$$, we have $$p_i\leq i$$. But I don't think this is helpful in finding the number of cute permutations.

I also tried for small values of $$n$$ by listing all the possible permutations.

• For $$n=2$$, it's easy to see that there is only one such permutation.

• For $$n=3$$, I found $$4$$ permutations.

• For $$n=4$$, I found $$10$$ permutations.

From here it seems to me that the the number of cute permutations is $$\binom 22+\binom 32+\dots+\binom n2$$. But I couldn't find a way to show that.

So, how to solve the problem? And what happens if we call a permutation less cute if there are exactly two numbers that are greater than its position? Can we solve in general?

• @Yorch Your answer is about permutations that decrease exactly once, unlike the cute permutation $1,4,3,2$. Unless you are suggesting a relationship between the two problems? Commented Aug 13, 2021 at 12:59
• |Cute|=|Eulerian| Commented Aug 13, 2021 at 14:30
• Which competition was this from? Commented Aug 14, 2021 at 14:05
• Your cute permutations are precisely the permutations that have exactly $1$ excedance. See Proposition 1.4.3 in Richard Stanley's EC1 for the answer to the more general question about $k$ excedances. Commented Sep 17, 2021 at 18:56

Here is how we form a cute permutation: select $$m$$ numbers; $$x_{1}. Put $$x_{m}$$ in $$x_{1}$$'s original location then for all $$i\in[1,2,...,m-1]$$ put $$x_{i}$$ in $$x_{i+1}$$'s original location. The number of cute permutations is given by the following expression:

$$\sum_{m=2}^{n}{\binom{n}{m}}=2^{n}-\left(n+1\right)$$

The idea is that out of $$n$$ numbers, some will change position ($$m$$ of them) while the rest will remain at their original position. Out of all the numbers that change position only one move to the left while the others move to the right.

By the way for $$n=4$$ there are $$11$$ cute permutations instead of $$10$$

• This is not a proof. Commented Aug 13, 2021 at 14:23
• @MishaLavrov true, this is more like a hint. I just wrote the answer with some bits about my thoughts, hopefully enough to give OP some ideas. Commented Aug 13, 2021 at 14:28
• What about the second question? Can we solve in general? Commented Aug 14, 2021 at 4:51

A cute permutation in $$S_n$$ can always be identified with one non-trivial (length greater than or equal to $$2$$) cyclic permutation acting on $$\{1,2,\dots,n\}$$ of a special form , so the task at hand is to count the number of cute cyclic permutations.

If you are presented with the the 'active' elements of a cute cyclic permutation of length two or more, you'll readily discover that there is one and only one way of re-building that permutation (see the example in the next section).

Since

$$\quad \text{The number of subsets of } \{1,2,\dots,n\} = 2^n$$
$$\;\;\;$$and the number of subsets with $$0$$ elements is $$1$$,
$$\quad\;$$and the number of subsets with $$1$$ element is $$n$$,
we conclude that the count of cute permutations is given by

$$\tag{1} 2^n-1-n$$

Example: If $$n = 4$$ then the subset $$\{1,3,4\}$$ corresponds to the cute (cyclic) permutation

$$\quad (4\, 3\, 1)$$

• A cute permutation will contain $n$ elements. Then why don't we continue the subtraction i.e $2^n-1-n-\binom n2-\dots$? Commented Aug 14, 2021 at 9:14