|
|
A192447
|
|
a(n) = n*(n-1)/2 if this is even, otherwise (n*(n-1)/2) + 1.
|
|
2
|
|
|
0, 2, 4, 6, 10, 16, 22, 28, 36, 46, 56, 66, 78, 92, 106, 120, 136, 154, 172, 190, 210, 232, 254, 276, 300, 326, 352, 378, 406, 436, 466, 496, 528, 562, 596, 630, 666, 704, 742, 780, 820, 862, 904, 946, 990, 1036, 1082, 1128, 1176, 1226, 1276, 1326, 1378, 1432
(list;
graph;
refs;
listen;
history;
text;
internal format)
|
|
|
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
|
|
|
FORMULA
|
a(n) = n*(n-1)/2 if this is even and a(n) = (n*(n-1)/2) + 1 otherwise.
G.f.: 2*x*(x^2 - x + 1)/((1 - x)^3*(1 + x^2)).
|
|
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
|
Equals the corresponding term of A000217 if it is even or is 1 more otherwise.
|
|
KEYWORD
|
nonn,easy
|
|
AUTHOR
|
|
|
STATUS
|
approved
|
|
|
|