A356114 Number of irreducible permutations of n with partition type [2, 1, 1, ..., 1] (with '1' taken n - 2 times).

0, 0, 0, 2, 9, 24, 55, 118, 245, 500, 1011, 2034, 4081, 8176, 16367, 32750, 65517, 131052, 262123, 524266, 1048553, 2097128, 4194279, 8388582, 16777189, 33554404, 67108835, 134217698, 268435425, 536870880, 1073741791, 2147483614, 4294967261, 8589934556, 17179869147

Offset: 0

Author

Peter Luschny, Aug 01 2022

Keywords

• nonn
• easy

Comments

Irreducible permutations in connection with partition types are discussed in A356262. Compare with the subdiagonal of A356263.

Examples

			a(4) = 9 = card({2413, 2431, 3142, 3241, 3421, 4132, 4213, 4231, 4312}). The other two permutations of type [2, 1, 1], 1432 and 3214, are reducible. That there are 11 permutations of type [2, 1, 1] we know from Euler's triangle A173018 or from its refined form A355777.
		

Links

• Index entries for linear recurrences with constant coefficients, signature (4,-5,2).

Crossrefs

Cf. A356262, A356263, A355777, A079500.

Programs

Maple

seq(`if`(n < 3, 0, combinat:-eulerian1(n, n - 2) - 2), n = 0..34);

Formula

a(n) = 2^n - n - 3 for n >= 3.

a(n) = Eulerian1(n, n - 2) - 2 for n >= 3.

G.f.: x^3*(2*x^2 - x - 2)/((x - 1)^2*(2*x - 1)).

a(n) = A356263(n, n - 2) for n >= 2.