login
The number of permutations w of [n] with no w(i)+1 == w(i+1) (mod n).
2

%I #40 Feb 17 2022 00:00:16

%S 1,0,0,3,4,40,216,1603,13000,118872,1202880,13361403,161638764,

%T 2115684272,29792671832,449145795915,7217975402768,123180993414224,

%U 2224874726830656,42402252681323859,850380681002034900,17902407539998807896,394741856473979171608,9097740802923890621491

%N The number of permutations w of [n] with no w(i)+1 == w(i+1) (mod n).

%C a(n) counts rearrangements of n children sitting at distinguishable carousel horses such that no child sits behind the same child after rearrangement. (The case of indistinguishable carousel horses is counted by A000757.)

%C Obtained from A000757 by multiplying by n; description comes from bijection between cyclic notation and one-line notation of a permutation.

%C Example and inspiration from S. Billey, University of Washington.

%H G. C. Greubel, <a href="/A167760/b167760.txt">Table of n, a(n) for n = 0..449</a>

%H V. Kotesovec, <a href="https://oeis.org/wiki/User:Vaclav_Kotesovec">Non-attacking chess pieces</a>, 6ed, 2013, p. 640.

%F a(n) = n*A000757(n) for n > 0.

%F a(n) = n*((-1)^n + Sum_{k=0..n-1} (-1)^k*binomial(n, k)*(n-k-1)!).

%F a(n) = n*(Sum_{j=3..n} (-1)^(n-j))*D(j-1), n >= 3, with the derangements numbers (subfactorials) D(n)=A000166(n).

%F 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

%F 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

%e 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.

%t 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) *)

%o (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

%o (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

%Y Cf. A000166, A000587, A000757.

%K nonn,easy,nice

%O 0,4

%A Joel Barnes (joel(AT)math.washington.edu), Nov 10 2009