4
$\begingroup$

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?

  • 0
    @Sasha : no, it can't have ...,3,2,...2012-01-05

1 Answers 1

10

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.

  • 0
    thanks a lot for the answer and references2012-01-06