Does anyone want to help explain the formula for counting number of permutations with no hits to the main diagonal: https://oeis.org/A003471 ? It was needed in one of my country's training contest yesterday, so I'm interested to find out more about how the formula is derived. Thank you!