A356291 Number of reducible permutations.

0, 0, 1, 3, 11, 49, 259, 1593, 11227, 89537, 799475, 7917897, 86257643, 1025959345, 13234866787, 184078090137, 2746061570587, 43736283267137, 740674930879379, 13289235961616937, 251805086618856395, 5024288943352588369, 105295629327037117123

Offset: 0

Author

Peter Luschny, Aug 02 2022

Keywords

• nonn

Crossrefs

Cf. A000142, A003319, A260503.

Programs

Maple

A356291 := n -> n! - A003319(n): seq(A356291(n), n = 0..22);

Python

def A356291_list(size: int):
    F, R, C = 1, [0], [1] + [0] * (size - 1)
    for n in range(1, size):
        F *= n
        for k in range(n, 0, -1):
            C[k] = C[k - 1] * k
        C[0] = -sum(C[k] for k in range(1, n + 1))
        R.append(F + C[0])
    return R
print(A356291_list(23))
# The test predicate, not suitable for calculation:
def reducible(p) -> bool:
    return any(i for i in range(0, len(p))
        if all(p[j] < p[k]
                for j in range(0, i)
                    for k in range(i, len(p))
    ))
from itertools import permutations
for n in range(8): print(len([p for p in permutations(range(n)) if reducible(p)]))

Formula

a(n) = n! - A003319(n).

a(n) = Sum_{j=1..n-1} (n - j)!*A003319(j).

a(n) ~ n!*(2/n + 1/n^2 + 5/n^3 + 32/n^4 + 253/n^5 + 2381/n^6 + ...). This follows from Vaclav Kotesovec's formula in A003319, see A260503 for more coefficients. In particular 2*(n-1)! < a(n) for n >= 5.