Martin Rubey
2007-06-06 09:12:45 UTC
Dear all,
Browsing Marni Mishna's thesis, I stumbled over the following very very nice
observation:
Regard the cycleIndexSeries as series in the powersum symmetric functions.
I.e., write p_i instead of x_i, as I suggested many times already.
The p_i are functions in variables t1, t2, t3, ... Expand the cycleIndexSeries
in these variables.
Then the coefficient of
t^n = t1^n1 t2^n2 t3^n3 ...
is the number of non-isomorphic colored structures using n1 times color 1, n2
times color 2, n3 times color 3, ...
-------------------------------------------------------------------------------
For example, take the cycleIndexSeries of E_2, or, in AldorCombinat parlance,
RestrictedSpecies(SetSpecies, 2):
(12) -> E2 ==> Interpret([parse "RestrictedSpecies(SetSpecies, 2)"], ACINT)
Type: Void
(13) -> coefficient(cycleIndexSeries()$E2,2)
1 2 1
(13) - x + - x
2 1 2 2
Type: SparseDistributedPolynomial(ACFraction ACInteger,CycleIndexVariable,SparseIndexedPowerProduct(CycleIndexVariable,ACMachineInteger))
Interpreting x1 as t1+t2+t3+... and x2 as t1^2+t2^2+t3^2+... we obtain
t1^2 + t2^2 + t3^2 + ... + t1 t2 + t1 t3 + t2 t3 + ...
Now, the combinatorial interpretation is as follows: there is exactly one E2
structure on {a,b}, namely {{a,b}}. We can color this (using the positive
integers as colors) as follows:
{1, 1}, {2, 2}, {3, 3}, ... {1, 2}, {1, 3}, {2, 3}, ...
By the way, if we had a package for symmetric functions, we could transform
1/2(p1^2 + p2) into h2, i.e., the complete symmetric function, from where the
combinatorial interpretation is obvious.
-------------------------------------------------------------------------------
For another example, take the cycleIndexSeries of C_3, cycles on three
elements 1/3 p_1^3 + 2/3 p_3. Expanding in terms of t1, t2, t3,... we obtain
t1^3 + t2^3 + t3^3 + ...
+ t1^2 t2 + t1 t2^2 + ...
+ 2 t1 t2 t3 + 2 t1 t2 t4 + ...
There are two cycles on {a,b,c}, namely (abc) and (acb). Coloring with one or
two colors, there is only one such colored structure:
1
/ \
1 --- 2
But when we color with three colors, we get two different structures:
1 1
/ \ / \
3 --- 2 2 --- 3
By the way, if we had a package for symmetric functions, we could transform 1/3
p_1^3 + 2/3 p_3 into s_{1,1,1} + s_{3}, i.e., the Schur functions, from where
the combinatorial interpretation is again obvious: semistandard Young tableaux
like
1 or 1 1 1 or 1 2 2 or 1 1 2 or 1 2 3.
2
3
(t1 t2 t3 t1^3 t1 t2^2 t1^2 t2 t1 t2 t3)
-------------------------------------------------------------------------------
Marni Mishna writes that this is due to Cauchy-Frobenius, i.e., (I guess)
Proposition 4.3.2 in BLL, expressing the cycle index series as sum over all
isomorphism types of the cycle index polynomials. I still have to check that.
In any case, this should be convincing evidence to write p_i instead of x_i and
interpret the cycle index series as a symmetric function.
Martin
-------------------------------------------------------------------------
This SF.net email is sponsored by DB2 Express
Download DB2 Express C - the FREE version of DB2 express and take
control of your XML. No limits. Just data. Click to get it now.
http://sourceforge.net/powerbar/db2/
Browsing Marni Mishna's thesis, I stumbled over the following very very nice
observation:
Regard the cycleIndexSeries as series in the powersum symmetric functions.
I.e., write p_i instead of x_i, as I suggested many times already.
The p_i are functions in variables t1, t2, t3, ... Expand the cycleIndexSeries
in these variables.
Then the coefficient of
t^n = t1^n1 t2^n2 t3^n3 ...
is the number of non-isomorphic colored structures using n1 times color 1, n2
times color 2, n3 times color 3, ...
-------------------------------------------------------------------------------
For example, take the cycleIndexSeries of E_2, or, in AldorCombinat parlance,
RestrictedSpecies(SetSpecies, 2):
(12) -> E2 ==> Interpret([parse "RestrictedSpecies(SetSpecies, 2)"], ACINT)
Type: Void
(13) -> coefficient(cycleIndexSeries()$E2,2)
1 2 1
(13) - x + - x
2 1 2 2
Type: SparseDistributedPolynomial(ACFraction ACInteger,CycleIndexVariable,SparseIndexedPowerProduct(CycleIndexVariable,ACMachineInteger))
Interpreting x1 as t1+t2+t3+... and x2 as t1^2+t2^2+t3^2+... we obtain
t1^2 + t2^2 + t3^2 + ... + t1 t2 + t1 t3 + t2 t3 + ...
Now, the combinatorial interpretation is as follows: there is exactly one E2
structure on {a,b}, namely {{a,b}}. We can color this (using the positive
integers as colors) as follows:
{1, 1}, {2, 2}, {3, 3}, ... {1, 2}, {1, 3}, {2, 3}, ...
By the way, if we had a package for symmetric functions, we could transform
1/2(p1^2 + p2) into h2, i.e., the complete symmetric function, from where the
combinatorial interpretation is obvious.
-------------------------------------------------------------------------------
For another example, take the cycleIndexSeries of C_3, cycles on three
elements 1/3 p_1^3 + 2/3 p_3. Expanding in terms of t1, t2, t3,... we obtain
t1^3 + t2^3 + t3^3 + ...
+ t1^2 t2 + t1 t2^2 + ...
+ 2 t1 t2 t3 + 2 t1 t2 t4 + ...
There are two cycles on {a,b,c}, namely (abc) and (acb). Coloring with one or
two colors, there is only one such colored structure:
1
/ \
1 --- 2
But when we color with three colors, we get two different structures:
1 1
/ \ / \
3 --- 2 2 --- 3
By the way, if we had a package for symmetric functions, we could transform 1/3
p_1^3 + 2/3 p_3 into s_{1,1,1} + s_{3}, i.e., the Schur functions, from where
the combinatorial interpretation is again obvious: semistandard Young tableaux
like
1 or 1 1 1 or 1 2 2 or 1 1 2 or 1 2 3.
2
3
(t1 t2 t3 t1^3 t1 t2^2 t1^2 t2 t1 t2 t3)
-------------------------------------------------------------------------------
Marni Mishna writes that this is due to Cauchy-Frobenius, i.e., (I guess)
Proposition 4.3.2 in BLL, expressing the cycle index series as sum over all
isomorphism types of the cycle index polynomials. I still have to check that.
In any case, this should be convincing evidence to write p_i instead of x_i and
interpret the cycle index series as a symmetric function.
Martin
-------------------------------------------------------------------------
This SF.net email is sponsored by DB2 Express
Download DB2 Express C - the FREE version of DB2 express and take
control of your XML. No limits. Just data. Click to get it now.
http://sourceforge.net/powerbar/db2/