Skip to main content
2 of 2
added 72 characters in body
Jonathan Allan
  • 21.3k
  • 2
  • 59
  • 109

For 30:

$(!4 - 4) \times \left( \frac{4!}{4} \right)$

$ =(9 - 4) \times \left( \frac{24}{4} \right) = 5 \times 6 = 30$

For 31:

$44 - 4 - !4$

$= 44 - 4 - 9 = 31$

Note that:

$!n$ is the subfactorial of $n$.
For a non-negative-integer $n$ this is the number of derangements of $n$
(the number of ways to arrange $n$ items such that no item is at its naturally ordered position)
This is
$n! \sum_{i=0}^n \frac{(-1)^i}{i!}$

As such
$!4 = 4! \sum_{i=0}^4 \frac{(-1)^i}{i!} = 24 \times \left(\frac{(-1)^0}{0!} + \frac{(-1)^1}{1!} + \frac{(-1)^2}{2!} + \frac{(-1)^3}{3!} + \frac{(-1)^4}{4!}\right)$
$= 24 \times \left(\frac{1}{1} + \frac{-1}{1} + \frac{1}{2} + \frac{-1}{6} + \frac{1}{24}\right)$
$= \left(24 - 24 + 12 - 4 + 1\right)$
$= 9$

Or, using ABCD, the 9 derangements are:
1. BADC
2. BCDA
3. BDAC
4. CADB
5. CDAB
6. CDBA
7. DABC
8. DCAB
9. DCBA

But not any of the other 15 permutations:
ABCD . ACDB . BACD . CABD . DACB
ABDC . ADBC . BCAD . CBAD . DBAC
ACBD . ADCB . BDCA . CBDA . DBCA

Jonathan Allan
  • 21.3k
  • 2
  • 59
  • 109