Compute OEIS A161169, approximately and quickly

8

1

\$T(n, k)\$ gives the number of permutations of length \$n\$ with up to \$k\$ inversions. This values grows very quickly, for example for \$T(20, 100) = 1551417550117463564\$.

The maximum number of inversions possible is \$n\frac{n-1}{2}\$ so for \$k = n\frac{n-1}{2}\$ we know that \$T(n, k) = n!\$.

To make this task more interesting, and to allow for a wider variety of possible answers you will only have to compute \$T(n, k)\$ approximately.

Examples:

For \$n = 3\$ and \$k\$ from \$0…3\$:

0.167, 0.5, 0.833, 1.0

For \$n = 4\$ and \$k\$ from \$0…6\$:

0.042, 0.167, 0.375, 0.625, 0.833, 0.958, 1.0

For \$n = 5\$ and \$k\$ from \$0…10\$:

0.008, 0.042, 0.117, 0.242, 0.408, 0.592, 0.758, 0.883, 0.958, 0.992, 1.0

For \$n = 50\$ and \$k\$ from \$0…1225\$:

0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.001, 0.001, 0.001, 0.001, 0.001, 0.001, 0.001, 0.001, 0.001, 0.001, 0.001, 0.001, 0.001, 0.001, 0.001, 0.001, 0.001, 0.001, 0.002, 0.002, 0.002, 0.002, 0.002, 0.002, 0.002, 0.002, 0.002, 0.003, 0.003, 0.003, 0.003, 0.003, 0.003, 0.003, 0.004, 0.004, 0.004, 0.004, 0.005, 0.005, 0.005, 0.005, 0.006, 0.006, 0.006, 0.006, 0.007, 0.007, 0.007, 0.008, 0.008, 0.008, 0.009, 0.009, 0.01, 0.01, 0.011, 0.011, 0.012, 0.012, 0.013, 0.013, 0.014, 0.015, 0.015, 0.016, 0.017, 0.017, 0.018, 0.019, 0.02, 0.02, 0.021, 0.022, 0.023, 0.024, 0.025, 0.026, 0.027, 0.028, 0.029, 0.03, 0.032, 0.033, 0.034, 0.035, 0.037, 0.038, 0.039, 0.041, 0.042, 0.044, 0.046, 0.047, 0.049, 0.051, 0.052, 0.054, 0.056, 0.058, 0.06, 0.062, 0.064, 0.066, 0.069, 0.071, 0.073, 0.075, 0.078, 0.08, 0.083, 0.085, 0.088, 0.091, 0.094, 0.096, 0.099, 0.102, 0.105, 0.108, 0.112, 0.115, 0.118, 0.121, 0.125, 0.128, 0.132, 0.136, 0.139, 0.143, 0.147, 0.151, 0.155, 0.159, 0.163, 0.167, 0.171, 0.175, 0.18, 0.184, 0.189, 0.193, 0.198, 0.202, 0.207, 0.212, 0.217, 0.222, 0.227, 0.232, 0.237, 0.242, 0.247, 0.253, 0.258, 0.263, 0.269, 0.274, 0.28, 0.286, 0.291, 0.297, 0.303, 0.309, 0.315, 0.321, 0.327, 0.333, 0.339, 0.345, 0.351, 0.357, 0.363, 0.37, 0.376, 0.382, 0.389, 0.395, 0.401, 0.408, 0.414, 0.421, 0.427, 0.434, 0.44, 0.447, 0.454, 0.46, 0.467, 0.473, 0.48, 0.487, 0.493, 0.5, 0.507, 0.513, 0.52, 0.527, 0.533, 0.54, 0.546, 0.553, 0.56, 0.566, 0.573, 0.579, 0.586, 0.592, 0.599, 0.605, 0.611, 0.618, 0.624, 0.63, 0.637, 0.643, 0.649, 0.655, 0.661, 0.667, 0.673, 0.679, 0.685, 0.691, 0.697, 0.703, 0.709, 0.714, 0.72, 0.726, 0.731, 0.737, 0.742, 0.747, 0.753, 0.758, 0.763, 0.768, 0.773, 0.778, 0.783, 0.788, 0.793, 0.798, 0.802, 0.807, 0.811, 0.816, 0.82, 0.825, 0.829, 0.833, 0.837, 0.841, 0.845, 0.849, 0.853, 0.857, 0.861, 0.864, 0.868, 0.872, 0.875, 0.879, 0.882, 0.885, 0.888, 0.892, 0.895, 0.898, 0.901, 0.904, 0.906, 0.909, 0.912, 0.915, 0.917, 0.92, 0.922, 0.925, 0.927, 0.929, 0.931, 0.934, 0.936, 0.938, 0.94, 0.942, 0.944, 0.946, 0.948, 0.949, 0.951, 0.953, 0.954, 0.956, 0.958, 0.959, 0.961, 0.962, 0.963, 0.965, 0.966, 0.967, 0.968, 0.97, 0.971, 0.972, 0.973, 0.974, 0.975, 0.976, 0.977, 0.978, 0.979, 0.98, 0.98, 0.981, 0.982, 0.983, 0.983, 0.984, 0.985, 0.985, 0.986, 0.987, 0.987, 0.988, 0.988, 0.989, 0.989, 0.99, 0.99, 0.991, 0.991, 0.992, 0.992, 0.992, 0.993, 0.993, 0.993, 0.994, 0.994, 0.994, 0.994, 0.995, 0.995, 0.995, 0.995, 0.996, 0.996, 0.996, 0.996, 0.997, 0.997, 0.997, 0.997, 0.997, 0.997, 0.997, 0.998, 0.998, 0.998, 0.998, 0.998, 0.998, 0.998, 0.998, 0.998, 0.999, 0.999, 0.999, 0.999, 0.999, 0.999, 0.999, 0.999, 0.999, 0.999, 0.999, 0.999, 0.999, 0.999, 0.999, 0.999, 0.999, 0.999, 1.0, 1.0, 1.0, 1.0, 1.0, 1.0, 1.0, 1.0, 1.0, 1.0, 1.0, 1.0, 1.0, 1.0, 1.0, 1.0, 1.0, 1.0, 1.0, 1.0, 1.0, 1.0, 1.0, 1.0, 1.0, 1.0, 1.0, 1.0, 1.0, 1.0, 1.0, 1.0, 1.0, 1.0, 1.0, 1.0, 1.0, 1.0, 1.0, 1.0, 1.0, 1.0, 1.0, 1.0, 1.0, 1.0, 1.0, 1.0, 1.0, 1.0, 1.0, 1.0, 1.0, 1.0, 1.0, 1.0, 1.0, 1.0, 1.0, 1.0, 1.0, 1.0, 1.0, 1.0, 1.0, 1.0, 1.0, 1.0, 1.0, 1.0, 1.0, 1.0, 1.0, 1.0, 1.0, 1.0, 1.0, 1.0, 1.0, 1.0, 1.0, 1.0, 1.0, 1.0, 1.0, 1.0, 1.0, 1.0, 1.0, 1.0, 1.0, 1.0, 1.0, 1.0, 1.0, 1.0, 1.0, 1.0, 1.0, 1.0, 1.0, 1.0, 1.0, 1.0, 1.0, 1.0, 1.0, 1.0, 1.0, 1.0, 1.0, 1.0, 1.0, 1.0, 1.0, 1.0, 1.0, 1.0, 1.0, 1.0, 1.0, 1.0, 1.0, 1.0, 1.0, 1.0, 1.0, 1.0, 1.0, 1.0, 1.0, 1.0, 1.0, 1.0, 1.0, 1.0, 1.0, 1.0, 1.0, 1.0, 1.0, 1.0, 1.0, 1.0, 1.0, 1.0, 1.0, 1.0, 1.0, 1.0, 1.0, 1.0, 1.0, 1.0, 1.0, 1.0, 1.0, 1.0, 1.0, 1.0, 1.0, 1.0, 1.0, 1.0, 1.0, 1.0, 1.0, 1.0, 1.0, 1.0, 1.0, 1.0, 1.0, 1.0, 1.0, 1.0, 1.0, 1.0, 1.0, 1.0, 1.0, 1.0, 1.0, 1.0, 1.0, 1.0, 1.0, 1.0, 1.0, 1.0, 1.0, 1.0, 1.0, 1.0, 1.0, 1.0, 1.0, 1.0, 1.0, 1.0, 1.0, 1.0, 1.0, 1.0, 1.0, 1.0, 1.0, 1.0, 1.0, 1.0, 1.0, 1.0, 1.0, 1.0, 1.0, 1.0, 1.0, 1.0, 1.0, 1.0, 1.0, 1.0, 1.0, 1.0, 1.0, 1.0, 1.0, 1.0, 1.0, 1.0, 1.0, 1.0, 1.0, 1.0, 1.0, 1.0, 1.0, 1.0, 1.0, 1.0, 1.0, 1.0, 1.0, 1.0, 1.0, 1.0, 1.0, 1.0, 1.0, 1.0, 1.0, 1.0, 1.0, 1.0, 1.0, 1.0, 1.0, 1.0, 1.0, 1.0, 1.0, 1.0, 1.0, 1.0, 1.0, 1.0, 1.0, 1.0, 1.0, 1.0, 1.0, 1.0, 1.0, 1.0, 1.0, 1.0, 1.0, 1.0, 1.0, 1.0, 1.0, 1.0, 1.0, 1.0, 1.0, 1.0, 1.0, 1.0, 1.0, 1.0, 1.0, 1.0, 1.0, 1.0, 1.0, 1.0, 1.0, 1.0, 1.0, 1.0, 1.0, 1.0, 1.0, 1.0, 1.0, 1.0, 1.0, 1.0, 1.0, 1.0, 1.0, 1.0, 1.0, 1.0, 1.0, 1.0, 1.0, 1.0, 1.0, 1.0, 1.0, 1.0, 1.0, 1.0, 1.0, 1.0, 1.0, 1.0, 1.0, 1.0, 1.0, 1.0, 1.0, 1.0, 1.0, 1.0, 1.0, 1.0, 1.0, 1.0, 1.0, 1.0, 1.0, 1.0, 1.0, 1.0, 1.0, 1.0, 1.0, 1.0, 1.0, 1.0, 1.0, 1.0, 1.0, 1.0, 1.0, 1.0, 1.0, 1.0, 1.0, 1.0, 1.0, 1.0, 1.0, 1.0, 1.0, 1.0, 1.0, 1.0, 1.0, 1.0, 1.0, 1.0, 1.0, 1.0, 1.0, 1.0, 1.0, 1.0, 1.0, 1.0, 1.0, 1.0, 1.0, 1.0, 1.0, 1.0, 1.0, 1.0, 1.0, 1.0, 1.0, 1.0, 1.0, 1.0, 1.0, 1.0, 1.0, 1.0, 1.0, 1.0, 1.0, 1.0, 1.0, 1.0, 1.0, 1.0, 1.0, 1.0, 1.0, 1.0, 1.0, 1.0, 1.0, 1.0, 1.0, 1.0, 1.0, 1.0

