A182449 The number of n-permutations whose connected components have the same size.

1, 2, 4, 15, 72, 472, 3448, 29264, 273371, 2834368, 31998904, 392958758, 5201061456, 73955306224, 1123596636018, 18177574748625, 311951144828864, 5661773589217182, 108355864447215064, 2181104926663522206, 46066653269313449442, 1018706122380363766288

Offset

1,2

Comments

See A003319 for definition of connected component.

a(p) = A003319(p)+1 for all prime numbers, p.

Links

Table of n, a(n) for n=1..22.

Formula

O.g.f.: Sum_{n>0} 1/(1-A003319(n)*x^n).

Example

a(4) = 15 because there are 13 connected permutations of {1,2,3,4} (these are counted by A003319) and 21/43 and 1/2/3/4.

Mathematica

nn = 20; p = Sum[n! x^n, {n, 0, nn}]; i = 1 - 1/p; a = CoefficientList[Series[i, {x, 0, nn}], x]; s = Sum[1/(1 - a[[n + 1]] x^n), {n, 1, nn}]; Drop[ CoefficientList[Series[s, {x, 0, nn}], x], 1]

Crossrefs

Sequence in context: A020110 A290024 A292757 * A140836 A020134 A307085

Adjacent sequences: A182446 A182447 A182448 * A182450 A182451 A182452

Keyword

nonn

Author

Geoffrey Critzer, Apr 29 2012

Status

approved