login
Number of reducible permutations.
5

%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