Query on Pólya counting and the cycle index polynomials

[William Keith]

Seqfan:

I am considering a combinatorial problem involving Pólya
enumeration. Given a collection of objects with weight enumeration
function f(q), the Pólya enumeration theorem says that the number of
unordered t-tuples of these objects with total weight N is generated
by Z_S(f(q), f(q^2), ... , f(q^t)), where Z_S is the cycle index
polynomial of the symmetric group. This is a multivariable polynomial
in monomials named with the partitions of t, with coefficients given
by A036039. There is a formula for each coefficient in terms of the
parts and multiplicities in its indexing partition.

If I require t-tuples wherein the components are distinct, the
coefficients are the same except they now have signs: Z_S(f(q),
-f(q^2), ... , (-1)^(t-1) f(q^t)). This result is equivalent to
taking Y_S(f(q), f(q^2), ... ,f(q^t)) where the coefficients of Y_S
are the signed version of the sequence, at A324254. In terms of the
parts for each monomial, the sign is exactly (-1) raised to (t minus
length of the indexing partition). So far, this much is available in
various combinatorics textbooks, albeit the latter claim less
frequently.

I now ask what the generating function is for t-tuples wherein we
slightly loosen the distinctness condition: let no three components be
equal. This is no longer a change of signs; new numbers arise. The
resulting sequences do not currently appear to be in the OEIS. One
may also obviously loosen the distinctness condition indefinitely to
any whole number of repetitions.

The question I am asking the group in this email is whether
anyone is familiar with a method for producing the requisite
coefficients, including their signs - ideally as simple as the
partition-parts formula for A036039 and A324254. If so, I would be
happy to produce the sequences and add them, or let you if you wish.
From experimentation I believe I know what they ought to be, but at
the moment it is only a conjecture. A source which discusses the
problem would be ideal.

I believe that, compared to the original cycle index polynomials,
one adds to the coefficient of the term labeled by lambda:

(3/t!) * (-1)^(number of parts divisible by 3) * (original coefficient).

From early calculations this looks like what one would also do to get
the generating function for t-tuples with no 4 parts equal, etc.,
replacing 3 by 4 above, and so on. However, it bothers me that this is
*not* the behavior for "no 2 parts equal," for there it is known that
one only subtracts from a term when there are an odd number of even
parts in its indexing partition; one does not add anything for
partitions with an even number of even parts. Hence my query to the
group to see if people more familiar with this type of counting
problem could illuminate my path.

I here give some small examples by way of illustration.

The number of unordered pairs of objects is enumerated by

(1/2) ( f(q)^2 + f(q^2) ).

To explain this without recourse to Pólya, think of the first term as
generating ordered 2-tuples, for which we then halve the count,
allowing (a,b) and (b,a) to be considered the same; this undercounts
(a,a) by half, which we add back in with the second term, generating
at double weight. Meanwhile the number of unordered pairs of
*distinct* objects is enumerated by

(1/2) ( f(q)^2 - f(q^2) )

since we wish to remove, not reinforce, the (a,a) half.

The generating function for unordered 4-tuples, from Pólya, is

(1/24) ( f(q)^4 + 6 f(q^2) f(q)^2 + 3 f(q^2)^2 + 8 f(q^3) f(q) + 6 f(q^4) ).

Now 4-tuples, distinct parts (no 2 components the same):

(1/24) ( f(q)^4 - 6 f(q^2) f(q)^2 + 3 f(q^2)^2 + 8 f(q^3) f(q) - 6 f(q^4) ).

Notice that we subtracted from the second and last terms (partitions
(2,1,1) and (4)), but did not add anything to the term indexed by
(2,2). Again to justify without Pólya, consider the first -6, on the
(2,1,1) term. Among ordered 4-tuples, a 4-tuple {a,a,b,c} in which
exactly two components are the same would arise 12 times in
distinguishable orders in the f(q)^4 term (C(4,2) = 6 choices of
components to house the equal pair, then 2 choices of order on the
remaining distinct components); we do not want any such 4-tuple and
hence subtract 6 times the associated generating function f(q^2)
f(q)^2, in which such a 4-tuple arises twice. On the other hand, a
tuple of type (2,2), i.e. {a,a,b,b}, would arise 6 times in the first
term, and twice in the second with weight -6, meaning -6 appearances
should be cancelled; such a tuple appears twice in f(q^2)^2, so its
coefficient should be 3, the same as in the original function.

