How many permutations of $\{1,2,3,...,n\}$ there are with no 2 consecutive numbers?

Question

How many permutations of $\{1,2,3,...,n\}$ are there with no 2 consecutive numbers?

For example:
$n=4$, $2143$, $3214$, $1324$ are the permutations we look for and $1234$, $1243$, $2134$ are what we DON'T look for.

My solution:

we will sub from all the permutations the bads. All permutations= $n!$

bads:

Lets define $A_i$ to be a group of all permutations containing $i,i+1$ in it. ($1\leq i\leq n-1$)

My problem is to count to group of :$|A_i \cap A_j|$ where $1 \leq i < j \leq n-1$.

Because there is a big difference between $A_i \cap A_{i+1}$ and $A_i \cap A_{i+5}$ (for instance), we can't say that both are the same. So we need to divide $|A_i \cap A_j|$ to 2 options.

1. when $i+1 = j$ then $|A_i \cap A_j|=(n-2)!$
2. when $i+1 < j$ then $|A_i \cap A_j|=(n-2)!$

So $|A_i \cap A_j|=(n-2)!+(n-2)!$

This is a big mistake but I have no clue why.

(the rest of the solution is the same).

Any help would be welcome.

Stav

Answer 1

If, as appears to be the case, you’re planning to use an inclusion-exclusion argument, you’ll need $\left|\bigcap_{k\in I}A_k\right|$ for every non-empty $I\subseteq[n-1]$. The trick is to realize that no matter how the integers in $I$ are spaced, the cardinality is going to be the same. When $|I|=2$, the case that you’re discussing in the question, there are two possibilities: the two members of $I$ are consecutive, or they are not. But in both cases it turns out that the cardinality of the intersection is $(n-2)!$: there are different calculations for the two cases, but they lead to the same result. Note that there is no reason at all to add these calculations: no $I$ belongs to both cases.

The set $I$ can be divided into blocks of consecutive integers. For example, $I=\{2,3,5,6,7,9\}$ has $3$ blocks: $\{2,3\},\{5,6,7\}$, and $\{9\}$. Suppose that $I$ has a block $\{k,k+1,\ldots,k+r\}$. Then every permutation in $\bigcap_{k\in I}A_k$ must contain the subsequence $\langle k,k+1,\ldots,k+r,k+r+1\rangle$; call this an extended block. If $I$ has $b$ blocks altogether, each permutation of $[n]$ that belongs to $\bigcap_{k\in I}A_k$ must contain all $b$ extended blocks as subsequences, but it can contain them in any order. Those extended blocks contain altogether $|I|+b$ integers: the blocks themselves contain $|I|$ integers, and each extended block has one extra integer on the righthand end. That leaves $n-|I|-b$ members of $[n]$ that can be permuted arbitrarily, because they aren’t in any extended block of $I$. Thus, the permutations in $\bigcap_{k\in I}A_k$ are really permutations of

$$b+(n-|I|-b)=n-|I|$$

things: $b$ extended blocks, and the $n-|I|-b$ single elements that are not part of any extended block. It follows that

$$\left|\bigcap_{k\in I}A_k\right|=(n-|I|)!$$

whenever $\varnothing\ne I\subseteq[n-1]$.

Now the inclusion-exclusion principle tells you that

$$\begin{align*} \left|\bigcup_{k\in[n-1]}A_k\right|&=\sum_{\varnothing\ne I\subseteq[n-1]}(-1)^{|I|-1}\left|\bigcap_{k\in I}A_k\right|\\ &=\sum_{\varnothing\ne I\subseteq[n-1]}(-1)^{|I|-1}(n-|I|)!\\ &=\sum_{k=1}^{n-1}\binom{n-1}k(-1)^{k-1}(n-k)!\;, \end{align*}$$

and I’ll leave the rest for you to finish off.

Answer 2

In both cases, there are $(n-2)!$ permutations.
In the first case, there is the triple $(i,i+1,i+2)$ and $n-3$ other numbers.
In the second case, there are two pairs, and $n-4$ other numbers.

Answer 3

Consider the following recurrence: the desired count $Q_n$ is $1$ for $n=1$ and $1$ for $n=2.$ For $n\gt 2$ we obtain an admissible permutation either by placing the value $n$ anywhere at $n-1$ possible positions of an admissible permutation from $Q_{n-1}$ (this is not $n$ because we may not place $n$ next and to the right of $n-1$) or we construct a permutation having exactly one pair of consecutive numbers and place the value $n$ between these two. This can be done by taking a permutation from $Q_{n-2}$ and replacing one of the $n-2$ values by a fused pair containing the value and its successor and incrementing the values that are larger than the first element of the fused pair.

We get the recurrence

$$Q_n = (n-1) Q_{n-1} + (n-2) Q_{n-2}$$

and $Q_1= Q_2= 1.$ This yields the sequence

$$1, 3, 11, 53, 309, 2119, 16687, 148329, 1468457, 16019531, 190899411, \\ 2467007773, 34361893981, 513137616783,\ldots$$

which is OEIS A000255, where a detailed entry may be found.

The Maple code for this was as follows.

with(combinat);

C :=
proc(n)
option remember;
local perm, pos, res;

    res := 0;
    perm := firstperm(n);

    while type(perm, `list`) do
        for pos to n-1 do
            if perm[pos] + 1 = perm[pos+1] then
                break;
            fi;
        od;

        if pos = n then
            res := res + 1;
        fi;

        perm := nextperm(perm);
    od;


    res;
end;


Q :=
proc(n)
option remember;

    if n = 1 or n = 2 then return 1 end if;

    (n - 1)*Q(n - 1) + (n - 2)*Q(n - 2)
end;

Addendum. Here is my perspective on the inclusion-exclusion approach. We take as the underlying partially ordered set the set $P$ of subsets (these are the nodes of the poset) of $\{1,2,\ldots,n-1\}$ where a subset $S\in P$ represents permutations where the elements of $S$ are next to their successors, plus possibly some other elements also next to their successors. The partially ordered set is ordered by set inclusion. To compute the cardinality of the permutations corresponding to $S$ suppose that the elements of $S$ listed in order form $m$ blocks. We first remove these from $[n].$ We must also remove the elements that are consecutive with the rightmost element of each block, so we have now removed $|S|+m$ elements. We then put the augmented and fused blocks back into the permutation and permute them. We have added in $m$ blocks, therefore the net change is $-|S|-m +m = -|S|.$ Hence by inclusion-exclusion we compute the quantity

$$\sum_{S\in P, S\ne\emptyset} (-1)^{|S|} (n-|S|)!.$$

Now this depends only on the number $q$ of elements in $S$ so we get

$$\sum_{q=1}^{n-1} {n-1\choose q} (-1)^q (n-q)!.$$

We must now ask about the weight assigned to a permutation with $p$ elements (call this set $T$) next to their successor. This permutation is included in or rather represented by all sets $S$ that are subsets of the set $T$, which is the poset spanned by the singletons and $T$ being the topmost node. We obtain

$$\sum_{q=1}^p (-1)^q {p\choose q} = -1 + (1-1)^p = -1.$$

The count assigns the weight minus one to the permutation. It follows that when we add $n!$ exactly those permutations remain that do not contain consecutive adjacent values, for a result of

$$n! + \sum_{q=1}^{n-1} {n-1\choose q} (-1)^q (n-q)!.$$

We may simplify this to

$$\sum_{q=0}^{n-1} {n-1\choose q} (-1)^q (n-q)!.$$