cp's OEIS Frontend

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

%I A341838 #72 Mar 01 2021 16:08:49
%S A341838 1,2,6,16,100,72,1764,768,39852,14400,1222100,277632,47179392,8754144,
%T A341838 2319055200
%N A341838 Number of permutations of degree n with highest Shannon entropy.
%C A341838 Starting from a list of n ordered numbers, the sequence gives the number of permutations of said list with the highest Shannon entropy.
%C A341838 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.
%C A341838 Confirmed for n <= 15. - _Hugo Pfoertner_, Feb 27 2021
%C A341838 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.
%C A341838 n^2 divides a(n) for n >= 4.
%H A341838 Wikipedia, <a href="https://en.wikipedia.org/wiki/Entropy_(information_theory)">Shannon Entropy</a>
%e A341838 Suppose we have an ordered list of n elements [1,2,3,4], whose entropy is 0, since all the differences are the same.
%e A341838 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.
%e A341838 The list of differences then becomes [1,2,3,2].
%e A341838 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.
%e A341838 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))).
%e A341838 In this example we get a value of E = 1.0397207... for the permutation [3,4,2,1].
%o A341838 (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));
%o A341838 entr(v) = - sum(k=1, #v, v[k]*log(v[k]));
%o A341838 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
%Y A341838 Cf. A002618 (with least instead of highest).
%K A341838 nonn,hard,more
%O A341838 1,2
%A A341838 _Andrea G. Amato_, Feb 24 2021
%E A341838 a(13)-a(14) from _Hugo Pfoertner_, Feb 27 2021
%E A341838 a(15) from _Hugo Pfoertner_, Mar 01 2021