# number of permutations in which no two consecutive numbers are adjacent

In how many ways can the natural numbers from 1 to 10 be arranged so that no two consecutive numbers are adjacent to each other, and how is the formula arrived at?

-
Should the consecutive numbers be ordered ? I.e. the arrangement can not have $\ldots, 2, 3, \ldots$, but can it have $\ldots, 3, 2, \ldots$ ? –  Sasha Jan 5 '12 at 19:32
@Sasha : no, it can't have ...,3,2,... –  true blue anil Jan 5 '12 at 19:51

This is OEIS sequence A002464. The value for $n=10$ is $479306$; the entry gives several formulas for calculating the terms. It also refers to p. 373 of Analytical Combinatorics by Flajolet and Sedgewick, which you can download here; that page gives a derivation of the ordinary generating function of the sequence.