Input:

One value: \$n\$.

Output:

\$\frac{T(n,\lfloor n^2/4 \rfloor)}{n!}\$ rounded to three decimal places. \$T(n, k)\$ is defined by OEIS sequence A161169.

Sample input and output

n = 3. Output: 0.833
n = 6. Output: 0.765
n = 9. Output: 0.694
n = 12. Output: 0.681
n = 15. Output: 0.651
n = 18. Output: 0.646
n = 50. Output: 0.586
n = 100. Output: 0.56
n = 150. Output: 0.549
n = 200. Output: 0.542
n = 250. Output: 0.538
n = 300. Output: 0.535

Your code should be correct no matter what values of \$n\$ and \$k\$ are given but will only be tested on \$k = \lfloor n^2/4 \rfloor \$. Your output must be within \$0.001\$ of the correct value.

Score

I will run your code on my machine: 8GB RAM, AMD FX(tm)-8350 Eight-Core Processor running Ubuntu 16.04.6 LTS.

I will test for \$n = 50, 100, 150, 200, 250, 300, 350, 400, ...\$ until it no longer completes in 10 seconds. I will also limit the RAM used to 6GB using https://github.com/pshved/timeout.

Your score is the highest \$n\$ your code can reach on my computer within the time limit. If there is a tie, the first answer wins.

