Partitions invariant under a permutation

[franktaw at netscape.net]

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 
permutation?

(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 
permutation
interchanges the part 1,3 with the part 2,4, and the resulting 
partition is the
same.)

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

1
1
2,2
2,3,5
3,3,7,7,15
2,4,5,7,12,20,52
4,3,9,9,8,10,20,31,31,67,203

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

4,3,9,8,9,10,31,20,31,67,203

This is partly hand computed, but I am fairly confident that it is 
correct:
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 
P(n);
the number of terms in the summation is already P(n).)

I would like to find a reasonably efficient method for computing this 
function
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; 
and
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 
explanation:
A002872, A002874, A0036075, A0036077, ....  There is a reference to
an article by Motzkin in these, but I don't have ready access to this.  
It
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 
into
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 
some
related ones, but I would like to know more about them first.  (I don't 
plan
to add the "Sorting Numbers" table sequence(s) mentioned above; I 
expect
someone else will be better able to do so.)

Franklin T. Adams-Watters