Combinatorics – Counting Permutations with No Two Consecutive Numbers

combinatoricsinclusion-exclusionpermutationsrecurrence-relationsrecursion

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

Best Answer

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

Related Question