Kvant Math Problem 1167

Verified: no
Verdicts: SKIP + SKIP
Solve time: 1m55s
Source on kvant.digital

Problem

How many permutations of the numbers 1, 2, $\ldots$, $n$ exist in which, for any number $i$ that is not in the first position, at least one of the numbers $i-1$ and $i+1$ is to the left of $i$?

A. V. Andzhans

Tournament of Cities (Autumn, 1988)

Exploration

Let $p(i)$ denote the position of $i$ in the permutation. The condition says that whenever $i$ is not first, at least one of $i-1$ and $i+1$ occurs earlier than $i$.

The endpoints require separate interpretation. For $i=1$, the only relevant neighbor is $2$, so if $1$ is not first then $2$ must be to its left. For $i=n$, if $n$ is not first then $n-1$ must be to its left.

Let us examine small cases.

For $n=1$, the only permutation works.

For $n=2$, both permutations work:

$$12,\qquad 21.$$

For $n=3$, the valid permutations are

$$123,\ 213,\ 231,\ 321.$$

There are $4$ of them.

The numbers $1,2,4$ suggest $2^{n-1}$.

To understand the structure, look at the first element. Suppose the first element is $k$. Since every other element must have a neighbor already appearing when it is inserted, perhaps the set of numbers already seen must always form an interval.

Starting with ${k}$, the next number must be $k-1$ or $k+1$, because any other number has neither neighbor present. After choosing one of them, the seen set becomes an interval of length $2$. Inductively, if the seen numbers form an interval $[a,b]$, then a new number can be added only at one of the ends, namely $a-1$ or $b+1$. Any interior missing number would have neither neighbor in the interval, and any number farther away has no neighboring number in the interval at all.

This appears to be the crucial observation. If it is correct, every valid permutation is obtained by starting from some $k$ and repeatedly extending the current interval left or right until reaching $[1,n]$.

How many such extension sequences are there? If the first element is $k$, then we must make exactly $k-1$ left extensions and $n-k$ right extensions. Their order is arbitrary. Hence the number of permutations beginning with $k$ is

$$\binom{n-1}{k-1}.$$

Summing over $k$ gives

$$\sum_{k=1}^{n}\binom{n-1}{k-1}=2^{n-1}.$$

The step most likely to hide an error is the claim that the already used numbers always form an interval and that every interval-extension sequence indeed satisfies the original condition.

Problem Understanding

We seek the number of permutations of $1,2,\dots,n$ such that every number $i$ that is not in the first position has at least one neighboring integer, either $i-1$ or $i+1$, appearing earlier in the permutation.

This is a Type C problem, since a numerical value is to be determined.

The core difficulty is to characterize all admissible permutations. The natural idea is that, reading the permutation from left to right, the set of numbers already encountered must remain a consecutive interval of integers.

The answer is

$$2^{,n-1}.$$

The reason this should be correct is that after choosing the first element $k$, every subsequent step amounts to enlarging the current interval either on the left or on the right.

Proof Architecture

Lemma 1. In any valid permutation, after the first $m$ terms have been read, the set of numbers appearing among them is a consecutive interval of integers.

Sketch. The first term forms an interval; if the current set is an interval $[a,b]$, the next admissible number must be either $a-1$ or $b+1$.

Lemma 2. Conversely, any permutation obtained by starting from a number $k$ and repeatedly adjoining either the current interval's left neighbor or its right neighbor satisfies the required condition.

Sketch. Every newly adjoined number has one of its neighbors already inside the interval.

Lemma 3. For a fixed first element $k$, the number of such permutations equals $\binom{n-1}{k-1}$.

Sketch. One must perform exactly $k-1$ left extensions and $n-k$ right extensions, and only their order matters.

The hardest direction is Lemma 1, because it must exclude every possibility except extending the current interval at an endpoint.

Solution

Let

$$a_1,a_2,\dots,a_n$$

be a valid permutation of $1,2,\dots,n$.

For each $m$, let

$$S_m={a_1,a_2,\dots,a_m}.$$

We first prove that $S_m$ is always an interval of consecutive integers.

