This is a follow up from my previous question: Formula for dropping dice (non-brute force) which asked how to determine the statistics for dropping the lowest die but now I'm asking how to determine the statistics when the lowest 2 dice are dropped.
So given XdY drop the lowest 2 where X is an integer of the number of dice (and is at least 3) and Y is an integer of the number of sides that the dice have (and is at least 2) what are the frequencies and probabilities (a probability mass function?) of each sum of the remaining dice? The formula must be better than O(n2) because it must be better than brute force.
Here are 2 test cases. Given 3d4 drop lowest 2 (a simple case):
Sum Frequency Probability
1 1 0.0156250000
2 7 0.1093750000
3 19 0.2968750000
4 37 0.5781250000
Which has a mean of 3.44 and standard deviation of 0.747.
Given 7d9 drop lowest 2 (a stress test):
Sum Frequency Probability
5 1 0.0000002091
6 7 0.0000014635
7 28 0.0000058541
8 84 0.0000175623
9 210 0.0000439058
10 470 0.0000982653
11 966 0.0002019666
12 1848 0.0003863709
13 3325 0.0006951749
14 5670 0.0011854561
15 9234 0.0019306000
16 14441 0.0030192544
17 21777 0.0045530297
18 31724 0.0066327003
19 44723 0.0093504683
20 61153 0.0127855731
21 81284 0.0169944652
22 105133 0.0219806986
23 132412 0.0276840598
24 162491 0.0339728315
25 194405 0.0406452561
26 226842 0.0474270270
27 258181 0.0539792334
28 286545 0.0599094412
29 310100 0.0648342065
30 327041 0.0683761488
31 335720 0.0701907121
32 335090 0.0700589947
33 324835 0.0679149290
34 305088 0.0637863218
35 276921 0.0578973019
36 242060 0.0506087328
37 202825 0.0424056689
38 161882 0.0338455047
39 122101 0.0255282859
40 85849 0.0179488933
41 55426 0.0115881997
42 32011 0.0066927049
43 15750 0.0032929337
44 5915 0.0012366796
45 1401 0.0002929143
Which has a mean of 30.56 and a standard deviation of 5.490. For comparison making this table using JavaScript brute force in Chrome took me 11 seconds.
I will accept a formula that only outputs probability but prefer one that only outputs frequency. If the formula can't be generalized into XdY drop Z then I'll ask follow up question(s) until I can get a formula for XdY drop Z (I couldn't figure out how to generalize the formula from my previous question).
Just like before I am a programmer not a statistician. It took me a while to figure out how to read each answer to my previous question. So please explain your answer plainly and show the steps taken (or better yet use well-written pseudo-code).
For reference the formula for dropping 1 die can be found here: Formula for dropping dice (non-brute force) which I implemented in JavaScript here: https://github.com/SkySpiral7/Dice/blob/7e9c69b247aeb6ef95e1f1ca2962cb52cea4c5de/src/main/javascript/beta/StackExchangeWhuber.js
Side question: The side bar linked me to Relevancy of order statistics to the roll-and-keep dice mechanic? which I don't really understand and while it is a formula for exactly what I want, the quadruple summations and choose functions make me think that it is far more computationally expensive than what I'm hoping for. Can this function be improved or is it more efficient than it looks? Otherwise I'll continue down this path of looking for an efficient formula. If this side question should instead be a full question (rather than a discussion in comments) then let me know.