OFFSET
1,2
COMMENTS
Least number of swaps of passports of n persons so that each two have swapped at least once and finally each one gets his own passport (JBMO 2011 Shortlist).
LINKS
Index entries for linear recurrences with constant coefficients, signature (3,-4,4,-3,1).
FORMULA
a(n) = n*(n-1)/2 if this is even and a(n) = (n*(n-1)/2) + 1 otherwise.
a(n) = 2*A054925(n+1).
G.f.: 2*x*(x^2 - x + 1)/((1 - x)^3*(1 + x^2)).
a(n) = (n^2 - n + 1 - (-1)^(n*(n-1)/2))/2. - Guenther Schrack, Jun 04 2019
EXAMPLE
a(3)=4: Let the initial state be Aa, Bb, Cc. Swap(AB) to get Ab, Ba, Cc. Swap(AC) to get Ac, Ba, Cb. Swap(BC) to get Ac, Bb, Ca. Swap(AC) to get Aa, Bb, Cc, done.
MATHEMATICA
Table[(n^2 - n + 1 - (-1)^(n (n - 1)/2))/2, {n, 1, 60}] (* Bruno Berselli, Jun 07 2019 *)
LinearRecurrence[{3, -4, 4, -3, 1}, {0, 2, 4, 6, 10}, 54] (* Georg Fischer, Oct 26 2020 *)
PROG
(PARI) a(n) = my(m=n*(n-1)/2); if (m % 2, m+1, m); \\ Michel Marcus, Jun 07 2019
CROSSREFS
KEYWORD
nonn,easy
AUTHOR
Ivaylo Kortezov, Jul 01 2011
STATUS
approved