OFFSET
1,2
COMMENTS
Starting from a list of n ordered numbers, the sequence gives the number of permutations of said list with the highest Shannon entropy.
For 0 < n < 4, the Shannon entropy is 0 for every permutation, while for n >= 4 I found the maximum value of the entropy to be log(n) - log(10 - 6(-1)^n)/n. This holds for at least n=12, and I conjecture that it holds for n > 12.
Confirmed for n <= 15. - Hugo Pfoertner, Feb 27 2021
For n >= 4, in the permutations with maximum entropy, the buckets always display one 2 and n-2 1's for even n, and two 2's and n-4 1's for odd n.
n^2 divides a(n) for n >= 4.
LINKS
Wikipedia, Shannon Entropy
EXAMPLE
Suppose we have an ordered list of n elements [1,2,3,4], whose entropy is 0, since all the differences are the same.
If we consider a permutation, such as [3,4,2,1] the first step is to calculate the differences F(j+1) - F(j), where F(j) are the elements of the list. As for the final difference, we calculate F(1) - F(n). If any of the differences is negative, we add n to make it positive.
The list of differences then becomes [1,2,3,2].
The second step is to count the times each number appears in the list of differences, so 0 appears zero times, 1 appears one time, 2 appears two times, 3 appears one time and 4 zero times, so the grouped list becomes [1,2,1], since the zeros are omitted.
The third and final step to calculate the entropy is to divide each of the numbers in the grouped list by n, thus obtaining p(1),p(2),...p(k) values, which sum to 1, and the entropy is given by E = -Sum_{j=1..k} (p(j)*log(p(j))).
In this example we get a value of E = 1.0397207... for the permutation [3,4,2,1].
PROG
(PARI) histo(n, p) = my(d = vector(n, k, my(x = if (k<n, p[k+1] - p[k], p[1] - p[n])); if (x<0, x+n, x)), vd = Set(d)); vecsort(vector(#vd, k, #select(x->(x==vd[k]), d) / n));
entr(v) = - sum(k=1, #v, v[k]*log(v[k]));
a(n) = {if (n==1, return (1)); my(v = vector(n!), map = Map(), list = List()); for(i=1, n!, my(val = histo(n, numtoperm(n, i)), nb = 0); if (mapisdefined(map, val), nb = mapget(map, val), listput(list, val)); nb++; mapput(map, val, nb); ); my(vlist = apply(entr, list), ind = 0, m = -oo); for (i=1, #vlist, if (vlist[i] > m, m = vlist[i]; ind = i); ); mapget(map, list[ind]); } \\ Michel Marcus, Feb 27 2021
CROSSREFS
KEYWORD
nonn,hard,more
AUTHOR
Andrea G. Amato, Feb 24 2021
EXTENSIONS
a(13)-a(14) from Hugo Pfoertner, Feb 27 2021
a(15) from Hugo Pfoertner, Mar 01 2021
STATUS
approved