

A167760


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


1



1, 0, 0, 3, 4, 40, 216, 1603, 13000, 118872, 1202880, 13361403, 161638764, 2115684272, 29792671832, 449145795915, 7217975402768, 123180993414224, 2224874726830656, 42402252681323859
(list;
graph;
refs;
listen;
history;
text;
internal format)



OFFSET

0,4


COMMENTS

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.)
Obtained from A000757 by multiplying by n; description comes from bijection between cyclic notation and oneline notation of a permutation.
Example and inspiration from S. Billey, University of Washington.


LINKS

G. C. Greubel, Table of n, a(n) for n = 0..449
V. Kotesovec, Nonattacking chess pieces, 6ed, 2013, p. 640.


FORMULA

a(n) = n*A000757(n) for n>0.
a(n) = n*((1)^n + Sum_{k=0..(n1)} (1)^k*binomial(n, k)*(nk1)!.
a(n) = n*(Sum_{j=3..n} (1)^(nj))*D(j1), 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) = (n4)*a(n1) + (4n8)*a(n2) + (5n6)*a(n3) + (n+6)*a(n4)  (2n12)*a(n5)  (n5)*a(n6), for n>=8.  Vaclav Kotesovec, Apr 11 2012


EXAMPLE

For n3, the a(4) = 4 solutions are, in oneline notation: 4321, 3214, 2143, 1432. w=1324 is not a solution since w(4 + 1) = w(4) + 1 = 1 mod 4.


MATHEMATICA

a[n_] = n*((1)^n + Sum[(1)^k*n!/((nk)*k!), {k, 0, n1}]); a[0]=1; Table[a[n], {n, 0, 19}] (* JeanFrançois Alcover, Jul 19 2012, after Michael Somos (cf. his formula in A000757) *)


PROG

(PARI) a(n) = if(n>0, n*(1)^n + n*sum(k=0, n1, (1)^k*binomial(n, k) * (n  k  1)!), 1) \\ Charles R Greathouse IV, Nov 03 2014
(MAGMA) [1] cat [n*((1)^n + (&+[(1)^k*Factorial(n)/((nk)* Factorial(k)): k in [0..n1]])): n in [1..20]]; // G. C. Greubel, Sep 22 2018


CROSSREFS

Cf. A000166, A000587, A000757.
Sequence in context: A274663 A088168 A032836 * A012472 A012876 A300882
Adjacent sequences: A167757 A167758 A167759 * A167761 A167762 A167763


KEYWORD

nonn,easy,nice


AUTHOR

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


STATUS

approved



