7
$\begingroup$

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

$\endgroup$
  • 1
    $\begingroup$ It makes no sense to add your two figures of $(n-2)!$ together: the first applies only when $i+1=j$, and the second applies only when $i+1<j$, so they never both to the same pair of $i$ and $j$. $\endgroup$ – Brian M. Scott Jun 11 '16 at 19:07
  • $\begingroup$ @BrianM.Scott Studying the subject and wasn't sure if the following statement was true.$N(A_iA_j)$ was same for all $i\neq j$(even if $i+1=j$) by calculation through inclusion principle. thus there was no contradiction? $\endgroup$ – user416486 Apr 23 '18 at 15:49
1
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ First of all thank you very much for your time. Secondly Im having hard time to undestand how I={2,3,5,6,7,9}I={2,3,5,6,7,9} has 3 blocks: {1,2},{5,6,7}{1,2},{5,6,7}, and {9}. how and why did you choose those blcoks specifically? what does a block mean? $\endgroup$ – Stav Alfi Jun 11 '16 at 19:53
  • 1
    $\begingroup$ @Stav: By block I simply mean a maximal set of consecutive integers. In the set $\{2,3,5,6,7,9\}$ the sets $\{2,3\},\{5,6,7\}$, and $\{9\}$ are the longest strings of consecutive integers, so they’re the blocks. The blocks of $\{1,5,6,7,8,12,13,14,20\}$ are $\{1\},\{5,6,7,8\},\{12,13,14\}$, and $\{20\}$: in each block the numbers are consecutive, and the blocks are as long as possible. Note that in the case $|I|=2$, your two cases correspond to one block, when $i+1=j$, and two blocks, when $i+1<j$. $\endgroup$ – Brian M. Scott Jun 11 '16 at 19:58
  • $\begingroup$ No, Thank you! I could not get a better answer! The second paragraph provided the answer to my question in the best way. Combining all was perfectlly clear. Thank you agian and good night from isreal! :) $\endgroup$ – Stav Alfi Jun 11 '16 at 20:24
  • $\begingroup$ @Stav: You’re welcome! (And have a good night.) $\endgroup$ – Brian M. Scott Jun 11 '16 at 20:26
  • $\begingroup$ @MarkoRiedel I think Brian's expression counts the permutations that do have 2 consecutive numbers. If you take $n!$ minus his sum, it reproduces your sequence. $\endgroup$ – David Zhang Jun 11 '16 at 22:05
4
$\begingroup$

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

$\endgroup$
0
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ You say that becouse in both cases we will permutate n-2 numbers , the answer should be (n-2)!. but my quastion is why you neglect the big deffrence between those 2 cases? $\endgroup$ – Stav Alfi Jun 11 '16 at 14:25
  • $\begingroup$ They are different; but they both have the same number of permutations. $\endgroup$ – Empy2 Jun 11 '16 at 14:27
  • $\begingroup$ Then how do we know when to sum 2 options instead of taking only one as an answer like now? $\endgroup$ – Stav Alfi Jun 11 '16 at 14:28
  • 1
    $\begingroup$ @Stav: For each fixed pair of $i$ and $j$ with $1\le i<j\le n-1$ there are $(n-2)!$ permutations in $A_i\cap A_j$; the reasoning explaining this is different when $j=i+1$ from when $j>i+1$, but in both cases the result of the reasoning is $(n-2)!$. $\endgroup$ – Brian M. Scott Jun 11 '16 at 19:06
  • $\begingroup$ Thank you for your comment. Just to clarify the rest of the prove, I see that |Ai∩Aj| for all cases is (n-2)! but very hard to guess for the |Ai1∩Ai2∩....Aik|=(n-k)!, how do you know that with out proving it? $\endgroup$ – Stav Alfi Jun 11 '16 at 19:21

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.