%I #15 Aug 04 2022 02:09:00
%S 0,0,1,3,11,49,259,1593,11227,89537,799475,7917897,86257643,
%T 1025959345,13234866787,184078090137,2746061570587,43736283267137,
%U 740674930879379,13289235961616937,251805086618856395,5024288943352588369,105295629327037117123
%N Number of reducible permutations.
%F a(n) = n! - A003319(n).
%F a(n) = Sum_{j=1..n-1} (n - j)!*A003319(j).
%F 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.
%p A356291 := n -> n! - A003319(n): seq(A356291(n), n = 0..22);
%o (Python)
%o def A356291_list(size: int):
%o F, R, C = 1, [0], [1] + [0] * (size - 1)
%o for n in range(1, size):
%o F *= n
%o for k in range(n, 0, -1):
%o C[k] = C[k - 1] * k
%o C[0] = -sum(C[k] for k in range(1, n + 1))
%o R.append(F + C[0])
%o return R
%o print(A356291_list(23))
%o # The test predicate, not suitable for calculation:
%o def reducible(p) -> bool:
%o return any(i for i in range(0, len(p))
%o if all(p[j] < p[k]
%o for j in range(0, i)
%o for k in range(i, len(p))
%o ))
%o from itertools import permutations
%o for n in range(8): print(len([p for p in permutations(range(n)) if reducible(p)]))
%Y Cf. A000142, A003319, A260503.
%K nonn
%O 0,4
%A _Peter Luschny_, Aug 02 2022