Notes

Your code does not need to be deterministic. That is random sampling methods are allowed as long as they give the right answer at least 9 times out of the first 10 times I test them.

Anush

Posted 2019-10-07T18:14:13.347

Reputation: 3 202

I think the restriction that the code should work for all $(n,k)$ should be changed to for all $n$ if you only look at the cases where $k=\lfloor\frac{n^2}{4}\rfloor$ and the only required output is $\frac{T(n,\lfloor\frac{n^2}{4}\rfloor)}{n!}$. – Shieru Asakoto – 2019-10-10T00:14:33.530

2FWIW, a naive random-sampling implementation in MATLAB can get to 200 on my laptop before timing out. – HiddenBabel – 2019-10-10T07:53:52.720

1

I would suggest asking for a program that takes both $n$ and $k$ as input, so that “correct no matter what values of $n$ and $k$ are given” is not a non-observable requirement.

– Anders Kaseorg – 2019-10-11T22:21:03.643

Answers

9

Python 3 + SciPy, score ≈ 1.86 · 10103

\$T(n, k)\$ approaches the normal distribution quickly enough that we can just compute it exactly for \$n < 97\$ and use the CDF of the normal distribution for \$n \ge 97\$. This solution runs in effectively constant time. (Technically, for \$n > 1.86 \cdot 10^{103}\$ the numbers start being too large to convert to float and we start getting OverflowError. This hardly matters because the answer is 0.500 for \$n > 1500000\$ or so.)

