public static long stirlingS1()

in commons-numbers-combinatorics/src/main/java/org/apache/commons/numbers/combinatorics/Stirling.java [115:167]

• 35 lines of code
• 9 McCabe index (conditional complexity)

    public static long stirlingS1(int n, int k) {
        checkArguments(n, k);

        if (n < StirlingS1Cache.MAX_N) {
            // The number is in the small cache
            return StirlingS1Cache.S1[n][k];
        }

        // Simple cases
        // https://en.wikipedia.org/wiki/Stirling_numbers_of_the_first_kind#Simple_identities
        if (k == 0) {
            return 0;
        } else if (k == n) {
            return 1;
        } else if (k == 1) {
            checkN(n, k, S1_OVERFLOW_K_EQUALS_1, S1_ERROR_FORMAT);
            // Note: Only occurs for n=21 so avoid computing the sign with pow(-1, n-1) * (n-1)!
            return Factorial.value(n - 1);
        } else if (k == n - 1) {
            return -BinomialCoefficient.value(n, 2);
        } else if (k == n - 2) {
            checkN(n, k, S1_OVERFLOW_K_EQUALS_NM2, S1_ERROR_FORMAT);
            // (3n-1) * binom(n, 3) / 4
            return productOver4(3L * n - 1, BinomialCoefficient.value(n, 3));
        } else if (k == n - 3) {
            checkN(n, k, S1_OVERFLOW_K_EQUALS_NM3, S1_ERROR_FORMAT);
            return -BinomialCoefficient.value(n, 2) * BinomialCoefficient.value(n, 4);
        }

        // Compute using:
        // s(n + 1, k) = s(n, k - 1)     - n       * s(n, k)
        // s(n, k)     = s(n - 1, k - 1) - (n - 1) * s(n - 1, k)

        // n >= 21 (MAX_N)
        // 2 <= k <= n-4

        // Start at the largest easily computed value: n < MAX_N or k < 2
        final int reduction = Math.min(n - StirlingS1Cache.MAX_N, k - 2) + 1;
        int n0 = n - reduction;
        int k0 = k - reduction;

        long sum = stirlingS1(n0, k0);
        while (n0 < n) {
            k0++;
            sum = Math.subtractExact(
                sum,
                Math.multiplyExact(n0, stirlingS1(n0, k0))
            );
            n0++;
        }

        return sum;
    }