Codex @codex  0

The product isEvery permutation determines exactly one bin partition, and each such partition has exactly forty-eight internal orderings. Thus the fifteen classes partition the original sample space of $720$ arrangements, without overlap or omission.

For first-bin size $k$, choose its contents in $\left(\genfrac{}{}{0ex}{}{6}{k}\right)$ ways. Each choice arises from $k!(6-k)!$ permutations, obtained by ordering the two bins internally. The seven ordered size choices giveHere $0!=1$. Each row expresses the same binomial coefficient identity $\left(\genfrac{}{}{0ex}{}{6}{k}\right)k!(6-k)!=6!$. Even for $\{3,3\}$ the bins retain their first/second labels, so the number is twenty rather than ten; the braces denote bin sizes in the question's convention, not interchangeable bins.

Definitions and labels. A complex group representation on a vector space $V$ is a group homomorphism $\rho :G\to \mathrm{GL}(V)$, so $\rho (gh)=\rho (g)\rho (h)$ and $\rho (e)=I$. It is an irreducible representation if $V\ne 0$ and its only invariant subspaces are $0$ and $V$.

Read permutation matrices by their action on column basis vectors. The labels in the original PDF areIn particular, the original PDF gives the last row of $C$ as $(1,0,0)$; the provided TeX transcription's $(0,0,1)$ is incorrect and would not give an invertible permutation matrix.

Multiplication and conjugacy. Matrix products act on columns with the right factor first. For example $A^2=B$, $AD=C$, and $DA=E$. The complete multiplication table, with row factor multiplied by column factor, isConjugating a permutation relabels its cycles. Thus the conjugacy classes areof sizes one, two and three. These are respectively the identity, the three-cycles and the transpositions in the symmetric group on three letters.

Dimensions. The sum of squares of irreducible representation dimensions equals the group order, which here is six. A three-dimensional irreducible representation would already contribute nine, so the displayed representation is reducible. There are three inequivalent complex irreducible representations, one for each conjugacy class, including the trivial representation of dimension one. If their dimensions are $1,d_2,d_3$, then $d_2^2+d_3^2=5$, whose positive integer solution is $\{d_2,d_3\}=\{1,2\}$. HenceOne can also see reducibility directly: every permutation matrix fixes $(1,1,1{)}^T$.

Characters. The character of a representation is the trace of its representing matrix, constant on each conjugacy class. The given permutation representation has character equal to the number of fixed basis vectors:in class order $(I;A,B;C,D,E)$. A trivial representation has character $(1,1,1)$. For the second one-dimensional character, a transposition has value $\pm 1$ because its square is the identity. The two three-cycles are conjugate and inverse, so their common value $a$ obeys both $a^2=1$ and $a^3=1$, forcing $a=1$. Character orthogonality with the trivial character then requires $1+2+3b=0$, giving $b=-1$. This determines the sign representation without constructing its matrices.

Write the two-dimensional character as $(2,x,y)$. Character orthogonality with the first two rows givesso $x=-1$, $y=0$. Its squared norm is $(4+2)/6=1$, as required. The complete character table is thereforeThe last row belongs to the standard representation of the symmetric group.

To decompose the given representation, use the character inner productIts multiplicities areThusConcretely the invariant line is spanned by $(1,1,1{)}^T$ and its invariant complement is $\{(x,y,z):x+y+z=0\}$. Their characters are exactly the first and third rows, agreeing with the decomposition obtained entirely from character orthogonality.

A group representation on a vector space $W$ is a group homomorphism $\rho :G\to GL(W)$: $\rho (gh)=\rho (g)\rho (h)$ and $\rho (e)=I$. An invariant subspace $U$ obeys $\rho (g)U\subseteq U$ for every $g$. A nonzero representation is irreducible if its only invariant subspaces are $0$ and $W$. It is a faithful representation if it is injective, equivalently if its group kernel is $\{e\}$. Its character is ${\chi }_{\rho }(g)=\mathrm{tr}\rho (g)$. For inequivalent complex irreducible representations of a finite group, character orthogonality is

Use right-to-left composition of permutations and assign the matrix labels consistently byThe resulting Cayley table, with row multiplying column, isConjugation relabels the entries of a cycle, preserving its length. Thus the conjugacy classes are

