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,4

Links

Table of n, a(n) for n=0..22.

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.

Maple

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

Prog

(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)]))

Crossrefs

Cf. A000142, A003319, A260503.

Sequence in context: A004211 A180869 A357836 * A001339 A307030 A335788

Adjacent sequences: A356288 A356289 A356290 * A356292 A356293 A356294

Keyword

nonn

Author

Peter Luschny, Aug 02 2022

Status

approved