A341838 Number of permutations of degree n with highest Shannon entropy.

1, 2, 6, 16, 100, 72, 1764, 768, 39852, 14400, 1222100, 277632, 47179392, 8754144, 2319055200

Offset: 1

Author

Andrea G. Amato, Feb 24 2021

Keywords

• nonn
• hard
• more

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.

Examples

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

Links

• Wikipedia, Shannon Entropy

Crossrefs

Cf. A002618 (with least instead of highest).

Programs

PARI

histo(n, p) = my(d = vector(n, k, my(x = if (k(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

Extensions

a(13)-a(14) from Hugo Pfoertner, Feb 27 2021

a(15) from Hugo Pfoertner, Mar 01 2021