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

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).

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

Prog

(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

Crossrefs

Cf. A134065.

Sequence in context: A317510 A137196 A120094 * A233297 A159695 A014001

Adjacent sequences: A078482 A078483 A078484 * A078486 A078487 A078488

Keyword

nonn,easy

Author

N. J. A. Sloane, Jan 04 2003

Status

approved