def derangements(n)
  ary = (1 .. n).to_a
  ary.permutation.select do |perm|
    ary.zip(perm).all? {|a,b| a!= b}
  end
end

def subfact(n)
  case n
  when 0 then 1
  when 1 then 0
  else (n-1)*(subfact(n-1) + subfact(n-2))
  end
end

puts 
derangements(4).each{|d|p d}

puts 
(0..9).each do |n|
  puts  % [n, derangements(n).size, subfact(n)]
end

puts 
(10..20).each do |n|
  puts 
end