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?
- Anybody can ask a question
- Anybody can answer
- The best answers are voted up and rise to the top
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.