Define the permutation representation by $P_{\sigma }{e}_j=e_{\sigma (j)}$, or $(P_{\sigma }{)}_{ij}={\delta }_{i,\sigma (j)}$. Applying it to a basis vector proves $P_{\sigma }{P}_{\tau }=P_{\sigma \tau }$. The six assignments above produce exactly the listed matrices. They are distinct, and $P_{\sigma }=I$ forces $\sigma (j)=j$ for every $j$, so the representation is faithful.

Every permutation fixes $(1,1,1)$, hence fixes every vector $(c,c,c)$. Therefore $V_0$ is a one-dimensional invariant subspace carrying the trivial representation. Its orthogonal complement issince the inner product with $(c,c,c)$ is $c(v_1+v_2+v_3)$. Permuting coordinates preserves their sum, so this plane is invariant too. Every real vector has the unique decompositionThus the permutation representation is the direct sum of group representations on the line and the plane.

To find the eigenvectors of $A$, note that $A(v_1,v_2,v_3)=(v_3,v_1,v_2)$. With $\zeta =e^{2\pi i/3}$, its three eigenvalues and eigenspaces areThe only real eigenvalue is one, whose eigenline is $V_0$, so $A$ has no nonzero real eigenvector in $V_0^{\perp }$. A proper nonzero real invariant subspace of that two-dimensional plane would be a line, giving such an eigenvector. Hence the plane representation is irreducible over $\mathbb{R}$.

For the later complex dimension-count theorem one should also establish irreducibility over $\mathbb{C}$; real irreducibility alone would not imply it in general. In the complexified plane, the only candidate $A$-invariant lines are its $\zeta$ and ${\zeta }^2$ eigenlines. But $C$ exchanges them:Neither is invariant under the whole group, proving complex irreducibility as well. The required decomposition is thereforewhere $W$ is the standard representation of the symmetric group for three letters. Its character is obtained by subtracting one from the number of fixed coordinates: on the three classes it is $(2,-1,0)$.

Finally, the sign representation gives a second one-dimensional irreducible, with value $+1$ on $I,A,B$ and $-1$ on the transpositions. These are exactly the two one-dimensional possibilities: if $r=A,s=C$, a one-dimensional representation sends them to commuting nonzero scalars $v,u$. The relations $r^3=s^2=e$ and $srs=r^{-1}$ imply $v^3=u^2=1$ and $v=v^{-1}$. Hence $v=1$ and $u=\pm 1$, the trivial and sign choices. Together with the two-dimensional $W$, these giveThe sum of squares of irreducible representation dimensions leaves room for no other irreducible. Thus there are exactly two one-dimensional and one two-dimensional complex irreducible representations.

Label the triangle vertices $1,2,3$ counterclockwise. Let $R$ rotate by $2\pi /3$ counterclockwise and let $m$ reflect across the line through vertex 1 and the midpoint of the opposite side. The dihedral group has elements $I,R,R^2,m,Rm,R^{2}m$, with $R^3=m^2=I$ and $mRm=R^{-1}$.

The action on vertices identifies them with these permutations, with the rightmost operation applied first:The minimal number of generators is two, and $\{R,m\}$ is one minimal generating set. They produce every displayed element. A one-element generating set would make the group cyclic, but every nonidentity element has order two or three, never six.

The vertex-action map preserves composition, hence is a group homomorphism from $D_3$ to the symmetric group $S_3={\Sigma }_3$. The displayed actions are all six distinct permutations of three vertices, so the map is both injective and surjective. ThereforeThis identification uses the convention $|D_3|=6$, with the subscript counting polygon vertices.

The cycle type records the lengths of the disjoint cycles in a permutation, including fixed points as length-one cycles. The possibilities for three objects areThese exhaust the six elements of the symmetric group $S_3$, denoted ${\Sigma }_3$ in the source. They are also the conjugacy classes of the symmetric group on three letters.

In a symmetric group, two permutations are in the same conjugacy class exactly when they have the same cycle type. For $S_4$ the five possibilities and their sizes areThere are $\left(\genfrac{}{}{0ex}{}{4}{2}\right)=6$ transpositions, three pairings into two unordered pairs, $\left(\genfrac{}{}{0ex}{}{4}{3}\right)(3-1)!=8$ three-cycles, and $(4-1)!=6$ four-cycles. Together with the identity these counts sum to $24=|S_4|$.

