Exercise 1 Find a proof for

\binom{n + x − 1}{n} = ∑_{a⟼n} ∏_{i=1}^{n} \frac{x^{a_{i}}}{i^{a_{i}}a_{i}!}

which is different from the one given in the lecture.

Solution

First observe that

\frac{n!}{∏_{i=1}^{n} a_{i}! ∏_{i=1}^{n} i^{a_{i}}}

is the number of π ∈ S_{n} having cycle type a = (a_{1}, …, a_{n}). This can be seen by the following combinatorial argument. Construct the cycle representation of any π with cycle type a starting with a permutation of n numbers,

π_{1}, π_{2}, π_{3}, …, π_{n−1}, π_{n}.

Next, cut out cycles according to the cycle type, giving

(π_{1}, …, π_{i})(π_{i+1}, …, π_{j}) … (π_{k}, …, π_{n}).

This gives all permutations of cycle type a, but some of them have been counted too often. First, permuting cycles of the same length does not change the permutation.

Hence the factor 1/ ∏_{i=1}^{n} a_{i}!. Secondly, every cycle of length i can be shifted to i

different representations. This explains the factor 1/ ∏_{i=1}^{n} i^{a_{i}}.

Using this counting result, we can compute

∑_{a⟼n} ∏_{i=1}^{n} \frac{x^{a_{i}}}{i^{a_{i}}a_{i}!} = \frac{1}{n!} ∑_{a⟼n} \frac{n!}{∏_{i=1}^{n} a_{i}! ∏_{i=1}^{n} i^{a_{i}}} x^{∑_{i=1}^{n} a_{i}} = \frac{1}{n!} ∑_{π∈S_{n}} x^{cn(π)}

= \frac{1}{n!} ∑_{k=0}^{n} c(n, k)x^{k} = \frac{1}{n!}x\overline{n} = \frac{(n + x − 1)\underline{n}}{n!} = \binom{n + x − 1}{n}.

The identity ∑_{k=0}^{n} c(n, k)x^{k} = x\overline{n} used in this calculation can be easily verified.

Exercise 2 Let H × G act on Y^{X}. Prove

|(H × G) \\ Y^{X}| = \frac{1}{|H||G|} ∑_{(h,g)∈H×G} ∏_{i} |Y_{h^{i}}|^{a_{i}(ḡ)}.

Solution

By the Cauchy-Frobenius-Lemma, we only need to show that the product on the right is equal to |Y_{(h,g)}^{X}|.

Consider f ∈ Y_{(h,g)}^{X}. For every x ∈ X, all values of f in the cycle of x in ḡ are determined by a single value f(x), because hf(g^{−1}x) = f(x) forces f(g^{−1}x) = h^{−1}f(x), and iteration determines the values on the entire cycle. If the cycle has length i, we end up with h^{−i}f(x) = f(g^{−i}x) = f(x), so that f(x) ∈ Y_{h^{i}}.

On the other hand, any value f(x) ∈ Y_{h^{i}} can be assigned to a canonical representative x of an i-cycle of ḡ in order to define uniquely a function f ∈ Y_{(h,g)}^{X}.

Exercise 3 Prove: |S_{[6]} \\ \{0, 1\}^{\binom{[6]}{2}}| = 156 using

|S_{[ν]} \\ X| = ∑_{a⟼ν} \frac{(k + 1)^{c_{a}}}{∏_{i} a_{i}!i^{a_{i}}}
where  c_{a} = \frac{1}{2} ∑_{i} ia_{i}^{2} − \frac{1}{2} ∑_{i odd} a_{i} + ∑_{r<s} a_{r}a_{s} gcd(r, s)

as shown in the lecture. Solution

a_{1} a_{2} a_{3} a_{4} a_{5} a_{6} c_{a} ∏_{i} a_{i}!i^{a_{i}} 3^{c_{a}} 3^{c_{a}}/ ∏_{i} a_{i}!i^{a_{i}}
6 0 0 0 0 0 15 720 32768 2048/45
4 1 0 0 0 0 11 48  2048  128/3
2 2 0 0 0 0 9  16  512  32
0 3 0 0 0 0 9  48  512  32/3
3 0 1 0 0 0 7  18  128  64/9
1 1 1 0 0 0 5  6  32  16/3
0 0 2 0 0 0 5  18  32  16/9
2 0 0 1 0 0 5  8  32  4
0 1 0 1 0 0 5  8  32  4
1 0 0 0 1 0 3  5  8  8/5
0 0 0 0 0 1 3  6  8  4/3

Σ 156 Exercise 4 Let G act on Y^{X} and g ∈ G. Let R be a ring with characteristic zero and W: Y → R. Prove:

∑_{f∈Y^{X}_{g}} ∏_{x∈X} W (f(x)) = ∏_{i=1}^{|X|}(∑_{y∈Y} W (y)^{i})^{a_{i}(ḡ)}.

Solution

f ∈ Y^{X}_{g} if and only if f is fixed on all cycles of ḡ. Therefore, for every f ∈ Y^{X}_{g}, the product in the left hand side has the form W (y_{1})^{l_{1}} ⋯ W (y_{m})^{l_{m}} where y_{i} runs over the values of the cycles of ḡ and l_{i} is the length of cycle i.

Every such product corresponds to one “distributive path” in the expansion of the right product. (The sum expresses the freedom to choose an independent value for each cycle.)