Partitions invariant under a permutation

franktaw at franktaw at
Sun Jul 6 02:18:29 CEST 2008

Given a permutation of n objects whose cycle structure is a partition P 
of n,
how many set partitions of n are there that are invariant under the 

(Note that it is the partition that is invariant, not the individual 
parts.  E.g., for
the permutation (1,2,3,4), the partition 1,3|2,4 is invariant; the 
interchanges the part 1,3 with the part 2,4, and the resulting 
partition is the

I believe that this sequence starts, from n=0:


in Mma order; for A&S order the n=6 line should be:


This is partly hand computed, but I am fairly confident that it is 
the formula (from the Polya Enumeration Theorem)

(Sum a(P)*A036039(P)) / n! = P(n) = A000041(n)

is satisfied.  (This is of course useless as a method for computing 
the number of terms in the summation is already P(n).)

I would like to find a reasonably efficient method for computing this 
in general.  There are some special cases that are relatively easy:

Taking T(n,k) to be a([k^n]), the kth column has e.g.f.

exp(Sum_{d|k} (exp(d*x-1)/d))

In particular, for k=1, this gives B(n) = A000110(n), the Bell numbers; 
for n=1, this gives tau(k) = A000005(k), the number of divisors.

(Note that when k is prime, this matches certain sequences in the
database with the title of "Sorting Numbers" with no further 
A002872, A002874, A0036075, A0036077, ....  There is a reference to
an article by Motzkin in these, but I don't have ready access to this.  
would help if someone would put some explanation of these in the OEIS
and/or Mathworld.  These sequences include slices of one or more "tabl"
sequences that are not in the OEIS; these should probably be added
(and would be a good place for the explanation).)

Also, a([c,1^k]) = A005493(k-1)+B(k)*tau(c); and
a([b,c]) = tau(b)*tau(c) + sigma(gcd(b,c)) where sigma is the sum of
divisors function A000203.

The general idea behind all of these formulas is that every n-cycle 
must be
partitioned into d parts, cyclically, so that d must be a divisor of n. 
 If any of
those parts are used in any other cycle, that cycle must be partitioned 
the same parts, with the same cycle (although the starting point may be
different, introducing an additional factor of d); this means that d 
must divide
both (all such) cycle sizes.  I don't see how to generalize this in any
reasonably efficient manner for arbitrary partitions, however.

I plan on submitting these two sequences -- a(P) and T(n,k) -- plus 
related ones, but I would like to know more about them first.  (I don't 
to add the "Sorting Numbers" table sequence(s) mentioned above; I 
someone else will be better able to do so.)

Franklin T. Adams-Watters

More information about the SeqFan mailing list