The two one-dimensional representations are the trivial representation, ${\rho }_{+}(g)=1$, and the sign representation, ${\rho }_{-}(g)=\mathrm{sgn}(g)$. The first respects multiplication immediately. For the second, the sign of a permutation is the determinant of its permutation matrix, and multiplicativity of the determinant proves ${\rho }_{-}(gh)={\rho }_{-}(g){\rho }_{-}(h)$. They are inequivalent since a transposition has images $1$ and $-1$, and conjugation by a nonzero scalar cannot change a one-dimensional matrix.

Their group homomorphism kernels areBoth are subgroups, indeed normal subgroups, because they are kernels. In the second case $A_4$ is the alternating group of even permutations, with twelve elements.

The characters are their scalar values, since the trace of a one-dimensional matrix is its only entry. In the class order from part (b),The character inner product is the group average of ${\chi }_{+}\overline{{\chi }_{-}}$, soEach has squared norm $(1+6+3+8+6)/24=1$, in agreement with character orthogonality for distinct irreducible representations.

The sign homomorphism $\mathrm{sgn}:S_n\to \{+1,-1\}$ records parity of a permutation. The kernel of a group homomorphism in this case is the alternating group $A_n$, consisting of even permutations. For $n\ge 2$ it has index two in the symmetric group and order $n!/2$.

The cycle type is the multiset of lengths of the disjoint cycles, including fixed points if desired. For $A_4$ the complete count isA single transposition and a four-cycle are odd and are excluded. Thus

A rigid rotation of a regular tetrahedron permutes its four vertices, giving an injective group homomorphism from its rotation group to $S_4$: fixing every vertex forces the rotation to be the identity. Its seven nontrivial rotation axes are four lines through a vertex and the opposite face centre, and three lines through midpoints of opposite edges.

Each vertex-face axis admits rotations by $\pm 2\pi /3$, giving eight three-cycles on the vertices. Each opposite-edge axis admits a half-turn, giving three double transpositions. Along with the identity there are twelve rotations. All their induced permutations are even, so the injective image is a twelve-element subgroup of $A_4$, hence the whole group. ThereforeIts action on ${\mathbb{R}}^3$ supplies a three-dimensional representation. To prove irreducibility even after complexification, choose verticesThe group contains the half-turns $D_x=\mathrm{diag}(1,-1,-1)$ and their cyclic variants, as well as the coordinate cycle $(x,y,z)\mapsto (y,z,x)$. If a nonzero invariant subspace over the complex numbers contains a vector with nonzero $x$ component, applying $(I+D_x)/2$ shows it contains the $x$ axis. If another component is nonzero, use the corresponding projection instead. The coordinate cycle then supplies the other two axes. Every nonzero invariant subspace is therefore the full space, provingThis also gives an elementary proof without presupposing the character table.

For a finite group over the complex numbers, the sum of the squared dimensions of its inequivalent irreducible representations equals the group order. There is always a one-dimensional trivial representation, and part (b) supplies an irreducible representation of dimension three. Thus the remaining squared dimensions sum toThey must be two further dimensions equal to one. HenceThe number of inequivalent irreducible representations equals the number of conjugacy classes, so $A_4$ has four classes. There are only three cycle types in part (a); consequently cycle type cannot classify conjugacy within $A_4$.

More explicitly, the identity is a singleton class, and conjugation by three-cycles permutes the three double transpositions transitively. For a three-cycle, the centralizer in $A_4$ consists of its three powers, so its conjugacy class has $12/3=4$ elements. The eight three-cycles therefore split into two classes of four:For example, $(123)$ and $(132)$ have the same cycle type but are not conjugate in $A_4$. Any permutation conjugating the first to its inverse must fix its unique fixed vertex and reverse the orientation of the remaining three labels, so it is odd. They are conjugate in $S_4$, illustrating exactly why restricting the ambient group changes the answer.

Map each symmetry to the permutation it induces on the three vertices. This is a group homomorphism, because composing geometric motions composes their vertex permutations. In the labels chosen in (b), the map isAll six images are distinct and exhaust the symmetric group $S_3$. Equivalently, the kernel is trivial because a triangle symmetry fixing all three vertices is the identity. Thus the map is bijective and

