login
This site is supported by donations to The OEIS Foundation.

 

Logo

Please make a donation to keep the OEIS running. We are now in our 55th year. In the past year we added 12000 new sequences and reached 8000 citations (which often say "discovered thanks to the OEIS"). We need to raise money to hire someone to manage submissions, which would reduce the load on our editors and speed up editing.
Other ways to donate

Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
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 one-line 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, Non-attacking chess pieces, 6ed, 2013, p. 640.

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

EXAMPLE

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.

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

PROG

(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

(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

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

Lookup | Welcome | Wiki | Register | Music | Plot 2 | Demos | Index | Browse | More | WebCam
Contribute new seq. or comment | Format | Style Sheet | Transforms | Superseeker | Recent
The OEIS Community | Maintained by The OEIS Foundation Inc.

License Agreements, Terms of Use, Privacy Policy. .

Last modified December 7 05:14 EST 2019. Contains 329839 sequences. (Running on oeis4.)