Consider the set 1,2,3,4,5,6,7,8 and the equation
$a+2b+3c+4d+5e+6f+7g+8h=S$
where $a,b,c,d,e,f,g,h$ are still the set 1,2,3,4,5,6,7,8ドル$.
The 8ドル!$ permutations of a,b,..h determine the variation of S in the range [120,204]. Now, how many times S is equal, for instance, to 156 or, better, how many permutations determine S to take the value 156?
In short words, can we solve the equation above (and also determine the S distribution), without of course merely sum executing or computer using?
-
$\begingroup$ the greatest sum is 1ドル^2+2^2+3^2+4^2+5^2+6^2=204$. any sum is of the form: 1ドル(1+a_1)+2(2+a_1)+3(3+a_3)+4(4+a_4)+\dots +8(8+a_8)$ where $a_i=f(i)-i$ so 1ドル(1+a_1)+2(2+a_1)+3(3+a_3)+4(4+a_4)+\dots +8(8+a_8)=204+a_2+2a_3+3a_4...+7a_8$ $\endgroup$Asinomás– Asinomás2013年12月18日 19:04:33 +00:00Commented Dec 18, 2013 at 19:04
-
$\begingroup$ this isn't necessarily useful, just an observation $\endgroup$Asinomás– Asinomás2013年12月18日 19:05:19 +00:00Commented Dec 18, 2013 at 19:05
-
$\begingroup$ The paper "Refined inversion statistics on permutations," by J. Sack and H. Ulfarsson, might be of interest. It's available at arxiv.org/pdf/1106.1995v2.pdf $\endgroup$Barry Cipra– Barry Cipra2013年12月18日 20:47:14 +00:00Commented Dec 18, 2013 at 20:47
1 Answer 1
Interesting question.
I think you can at least restrict your search space a bit if you're looking to compute the frequency for a single value of $S$.
Take $h=8$. There are indeed some cases for which $h=8$ and $S = 156$. The minimum value for $S$ with $h=8$ is
$1ドル(7) + 2(6) + 3(5) + 4(4) + 5(3) + 6(2) + 7(1) + 8(8) = 148.$$
The value os $S$ is most sensitive to the value of $h,ドル and second-most-sensitive to the value of $g$. What if we set $h=8, g=2$? Then the minimum value of $S$ is
$1ドル(7) + 2(6) + 3(5) + 4(4) + 5(3) + 6(1) + 7(2) + 8(8) = 149.$$
Taking it further, $g = 3$ has a minimum of 151ドル,ドル and $g=4$ has a minimum of 154ドル$. But $g=5$ gives a minimum of 158ドル$ which is greater than 156ドル$. So you don't have to worry about searching any values for $h=8, g=5,6,7$. That's over two thousand cases (out of about forty thousand) you don't have to worry about.
Then, for each of $h=8, g=1,2,3,4,ドル increase the value of $f$ until your minimum exceeds 156ドル,ドル and throw those cases out.
For $h=7, g=6$ the minimum is 156ドル$. That's the only case there. You can throw away all cases for $h=7, g=8$.
For $h=6$ down, you have to check all values of $g$ based on this criterion.
Then start from the other end: $h=1$. The maximum value for $S$ is 176ドル$. Decrease $g$ to see if you can get the maximum sum below 156ドル$. And you can: $h=1, g=2$. Throw those out.
As you go along, you can also take advantage of the fact that 156ドル$ is even. You can throw away cases for which exactly one, or exactly three, of $a,c,e,g$ are odd, because the sum will be odd.
By being smart about what you calculate, you can get rid of a bunch of your cases and not cycle through all of them.
I don't see a way to get a full distribution without calculating all of them, though.