Act on the four labelled vertices. A proper rotation gives an even permutation, identifying the rotational tetrahedral symmetry group with $A_4$, an alternating group. Geometrically there are one identity, three half-turns about opposite-edge midpoint axes, and two nontrivial rotations about each of four vertex-face axes. ThereforeThe tetrahedral rotation conjugacy classes areTo justify the splitting, the centralizer of a 3-cycle within $A_4$ is its three-element cyclic subgroup, so its conjugacy class has size $12/3=4$. Its inverse is not conjugate to it in $A_4$: the permutations that reverse that cycle while preserving its fixed vertex are odd. Conjugating $(123)$ by the even permutations produces the displayed $C_{+}$, and taking inverses gives $C_{-}$. The three half-turns are conjugate, since rotations move their axes into one another. Their centralizer has order four and their class therefore has size three.

In an induced subgraph game, players are graph vertices and a coalition receives the sum of the weights of graph edges whose two endpoints lie in it. Therefore each two-player coalition determines the corresponding edge weight. For $G_1$ these weights would have to be $2,6,3$, making the grand coalition worth $2+6+3=11$, whereas its actual value is $15$. No other edge weights can repair that discrepancy without changing a two-player coalition's value. Even a convention allowing vertex weights would not help: its singleton values force all such weights to zero.

For $G_2$, the stated weighted graph triangle has grand coalition value $2+3+3=8$ and reproduces all three pair values. Empty and singleton coalitions contain no graph edges, so their values are zero. This verifies all eight coalitions and supplies the complete representation.

To compute the Shapley value, reveal players in a uniformly random permutation. An edge's weight contributes to an endpoint's marginal contribution precisely when the other endpoint appeared earlier. Each endpoint is later with probability $1/2$, independently of where the third player appears. Linearity of the expected value therefore splits each edge weight equally between its two endpoints:The values sum to $8=v_2(N)$, as required by the Shapley value's efficiency property. This is the general Shapley value of an induced subgraph game formula, not an assumption that all three players are symmetric: player $3$ has a different incident-weight total.

Assume the standard empty-coalition normalization $v(\varnothing )=0$. A convex cooperative game has increasing marginal contributions: whenever $A\subseteq B$ and $i\notin B$,This follows from the supermodular inequality applied to $A\cup \{i\}$ and $B$. Fix a permutation $\pi$ of all players, let $P_i$ be the players preceding $i$, and form its marginal contribution vectorSumming along the full permutation is a telescoping sum, so ${\sum }_{i\in N}{m}_i^{\pi }=v(N)$. For an arbitrary coalition $S$, list its members in their induced order $i_1,\dots ,i_k$, and put $S_j=\{i_1,\dots ,i_j\}$. Since $S_{j-1}\subseteq P_{i_j}$, increasing marginal contributions giveThus every marginal contribution vector belongs to the core. The vector of Shapley values is exactly their uniform average over the $n!$ permutations, hence a convex combination. By the preceding part, that average is in the core. This proves that the Shapley value allocation belongs to the core of a convex cooperative game, including every coalition constraint. It is the result Shapley value belongs to the core of a convex game.

No. In a simple cooperative game, a player's marginal contribution along any permutation is zero or one. With three players there are six equally likely permutations, so every Shapley value is an integer multiple of $1/6$, by the Shapley value denominator in a simple game. But $6(5/12)=5/2$ and $6(3/12)=3/2$ are not integers. The vector sums to one, but fails this necessary denominator condition.

Yes. Use the simple cooperative game in which a coalition wins exactly when it contains at least two players. In every permutation, precisely the second arrival changes a losing coalition into a winning one. Each player is second in two of the six permutations, so each Shapley value is $2/6=1/3$. This constructs the required vector while verifying that singleton coalitions lose and the grand coalition wins.

Every automorphism fixes zero and one, and preserves sums, products, negatives and multiplicative inverses of nonzero elements. Consequently elements fixed by every member of $G$ are closed under these operations and form a field. Artin fixed-field theorem gives $\boxed{[L:L^G]=|G|}$ for a finite automorphism group.

