login
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.
1
0, 1, 3, 11, 41, 191, 1055, 6959, 53159, 462239, 4499999, 48454559, 571409999, 7321386239, 101249648639, 1502852279039, 23827244757119, 401839065331199, 7182224591270400, 135607710526041600, 2696935204633823744
OFFSET
2,3
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
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].
EXAMPLE
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.
CROSSREFS
Sequence in context: A149066 A149067 A018962 * A358426 A096147 A225431
KEYWORD
easy,nonn
AUTHOR
Eugene McDonnell (eemcd(AT)mac.com), Feb 23 2005
STATUS
approved