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?

  • 3
    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$ ?2012-01-05
  • 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
    Beat me to it, good job.2012-01-05
  • 0
    thanks a lot for the answer and references2012-01-06