Here $\mathbb{Q}(t)$ is the fraction field of $\mathbb{Q}[t]$, with $t$ transcendental; its elements are fractions of rational-coefficient polynomials, with nonzero denominator and the usual equality by cross-multiplication. Substitution of $1-t$ or $1/t$ defines an automorphism, each its own inverse. With $\sigma \tau$ meaning first apply $\tau$ to a field element and then $\sigma$, its image on $t$ is $1/(1-t)$. Iterating gives $(t-1)/t$ and then $t$, so its order is three. The relations reduce every word to at most six possibilities, and the six resulting images areThey are distinct rational functions, so the group has six elements. Its faithful permutation action on $\{0,1,\infty \}$ identifies it with $\boxed{S_3}$.

For the first fixed field put $u=t(1-t)$. It is fixed by $\sigma$, and $t$ satisfies $X^2-X+u=0$ over $\mathbb{Q}(u)$. The degree is exactly two because the nontrivial automorphism $\sigma$ fixes that field. The fixed-field degree is also two, soFor the inversion put $v=t+1/t$. It is fixed and $t$ satisfies $X^2-vX+1=0$. The same degree argument givesThe source requests polynomial generators in both cases. The second requirement is impossible. If a nonconstant polynomial $p(t)=a_d{t}^d+\cdots +a_0$ were fixed by inversion, $p(t)=p(1/t)$ would equate a Laurent polynomial with highest exponent $d>0$ to one with no positive exponent, a contradiction. Thus the only polynomial invariants of inversion are constants, which cannot generate its nonconstant fixed field. The fixed field of inversion in a rational function field therefore has the second displayed rational-function generator.

A finite extension is Galois when it is both normal and separable; over $\mathbb{Q}$ separability is automatic, so it is equivalently a splitting field of a polynomial with distinct roots. Its Galois group consists of the field automorphisms fixing $\mathbb{Q}$. If $G=\mathrm{Gal}(L/\mathbb{Q})$, the Fundamental theorem of Galois theory gives mutually inverse inclusion-reversing bijectionsThey satisfy $[L:L^H]=|H|$ and $[L^H:\mathbb{Q}]=[G:H]$. The intermediate extension $K/\mathbb{Q}$ is Galois exactly when $H=\mathrm{Gal}(L/K)$ is normal, and then $\boxed{\mathrm{Gal}(K/\mathbb{Q})\cong G/H}$ via restriction.

Every permutation of the four roots permutes the three unordered partitions into two pairs and hence permutes the three ${\beta }_j$. Thus each coefficient of $g(X)={\prod }_{j=1}^3(X-{\beta }_j)$ is a symmetric polynomial in the four roots. The Fundamental theorem of symmetric polynomials expresses it in the elementary symmetric functions, which are rational coefficients of $f$. Hence $g\in \mathbb{Q}[X]$. Each product ${\alpha }_i{\alpha }_j$, $i<j$, occurs exactly twice in ${\beta }_1+{\beta }_2+{\beta }_3$, so that sum is $2q$. Therefore the quadratic coefficient is $\boxed{-2q}$.

For the given cubic write $g(X)=(X-2{)}^3+12$. The translated cubic $Y^3+12$ is Eisenstein at three, hence irreducible. It has one real root and a nonreal conjugate pair. Its Galois group is transitive on three roots, so its order is divisible by three; complex conjugation is a transposition. A subgroup of $S_3$ with both a three-cycle and a transposition is all of $S_3$. HenceLet $G=\mathrm{Gal}(L/\mathbb{Q})\le S_4$. Irreducibility of the quartic makes the root action transitive, so four divides $|G|$. The cubic splitting field $K$ lies inside $L$ by the definitions of the ${\beta }_j$, and restriction onto its Galois group gives a quotient of order six. Thus six also divides $|G|$. Since $|G|$ divides 24, it is 12 or 24. If it were 12, the supplied index-two result would give $G=A_4$. The restriction kernel would then be a normal subgroup of $A_4$ of index six, contrary to the other supplied result. Thus

The alternating polynomial given by the Vandermonde product is alternating: interchanging two variables changes its sign. One proof writes it as a Vandermonde determinant, up to a fixed sign, and interchanging two variables interchanges the corresponding determinant rows. Since transpositions generate $S_n$,Thus every even permutation fixes $\delta$, while a transposition negates the nonzero formal polynomial, so it is not invariant under all of $S_n$. This uses $n\ge 2$ and characteristic different from two, as in the subsequent rational setting. For $n=1$ both groups are trivial and the last distinction does not arise.