For $m=1$, the set $S_1={a_1}$ is an interval.

Assume that for some $m<n$, the set $S_m$ is the interval

$$[a,b]={a,a+1,\dots,b}.$$

Consider the next element $a_{m+1}$.

Since $a_{m+1}$ is not in the first position, the defining condition gives that at least one of its neighbors, $a_{m+1}-1$ or $a_{m+1}+1$, belongs to $S_m$.

Because $S_m=[a,b]$, this is possible only in the following two cases.

If $a_{m+1}<a$, then the only way a neighbor of $a_{m+1}$ can belong to $[a,b]$ is when

$$a_{m+1}+1=a,$$

hence

$$a_{m+1}=a-1.$$

If $a_{m+1}>b$, then the only way a neighbor of $a_{m+1}$ can belong to $[a,b]$ is when

$$a_{m+1}-1=b,$$

hence

$$a_{m+1}=b+1.$$

The possibility $a<a_{m+1}<b$ cannot occur, since all numbers of the interval already belong to $S_m$.

Thus

$$a_{m+1}\in{a-1,b+1},$$

and therefore

$$S_{m+1}$$

is again an interval. By induction, every set $S_m$ is an interval.

Now fix the first element $a_1=k$.

Since every $S_m$ is an interval and begins as ${k}$, each subsequent step enlarges the current interval by exactly one unit on the left or on the right. To reach the final interval $[1,n]$, we must perform exactly

$$k-1$$

left enlargements and exactly

$$n-k$$

right enlargements.

Conversely, any sequence of such enlargements produces a valid permutation. Indeed, whenever a new number is added on the left, it equals $a-1$ and has neighbor $a$ already present; whenever a new number is added on the right, it equals $b+1$ and has neighbor $b$ already present. Hence the required condition is satisfied at every step.

Therefore, for a fixed first element $k$, valid permutations are in one-to-one correspondence with sequences consisting of

$$k-1$$

symbols $L$ and

$$n-k$$

symbols $R$.

The number of such sequences is

$$\binom{n-1}{k-1}.$$

Summing over all possible values of $k$,

$$N=\sum_{k=1}^{n}\binom{n-1}{k-1}.$$

Using the binomial identity,

$$N=2^{,n-1}.$$

Hence the number of required permutations is

$$\boxed{2^{,n-1}}.$$

Verification of Key Steps

The first delicate point is the assertion that an admissible next element must be $a-1$ or $b+1$ when the previously seen numbers form $[a,b]$.

Suppose $x<a-1$. Then neither $x-1$ nor $x+1$ belongs to $[a,b]$, because $x+1\le a-1$. Hence $x$ cannot satisfy the condition. The same argument excludes every $x>b+1$. Thus only the two endpoints are possible.

The second delicate point is the converse direction. Starting from an interval $[a,b]$, if we append $a-1$, then its neighbor $a$ already lies to its left. If we append $b+1$, then its neighbor $b$ already lies to its left. The condition requires at least one neighboring integer to occur earlier, so every such extension is admissible.

The third delicate point is the counting. For fixed $k$, each valid permutation determines uniquely the sequence of left and right interval extensions, because at every step the new element is either the current left endpoint minus one or the current right endpoint plus one. Conversely, every such extension sequence determines the permutation uniquely. Hence the count really is the binomial coefficient $\binom{n-1}{k-1}$.

Alternative Approaches

One may encode a valid permutation by recording only its first element $k$ and, for each later position, whether the current interval grows to the left or to the right. The interval property can be proved directly from the condition, and then the permutation is reconstructed uniquely from this binary record. For fixed $k$, the record is a word of length $n-1$ containing $k-1$ letters of one type and $n-k$ of the other, yielding $\binom{n-1}{k-1}$ possibilities.

Another viewpoint is graph-theoretic. Consider the path graph on vertices $1,2,\dots,n$. The condition says that every vertex except the first appears after one of its neighbors. Reading the permutation from left to right, the already chosen vertices must induce a connected subgraph of the path, hence an interval. The rest of the argument becomes the same interval-extension count.