Now the newer item, 4-tuples with no 3 components the same:

(1/24) ( f(q)^4 + 6 f(q^2) f(q)^2 + 3 f(q^2)^2 - 16 f(q^3) f(q) + 6 f(q^4) ).

The one subtraction is from the (3,1) term, subtracting 24, or 3 times
the original coefficient.

On the other hand, consider t=6 parts with no 3 equal. The required
generating function, unless I have made some calculation error, makes
the following changes to the original cycle index polynomials for S_6,
listed by partition (all other components equal the originals): for
(3,1,1,1), 40 becomes -80 (we subtracted 3*40); for (3,2,1), 120
becomes -240 (we subtracted 3*120); for (3,3), 40 becomes 160 (we ADD
3*40); for (6), 120 becomes -240 (we subtracted 3*120).

The adding behavior does not occur in the distinct-components case.
So I'm wondering what is up here. Many thanks for any time someone
can provide.

Cordially,
William Keith

[Max Alekseyev]

>     I believe that, compared to the original cycle index polynomials,
> one adds to the coefficient of the term labeled by lambda:

> (3/t!) * (-1)^(number of parts divisible by 3) * (original coefficient).

Let

M_k(lambda) = number of parts in lambda divisible by k.

If we bound the multiplicities to be < r, the coefficient corresponding to lambda in the original cycle index polynomials should be multiplied by

(1-r) ^ M_r(lambda).

For example, when r=3, we get each coefficient changed to

(-2)^(number of parts divisible by 3) * (original coefficient) / t!.

In terms of addition that corresponds to adding

((-2)^(number of parts divisible by 3) - 1) * (original coefficient) / t!.

Note that numerically ((-2)^(number of parts divisible by 3) - 1) equals 3*(-1)^(number of parts divisible by 3) given by your formula only when this number of parts is 1 or 2, but then they diverge.

Regards,

Max

--
You received this message because you are subscribed to the Google Groups "SeqFan" group.
To unsubscribe from this group and stop receiving emails from it, send an email to seqfan+un...@googlegroups.com.
To view this discussion visit https://groups.google.com/d/msgid/seqfan/CA%2BG%2B0WVO-1xze-24mNvVkpJ%3DyRw3jmZRDNm1D%3DhQh3C52-prFQ%40mail.gmail.com.

[William Keith]

Thank you Max. I have tested this with t=9 and your formula appears
to be correct. I can add some of the relevant sequences when I get a
chance. I would like to use some of the resulting generating
functions in a paper, so may I ask whether you have a source for the
claim, or if you can briefly explain how I might derive it based on
the same sort of application of Pólya's theorem that is normally used
to prove the r=2 case?

Best,
William Keith

[Max Alekseyev]

You may like to refer to Proposition 5.1 in this paper: https://arxiv.org/abs/2502.00378

Regards,

Max

--
You received this message because you are subscribed to the Google Groups "SeqFan" group.
To unsubscribe from this group and stop receiving emails from it, send an email to seqfan+un...@googlegroups.com.

To view this discussion visit https://groups.google.com/d/msgid/seqfan/CA%2BG%2B0WVGNpKDiD%3Dn0hfnjMrmXmx1uVbmCcYS3ie86hrEHJH0Cw%40mail.gmail.com.

[William Keith]

Thank you Max, I believe this proposition is what I need.

Best,
William

[Jaquarious Mitchell]

--
You received this message because you are subscribed to the Google Groups "SeqFan" group.
To unsubscribe from this group and stop receiving emails from it, send an email to seqfan+un...@googlegroups.com.

To view this discussion visit https://groups.google.com/d/msgid/seqfan/CA%2BG%2B0WUYTZxD%3DqohBMVRfDCmsyE41sLYxcp5eHuHTFCq6UVQ%2Bg%40mail.gmail.com.