Andrea G. Amato has authored 2 sequences.
A342140
Number of permutations of degree n with greatest sum of distances and highest Shannon entropy.
Original entry on oeis.org
1, 1, 3, 2, 17, 4, 86, 4, 488, 12, 3172, 40, 22912, 56, 166814, 256
Offset: 1
Starting from (1,2,3,4), there are only two permutations that have both the greatest sum of distances (which is 8 for n=4) and the highest Shannon entropy (which is 1.039720... for n=4). These permutations are (3,4,2,1) and (4,3,1,2).
Cf.
A007590 (greatest sum of distances of a given n).
Cf.
A062870 (permutations that possess this property).
Cf.
A341838 (number of permutations with the highest Shannon entropy).
A341838
Number of permutations of degree n with highest Shannon entropy.
Original entry on oeis.org
1, 2, 6, 16, 100, 72, 1764, 768, 39852, 14400, 1222100, 277632, 47179392, 8754144, 2319055200
Offset: 1
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].
Cf.
A002618 (with least instead of highest).
-
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
Comments