A102417 In the lexicographically ordered table of permutations of [n], there are two entries that give the greatest sum of pairwise products and they are reversals of each other. The items in this sequence are the indices of the earlier of the two.

0, 1, 3, 11, 41, 191, 1055, 6959, 53159, 462239, 4499999, 48454559, 571409999, 7321386239, 101249648639, 1502852279039, 23827244757119, 401839065331199, 7182224591270400, 135607710526041600, 2696935204633823744

Offset: 2

Author

Eugene McDonnell (eemcd(AT)mac.com), Feb 23 2005

Keywords

• easy
• nonn

Comments

The sequence of maximum sums, for which those here are the indices, is given by A101986. The formula for a(n) is essentially an inner product. For example, if n is 7, the result is obtained by (7 6 5 4 3 2 1) ip d2(1 2 3 4 5 6 7) where d2(k) = k! if k is odd and k! - (k/2)! if k is even, that is, (7 6 5 4 3 2 1) ip (1 1 6 22 120 714 5040) or 6959.

Changing the offset to 1 would change the sequence so that it gives the greater of the two indices of the rows that yield the maximum sum of products, but for permutations one shorter in length. For example, with offset 2, index 3 is the index of the earlier row having the permutation giving maximum value for permutations of length 4; with offset 1, index 3 is the later index for the permutation giving maximum value for permutations of length 3. - Eugene McDonnell (eemcd(AT)mac.com), Feb 23 2005

Examples

			The 6959th entry in the table of permutations of order 9 is {1, 3, 5, 7, 9, 8, 6, 4, 2}, which has the pairwise products 3 15 35 63 72 48 24 8; these sum to 268 and this is the ninth entry in A101986, so a(9) = 6959.
		

Formula

a(n) = Sum_{k=1..n} (n+1-k)*d2(k) where d2(k) = k! if k is odd, k! - (k/2)! otherwise [with thanks to Max Alekseyev].