How many permutations of $\{1,2,3,...,n\}$ there are with no 2 consecutive numbers? 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.


*

*when $i+1 = j$ then $|A_i \cap A_j|=(n-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
 A: 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.
A: 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)!.$$
A: 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.
