Partitions invariant under a permutation
franktaw at netscape.net
franktaw at netscape.net
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
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
More information about the SeqFan
mailing list