A078485 Number of irreducible indecomposable permutations of degree n.

0, 1, 1, 1, 7, 15, 31, 63, 127, 255, 511, 1023, 2047, 4095, 8191, 16383, 32767, 65535, 131071, 262143, 524287, 1048575, 2097151, 4194303, 8388607, 16777215, 33554431, 67108863, 134217727, 268435455, 536870911, 1073741823, 2147483647, 4294967295, 8589934591

Offset: 0

Author

N. J. A. Sloane, Jan 04 2003

Keywords

• nonn
• easy

Links

• Colin Barker, Table of n, a(n) for n = 0..1000
• M. D. Atkinson and T. Stitt, Restricted permutations and the wreath product, Preprint, 2002.
• M. D. Atkinson and T. Stitt, Restricted permutations and the wreath product, Discrete Math., 259 (2002), 19-36.
• Index entries for linear recurrences with constant coefficients, signature (3,-2).

Crossrefs

Cf. A134065.

Programs

PARI

concat(0, Vec(x*(1-2*x+6*x^3-4*x^4)/((1-x)*(1-2*x)) + O(x^50))) \\ Colin Barker, May 27 2016

Formula

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

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

(1, 7, 15, 31, 63, ...) = row sums of triangle A134065. - Gary W. Adamson, Oct 06 2007

a(n) = 3*a(n-1) - 2*a(n-2) for n > 2. - Colin Barker, May 27 2016