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

Comments

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

Links

Paolo Xausa, Table of n, a(n) for n = 0..3000

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

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.

Example

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.

Maple

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

Mathematica

A356114[n_] := If[n < 3, 0, 2^n - n - 3]; Array[A356114, 35, 0] (* or *)
LinearRecurrence[{4, -5, 2}, {0, 0, 0, 2, 9, 24}, 35] (* Paolo Xausa, Feb 07 2026 *)

Crossrefs

Cf. A356262, A356263, A355777, A079500.

Sequence in context: A381632 A131357 A274543 * A079997 A351252 A275260

Adjacent sequences: A356111 A356112 A356113 * A356115 A356116 A356117

Keyword

nonn,easy

Author

Peter Luschny, Aug 01 2022

Status

approved