A192447 a(n) = n*(n-1)/2 if this is even, otherwise (n*(n-1)/2) + 1.

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

Offset: 1

Author

Ivaylo Kortezov, Jul 01 2011

Keywords

• nonn
• easy

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

Examples

			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.
		

Links

• Index entries for linear recurrences with constant coefficients, signature (3,-4,4,-3,1).

Crossrefs

Equals the corresponding term of A000217 if it is even or is 1 more otherwise.

Cf. A054925, A213484, A373584.

Programs

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

PARI

a(n) = my(m=n*(n-1)/2); if (m % 2, m+1, m); \\ Michel Marcus, Jun 07 2019

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

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

Sum_{n>=2} 1/a(n) = 2 - Pi/2 + Pi*sinh(sqrt(7)*Pi/4)/(sqrt(7)*(1/sqrt(2) + cosh(sqrt(7)*Pi/4))). - Amiram Eldar, Dec 14 2024

a(n) = 2*(A213484(n+1) - 1)/3 = (A373584(n) - 1)/3. - Hugo Pfoertner, Dec 15 2024