A167760 The number of permutations w of [n] with no w(i)+1 == w(i+1) (mod n).
1, 0, 0, 3, 4, 40, 216, 1603, 13000, 118872, 1202880, 13361403, 161638764, 2115684272, 29792671832, 449145795915, 7217975402768, 123180993414224, 2224874726830656, 42402252681323859, 850380681002034900, 17902407539998807896, 394741856473979171608, 9097740802923890621491
Offset: 0
Examples
For n-3, the a(4) = 4 solutions are, in one-line notation: 4321, 3214, 2143, 1432. w=1324 is not a solution since w(4 + 1) = w(4) + 1 = 1 mod 4.
Links
- G. C. Greubel, Table of n, a(n) for n = 0..449
- V. Kotesovec, Non-attacking chess pieces, 6ed, 2013, p. 640.
Programs
-
Magma
[1] cat [n*((-1)^n + (&+[(-1)^k*Factorial(n)/((n-k)* Factorial(k)): k in [0..n-1]])): n in [1..20]]; // G. C. Greubel, Sep 22 2018
-
Mathematica
a[n_] = n*((-1)^n + Sum[(-1)^k*n!/((n-k)*k!), {k, 0, n-1}]); a[0]=1; Table[a[n], {n, 0, 19}] (* Jean-François Alcover, Jul 19 2012, after Michael Somos (cf. his formula in A000757) *) -
PARI
a(n) = if(n>0,n*(-1)^n + n*sum(k=0, n-1, (-1)^k*binomial(n, k) * (n - k - 1)!), 1) \\ Charles R Greathouse IV, Nov 03 2014
Formula
a(n) = n*A000757(n) for n > 0.
a(n) = n*((-1)^n + Sum_{k=0..n-1} (-1)^k*binomial(n, k)*(n-k-1)!).
a(n) = n*(Sum_{j=3..n} (-1)^(n-j))*D(j-1), n >= 3, with the derangements numbers (subfactorials) D(n)=A000166(n).
a(n) ~ (n!/e)*(1 - 1/n + 1/n^3 + 1/n^4 - 2/n^5 - 9/n^6 - 9/n^7 + 50/n^8 + 267/n^9 + 413/n^10 + ...), numerators are A000587. - Vaclav Kotesovec, Apr 11 2012
a(n) = (n-4)*a(n-1) + (4n-8)*a(n-2) + (5n-6)*a(n-3) + (n+6)*a(n-4) - (2n-12)*a(n-5) - (n-5)*a(n-6), for n >= 8. - Vaclav Kotesovec, Apr 11 2012
Comments