A new explicit formula for the determinant that contains superexponentially fewer terms than the usual Leibniz formula
The standard formula for determinants of an n×n matrix (equation 1 in the paper) is the sum of n! terms, one term for each permutation of {1..n}.
The paper details a method (equation 11) in which the sum is instead over all what they call »partial partitions of {1..n}«, denoted PP(n). I don’t know the size of PP(n), but if their claim is correct then PP(n) has exponentially less elements than S(n) (which has n! elements). I don’t see the value of |PP(n)| in the paper, but if it’s O(n^42), that would be an example of something that’s superexponentially smaller/faster. (n! is approximately n^n/e^n, the Stirling Formula.)
There’s a bit of a subtlety here, which is that the formula evaluates to zero whenever the partial partition contains a singleton. For example, the partial partitions of {1,2,3} are:
{}
{1}
{2}
{3}
{1, 2}
{1, 3}
{2, 3}
{1, 2, 3}
{1, 2} | {3}
{1, 3} | {2}
{1} | {2, 3}
{1} | {2} | {3}
{}
{1, 2}
{1, 3}
{2, 3}
{1, 2, 3}
In general the number of partial partitions of n elements that have no singleton parts is the n’th Bell number[0]. The Bell numbers grow much more slowly than the factorials, but still much faster than any polynomial.