Number of cute permutations

Question

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?

Answer 1

Here is how we form a cute permutation: select $m$ numbers; $x_{1}<x_{2}<...<x_{m}$. 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$

Answer 2

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)$