import sys
import numpy as np
from scipy.special import erfc

n = int(sys.argv[1])
k = n * n // 4

if n < 97:
    a = np.array([1])
    for i in range(1, n + 1):
        a = np.cumsum((np.r_[a, np.ones(i)] - np.r_[np.zeros(i), a])[:-1] / i)
    out = a[k]
else:
    mean = n * (n - 1) / 4
    variance = n * (n - 1) * (2 * n + 5) / 72
    out = erfc((mean - k - 0.5) / np.sqrt(2 * variance)) / 2

print("%.3f" % (out,))

Try it online!

Anders Kaseorg

Posted 2019-10-07T18:14:13.347

Reputation: 29 242

Is it proven to approach the normal distribution? How did you figure that out? – HiddenBabel – 2019-10-11T00:36:42.497

1

@HiddenBabel Inserting $n$ into any permutation of $1, \dotsc, n - 1$ adds a number of inversions equal to $n$ minus its position. When building random permutations, this number of added inversions is an independent uniformly random number from $0, \dotsc, n - 1$. The central limit theorem tells you that when you add a large number of small enough independent random variables, the result approaches a normal distribution.

– Anders Kaseorg – 2019-10-11T00:44:45.670

Is it correct (up to the required precision) for all n and k? I will test it in about 12 hours time. – Anush – 2019-10-11T06:54:49.627

Unfortunately my internet connection has gone down so it will take me a few days until I can test this. – Anush – 2019-10-11T18:43:44.863

1@Anush Yeah, all $n$ and $k$ (if you edit the program to take $k$ as input). Although I just realized that I had forgotten to take into account the combined effect of the normal distribution approximation with the three-digit rounding, so I’ve bumped the cutoff to $n \ge 97$. The worst case is $T(97, 2217)/97! \approx 0.24598945$, where the normal distribution approximation is $0.24548087$ which rounds to $0.245$ for an error of $0.00098945$. – Anders Kaseorg – 2019-10-11T22:17:03.187

I really like the way you have done this. Have a bounty! – Anush – 2019-10-13T18:26:28.053

Asked: 2019-10-07T18:14:13.347

Viewed: 618 times

Active: 2019-10-11T22:12:48.997