From rook polynomials.

Terms

a(0) =1a(1) =6a(2) =22a(3) =64a(4) =162a(5) =374a(6) =809a(7) =1668a(8) =3316a(9) =6408a(10) =12108a(11) =22468a(12) =41081a(13) =74202a(14) =132666a(15) =235160a(16) =413790a(17) =723530a(18) =1258225a(19) =2177640a(20) =3753096a(21) =6444336a(22) =11028792a(23) =18818664a(24) =32024977a(25) =54367374a(26) =92094334a(27) =155688208a(28) =262711866a(29) =442556798