|
|
A167760
|
|
The number of permutations w of [n] with no w(i)+1 == w(i+1) (mod n).
|
|
2
|
|
|
1, 0, 0, 3, 4, 40, 216, 1603, 13000, 118872, 1202880, 13361403, 161638764, 2115684272, 29792671832, 449145795915, 7217975402768, 123180993414224, 2224874726830656, 42402252681323859, 850380681002034900, 17902407539998807896, 394741856473979171608, 9097740802923890621491
(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
|
|
|
FORMULA
|
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
|
|
|
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
|
|
|
KEYWORD
|
nonn,easy,nice
|
|
AUTHOR
|
Joel Barnes (joel(AT)math.washington.edu), Nov 10 2009
|
|
STATUS
|
approved
|
|
|
|