SOLUTIONS TO SUPPLEMENTARY EXERCISES

for Chapter 7 (symmetric functions) of

Enumerative Combinatorics, vol. 2
by Richard P. Stanley
version of 24 March 2023

Notation. The symbol ♣ denotes a request to the reader.

1. Let ν ⊢ k ≤ n. Let λ (respectively, µ) be the partition obtained from ν

by adding a part equal to n − k (respectively, n − k + 1). This bijection
ν 7→ (λ, µ) shows that f (n) = p(0) + p(1) + · · · + p(n). See also EC1,
second ed., Exercise 1.71.

2. To get a partition of rank r, take an r × r square S and two partitions

λ, µ with largest part at most r. Attach (the diagram of) λ to the right
of S and µ′ below S. This construction yields
2
tr
Fr (t) = .
(1 − t)2 (1 − t2 )2 · · · (1 − tr )2

See also EC1, second ed., Prop. 1.8.6(b).

3. Note that p1 = e1 .

4. Note that
n
X n
X
k k
(−1) 2 ek e1n−k − en1 = (−1)k 2k ek e1n−k .
k=2 k=0

The proof is now immediate from the observation that

n
Y
Fn (x) = (e1 − 2xi ).
i=1

Use the binomial theorem and the formula e2 = 21 (p12 − p2 ) (suggested

by Darij Grinberg).

1
6. By Exercise 7.48(f) we have
1
FNCn+1 = [tn ]E(t)n+1 .
n+1
But E(t) = 1/H(−t), so
1
FNCn+1 = [tn ]H(−t)−n−1 .
n+1
Now

H(−t)−n−1 = (1 + (−h1 t + h2 t2 − h3 t3 + · · · ))−n−1

X −n − 1
= (−h1 t + h2 t2 − h3 t3 + · · · )k .
k≥0
k

It is now straightforward to expand each term by the multinomial the-

orem, etc.

7. Answer : a ≥ 2. Suppose a ≥ 2. Then 1 + at + t2 = (1 + αt)(1 + βt)

where α, β ≥ 0. Now expand F (x) as in the solution to Problem 12 to
get e-positivity. Conversely, suppose that a < 2. Now α and β are not
nonnegative real numbers. Since arg(αn ) = n arg(α), it is easy to see
that for some n > 0 we have ℜ(αn ) < 0, where ℜ denotes real part.
Then the coefficient of en+1 e1 in F (x) is

[en+1 e1 ]F (x) = αβ(αn + β n ) = αn + β n = 2ℜ(αn ) < 0.

Note the subtlety of this problem: there is no λ for which the coefficient
Q
of eλ in F (x) is negative for all a < 2. For the generalization to P (xi )
where P (t) is any polynomial satisfying P (0) = 1, see Exercise 7.91(e).
For the even more general (and considerably more difficult) generaliza-
tion when P (t) is an arbitrary power series satisfying P (0) = 1, see
the references to Edrei and Thoma in the solution to Exercise 7.91(e).

8. It is not difficult to check that the coefficient of h21n−2 in eλ is ℓ(λ) − n.

Since this number is negative unless λ = h1n i, it follows that we must
have f = αen1 = αhn1 for α ≥ 0.

9. Open.

2
10. Since ω 2 = 1, the eigenvalues of ω are ±1. But if f 6= 0 and ωf = 2f ,
then f is an eigenvector for the eigenvalue 2. Hence f = 0.

11. (a) We have heλ , hµ i = Mλµ and hhλ , hµ i = Nλµ (as defined in Propo-
sitions 7.4.1 and 7.5.1). Clearly from the definitions we have
Mλµ ≤ Nλµ .
(b) We want to characterize those λ, µ for which every N-matrix with
row sum vector λ and column sum vector µ is a (0, 1)-matrix.
For any λ, µ ⊢ n it is easy to find an N-matrix A = (aij ) with
row(A) = λ, col(A) = µ, and a11 = min{λ1 , µ1 }. Hence a neces-
sary condition is that either λ = h1n i or µ = h1n i. It is easy to
see that this condition is also sufficient.

12. Let P (x) = (1 + αx)(1 + βx) · · · . Then

Y Y
ω P (xi ) = ω (1 + αxi )(1 + βxi ) · · ·
i i
! !
X X
= ω αn en β n en ···
n≥0 n≥0
! !
X X
= αn hn β n hn ···
n≥0 n≥0
1
= Q
i (1 − αxi )(1 − βxi ) · · ·
1
= Q .
i P (−xi )

One could also take logarithms and expand in terms of power sums,
etc.

13. Note that mhkj i = ej (xk1 , xk2 , . . . ). Hence by Proposition 7.7.6,

X
mhkj i = ελ zλ−1 pkλ ,
λ⊢j

where kλ = (kλ1 , kλ2 , . . . ).

14. (a) By Corollary 7.7.2 the transition matrix (Rλµ ) between the mµ ’s
and pλ ’s is upper triangular with respect to any linear extension

3
 of dominance order, with diagonal entries Rµµ = dµ . An easy
combinatorial argument shows that Rλµ is divisible by dµ . We can
perform integral elementary row operations on the matrix (Rλµ ),
except for multiplying a row by a scalar, without changing the
abelian group generated by the rows. Since dµ divides Rλµ we can
obtain the diagonal matrix (dµ ) by such row operations, and the
proof follows.
(b) The matrix Xn is the transition matrix between the sλ ’s and pµ ’s.
Since the set {sλ }λ⊢n is a basis for ΛnZ (see the first sentence after
the proof of Corollary 7.10.6), the proof follows from (a) and the
definition of Smith normal form.
For some further results along these lines, see C. Bessenrodt, J. B.
Olsson, and R. P. Stanley, J. Algebraic Combinatorics 21 (2005),
163–177; arXiv:math/040311.

15. We have
Y X
(1 + xi )α = exp α log(1 + xi )
i i
XX xni
= exp α (−1)n−1
i n≥1
n
X pn
= exp α (−1)n
n≥1
n
X
= ǫλ αℓ(λ) zλ−1 pλ ,
λ

by the exponential formula, permutation version (Cor. 5.1.9).

Q
16. Let C(x, y) = i,j (1 − xi yj )−1 . By (7.20), we have
X1
C(x, y) = exp pn (x)pn (y),
n≥1
n

from which it is immediate that

∂ pk (y)
C(x, y) = C(x, y).
∂pk (x) k

4
17. For fixed u ∈ G, the number of v ∈ G satisfying uv = vu is (by
definition) #C(u), where C(u) is the centralizer of u. By elementary
group theory, #C(u) = #G/#Ku , where Ku is the conjugacy class of
G containing u. Hence if C(G) denotes the set of conjugacy classes of
G, then
X
#{(u, v) ∈ G : uv = vu} = #C(u)
u∈G
X #G
=
u∈G
#Ku
X X 1
= (#G)
u∈K
#K
K∈C(G)

= (#G)k(G),

where k(G) denotes the number of conjugacy classes in G. For G = Sn

the answer becomes p(n)n!.

18. Since zλ = 1m1 m1 ! 2m2 m2 ! · · · , the condition that zλ 6≡ 0 (mod p) is

equivalent to λ having no parts divisible by p and no parts with mul-
tiplicity at least p. Hence
Y
Fp (x) = (1 + xk + x2k + · · · + x(p−1)k )
k≥1
p∤k
Y 1 − xpk
= .
k≥1
1 − xk
p∤k

Note that [why?] f2 (n) is the number of self-conjugate partitions of n.

19. (a) This is a result of S. Kakeya, Japanese J. Math. 4 (1927), 77–85;

www.jstage.jst.go.jp/article/jjm1924/4/0/4 0 77/ pdf.
Kakeya also conjectured the converse. See also item A007323 in
the Encyclopedia of Integer Sequences, MathOverflow 310210, and
R. Dvornicich and U. Zannier, Advances in Math. 222 (2009),
1982–2003.

5
 P Q
20. (a) Let H(t) = hn tn = (1 − xi t)−1 . Then

H(1) − H(−1)
T =
H(1) + H(−1)
P pn
P

exp n

− exp (−1)n pnn
= P pn P

exp + exp (−1) n pn
n n
P pn

P pn


exp − exp − n odd
= Pn odd pnn
P n

pn
exp n odd n + exp − n odd n

(b) Let
ex − e−x X n x2n+1
tanh x = = (−1) E2n+1 ,
ex + e−x n≥0
(2n + 1)!

where E2n+1 is an Euler number (the number of alternating per-

mutations of 1, 2, . . . , 2n + 1, as discussed e.g. in EC1, second ed.,
§1.6.). Let X pn
y= .
n odd
n
Then by (a),

T = tanh y
X y 2n+1
= (−1)n E2n+1 .
n≥0
(2n + 1)!

m1 m3 m5
P it follows easily that if λ = h1 3 5 · · · i where
From this
ℓ(λ) = mi = 2m + 1, then

(−1)m E2m+1
[pλ ]T = ,
zλ
and otherwise this coefficient is 0. For the algebraic significance
of this problem, see Exercise 7.64.

21. See the answer by Darij Grinberg at MathOverflow #403153. Is there

a more conceptual proof?

22. Since the coefficient of hµ for µ = (µ1 , . . . , µk ) (so ℓ(µ) ≤ k) in (1 +

h1 + h2 + · · · )k is just the number of permutations of the entries of

6
 the vector µ, it follows that the desired scalar product is just the total
number of N-matrices with k rows and with column sums
λ1 , λ2 , . . . .
The number of sequences (a1 , . . . , ak ) with sum s is s+k−1
s
. Hence
  
k λ1 + k − 1 λ2 + k − 1
h(1 + h1 + h2 + · · · ) , hλ i = ··· .
λ1 λ2

23. (a) Without loss of generality (since Fp is symmetric), consider the

coefficient of the monomial M = xa11 · · · xakk , where each ai > 0. If
P
p−1
a term T = i∈S xi contains M, then the coefficient of M


is the multinomial coefficient a1p−1,...,ak
. The number of p-subsets


S for which the term T contains M is 2p−1−k p−k
, the number of
(p − k)-element subsets of [2p − 1] − [k]. Now
 
2p − 1 − k (2p − 1 − k)!
= .
p−k (p − k)! (p − 1)!

Since 1 ≤ k ≤ p − 1, the numerator is divisible by p but not the

denominator, and the proof follows.
(b) Let a1 , . . . , a2p−1 ∈ Z. We have by (a) and elementary properties
of congruences that
X
#{S ⊆ [2p − 1] : i ≡ 0 (mod p) and #S = p}
i∈S
 !p−1 
X X  
1 − ≡ 2p − 1
≡ ai ≡ 1 (mod p),
S⊆[2p−1] i∈S
p
#S=p

and the proof follows. We have obtained the proofs of (a) and
(b) from W. D. Gao, J. Number Theory 56 (1996), 211–213, and
H. Pan, Amer. Math. Monthly 113 (2006), 652–654. The original
paper of P. Erdős, A. Ginzburg, and A. Ziv appeared in Bull.
Research Council Israel 10F (1961), 41–43.
(c) It is not hard to see that if λ = h1m1 2m2 · · · i then

(m1 ! m2 ! · · · )mλ ∈ Z[p1 , p2 , . . . ].

7
 (See Problem 85(a).) Let ℓ(λ) = k and λ ⊢ p − 1. By the solution
to (a) the coefficient C of mλ in Fp is
 
2p − 1 − k (p − 1)!
C= Q .
p−k λi !

Now
(p − 1)!
Q Q
( λi !) ( mi !)
is just the number of partitions of [p−1] with block sizes λ1 , λ2 , . . .
and is hence an integer. Thus

(p − 1)!
Q mλ ∈ Z[p1 , p2 , . . . ].
λi !
2p−1−k


Since p−k
≡ 0 (mod p), the proof follows.

24. (a) By linearity it suffices to do this for a fixed basis uλ . The easiest
choice is uλ = pλ . If λ ⊢ n, then

pλ (kx) = k ℓ(λ) pλ (x).

We could also observe that the stated formula is clear when j, k ∈

P and use the fact that a polynomial in one variable over a field of
characteristic 0 is determined by its values at the positive integers.
(b) Again it suffices to choose f (x) = pλ (x), for which the compu-
tation is trivial. Note in fact that f g(kx) = f (kx)g(kx), so the
operation f (x) 7→ f (kx) is in fact an endomorphism (in fact, an
automorphism) of ΛQ . Hence it actually suffices to take f = pn .
(c) Since both the operations f (x) 7→ f (kx) and ω are linear, it suf-
fices to take f (x) = pλ (x) (or even pn (x) as discussed in (b)). Now
for λ ⊢ n we have

pλ (−x) = (−1)ℓ(λ) pλ (x) = (−1)n ωpλ (x).

Hence f (−x) = (−1)n ωf (x) for all f ∈ ΛnQ .

Note in particular

the “reciprocity”


en (−x) = (−1)n hn (x), an
−N N
extension of n = (−1)n n .

8
25. Since hhλ , mµ i = δλµ , it follows from Proposition 7.5.1 that hhλ , hµ i =
Nλµ . Hence we want the number of N-matrices A with row and column
sum vector (2, 1n−2, 0, 0, . . . ). If A11 = 2, then subtracting 1 from A11
yields an (n − 1) × (n − 1) permutation matrix, of which there are

2
(n − 1)!. If A11 = 0 there are n−2 2
(n − 4)! matrices. Adding these
two numbers gives (n2 − n + 2)(n − 2)!/4.
Another method: use h2 = 21 (p21 + p2 ). Hence

1 n
hh2 h1n−2 , h2 h1n−2 i = hp1 + p2 p1n−2 , pn1 + p2 p1n−2 i
4
1
= (zh1n i + zh2,1n−2 i ),
4
etc.

26. The linear transformation defined by eλ 7→ hλ +eλ is just ω +I (where I

is the identity transformation), so we want to compute rank(ω+I). Now
ω is an involution and hence diagonalizable (its minimal polynomial has
distinct roots). The eigenvalues of ω are ±1. Hence rank(ω + I) is the
number of eigenvalues of ω equal to 1. By the argument near the end of
Section 7.7, this is equal to the number e(n) of even conjugacy classes
of Sn . See Exercise 1.22(b) (together with Proposition 1.8.4) for the
generating function of e(n).

27. (a) The matrix of ϕ−1 with respect to the basis {mλ } is the matrix M
of Section 7.4. By a simple result of linear algebra, M and M −1
have the same Jordan block sizes. By Theorem 7.4.4 the matrix
M is upper triangular with 1’s on the main diagonal. Hence the
size of the largest Jordan block of ϕ is the least integer m for
which (M − I)m = 0. Again by Theorem 7.4.4 we have Mλµ = 0
unless µ ≤ λ′ . By Proposition 7.4.1 and the Gale-Ryser theorem
(a basic combinatorial result which everyone should know) the
converse is true, i.e., Mλµ > 0 if µ ≤ λ′ . Since all entries of M are
nonnegative, there is no cancellation in the computation of powers
of M − I. It follows that m is the size of the longest chain in the
poset Par(n), ordered by dominance. Now use Exercise 7.2(f).
(This exercise gives the length of the longest chain, so you need to
add 1 to get the size.) For some further work on chains in Par(n),
see E. Early, Discrete Math. 313 (2013), 2168–2177.

9
 (b) Define µ1 , µ2 , . . . by setting µ1 +µ2 +· · ·+µi equal to the number of
elements in the largest union of i chains of Par(n) (with the domi-
nance order). If the nonzero entries of M above the main diagonal
were generic, then a theorem of Gansner and Saks (independently)
shows that the Jordan block sizes of M are µ1 , µ2 , . . . . It seems
plausible that M is “sufficiently generic” for the Gansner-Saks re-
sult to hold for M itself, but we don’t know how to show this. (An
interesting consequence: corank(M − I) (= p(n) − rank(M − I)) is
the size of the largest antichain in Par(n). I don’t know whether
anyone has looked at the problem of determining this size.) Re-
gardless, is there an explicit formula for the numbers µ1 , µ2 , . . . ?

28. (a) Since ω is an isometry and an involution, we have

hωf, gi = hω 2f, ωgi = hf, ωgi.

Hence ω, and thus also ω + aI, is self-adjoint.

(b) It is easy to verify by considering the basis {pλ } that the adjoint
∂
p⊥
j to Mj is j ∂pj .

29. We want to count SSYT’s of shape (k, k, k) with k − 1 1’s, k − 1 2’s,

and one 3, 4, . . . , k + 4. The 1’s must go into
the first row. If all the 2’s
are in the second row, then there are k+1 2
choices for the remaining
numbers. Suppose there is one 2 in the first row and k − 2 in the
second row. The hook-length formula (Corollary 7.21.6) makes it easy
to count the possibilities, but we can also give a naive argument. Given
an SSYT of shape (k, k, k) and type (k − 1, k − 1, 1k+2) with all the
2’s in the second row (as counted above), interchange the last 2 in the
second row with the last element of the first row. This will give an
SSYT with one exception, when the last column is (k + 2, k + 3, k + 4),
and the correspondence is reversible. Hence
   
k+1 k+1
K(k,k,k),(k−1,k−1,1k+2) = + −1
2 2
= k 2 + k − 1.

30. (a) Let T be the 180◦ rotation of a semistandard tableau of shape

hk n i/λ and content h(k − 1)n i. (Note that by Exercise 7.56(a),

10
 for any skew θ and 180◦ rotation θr , and for any partition µ, we
have Kθ,µ = Kθr ,µ .) Let T ′ be the tableau of shape λ whose ith
column consists of the elements of [n] not in column k + 1 − i of
T , arranged in increasing order. For instance, suppose that k = 4,
n = 6, λ = (4, 2), and

1 1 1 3
2 2 2 4
T = 3 3 4 5 .
4 5 6 6
5 6

Then
1 3 4 6
T′ = .
2 5
It is easy to check that the map T 7→ T ′ is a bijection from SSYT
of shape hk n i/λ and content h(k − 1)n i to SYT of shape λ.
(b) We have
X
Khkn i,h(k−1)n ,1n i = Kλ,h1n i Khkn i/λ,h(k−1)n i
λ⊆hk n i
λ⊢n
X
2
= fλ
λ⊆hk n i
λ⊢n
X
2
= fλ .
λ⊢n
λ1 ≤k

′
By Corollary 7.23.12 (using f λ = f λ ), the last expression is equal
to the number of permutations in Sn with no increasing subse-
quence of length k + 1.

31. See math.mit.edu/∼rstan/papers/sfcong.pdf. There are a number

of open problems and further directions for research in this area that
may be interesting to pursue.
    
2 4 2(n − 1)
32. Answer: ···
1 2 n−1

11
 P
33. Since hµ = λ Kλµ sλ
we have
X X
g(λ)sλ = hµ
λ µ
Y
= (1 − hn )−1 .
n≥1

See MathOverflow #18597.

34. (a) Let E(i) denote the expected number of i’s among all SSYT of
shape λ and largest part at most n, for 1 ≤ i ≤ n. Then

|λ| = d = E(1) + E(2) + · · · + E(n).

Since sλ is a symmetric function we have E(1) = E(2) = · · · =

E(n). Hence E(i) = d/n for all 1 ≤ i ≤ n.
(b) First note that

∂ k sλ (x1 ,...,xn )
∂xk1 x1 =···=xn =1
Bλ,n (k) = .
k! sλ (1n )

Thus
X sλ (t + 1, 1n−1 )
Bλ,n (k)tk = ,
k≥0
sλ (1n )

by Taylor’s formula (Exercise 1.167 of EC1, second ed.).

Now in equation (27) put x1 = t and x2 = · · · = xn = 0. Since
sµ (t, 0, 0, . . . ) = 0 unless µ = k (where we abbreviate the partition
(k) as k), we get
X
sλ (t + 1, 1n−1) = dλk sk (t, 0, 0, . . . )
k
X
= dλk tk .
k

Hence
dλk
Bλ,n (k) = .
sλ (1n )

12
 The solution to Problem 87 shows that
Q
f λ/k u∈λ/k (n + c(u))
dλk = .
(d − k)!

Then Bλ,n (k) simplifies straightforwardly to the claimed formula

using Corollary 7.21.4.
(c) Using (a) and (b), the expected value of m1 (T )2 is given by

2d(d − 1) f λ/(2) d
2Bλ,n (2) + Bλ,n (1) = λ
+ .
n(n + 1) f n

(d) By the combinatorial definition of skew Schur functions (Defini-

tion 7.10.1) the right-hand side is equal to Bλ,n (k), so the proof
follows from (b).

35. See Y. Baryshnikov and D. Romik, Israel J. Math. 178 (2010), 157–186;
arXiv:0709.0498 (Theorem 1). For a simpler approach to counting
f λ/µ for some similar problems including αn , see R. Stanley, Electronic
J. Combinatorics 18 (2011-2), P16.

36. Follows from Theorem 10.3 of J. S. Kim, K.-H. Lee, and S.-J. Oh,
(3,3)
arXiv:1703.10321. (There is a typo in Theorem 10.3: |S2m−1 | should
(3,3)
be |S2m+1 |.) (Private communication from Jang Soo Kim, 30 August
2018.)

37. (a) Hint. Apply the exponential specialization.

38. See A. Okounkov and G. Olshanski, Algebra i Analiz 9 (1997), 73–146

(Russian); English translation, St. Petersburg Math. J. 9 (1998), 239–
300; arXiv:q-alg/9605042 (Thm. 8.1 and Thm. 11.1). A q-analogue of
this result was obtained by X. Chen ( ) and R. Stanley, Annals
of Combinatorics 20 (2016), 539–548;
math.mit.edu/∼rstan/papers/q-oo.pdf.
Problem 102 is a special case.

39. (a) Note that (b) is a restatement of (a) using the code Cλ of Exer-
cise 7.59. We are also using part (b) of Exercise 7.59 (in the re-
verse form of adding rather than removing a border strip). Hence

13
 it suffices to prove (b). Suppose that there are k integers j < b
for which f (j) = 1. Then by definition of a and b, the only pos-
sible values of j for which f (j) = 1 and f (j − n) = 0 are the k
integers j < b for which f (j) = 0, together with the n integers
b + 1, b + 2, . . . , b + n. The only ones which fail to have the desired
property are those of the form j + n where j < b and f (j) = 1.
Thus the number of integers j for which f (j) = 1 and f (j −n) = 0
is (n + k) − k = n.

40. Let the successive maximum size border strips be D1 , . . . , Dk , so Dk is

the “innermost” border strip. Let Dk correspond to the composition
α1 , i.e., Dk = Bα1 in the notation of §7.23 of EC2. Then Dk−1 can be
decomposed into three (nonempty) border strips in a canonical way,
where the middle border strip corresponds to α1 . Let the two other
border strips correspond to α2 and α3 . Continuing this construction
to Dk−2 , we decompose it into three border strips with (an isomorphic
copy of) Dk−1 in the middle, and border strips corresponding to α4
and α5 at the ends. The middle Dk−1 decomposes into border strips
corresponding to α1 , α2 , α3 . At the end of this process, the skew shape
is decomposed into k copies of α1 , k −1 copies of α2 and α3 , k −2 copies
of α4 and α5 , etc. The process can be reversed given α1 , . . . , α2k−1 .
Example. The figure below shows a skew shape of depth three. The
innermost border strip has squares labelled 1. The next innermost has
squares labelled 1* that duplicate 1, and two further pieces that are
border strips, labelled 2 and 3. Finally the outermost border strip (the
first one removed) duplicates 1 with 1’, 2 with 2’, 3 with 3’, and has 4
and 5 in addition.

14
 4
2 4 4 4
1 2 2’
1 1 1* 2’
1 1* 1* 1’
3 3 1* 1’ 1’
3 3 3’ 3’ 1’
5 3’ 3’
5

We obtain
X 1 |+(k−1)(|α2 |+|α3 |)+(k−2)(|α4 |+|α5 |)+···+(|α2k−2 |+|α2k−1 |)
Bk (x) = xk|α ,
α1 ,...,α2k−1

where α1 , . . . , α2k−1 are nonempty compositions. It follows easily that

2
xk
Bk (x) = Qk−1 .
(1 − 2xk ) i 2
i=1 (1 − 2x )

41. (a) See Figure 7-5 (Section 7.15), where ν = λ and ρ = ∅.

(b) Using (a) (extended to a product of finitely many Schur functions)
and the fact that hν = sν1 sν2 · · · , we have for suitable ρ, σ that
Kλ/µ,ν = hsλ/µ , hν i = hsλ , sµ hν i = hsλ , sρ/σ i = cρλσ .

42. (a) For λ ⊢ n let ϕλ be an irreducible matrix representation of Sn

with character χλ , such that ϕλ (w) is a matrix of integers for each
w ∈ Sn . (It is known that such representations exist. A good
reference is B. Sagan, The Symmetric Group.) For each ρ ⊢ n let
c̃ρ denote the sum (in the group algebra Z[Sn ]) of all elements in
Sn of cycle type ρ. Then c̃ρ commutes with each w ∈ Sn , so by
a basic result in representation theory (Schur’s lemma) ϕ(c̃ρ ) is a
scalar multiple of the identity matrix, say
ϕ(c̃ρ ) = ωρλ Id , (17)

15
 where ωρλ ∈ Z and d = n!/Hλ , the degree of χλ . Taking traces in
equation (17) yields
n! λ n! λ
χρ = ω .
zρ Hλ ρ
Therefore
Hλ λ
ωρλ = χ
zρ ρ
is an integer for all λ, ρ. The desired result follows easily.
A p-integral formula for Hλ sλ was given by Hanlon, J. Comb.
Theory Series A 47 (1988), 37–70 (Property 3 on page 63).
(b) Immediate from Problem 38, but this is cheating. For an elemen-
tary proof, for a ∈ Λn let a⊥ denote the adjoint to multiplication
by a, i.e., ha⊥ b, ci = hb, aci for all b, c ∈ Λ. It’s easy to check (by
verifying it for a = pλ , b = pµ , and c = pν , and using linearity)
that if we write a as a polynomial a(p1 , . . . , pn ) in p1 , . . . , pn , then
 
⊥ ∂ ∂ ∂
a =a ,2 ,3 ,... .
∂p1 ∂p2 ∂p3
For a partition ρ, define the differential operator
∂ ∂
Dρ = ··· .
∂pρ1 ∂pρ2
Then

sλ/µ = s⊥
µ sλ
!
X 1 X
= zρ−1 χµ (ρ)1m1 (ρ) 2m2 (ρ) · · · Dρ dλσ pσ ,
ρ
Hλ σ

where dλσ ∈ Z by (a). Carrying out the differentiation gives

sλ/µ =
1 X
dλσ zρ−1 χµ (ρ)1m1 (ρ) 2m2 (ρ) · · · (m1 (σ))m1 (ρ) (m2 (σ))m2 (ρ) · · · pσ−ρ .
Hλ σ,ρ
Now the falling factorial (mi (σ))mi (ρ) is divisible by mi (ρ)!. Hence

zρ−1 1m1 (ρ) 2m2 (ρ) · · · (m1 (σ))m1 (ρ) (m2 (σ))m2 (ρ) · · · ∈ Z,

16
 so we have
1 X
sλ/µ = gλσ pσ−ρ
Hλ
for some integers gλσ . Now take the coefficient of x1 x2 · · · xn−k
on both sides. The coefficient of x1 x2 · · · xn−k in pν is 0 unless
ν = h1n−k i, in which case the coefficient is (n − k)!. Thus for some
integer g we get
1
f λ/µ = g · (n − k)!,
Hλ
so
Hλ f λ/µ (n)k f λ/µ
g= = ,
(n − k)! fλ
completing the proof.
Is there a simpler proof?
Greta Panova has pointed out that the proof also follows immedi-
ately from Naruse’s formula (Problem 43) for the number of SYT
of skew shape λ/µ. In fact (using notation from Problem 43),
(n)j f λ/µ Y Y
= h(u).
fλ u∈E
E∈(λ/µ)

43. This formula is due to Hiroshi Naruse, 73rd Sém. Lothar. Combin.,
2014; www.emis.de/journals/SLC/wpapers/s73vortrag/naruse.pdf.
It has led to a lot of subsequent work. In particular, a q-analogue ap-
pears in a paper by A. H. Morales, I. Pak, and G. Panova, J. Combin.
Theory, Ser. A 154 (2018), 26–49, arXiv:1512.08348. Morales et al.
have written (at least) three sequels to this paper.
44. This result was conjectured by P. McNamara (after the k = 1 case was
conjectured by S. Assaf and then proved independently by S. Assaf and
R. Stanley) and proved combinatorially by S. Assaf (March, 2009). See
S. Assaf and P. McNamara (with an appendix by T. Lam), J. Comb.
Theory Ser. A 118 (2011) 277–290; arXiv:0908.0345. For a continua-
tion, see T. Lam, A. Lauve, and F. Sottile, Int. Math. Res. Not. IMRN
6 (2011), 1205–1219; arXiv:0908.3714. For a skew Murnaghan-Naka-
yama rule and a q-analogue, see M. Konvalinka, J. Alg. Combinatorics
35 (2012), 519–545; arXiv:1101.5250. For further work in this area,
see V. Tewari and S. van Willigenburg, Advances in Applied Math. 100
(2018), 101–121.

17
45. (a) This result is due to J. N. Bernstein and appears in Macdon-
ald [7.96, Exam. I.5.29.b.5]. See M. Zabrocki, J. Alg. Comb. 13
(2000), 83–101, arXiv:math/9904084, for a host of related results.
(b) If we apply RSK to w, we get precisely those pairs (P, Q) of SYT
with at most n − k columns, and for which the first row of Q is
1, 2, . . . , n − k. Hence
X
fk (n) = f (n−k,λ) f λ .
λ⊢k

By (a),
X X
fk (n) = [x1 · · · xn y1 · · · yk ] (−1)i hn−k+i (x)ei (x)⊥ sλ (x)sλ (y).
i≥0 λ⊢k

By Exercise 7.27(c) and the Cauchy identity we get

X Y
fk (n) = [x1 · · · xn y1 · · · yk ] (−1)i hk+i (x)ei (y) (1 − xi yj )−1 ,
i≥0

etc. This result is due to A. Garsia and A. Goupil, Electronic J.

Combinatorics 16(2) (2009), R19.
(c) See G. Panova, Discrete Mathematics and Theoretical Computer
Science Proceedings (2010), arXiv:0905.2013.

46. Let ℓ(µ) = ℓ. The first column of λ consists of 1 and any n − k of the
numbers 2, 3, . . . , ℓ. Hence
 
ℓ−1
K(k,1n−k ),µ = .
n−k

47. There are various ways to describe P and Q. One elegant description
(though perhaps not the best for proving correctness) is to fill in each
tableau in the order (1, 1), (1, 2), (2, 1), (1, 3), (2, 2), (3, 1), . . . , always
using the least number available that keeps the columns strictly increas-
ing, and ignoring any positions that cannot be filled. For instance, if
m = 4 and n = 3, then the numbers that go into P are 111122223333.
First let P11 = 1, then P12 = 1, then P2,1 = 2, etc. Note that no
number is available for P41 , so we continue with P15 = 2, etc.

18
48. (a) Call an SYT T shiftable if it becomes an SHSYT by pushing the
ith row of T i − 1 squares to the right, for all i ≥ 1. The key fact
is that for each W -equivalence class X, there is a unique shiftable
SYT that is the insertion tableau of some w ∈ X. For further
details, see D. Worley, Ph.D. thesis, M.I.T., 1984 (Theorem 6.2.2).
Worley’s result has never been published.
♣ Has someone else published this result?
(b) One possible example of an “interesting way” is to fix k ≥ 1
and define two permutations u, v ∈ Sn to be Wk -equivalent if
they have the same insertion tableau and the same set of their
first k elements (when written as words). Or perhaps the first
k elements of u (in order) should be the reverse or inverse (after
standardizing) of the first k elements of v.
49. (a) Given w1 w2 · · · wn , insert w1 , w2 , . . . , wn successively into an in-
sertion shifted tableau P as follows. Use ordinary row insertion
as long as a diagonal element (i.e., the first element of some row)
is not bumped. As soon as a diagonal element is bumped, switch
to column insertion. Define a recording shifted tableau Q by in-
serting 1, 2, . . . , n into Q to keep the same shape as P (just as in
ordinary RSK). Moreover, if the new position in P was obtained
by a column-insertion (i.e., if sometime in the bumping process a
diagonal element was bumped) then circle the corresponding ele-
ment of Q. This sets up a bijection between Sn and pairs (P, Q)
of shifted SYT of the same shape λ |= n, and with some subset of
the n − ℓ(λ) nondiagonal elements of Q circled, thereby proving
(2). For instance, if w = 2651743 then P is built up as follows:

2 26 25 125 1257 1247 123 67

.
6 6 6 56 45

Moreover, Q is given (with an element underlined instead of cir-

cled) by
12457
.
36
This bijection is due to D. Worley, Ph.D. thesis, M.I.T, 1984 (§6.1)
(in the more general context of semistandard shifted tableaux) and
B. Sagan, J. Combinatorial Theory (A) 45 (1987), 62–103.

19
 (b) Equation (3) is a formal consequence of the following facts, which
are not difficult to verify. Let Vn be the complex vector space with
basis {λ : λ |= n}. Define linear transformations Un : Vn → Vn+1
and Dn : Vn → Vn−1 by
X X
Un (λ) = µ+ζ ν
µ ν
√ X X
Dn (λ) = 2 σ+ζ τ,
σ τ

where (i) λ ⊂ µ |= n + 1 and ℓ(µ) = ℓ(λ), (ii) λ ⊂ ν |= n + 1 and

ℓ(ν) = ℓ(λ) + 1, (iii) λ ⊃ σ |= n − 1 and ℓ(σ) = ℓ(λ), and (iv)
λ ⊃ τ |= n + 1 and ℓ(τ ) = ℓ(λ) − 1. Let In denote the identity
operator on Vn . Then

Dn+1 Un − Un−1 Dn = In
   
X X X
Dn+1  λ = Un−1  λ + ζ λ.
λ|=n+1 λ|=n−1 λ|=n

This result is due to Mark Haiman. For further details, see R.

Stanley, in Invariant Theory and Tableaux (D. Stanton, ed.), The
IMA Volumes in Mathematics and Its Applications, vol. 19, Springer-
Verlag, New York, 1990, pp. 145–165 (§3).
This problem just scratches the surface of the theory of shifted shapes.
Practically anything that can be done for ordinary shapes has a shifted
analogue (including the connections with representation theory). See
Problem 50 below for further examples.

50. (a) Analogous to the Bender-Knuth proof that sλ is a symmetric func-

tion.
(b) Clearly we want a “shifted analogue” of RSK. See the thesis of
Worley or paper of Sagan (Cor. 8.3) cited in #49 above.
(c) Analogous to the proof of Theorem 7.20.1, using the same method
of merging two strict partitions with the same number of parts into
a single partition. This result is due to O. Foda and M. Wheeler,
BKP plane partitions, J. High Energy Phys. (2007), 075, and M.
Vuletić, Shifted Schur processes and asymptotics of large random

20
 strict plane partitions, Int. Math. Res. Not. (2007), rnm043. For
a generalization, see M. Vuletić, A generalization of MacMahon’s
formula, Trans. Amer. Math. Soc. 361 (2009), 2789–2804.

51. See mathoverflow.net/questions/193459.

52. Given a skew SYT of shape λ/2, add 2 to each entry and fill in the
two “missing” squares with 1,2 from left-to-right. This gives a bijection
with SYT of shape λ such that 2 appears in the first row. Thus the
first sum is equal to the number of w ∈ Sn such that under RSK the
insertion tableau has a 2 in the first row. This will be the case if and
only if 2 follows 1 in w (i.e., w −1 (2) > w −1(1)). There are n!/2 such
permutations, so X
f λ/2 f λ = n!/2. (18)
λ⊢n

By similar reasoning, the second sum is given by the number of w ∈ Sn

such that w −1 (2) > w −1 (1) and w(2)
> w(1). If neither w(1) nor w(2)
equals 1 or 2, then there are 21 n−2
2
(n − 2)! such permutations. We
can never have w(2) = 1. If w(1) = 1 then there are (n − 1)! such
permutations. Hence
X  


λ/2 2 1 n−2
f = (n − 2)! + (n − 1)!
λ⊢n
2 2
1 2
= (n − n + 2)(n − 2)!. (19)
4
Alternative proof of (19). Given a skew SYT of shape λ/2, add
1 to each entry and fill in the two missing squares with 1’s. This gives a
bijection with SSYT of shape λ and type (2, 1n−2 ). The RSK algorithm
shows that the number of pairs of such SSYT of the same shape is equal
to the number of N-matrices with row and column sum vector (2, 1n−2 ).
This was enumerated in the solution to Problem 25. (Equation (18)
can also be obtained in this way.)

53. (a) See Theorem 4.3 of A. Reifegerste, arXiv:math/0309266. The

key lemma for the proof is that any Knuth transformation (Ap-
pendix 1, Definition A.1.1.3 of EC2) reverses the sign of the record-
ing tableau.

21
 (b) From (a) we get
X
0 = sgn(w)
w∈Sn
X X
= (−1)v(λ) sgn(P ) · sgn(Q)
λ⊢n (P,Q)
X
= (−1)v(λ) Iλ (−1)2 .
λ⊢n

This result was first proved for n even by R. Stanley, Advances in

Applied Math. 28 (2002), 282–284 (Theorem 3.2(b)); arXiv:math/
0211113. The result for any n is due independently to Reifegerste
(cited above) and (in more general form) by T. Lam, J. Comb.
Theory Ser. A 107 (2004), 87–115 (Theorem 23); arXiv:math/
0308265. See also the footnote to Conjecture 3.3 of the paper of
Stanley.
rsk
54. (a) By Exercise 7.28(a), if w ∈ Sn is an involution and w → (P, P ),
then the number of fixed points of w is the number of columns
of
P P of oddλ length. Hence (after transposing P ) we see that
λ⊢n o(λ)f is the total number of fixed points of all involutions
in Sn . Since i is a fixed point in tn−1 involutions, the total number
of fixed points in all involutions in Sn is ntn−1 .
(b) By Corollary 7.15.9 we get
* +
X
d(λ) = sλ/1 , sµ .
µ⊢n−1

22
 Hence
* * + +
X X X X
d(λ)f λ = f λ sλ , sλ/1 , sµ sλ
λ⊢n λ⊢n λ⊢n µ⊢n−1
* * + +
X X
= pn1 , sλ , p1 sµ sλ
λ⊢n µ⊢n−1
* +
X X
= sλ , p1 sµ f λ (since hpn1 , sλ i = f λ )
λ µ⊢n−1
* +
X
= pn1 , p1 sµ .
µ⊢n−1

Since the operation ∂p∂ 1 is adjoint to multiplication by p1 (see the

solution to Exercise 7.35(a)), we get
* +
X X
λ n−1
d(λ)f = np1 , sµ
λ⊢n µ⊢n−1
X
= n fµ
µ⊢n−1
= ntn−1 .

Both results of this exercise, with different proofs, are due to K. Carde,
J. Loubert, A. Potechin, and A. Sanborn, 2008 REU report (Corol-
lary 6.3), available at

www-users.math.umn.edu/∼reiner/REU/HanConjReport.pdf.

Is it just a coincidence that the sums in (a) and (b) have the same
value?
P
Alternative proof (D. Grinberg, 2021). Let dn = λ⊢n d(λ)f λ . Now,
X X
tn+1 = fµ = (d(λ) + 1)f λ , (20)
µ⊢n+1 λ⊢n

since each f µ equals the sum of the f λ ’s over all λ that are covered by
µ in Young’s lattice, and since each partition λ is covered by exactly

23
 d(λ) + 1 partitions. Equation (20) becomes
X X X
tn+1 = (d(λ) + 1)f λ = d(λ)f λ + f λ = dn + tn ,
λ⊢n λ⊢n λ⊢n

so that dn = tn+1 − tn = ntn−1 by the standard recurrence for the

numbers tn .
55. This is a minor reformulation of a result of K. Carde, J. Loubert, A.
Potechin, and A. Sanborn, arXiv:0808:0928 (Theorem 1.1, second
version), which in turn is a reformulation of a conjecture of G. Han.
56. 1, 2, . . . , k will appear in the first row of ins(w) if and only if 1, 2, . . . , k
is a subsequence of w (written as a word) [why?]. The probability
that 1, 2, . . . , k is a subsequence of w ∈ Sn but 1, 2, . . . , k + 1 isn’t a
subsequence is given by k/(k +1)! if k < n, and by 1/n! if k = n. Hence
n−1
X k n
En = k· + .
k=1
(k + 1)! n!

Thus
X k2
lim En =
n→∞
k≥1
(k + 1)!
X k(k + 1) − (k + 1) + 1
=
k≥1
(k + 1)!
= e − (e − 1) + (e − 2)
= e − 1.

Alternative solution (considerably more elegant). The probability

that 1, 2, . . . , i appear in the first row of ins(w) is 1/i! for 1 ≤ i ≤ n.
Hence n
X 1
En = ,
i=1
i!
etc.
57. See mathoverflow.net/questions/82353. Taedong Yun (private com-
munication, 16 April 2012) computed that the total number

of permu-
2n−2
tations w ∈ Sn for which P (1, 3) = n is equal to n−3 , from which it

24
 follows that
X  
1 2n − 2
v13 = = 5.090678729 · · · .
n≥1
(n − 1)! n − 3

This gives an alternative formula to the one in the MathOverflow ref-

erence above.

(e) The motivation for this conjecture comes from a paper of A.

Berele and A. Regev, Advances in Math. 64 (1987), 118–175, with
further elucidation at arXiv:1007.3833. Consider a standard
Young tableau P with P (i, j) = n. The positions occupied by
1, 2, . . . , n − 1 are contained in an (i − 1, j − 1)-hook, using the
terminology of the papers just cited. Conversely, when n is large
compared to i and j, we expect that “most” SYT T of size n − 1
contained in an (i−1, j −1)-hook will contain the squares (i−1, j)
and (i, j − 1), so we can extend T by adding the square (i, j) and
inserting an n. By the result of Berele and Regev, for fixed i, j
the number of w ∈ Sn whose shape under RSK is contained in
an (i − 1, j − 1)-hook is roughly (i + j)2n . (Their formula actu-
ally involves (i + j − 2)2n , but (i + j)2n is a sufficiently accurate
estimate for our purposes.) Thus the expected value of P (i, j) is
P 2n
roughly n n (i+j)
2
n!
, which is roughly e(i+j) . Can this argument
(or a better similar argument if the present one is flawed) be made
precise?

58. See the answer by R. Stanley at MathOverflow,

mathoverflow.net/questions/331579.

59. See D. Romik, The number of steps in the Robinson-Schensted algo-

rithm, Functional Analysis and Its Applications 39 (2005), 152–155;

www.stat.berkeley.edu/∼romik/paperfiles/schensted.pdf.

The proof follows fairly straightforwardly from the result of Logan-

Shepp and Kerov-Vershik on the “typical” shape of a SYT mentioned in
the solution to Exercise 7.109. For further information, see R. Stanley,

25
 in Proc. Internat. Cong. Math. (Madrid, 2006), vol. 1, European Math-
ematical Society, Zurich, 2007, pp. 545–579. For the more subtle prob-
lem of the limiting shape of bumping paths, see D. Romik and P. Śniady,
Random Struct. Algorithms 48 (2016), 171–182; arXiv:1304.7589.
60. This result was proved for square shapes (but the proof is exactly
the same for rectangles) by D. Romik, Advances in Applied Math. 37
(2006), 501–510;
www.stat.berkeley.edu/∼romik/paperfiles/extremal.pdf.
Perhaps the simplest proof is to consider the inverse map (P, Q) 7→ w.
61. Put x1 = · · · = xi = t and y1 = · · · = yj = 1 and all other xr , ys = 0 in
the Cauchy identity (Theorem 7.12.1). We get
fn (i, j) = [tn ](1 − t)−ij
 
n + ij − 1
= .
ij − 1
62. By setting xi = yi in (7.44) and comparing with (7.20) we get
X
yn = zλ−1 p2λ .
λ⊢n

Write (λ, λ) for the partition (λ1 , λ1 , λ2 , λ2 , . . . ). By the orthogonality

of the power sums (equation (7.34)) we get
X
hyn , yn i = zλ−2 z(λ,λ)
λ⊢n
X 12m1 22m2 · · · (2m1 )! (2m2 )! · · ·
=
12m1 22m2 · · · (m1 )!2 (m2 )!2 · · ·
λ=(1m1 2m2 ··· )⊢n
X  
2mi
= .
m1 m2
mi
λ=(1 2 ··· )⊢n

Thus
! !
X X 2m1  X 2m2 
hyn , yn ixn = tm1 t2m2 · · ·
n≥0 m ≥0
m1 m ≥0
m2
1 2

1 1 1
= √ √ √ ···
1 − 4x 1 − 4x2 1 − 4x3
= P (x, 4)1/2 .

26
63. See J. F. Willenbring, J. Algebra 242 (2001), 691–708. Willenbring’s
proof is based on the representation theory of the orthogonal group.
The formula given here is simpler than Willenbring’s (though of course
equal to it). It can be obtained analogously to Problem 62 (though
more complicated). To begin,P set each xi = yi in (7.44) and P
use (7.20)
2
to get the p-expansion of sµ . For the p-expansion of s2λ use
Exercise 7.28. The equality of Willenbring’s formula with the one of
this exercise can be proved by expanding their logarithms.

64. The symmetric function G ∈ Λ̂R has the desired property if and only
if it has the form G = αF (x1 )F (x2 ) · · · , where α ∈ R, F (x) ∈ R[[x]]
and FP (0) = 1. Equivalently (as is easy to see), log G(x) has the form
c0 + k≥1 ck pk , where ck ∈ R. (See Exercise 7.91 for more on such
series.)
Proof. We may assume
P [why?] that G has constant term 1. Now
assume that log G = k≥1 ck pk . Then, as in Proposition 7.74, we have
!
X Y
G= zλ−1 cλi pλ .
λ i
P P Q
Let f = µ aµ pµ and g = ν bν pν . For any partition ρ let cρ = i cρi .
Then by the orthogonality of the power sums,
* +
X X
hG, f gi = zλ−1 cλ pλ , aµ bν pµ pν
λ µ,ν
X
= aµ bν cµ cν
µ,ν
! !
X X
= aµ cµ bµ cµ
µ µ
= hG, f i · hG, gi.
P −1
Conversely, let I = λ zλ dλ pλ , and suppose that hI, f gi = hI, f i ·
hI, gi for all f, g. In particular,

dµ∪ν = hI, pµ pν i = dµ dν ,
Q
so by iteration dλ = dλi , completing the proof.

27
65. Since Schur functions sλ (x1 , . . . , xn ) are the polynomial characters of
GL(n, C) (Appendix 2), it follows by Weyl’s “unitary trick” that they
are the irreducible characters of the unitary group U(n). Hence
Z
2k 2k
hVn , Vn in = Vn2k Vn2k du
u∈U (n)
Z
= |Vn |4k du.
u∈U (n)

The Weyl integration formula allows us to express this integral as an

integral over a torus. By the residue theorem, it is equal to
1 Y
CT (1 − xi x−1
j )
2k+1
,
n! i,j=1,...,n
i6=j

where CT denotes constant term. The value of this constant term was
conjectured (as a special case of a more general conjecture) by F. J.
Dyson to be (kn)!/(2k +1)!n and given an elegant proof (after an earlier
more complicated proof by Gunson and Wilson) by I. J. Good, J. Math.
Phys. 11 (1970), 1884. See I. G. Macdonald, SIAM J. Math. Anal. 13
(1982), 988–1007. For much more on this subject, see the survey by
P. J. Forrester and S. Ole Warnaar, Bull. Amer. Math. Soc. 45 (2008),
489–534.
66. It is clear from Corollary 7.13.8 that
X X
sλ = Lµ mµ ,
λ⊢2n µ⊢2n

where Lµ is the number of symmetric N-matrices (Aij )i,j≥1 with row(A) =

col(A) = µ. Since hhλ , mµ i = δλµ , it follows that an is the number of
n × n symmetric N-matrices with every row and column sum equal to
two. Hence by Example 5.2.7 we get
t2 t
e 4 + 2(1−t)
F (t) = √ .
1−t
67. (a) It follows from Exercise 7.35(a) or from Problem 28(b) that ∂p∂ 1 sλ =
sλ/1 . Hence from the case n = 1 of Theorem 7.15.7 and Corol-
lary 7.15.19, we have
Tn = (U + D + DU)n 1, (21)

28
where U = p1 (i.e., the operator given by multiplication by p1 )
and D = ∂p∂ 1 . (See Exercise 7.24 for similar reasoning.) From this
it is clear that Tn = gn (p1 ), for some polynomial gn ∈ Z[t].
P n
Now let y = n≥0 gn (t) xn! . Then from (21) we have

∂ ∂ ∂y
(t + + t)y = .
∂t ∂t ∂x
a partial differential equation with the initial condition y(0) = 1.
There are various methods for solving this type of equation. For
instance, let y = ez . Then

t + zt + 1 + tzt = zx . (22)

The general solution to the associated homogeneous equation ut +

tut = ux is u(x, t) = F (log(1 + t) + x) for any (smooth) F . A
particular solution is seen by inspection (or by plugging in a linear
polynomial with indeterminate coefficients) to be −t. Hence the
general solution to (22) is given by

z(x, t) = −t + F (log(1 + t) + x).

The initial condition z(0, t) = 0 shows that F (log(1 + t) + x) =

−1 + exp(log(1 + t) + x). Hence
x
y = e−1−t+(1+t)e . (23)

Thus
X xn
f (n) = y|t=0
n≥0
n!
x
= ee −1
X xn
= B(n) ,
n≥0
n!

where B(n) denotes a Bell number (the number of partitions of

an n-set; see equation (1.94f) of EC1, second ed.). So we finally
get f (n) = B(n). An elegant bijective proof based on growth
diagrams was given by M. Korn (unpublished), and was rediscov-
ered (in a more general context) by C. Krattenthaler, Adv. Appl.

29
 Math. 37 (2006), 404–431; arXiv.math/0510676. For another
bijective proof, see Section 4 of William Y. C. Chen, Eva Y. P.
Deng, Rosena R. X. Du, R. Stanley, and Catherine H. Yan, Trans.
Amer. Math. Soc. 359 (2007), 1555–1575; arXiv.math/0501230.
(b) We have by (23) that
X xm y n x y
hTm , Tn i = e−1−p1 +(1+p1 )e , e−1−p1 +(1+p1 )e
m,n≥0
m! n!

= exp(ex + ey − 2) hexp(p1 (ex − 1), exp(p1 (ey − 1)i

* +
X (ex − 1)m X (ey − 1)n
= exp(ex + ey − 2) pm
1 , pn1
m≥0
m! n≥0
n!
X 1
= exp(ex + ey − 2) (ex − 1)n (ey − 1)n
n≥0
n!
= exp (ex + ey − 2 + (ex − 1)(ey − 1))
= exp(ex+y − 1)
X (x + y)k
= B(k)
k≥0
k!
X xm y n
= B(m + n) ,
m,n≥0
m! n!

whence hTm , Tn i = B(m + n).

The following much slicker argument was given by T. Lam. The
result of part (a) may be restated as
hTn , 1i = h(U + D + DU)n 1, 1i = B(n).
But U and D are adjoint with respect to h, i, so U + D + DU is
self-adjoint. Hence
hTm , Tn i = h(U + D + DU)m 1, (U + D + DU)n 1i
= h(U + D + DU)m+n 1, 1i
= B(m + n).

Solutions to (a) and (b) can also be given using induction, working
directly with the operators U and D and avoiding generating functions.

30
 This problem is not as contrived as it may first appear. There is a
semisimple algebra Pn , called the partition algebra, whose irreducible
representations σ λ are indexed by (certain) partitions λ, such that
dim σ λ = hTn , sλ i. See P. Martin, J. Knot Theory Ramifications 3
(1994), 51–82; P. Martin, J. Algebra 183 (1996), 319–358; P. Martin
and G. Rollet, Compositio Math. 112 (1998), 237–254; P. Martin and
D. Woodcock, J. Algebra 203 (1998), 91–124; C. Xi, Compositio Math.
119 (1999), 99–109; W. Doran and D. Wales, J. Algebra 231 (2000),
265–330; P. Martin, J. Phys. A 33 (2000), 3669–3695; T. Halverson, J.
Algebra 238 (2001), 502–533.

68. (a) It is easy to see that

 
∂ ∂
g(p) + h(p) F (x, p) = F (x, p),
∂p ∂x

with the initial condition F (0, p) = 1. It is then routine to check

that the stated formula for F (x, p) does satisfy this differential
equation and initial condition.
(b) We have L(t) = Lh−1i (t) = t and M(t) = 12 t2 . Hence by (a),
 
1 2 1 2
F (x, p) = exp − p + (x + p)
2 2
 
1 2
= exp px + x .
2

(c) We have [why?]

X X xn
gλ (n)sλ = F (x, p),
n≥0 λ∈Par
n!

where F (x, p) corresponds to g(t) = 1 + t and h(t) = 1 + t. Hence

L(t) = log(1 + t), Lh−1i (t) = et − 1, and M(t) = t, so

Lh−1i (x + L(p)) = (1 + t)ex − 1

 
F (x, p) = exp −p + ex+log(1+t) − 1
= exp(−1 − p + (1 + p)ex ).

31
 (d) We have g(t) = h(t) = 1/(1 − t), L(t) = t − 12 t2 , Lh−1i (t) =
√
1 − 1 − 2t, and M(t) = t. We get
X xn
g∅ (n)sλ = F (x, p)
n≥0
n!
 s !
1 2
= exp −p + 1 − 1 − 2 x + p − p
2
 p 
= exp 1 − p − (1 − p)2 − 2x .

(e) We have g(t) = 1/(1 − t), h(t) = 1, L(t) = Lh−1i (t) = t, and
M(t) = − log(1 − t). Hence

F (x, p) = exp (log(1 − p) − log(1 − x − p))

1
= x
1 − 1−p
X xn
= n
,
n≥0
(1 − p)

etc. Is there a nice bijective proof?

69. One first shows that ins(w) can be obtained by row inserting an+1 ,
then column inserting an , then row inserting an+2 , then column in-
serting an−1 , etc., ending with a row insertion of a2n followed by a
column insertion of a1 . It can be shown that for each 1 ≤ i ≤ n the
shape increases by the addition of one domino after inserting an+i and
an+1−i , and the proof follows. Alternatively, by Theorem A.1.2.10 we
have P = evac(P ). Now consider the growth diagram for comput-
ing evac(P ) (Figure A1-13), or see Section 3 of R. Stanley, Promotion
and evacuation, Electronic J. Comb. 15(2) (2008–2009). For a good
overview of this topic, see M. Shimozono and D. E. White, Electronic
J. Combinatorics 8(1) (2001), R21.

70. If d ∤ n and λ ⊢ n, then some λj is not divisible by d. Hence

1 − ζ dλj
pλj (1, ζ, . . . , ζ d−1) = = 0.
1 − ζ λj

32
 Thus pλ (1, ζ, . . . , ζ d−1) = 0, and the proof follows (since the pλ ’s for
λ ⊢ n are a basis for ΛnQ ).
For stronger results about sλ (1, ζ, . . . , ζ d−1), note that
X 1 X
sλ (1, ζ, . . . , ζ d−1)sλ (x) = Y = hn (xd1 , xd2 , . . . )
d
λ (1 − xk ) n≥0
k

and see Exercise 7.61.

71. See I. P. Goulden, Canad. J. Math. 42 (1990), 763–775 (Theorem 2.3(a)).

72. We have X X X
hλ/µ (u) = 1. (24)
u∈λ/µ u∈λ/µ v∈H(u)

Given u, v ∈ λ/µ, it is easy to see that

v ∈ Hλ/µ (u) ⇐⇒ u ∈ H(λ/µ)r (v).

P
Hence reversing the order of summation in (24) gives u∈(λ/µ)r h(λ/µ)r (u),
as desired.

73. (a) This identity was conjectured by T. Amdeberhan on MathOver-

flow 312771 on October 13, 2018, with solutions by G. Zaimi and
S. Hopkins.

74. (a) Let X

f (n) = ηk (λ).
λ⊢n

It is an easy consequence of Exercise 7.59(a,b) that the number

of ways to add a border strip of size k to λ is k more than the
number of border strips (or hooks) of λ of size k. (In fact, this is
a direct consequence of Exercise 7.59(e) and the observation that
in Y k , an element λ is covered by k more elements than it covers.
See Exercise 3.51(c) of EC1, second ed.) It follows that f (n +
k) = kp(n) + f (n),Pwhere p(n) denotes the P number of partitions
of n. Let F (x) = n≥0 f (n)xn and P (x) = n≥0 p(n)xn . We get

33
 x−k F (x) = kP (x) + F (x), whence F (x) = kxk P (x)/(1 − xk ). It
is easy to see that
!
X X xk P (x)
k
mk (λ) x = ,
n≥0 λ⊢n
1 − xk

and the proof follows. This result is due to R. Bacher and L.

Manivel, Sém. Lotharingien de Combinatoire 47 (2002), B47d;
arXiv.math/0108199.
(b) This is a result of C. Bessenrodt and G. Han, Discrete Math.
309 (2009), 6070–6073. The proof follows easily from the follow-
ing stronger result, which is proved by a combinatorial argument.
Given u = (i, j) ∈ λ, let a(u) = λi − i (the arm length of u) and
l(u) = λ′j − j (the leg length of u), so h(u) = a(u) + l(u) + 1.
Let fn (a, l, r) denote the number of ordered pairs (λ, u) such that
λ ⊢ n, u ∈ λ, a(u) = a, l(u) = l, r(u) = r. Then
X   
n 1 l + a r + a (m+1)(l+1)+1
fn (a, l, r)q = Q i
q .
n≥0 i≥a+1 (1 − q ) a a

(c) Reformulation of (a).

75. See Lemma 3.1 of K. Liu, C. Yan, and J. Zhou, Sci. China Ser. A 45
(2002), 420–431. A combinatorial proof was later given by G. Warring-
ton, J. Combinatorial Theory Ser. A 116 (2009), 379–403.
76. Easy.
77. By Theorem 7.15.1 we have
a2(λ+δ)
sλ (x21 , . . . , x2n ) =
a2δ
a(2λ+δ)+δ aδ
= ·
aδ a2δ
s2λ+δ (x1 , . . . , xn )
= ,
sδ (x1 , . . . , xn )
whence
sδ (x1 , . . . , xn )sλ (x21 , . . . , x2n ) = s2λ+δ (x1 , . . . , xn ).
For some related results, see Exercise 7.30.

34
78. By the solution to Exercise 7.69(a) we have
  
X t
 X 1 X 1 
sλ = exp t  pn + p2n/2  .
n≥1
n n≥1
n
n odd n even

We can now apply the exponential formula as in the solution to Exer-

cise 7.69(a).

79. Let N = 2n and λ = δN = (N, N −1, . . . , 1). Thus in Exercise 7.40, r =

n and B(i, j) = B(2N+1−i−j ,1) , the “zigzag” border strip corresponding
to the composition (2N +1−i−j , 1). The number f B(i,j) of SYT of (skew)
shape B(i, j) is E|B(i,j)| = E2N +3−2i−2j (see Exercise 7.64(a)). Take the
formula of Exercise 7.40, reflect the matrix through the antidiagonal
(which doesn’t effect the determinant) and apply ex (the exponential
specialization) to obtain
f δN
An = .
|δN |!
Thus by the hook-length formula (Corollary 7.21.6) we get
1 1
An = Y = .
h(u) 1N 3N −1 5N −2· · · (2N − 1)1
u∈δN

Exactly analogous reasoning for for N = 2n − 1 yields that

1
Bn = .
1N 3N −1 5N −2 · · · (2N − 1)1

80. Let τ = τn be the “zigzag shape” of Exercise 7.64. By Corollary 7.23.8

we have f (n) = hτ, τ i. Let χ = ch(τ ). Since ch is an isometry
(Prop. 7.18.1) we have f (n) = hχ, χi. By Exercise 7.64 we get for
n odd that
X
hχ, χi = zµ−1 χ(µ)2
µ⊢n
X
= zµ−1 E2r
2
,
µ

35
 where µ ranges over all partitions of n with 2r + 1 odd parts and no
even parts. The proof now follows from a routine application of Corol-
lary 5.1.8. The proof for even n is similar, using a simple modification
of Corollary 5.1.8.
This result is due to R. Stanley, J. Combinatorial Theory Ser. A 114
(2007), 436–460 (Theorem 3.1); arXiv:math/0603520.
81. See R. Stanley, J. Combinatorial Theory (A) 114 (2007), 436–460;
arXiv.math/0603520 (Corollary 5.7).
82. This was a conjecture of R. Stanley, presented on June 25, 2003, at the
15th FPSAC meeting in Vadstena, Sweden, and available at
math.mit.edu/∼rstan/transparencies/fpsacproblem.pdf.

It was proved by M. Ishikawa, Ramanujan J. 16 (2008), 211–234;

arXiv.math/0408204.
83. (a) By (7.66) we have
X
sλ (x, y) = sµ (x)sλ/µ (y).
µ⊆λ

Now apply ωy and use Theorem 7.15.6.

(b) It is clear from the definition (4) that
pn (x/y)x1=t, y1 =−t = pn (x/y)x1=y1 =0 .

Since ωy and the substitutions x1 = t, y1 = −t and x1 = y1 = 0

are homomorphisms (into suitable rings), it follows that g(x, y)
satisfies (6) whenever g ∈ im(ωy ).
Conversely, suppose that g(x, y) ∈ Λ(x) ⊗ Λ(y) and that g(x, y)
satisfies (6). Thus by hypothesis
g((t, x), (−t, y)) = g(x, y), (25)

where (t, x) = (t, x1 , x2 , . . . ) and similarly for (t, y). Define

1

ui = pi (x) + (−1)i pi (y)
2
1

vi = pi (x) + (−1)i−1 pi (y) .
2
36
 It is clear that g(x, y) can be written uniquely as a polynomial
P (u1 , u2, . . . ; v1 , v2 , . . . ) in the ui ’s and vi ’s, and we want to show
that no ui appears. Now
g((t, x), (−t, y)) = P (u1 + t, u2 + t2 , . . . ; v1 , v2 , . . . ). (26)
By considering the coefficient of t in (26) and using (25), we see
that u1 does not appear in P . Now by considering the coefficient
of t2 is follows that u2 does not appear in P , etc. This proof is
due to John Stembridge (unpublished).
(c) See J. R. Stembridge, J. Algebra 95 (1985), 439–444 (Theorem 1).
(d) This is immediate from
p2i (x/x) = p2i (x) + (−1)2i−1 p2i (x) = 0.

(e) From (a) it is easy to see that

[xα y β ]sλ (x/y) = hhα eβ , sλ i.
This corresponds to building up the shape λ by first adding hor-
izontal strips of sizes α1 , α2 , . . . and then vertical strips of sizes
β1 , β2 , . . . . But multiplication of symmetric functions is commu-
tative, so we could first add a horizontal strip H1 of size α1 , then
a vertical strip V1 of size β1 , then a horizontal strip H2 of size α2 ,
then a vertical strip V2 of size β2 , etc. To get sλ (x/x), fill in each
square of Hi ∪Vi with i, getting an array T , and sum all xT ’s. Now
the array T is precisely a supertableau. How many times does a
particular supertableau T get counted? For each component C of
Hi ∪Vi , there are exactly two ways to decompose C into a horizon-
tal strip H followed by a vertical strip V . (The last square in the
top row can be part of H or V , but there are no other choices.)
Hence the number of times T gets counted is 2c(T ) , completing the
proof.
(f) First note that s(nm ) (x1 , . . . , xm /y1 , . . . , yn ) is a homogeneous poly-
nomial of degree mn. If µ ⊆ (nm ), then either ℓ(µ) = m or (nm )/µ
contains a row of length n. In the former case sµ (x2 , x3 , . . . , xm ) =
0 and in the latter s(nm )′ /µ′ (y2 , y3, . . . , yn ) = 0. Thus by (5) we
have s(nm ) (0, x2 , . . . , xm /0, y2 , . . . , yn ) = 0, so by (6) we have
s(nm ) (x1 , x2 , . . . , xm /y1 , y2 , . . . , yn ) x1 =−y1
= 0.

37
 Hence s(nm ) (x1 , x2 , . . . , xm /y1 , y2 , . . . , yn ) is divisible by x1 +y1 . By
symmetry, s(nm ) (x1 , x2 , . . . , xm /y1 , y2 , . . . , yn ) is divisible by xi +
yj for all 1 ≤ i ≤ m and 1 ≤ j ≤ n. This accounts Q for mn
factors, so s(nm ) (x1 , x2 , . . . , xm /y1 , y2 , . . . , yn ) = c (xi + yj ) for
some constant c. It is easy to see that c = 1, e.g., by considering
the coefficient of xn1 xn2 · · · xnm , completing the proof. This result is
due to D. E. Littlewood and can be found in [7.88, XVIII on page
115].
Bijective proof. Immediate from Exercise 7.42 (with the typo
sλ̃ (y) replaced with sλ̃′ (y)).
(g) This result is due to A. Berele and A. Regev, Advances in Math.
64 (1987), 118–175. A bijective proof was given by J. B. Remmel,
Linear and Multilinear Algebra 28 (1990), 119–154. For another
proof, see [7.96, Exam. I.3.23(4)].

84. See P. Clifford and R. Stanley, Electronic J. Combinatorics 11(1) (2004),

R67; arXiv.math/0311382.

85. (a) Let λ, µ ⊢ n. A monomial xλ1 1 xλ2 2 · · · is obtained from pµ by

picking out a term from each factor pµi of pµ . If say λt+1 =
· · · = λt+r , then we can permute the choices giving rise to these
exponents in r! ways. It follows that pµ is a Z-linear combination
of the m̃λ ’s.
A noncomputational way to prove the converse is the following.
Recall that Λn denotes the abelian group (under addition) of Z-
linear combinations of the mλ ’s, where λ ⊢ n. Let Υn denote
the Z-linear combinations of the m̃λ ’s, where λ ⊢ n. Let Πn
denote the Z-linear combinations of the pλ ’s, where λ ⊢ n. In the
previous paragraph we have shown that ΠnQ⊆ ΥQ n
. Clearly by the
n n
definition of m̃λ , the index of Υ in Λ is λ⊢n i ri (λ)!. By the
Note following Corollary 7.7.2, this number is also the index of Πn
in Λn , so Υn = Πn .
(b) One could conjecture, for instance, that γ(sλ ) is s-positive; and if
λ1 ≤ 2, then γ(sλ ) is e-positive.
⊥
P hsk−1pλ , pµ i = hpλ , sk pµ i. The proof now follows from
86. (a) We have
sk = µ⊢k zµ pµ and the orthogonality relation hpλ , pν i = δλν zλ .

38
 (b) See mathoverflow.net/questions/376494 (answer by R. Stan-
ley).
87. Sketch of proof. Write ϑn for ϑ specialized to t = n, where n ∈ P. Note
that
ϑn (pk )(x1 , . . . , xn ) = pk (x1 + 1, . . . , xn + 1).
Hence
ϑn (sλ )(x1 , . . . , xn ) = sλ (x1 + 1, . . . , xn + 1).
Now
aλ+δ (x1 + 1, . . . , xn + 1)
sλ (x1 + 1, . . . , xn + 1) =
aδ (x1 + 1, . . . , xn + 1)
aλ+δ (x1 + 1, . . . , xn + 1)
= .
aδ (x1 , . . . , xn )
By expanding the entries of aλ+δ (x1 + 1, . . . , xn + 1) and using the
multilinearity of the determinant we get (see I. G. Macdonald, Sym-
metric Functions and Hall Polynomials, second ed., Example I.3.10 on
page 47) X
sλ (x1 + 1, . . . , xn + 1) = dλµ sµ , (27)
µ⊆λ

where  
λi + n − i
dλµ = det .
µj + n − j 1≤i,j≤n
We can factor out factorials from the numerators of the row entries and
denominators of the column Q entries of the above determinant. These
factorials altogether yield u∈λ/µ (n + c(u)). What remains is exactly
the determinant for f λ/µ /|λ/µ|! given by Corollary 7.16.3, and we ob-
tain
 
X f λ/µ Y
ϑn (sλ )(x1 , . . . , xn ) =  (n + c(u)) sµ (x1 , . . . , xn ).
µ⊆λ
|λ/µ|!
u∈λ/µ

We can set xi+1 = · · · = xn = 0 to obtain the above equation in i

variables. In other words,
 
X f λ/µ Y
ϑn (sλ )(x1 , . . . , xi ) =  (n + c(u)) sµ (x1 , . . . , xi )
µ⊆λ
|λ/µ|!
u∈λ/µ

39
 for all n ≥ i. Both sides are polynomials in n, so they are equal as
polynomials, and we can replace n with the indeterminate t. Now let
i → ∞.
Is there a more conceptual proof that doesn’t involve the evaluation of
a determinant?
Equation (27) (without the evaluation of the determinant dλµ ) goes
back to A. Lascoux, C. R. Acad. Sci. Paris Sér. A-B 286 (1978), 385–
387. See also I. G. Macdonald, Symmetric Functions and Hall Polyno-
mials, second ed. (Example I.3.10 on pages 47–48). The evaluation of
dλµ is due to R. Stanley. For further aspects of this result, see S. C.
Billey, B. Rhoades, and V. Tewari, Int. Math. Research Not. IMRN
(2019); arXiv:1920.11165 (Section 4).

88. See Lemma 3.2 of R. Stanley, Ramanujan J. 23 (2010), 91–105;

arXiv:0807.0383.

89. Part (a) follows from Section 4.2 of

www.mat.univie.ac.at/∼slc/wpapers/FPSAC2018/
50-Thiel-Williams.html
by M. Thiel and N. Williams. The key to doing the entire exercise is
to first show that for any symmetric function f , we have
n−1
r
z }| { 1
[z ]f (z + 1, 1, · · · , 1, 0, 0, . . .) = ψr f,
n · r!
where [z r ]g denotes the coefficient of z r in g (when expanded as a power
series in z). This exercise is based on unpublished work of X. Li, L.
Mu, and R. Stanley.

90. This is the special case of Exercise 7.47(j) where P is both (3 + 1)-free
and (2 + 2)-free. It was shown by M. Guay-Paquet, arXiv:1306.2400,
that this special case actually implies the full conjecture.
For the case I = {{1, 2}, {2, 3}, . . . , {n − 1, n}} (i.e., no two consecu-
tive elements of i1 i2 · · · in are equal), see Exercise 7.47(k). Ben Joseph
claimed to have a proof based on the involution principle for the case
I = {{1, 2, 3}, {2, 3, 4}, . . . , {n − 2, n − 1, n}}, but this was never writ-
ten up. A different proof is due to S. Dahlberg, Sém. Lotharingien de
Combinatoire 82B (2019), Article #59, 12 pp.

40
 David Gebhard and Bruce Sagan, J. Algebraic Comb. 13 (2001), 227–
255, have generalized Exercise 7.47(k) to the case I = {{1, 2, . . . , k1 }, {k1 , k1 +
1, . . . , k2 }, {k2 , k2 +1, . . . , k3 }, . . . , {kr , kr +1, . . . , n}}. For further work
on chromatic symmetric functions and their quasisymmetric generaliza-
tion, see the web page
www.symmetricfunctions.com/chromaticQuasisymmetric.htm
of Per Alexandersson.

91. (a) We have

X X X
a(m, n) = f µ f ν f λ cλµν
µ⊢m ν⊢n−m λ⊢n
X X X
= f µ f ν f λ hsµ sν , sλ i
µ⊢m ν⊢n−m λ⊢n
* ! ! +
X X X
= f µ sµ f ν sν , f λ sλ
µ⊢m ν⊢n−m λ⊢n
m n−m n
= hp1 p1 , p1 i
= n!.

Similarly we obtain
* +
X
b(m, n) = pn1 , sλ
λ⊢n
= t(n),
P
since e.g. if f ∈ Λn then hpn1 , f i = [x1 x2 · · · xn ]f , while λ⊢n fλ =
t(n) by Corollary 7.13.9. In the same way we obtain
* ! +
X
c(m, n) = sµ p1n−m , pn1 .
µ⊢m

An elegant way to proceed is to use the fact (Problem 28(b)) that

41
 ∂
multiplication by p1 is adjoint to ∂p1
. Hence
* +
X ∂n−m
c(m, n) = sµ , n−m
pn1
µ⊢m
∂ p1
* +
X
= sµ , (n)n−m pm
1
µ⊢m
= (n)n−m t(m).

Finally,
* ! ! +
X X
d(m, n) = sµ sν , pn1
µ⊢m ν⊢n−m
! !
X X
= [x1 x2 · · · xn ] sµ sν
µ⊢m ν⊢n−m
 
n
= t(m)t(n − m).
m

(b) See C. Ikenmeyer, J. Alg. Combinatorics 44 (2016), 1–29 (Theo-

rem 1.1); arXiv 1209.1521.
(c) We have (pointed out by B. Tenner)
* ! ! +
X X X
ν
e(m, n) = sµ f sν , sλ
µ⊢m ν⊢n−m λ⊢n
* ! +
X X
= sµ p1n−m , sλ
µ⊢m λ⊢n
XX
= p1n−m sµ , sλ
µ⊢m λ⊢n
XX
= p1n−m , sλ/µ
µ⊢m λ⊢n
XX
= f λ/µ .
µ⊢m λ⊢n

Now use Exercise 7.27(a).

42
92. (a) Let
!2
X
Yn = sµ (x)sµ (y) .
µ⊢n

It is easy to see that the coefficient of q n in the left-hand side

of (7) is just hYn , Yn i (scalar product in the ring Λ(x) ⊗ Λ(y)).
Expanding Yn in terms of power sums yields
X
hYn , Yn i = zµ−1 zν−1 zµ∪ν ,
|µ|+|ν|=n

from which it is easy to complete the proof. The original proof of

Jeb Willenbring (private communication of 5 June 2003) is based
on representation theory. See P. E. Harris and J. F. Willenbring, in
Symmetry: representation theory and its applications, Birkhäuser,
New York, 2014, pp. 305–326.
(e) Follows easily from Exercise 7.71(c) and letting n → ∞ in part
(d) of the present problem.

93. Conjectured by Stijn Lievens and Neli Stiolova, and proved by Ron
King in July, 2007, in a manuscript entitled “Notes on certain sums of
Schur functions.”
♣ Can this manuscript be accessed online? Is there another reference?

94. This conjecture is due to S. Sundaram. It has been checked for even
n ≤ 20.

95. See T. Lam, A. Postnikov, and P. Pylyavskyy, Amer. J. Math. 129

(2007), 1611–1622; arXiv:math/0502446.

96. This result is the famous “saturation conjecture” for Littlewood-Richard-

son coefficients. The first proof was by given by A. Knutson and T.
Tao, J. Amer. Math. Soc. 12 (1999), 1055–1090; math.RT/9807160.
An exposition of this proof was given by A. S. Buch, Enseign. Math.
46 (2000), 43–60; arXiv.math/9810180. Later proofs were given by
H. Derksen and J. Weyman, J. Amer. Math. Soc. 13 (2000), 467–479,
and P. Belkale, J. Alg. Geom. 15 (2006), 133–173; math.AG/0208107.
For some generalizations of the saturation conjecture, see A. N. Kirillov,
Publ. Res. Inst. Math. Sci. 40 (2004), 1147–1239; arXiv.math/0404353.

43
 97. This result is closely related the saturation conjecture (Problem 96
above) and to the problem of characterizing the possible eigenvalues of
hermitian matrices A, B, A + B. For a nice survey of this area see W.
Fulton, Bull. Amer. Math. Soc. 37 (2000), 209–249; math.AG/9908012.
98. (a) This result follows from the theory of Hall polynomials, not dis-
cussed in EC2. See (4.3) on page 188 of Macdonald, Symmet-
ric Functions and Hall Polynomials, second ed. To complete the
λ
proof, one needs to show that gµν (p) 6= 0 (when p is prime). This
fact follows from a result of F. M. Maley, J. Algebra 184 (1996),
λ
363–371, that gµν (t) has nonnegative coefficients when expanded
in powers of t − 1.
(b) This result (if true) would give an algebraic strenghtening of the
Saturation Conjecture (Exercise 96 above). For a somewhat more
general context, see mathoverflow.net/questions/212368.
99. (a) One method is to note that by the Murnaghan-Nakayama rule we
have χλ ((n)) 6= 0 (if and) only if λ is a hook. But the only hooks
λ with a border strip of size n − 1 (otherwise χλ (n − 1, 1) = 0)
n
are (n) and (1n ). Since χn (µ) = εµ χ1 (µ) = 1 6= 0 for all µ ⊢ n, it
follows that λ = (n) or λ = (1n ).
100. Let µ1 be the size of the largest border strip B1 of λ. Thus µ1 =
h(1, 1) = λ1 + λ′1 − 1, the hook length of square (1,1). Let µ2 be
the size of the largest border strip B2 after we remove B1 from λ.
Thus µ1 = h(2, 2) = λ2 + λ′2 − 3. Continue in this way to obtain
µ = (µ1 , µ2, . . . ). The number of parts of µ is rank(λ). Since each Bi
is unique, there is only one border strip tableau of type µ. Thus by the
Murnaghan-Nakayama rule χλ (µ) = ±1.
101. Given w ∈ Sn , let

sq(w) = #{u ∈ Sn : u2 = w},

the number of square roots of w. Let ϕ : ΛQ → Q be the linear

transformation (not a ring homomorphism) defined by ϕ(sλ ) = 1.
Thus ϕ⊗k (the kth tensor power of ϕ) is a linear transformation from
ΛQ (x(1) ) ⊗ · · · ⊗ ΛQ (x(k) ) to Q defined by

ϕ(sλ1 (x(1) ) · · · sλk (x(k) )) = 1.

44
 By the solution to Exercise 7.69(b) we have ϕ(pλ ) = sq(w), where
ρ(w) = λ. Now apply ϕ⊗k to both sides of (7.186).

102. Equivalent to equation (4.7) of J. B. Lewis, V. Reiner, and D. Stan-

ton, J. Alg. Combinatorics 40(3) (2014), 663–691; arXiv:1308.1468,
where the result is attributed to Kerov and to Garsia-Haiman. Sev-
eral persons subsequently found elegant combinatorial proofs, the first
being X. Chen ( ).

103. See R. Stanley, Ramanujan J. 23 (2010), 91–105, arXiv:0807.0383;

G. Olshanski, Electronic J. Math. 17 (2010), R43, arXiv:0905.1304;
and G. Panova, Ramanujan J. 27 (2012), 349–356, arXiv:0811.3463.

104. Let λ be a p-core with λ1 = k. Remove from λ all rows such that the
first square (i, 1) of the row satisfies h(i, 1) ≡ h(1, 1) (mod p), where
h(i, j) is the hook length of the square (i, j). One can check that this
sets up a bijection with (p − 1)-cores µ with µ1 ≤ k. Thus if fp (k)
denotes the number of p-cores with largest part k, then

fp (k) = fp−1 (1) + fp−1 (2) + · · · + fp−1(k),

from which the proof follows easily. This result was explained by M.
Vazirani in a conversation at MSRI on March 24, 2008.

105. Conjectured by D. Armstrong, C. R. H. Hanusa, and B. C. Jones, Europ.

J. Combinatorics 41 (2014), 205–220; arXiv:1308:0572. For proofs
see W. Y. C. Chen, H. H. Y. Huang, and L. X. W. Wang, Proc. Amer.
Math. Soc. 144 (2016), 1391–1399, arXiv:1405.2175, and P. D. John-
son, Electron. J. Combin. 25 (2019), Paper 3.47, arXiv:1502.07834.

106. (a) We have

1 k 1 k−1 k
hχλ · · · χλ , χ(n) i = hχλ · · · χλ , χλ i.

45
 Thus [why?]
X 1 k−1 1 k−1
uk (n) = hχλ · · · χλ , χλ · · · χλ i
λ1 ,...,λk−1
X  2  k−1 2 
λ1 λ (n)
= χ ··· χ ,χ
λ1 ,...,λk−1
* !k−1 +
X
µ 2
= (χ ) , χ(n) .
µ⊢n

By Exercise 7.82(a),
X X
ch (χµ )2 = pµ .
µ⊢n µ⊢n

Hence [why?]
* !∗(k−1) +
X
uk (n) = pµ , hn ,
µ⊢n

where ∗(k −1) denotes the (k −1)th power with respect to ∗. Now
since
pλ ∗ pµ = zµ pµ δλµ ,
P −1
and hn = µ⊢n zµ pµ , finally we get [why?]
X
uk (n) = (zµ )k−1.
µ⊢n

Thanks to Sam Hopkins for asking about the value of u2 (n).

Some references are J. B. Geloun and S. Ramgoolan, Ann. Inst.
Henri Poincaré D 1 (2014), 77–138, arXiv:1307.6490 (equa-
tion (18)); OEIS A110143, MO 41337, and MO 162428, where
MO = MathOverflow.
(b) We now have [why?]
X D 1 k
E
vk (n) = χλ · · · χλ , χ(n)
λ1 ,...,λk
* !∗k +
X
= sλ , hn .
λ⊢n

46
 Now by Exercise 7.69(a) we have
X 1 X
sλ = pρ(w2 )
λ⊢n
n! w∈Sn
X
= zµ−1 sq(wµ )pµ ,
µ⊢n

where wµ is a permutation in Sn of cycle type µ. Hence [why?]

X
vk (n) = zµ−1 sq(wµ )k
µ
1 X
= sq(w)k .
n! w∈S
n

Note the special case k = 2:

1 X
sq(w)2 = p(n).
n! w∈S
n

(For a different generalization, see Problem 101.)

Note. For any finite group G of order d with k conjugacy classes
we have (Problem 17)
#{(u, v) ∈ G × G : uv = vu} = kd.
Hence
#{(u, v) ∈ Sn ×Sn : uv = vu} = #{(u, v) ∈ Sn ×Sn : u2 = v 2 }.
(In fact, this is true for any finite group G all of whose complex
representations are equivalent to real representations.) Is there a
combinatorial proof?
(c) Let k = 3 in √equation (10). The number of terms in the two sums
is around ec n . The largest term on the right-hand side is n!,
coming from µ = h1n i. Hence the largest √
term on the left-hand
c n
side is n!, up to a factor of the order e . From this observation
and Stirling’s formula for n! the proof follows easily. For further
information, including the partitions λ, µ, ν achieving the maxi-
mum, see I. Pak, G. Panova, and D. Yeliussizov, J. Combinatorial
Theory Ser. A 165 (2019), 44–77; arXiv:1804.04693.

47
107. (a) See R. Stanley, Advances in Applied Math. 30 (2003), 283–294;
arXiv.math/0106115 (Theorem 2.2). The proof consists simply
of applying the exponential specialization ex (EC2, pp. 304–306)
to the identity of Exercise 7.27(e). Since this identity has a bi-
jective proof via a skew version of RSK, its exponential special-
ization is therefore just a special case of this bijective proof. A
somewhat different bijective proof was given by Aaron D. Jag-
gard, Electronic J. Combinatorics 12 (2005), R14 (Theorem 3.2);
arXiv.math/0107130.
(b) See R. Stanley, ibid. (Theorem 2.1).

108. (b) See D. White, Advances in Math. 50, 160–186, though there may
be earlier references.
(c) Easy consequence of (b), the isomorphism ϕ, and the Murnaghan-
Nakayama rule.

109. (a) See R. Stanley, Sém. Lotharingien de Combinatoire 50 (2003),

B50d; arXiv.math/0109093 (Theorem 1).
(b) See V. Féray, Ann. Combinatorics 13 (2010), 453–461;
arXiv.math/0612090. There is also an exposition in P.-L. Méliot,
Representation Theory of Symmetric Groups, Chapman and Hall/CRC,
2017.

110. (a) We may assume q ∈ P. In Exercise 7.70, let k = 3
and x(3)
= 1q .

Take the scalar product of both sides with pn x(1) pn x(2) . The
right-hand side becomes after some simplification
X
RHS = n q κ(w(1,2,...,n)) .
ρ(w)=(n)

The left-hand side becomes (using Corollary 7.21.4)

X Y
LHS = χλ ((n))2 (q + c(u)).
λ⊢n u∈λ

Now e.g. by the Murnaghan-Nakayama rule we have


λ (−1)n−i , if λ = (i, 1n−i )
χ ((n)) =
0, otherwise.

48
 From this we easily get
n
1X
Pn (q) = (q + i − 1)n
n i=1
1
= ((q + n)n+1 − (q)n+1 ) .
n(n + 1)

(b) If Pn (z) = 0 then

|(z + 1)(z + 2) · · · (z + n)|2 = |(z − 1)(z − 2) · · · (z − n)|2 . (28)

Let z = a + bi where a, b ∈ R and a > 0. Then for j > 0 we have

|(z + j)|2 − |(z − j)|2 = 4aj > 0.

Hence the left-hand side of (28) is greater than the right. The
reverse inequality holds if a < 0. Hence if (28) holds then a = 0,
and the proof follows.
(c) See R. X. F. Chen and C. M. Reidys, SIAM J. Discrete Math. 30
(2016), 1660–1684, arXiv:1502.07674, and the references therein.
(d) (sketch) As in (a) we obtain
n
X i
Pλ (q) = χhn−i,1 i (µ)(−1)i−1 (q + n − i)n .
i=1

Now if we apply the specialization (homomorphism) ψ(pn ) = 1 −

(−t)n , then
 k
t (1 + t), λ = hn − k, 1k i, 0 ≤ k ≤ n − 1
ψ(sλ ) =
0, otherwise.
P
Hence from pµ = λ χλ (µ)sλ we get
Q n−1
(1 − (−t)µi ) X hn−k,1k i
= χ (µ)tk ,
1+t k=0

so Q
(1 − (−t)µi )
Pλ (q) = .
1+t tk →(−1)k (q+n−k−1)n

49
 It is now not hard to complete the proof using Lemma 9.3 of A.
Postnikov and R. Stanley, J. Combinatorial Theory (A) 91 (2000),
544–597.
For this entire exercise, see R. Stanley, Europ. J. Combinatorics 32
(2011), 937–943; arXiv:0901.2008.
111. (a) Let α = (α1 , . . . , αk ). Define

m ◦ α = (α1 , [α2 , . . . , αk−1 , αk + α1 ]m−1 , α2 , . . . , αk ),

where [γ]m denotes the concatenation of γ with itself m times. For

instance, 3 ◦ (2, 1, 3, 2) = (2, 1, 3, 4, 1, 3, 4, 1, 3, 2). Define

(β1 , . . . , βh ) ◦ α = (β1 ◦ α, . . . , βh ◦ α).

For instance, (1, 3, 2)◦(2, 1) = (2, 1, 2, 3, 3, 1, 2, 3, 1). Given a com-

position α, there is unique way to write it as β 1 ◦β 2 ◦· · ·◦β j , where
each β i is irreducible with respect to ◦ (i.e., β 6= γ◦δ, where γ and δ
are compositions of integers greater than one). If β = (β1 , . . . , βh ),
let β = (βh , . . . , β1 ). L. Billera and S. van Willigenburg, Advances
in Math. 204 (2006), 204–240, arXiv.math/0405434, have shown
that the compositions equivalent to α are exactly those of the form
(β 1 )′ ◦ (β 2 )′ ◦ · · · ◦ (β j )′ , where each (β i )′ is β i or β i . For instance,
since 12132 = 12 ◦ 12, the compositions equivalent to 12132 are
12132, 12 ◦ 21 = 21231, 21 ◦ 12 = 13212, and 21 ◦ 21 = 23121.
(b) See Theorem 3.4 of M. Rubey, Sém. Lotharingien de Combinatoire
64 (2011), B64c; arXiv:1008.2501.
112. See R. Stanley, J. Combinatorial Theory (A) 100 (2002), 349–375;
arXiv.math/0109092 (Corollary 5.3). A direct combinatorial argu-
ment was given by Thomas Lam.
113. See R. Stanley, J. Combinatorial Theory (A) 100 (2002), 349–375;
arXiv.math/0109092 (Proposition 2.2 and Theorem 3.2). For the last
item, see W. Y. C. Chen and A. L. B. Yang, Trans. Amer. Math. Soc.
360 (2008), 3121–3131; arXiv.math/0509181.
114. See N. Eriksen and A. Hultman, Estimating the expected reversal dis-
tance after a fixed number of reversals, Advances in Applied Math. 32
(2004), 439–453 (Theorem 3).

50
115.(a,b) See B. Joseph, Ph.D. thesis, M.I.T, 2001 (Chapter 3), available
at dspace.mit.edu/handle/1721.1/8225. This proof was never
published.
(c) Immediate from (a) and the definition of the scalar product hfn , sgni.
This result is attributed to Paul D. Hanna, 9 March 2013, in OEIS
A033917.

116. (a) We have X X

sλ (x)sλ (y) = zλ−1 pλ (x)pλ (y). (29)
λ⊢n λ⊢n
i−1
Set yi = q and multiply by (1 − q)(1 − q 2 ) · · · (1 − q n ). By
Proposition 7.19.11 we obtain
 
X X X n
 maj(T )  −1 (1 − q) · · · (1 − q )
q sλ = zλ pλ ,
λ⊢n λ⊢n
(1 − q λ1 ) · · · (1 − q λℓ )
sh(T )=λ

where ℓ = ℓ(λ). Now set q = −1. The left-hand side becomes

Rn . The term indexed by λ on the right-hand side vanishes unless
λ = (2m ) or λ = (2m , 1). Moreover, z(2m ) = z(2m ,1) = 2m m!, and

(1 − q)(1 − q 2 ) · · · (1 − q 2m )
lim
q→−1 (1 − q 2 )m

(1 − q)(1 − q 2 ) · · · (1 − q 2m+1 )
= lim = 2m m!.
q→−1 (1 − q)(1 − q 2 )m
Hence 
 pm
2 , n = 2m
Rn =

p1 pm
2 , n = 2m + 1.

(b) For definiteness let n = 2m; the case n = 2m + 1 is essentially

the same. By (a) we need to characterize all λ ⊢ n for which
hpm 6 0. By Corollary 7.17.4, if hpm
2 , sλ i = 2 , sλ i =
6 0 then there ex-
ists a border strip tableau of shape λ and type (2m ). Moreover,
a simple argument shows that all border strip tableaux of shape
λ and type (2m ) have the same parity of horizontal (and hence of
vertical) dominos. Thus there is no cancellation of signs in the
computation of χλ (2m ) = hpm m
2 , sλ i, so hp2 , sλ i =
6 0 if and only if

51
 there exists a border strip tableau of shape λ and type (2m ). (This
fact also follows from Problem 108.) Such a border strip tableau
defines a covering of the shape of λ with m (disjoint) dominos.
Moreover, it’s easy to see that the dominos of any covering of
λ with m dominos can be ordered so that they define a border
strip tableau, and the proof follows. (A crucial point in extend-
ing the argument to odd n is that a border strip tableau of type
(2, 2, . . . , 2, 1) always has the same square (1, 1) as the border strip
of size 1. This fact breaks down for skew shapes.)
For a generalization to posets, not involving symmetric functions,
see Theorem 5.1 of R. Stanley, Advances in Applied Math. 34
(2005), 880–902; arXiv:math/0211113.
(c) For the first statement, see Prop. 5.3 of the previous reference,
which in fact is valid for more general labelled posets than Schur
labelled skew shapes.
For the second statement, let λ/µ = 43/2. Then we can place
⌊5/2⌋ = 2 disjoint dominos on the diagram of 43/2, but E(43/2) =
5 and O(43/2) = 4.
(d) Similar to (a)–(c); details omitted.

117. (a) For the case of rectangular shapes, see D. E. White, J. Combina-
torial Theory (A) 95 (2001), 1–38.
(b) This was a conjecture of R. Stanley. For proofs see J. Sjöstrand, J.
Combinatorial Theory, Ser. A 111 (2005), 190–203, arXiv.math/0309231,
and T. Lam, J. Combinatorial Theory Ser. A 107 (2004), 87–115,
arXiv.math/0308265.

118. (a) For any homogeneous symmetric function Y of degree n, hY, pn1 i
is equal to [x1 x2 · · · xn ]Y (the coefficient of x1 x2 · · · xn in Y ). For
any n-vertex graph G, [x1 x2 · · · xn ]XG is equal to the number of
proper colorings of G using the colors 1, 2, . . . , n once each. Hence
hXG , pn1 i = n!, so the proof follows since Fn is a sum of Cn XG ’s.
P
(b) For any n-vertex
P graph G with X G = λ⊢n dλ eλ , Exercise 7.47(g)
asserts that λ⊢n dλ is the number of acyclic orientations of G
ℓ(λ)=k
with k sinks. Hence ch1n i is the total number of acyclic orientations
of n-vertex unit interval graphs (always up to isomorphism) with

52
 n sinks. The only such graph is the one with no edges, and it has
one acyclic orientation. Hence ch1n i = 1.
(c) Since h2, 1n−2i is the only partition of n with n − 1 parts, we want
the total number of acyclic orientations with n − 1 sinks of n-
vertex unit interval graphs. Such a graph can have exactly one
edge (with two acyclic orientations having n−1 sinks), or have two
incident edges (with one acyclic orientation having n − 1 sinks).
There are n − 1 n-vertex unit interval graphs with exactly one
edge, and n − 2 with two incident edges. Hence

ch2,1n−2 i = 2(n − 1) + (n − 2) = 3n − 4.

(d) Let the unit interval graph G have vertices 1, 2, . . . , n in the order
of the unit intervals that define it. (The unit intervals are ordered
by the order of their left endpoints.) Let vertex i be adjacent to
di vertices j < i (so d1 = 0). It is easy to see that
n
Y
χG (q) = (q − di ).
i=1

It is well-known that (−1)n χG (−1)Q = ao(G), the number of acyclic

orientations of G. Hence ao(G) = (di + 1). It is also easy to see
that these sequences (d1 , . . . , dn ) ∈ Pn are characterized by d1 = 1
and di+1 ≤ 1+di . Let Dn denote the set of all such sequences. (We
have #Dn = Cn by Exercise 80 in R. Stanley, Catalan Numbers.)
We need to show that
Y
di = (2n − 1)!!.
(d1 ,...,dn )∈Dn

Let ei = 2i − di . It is not hard to see that the number of complete

matchings M on [2n] such that e1 , . . . , en are the smaller vertices
of the edges of M is equal to d1 · · · dn . Moreover, all possible such
“smaller vertex” sets {e1 , . . . , en } are obtained in this way, and
the proof follows.
(e) Let G be any n-vertex graph and v any vertex of G. Greene and
Zaslavsky (1983) showed that the number of acyclic orientations

53
 of G having v as the only sink is equal to [q]χG (q). Using the
notation of (d) above, it follows that
X
c(n) = n (d2 − 1)(d3 − 1) · · · (dn − 1).
(a1 ,...,an )∈Dn

The set of sequences (d2 − 1, . . . , dn − 1) with no term equal to 0

is just the set Dn−1 , so the proof follows from (d).
(g) Answer. Write a matching M on [2n] in the canonical form
((a1 , b1 ), . . . , (an , bn )), where a1 < a2 < · · · < an and ai < bi .
Let wM be the standardization of the sequence b1 , . . . , bn . Then
X
ωFn = pρ(wM ) ,
M

summed over all matchings on [2n].

Example. When n = 2, the matchings are (12, 34), (13, 24), and
(14, 23). The sequences b1 , b2 are 24, 34, 43, with standardizations
12, 12, 21. Hence
ωF2 = 2pρ(12) + pρ(21) = 2p21 + p2 .

119. Follows from the solution to Exercise 7.47(f), or equivalently, from The-
orem 3.1 and equation (8) of R. Stanley, Advances in Math. 111 (1995),
166–194. See also T. Y. Chow, arXiv:math/9712229. (The difficulty
rating of this exercise assumes no knowledge of Exercise 7.47(f).)
120. (a) Let M = xa11 · · · xakk be a monomial of degree n, with each ai > 0.
Suppose that M appears in LXdes(w) . Write w as a juxtaposi-
tion (not the product of permutations in Sn ) v1 v2 · · · vk , where
vi has length ai . The partial permutations vi therefore have no
a a
X-descents. For π ∈ Sk let π(M) = x1π(1) · · · xkπ(k) . Then π(M)
appears in the permutation vπ(1) · · · vπ(k) . It follows easily that UX
is a symmetric function.
Moreover, if rj (M) of the bi ’s are equal to j, then the vi ’s of length
j can be permuted in rj (M)! ways. Hence the coefficient of M
in Ux is divisible by r1 (M)! · · · rk (M)!. In other words, UX is
a Z-linear combination of the augemented monomial symmetric
functions m̃λ of Problem 84(c). Now use Problem 85 to deduce
that UX is p-integral.

54
(b) Answer: UX = ωUX .
(c) Conjectured by R. Stanley and proved by I. Gessel (private com-
munication dated 5 November 2021).
Here is a sketch of Gessel’s proof. For any finite multiset M of
positive integers define
(M )
X
UX = LXDes(w) ,
w

where the sum is over all permutations w of the multiset M. Write

just UX when M = [n].
Define the generating function
X X
G(t) = tm y i1 · · · y im ,
m≥0 i1 ,...,im

where the inner sum is over all sequences i1 i2 · · · im with no X-

descents. One first shows (proof omitted) that if M = {1j1 , 2j2 , . . . }
(M )
then UX is the coefficient of y1j1 y2j2 · · · in the infinite product
Y
P := G(xk ).
k≥1

For simplicity we will ignore powers of yi greater than 1, i.e., we

are working in the ring Q[[x1 , x2 , . . . , y1 , y2 , . . . ]]/(y12, y22, . . . ). Let
X
g(t) = log G(t) := gm tm .
n≥1

Then X X X
log P = g(xk ) = gm xm
k = g m pm ,
k≥1 k,m≥1 m≥0
so !
X
P = exp g m pm . (30)
m≥0

We claim that g(t) counts words (without repetitions) with no

X-descents that start with their smallest entry. By the exponen-
tial formula, this is equivalent to the existence of a bijection from

55
 sets of words (with disjoint distinct entries) that start with their
smallest entry to words (with no repetitions) with no X-descents:
given a set of such words, we concatenate them in increasing or-
der of their first element. The inverse is that we cut each word
before each left-to-right maximum. We only need to check that
concatenating words doesn’t introduce any new X-descents. This
follows from the property that if (i, j) ∈ X then i > j. Thus when
we exponentiate in equation (30) we recover all words without X-
descents, but now weighted as in the problem.
(d) No. Gessel noted that if X = {(1, 3), (2, 1), (3, 1), (3, 2)}, then
UX = p31 − p2 p1 + p3 .
(e) Equivalent to Problem 119 above.
(f) Expand the right-hand side of equation (11) in terms of the fun-
damental quasisymmetric functions LS . We need to show that the
coefficient of LS is equal to the number of permutations w ∈ Sn
with XDes(w) = S. Now the L-expansion of si,1n−i is given by
X
si,1n−i = LS .
[n−1]
S∈( n−i )

Thus we need ∈ S
n with XDes(w) =

to show that the number of w [n−1]
S ∈ [n−1]
n−i
is equal to fi . Hence given S ∈ n−i
we want to define
a bijection

{w ∈ Sn : XDes(w) = S} → {u ∈ Si : XDes(u) = ∅}.

Given w, factor it (as a word) into maximal factors of the form

k, k − 1, . . . , k − i to obtain u. For instance, if w = 3247651 (so
S = {1, 4, 5}) then we factor w as 32 · 4 · 765 · 1. Now replace the
factor with the least elements by 1, the factor with the next least
elements by 2, etc. For our example we replace 1 by 1, 32 by 2, 4
by 3, and 765 by 4 to get u = 2341. It is easy to check that this
procedure gives the desired bijection.
(g) Similar to (f).
(h) Similar to (f) and (g).

121. (a) Immediate from the definition of UX and Problem 120(b).

56
 (b) It suffices to verify it for f = pi , which is routine.
(c) Follows from (a), (b), and the p-integrality of UX (Problem 120(a)).
This result appears as Problem 7.7 in I. Tomescu, Problems in
Combinatorics and Graph Theory, John Wiley & Sons, Chich-
ester, 1985. The proof given here is due to D. Grinberg, private
communication, 5 April 2022.

122. (a) Let w = a1 a2 · · · an ∈ Sn and XDes(w) = S = {i1 , . . . , ik }. Let

w r = an an−1 · · · a1 , S ′ = {n − i1 , . . . , n − ik }, and S = [n − 1] − S.
Since X is a tournament, XDes(w r ) = S ′ P (where the meaning of
XDes should be clear). Suppose that f = S⊆[n−1] cS FS ∈ Λn . It
P
is easily seen that ωf = S⊆[n−1] cS FS . On the other hand, by
Proposition 7.19.2, cS = cS ′ . From these observations the result
follows.
(b) This remarkable formula was proved by Darij Grinberg (private
communication, 19 April 2022).
(c) Note that ham(X) is the sum of the coefficients in the power sum
expansion of UX . Moreover, for any X the coefficient of pn1 is 1.
If (b) holds then all other coefficients are even, so the sum of the
coefficients is odd, and the proof follows.
The result that every tournament has an odd number of Hamil-
tonian cycles is due to L. Rédei, Acta Litteraria Szeged 7 (1934),
39–43.

123. (b) This result is equivalent to a result of I. Schur, Math. Z. 1 (1918),

184–207, as may be seen by expanding each pρ(w) in the definition
of sfdet(A) in terms of Schur functions and taking the coefficient
of sλ .
(d) Similarly, this result is equivalent to a result of J. Stembridge,
Bull. London Math. Soc. 23 (1991), 422–428. For a generalization
of (b) and (c), see B. Kostant, J. Amer. Math. Soc. 8 (1995),
181–186.
(e) Similarly, this assertion is equivalent to Stembridge, Canad. J.
Math. 44 (1992), 1079–1099 (Conjecture 2.1).
(f) M. Guay-Paquet, arXiv:1306.2400, has reduced Exercise 7.47(j)
to the case where P is both (3 + 1)-free and (2 + 2)-free, i.e.,

57
 a semiorder (solution to Exercise 6.19(ddd)). It follows from
the sentence preceding Conjecture 5.1 of R. Stanley, Advances
in Math. 111 (1995), 166–194, that Exercise 7.47(j) is equivalent
to the h-positivity of sfdet(A), where if G has n vertices then A
is the n × n (0, 1)-matrix with the 0’s occupying a certain rotated
Young diagram justified into the lower left-hand corner and lying
below the main diagonal. Such a matrix is totally nonnegative, so
Exercise 7.47(j) is a special case of (d). For another combinatorial
application of the total nonnegativity of A, see the final paragraph
of R. Stanley, J. Combinatorial Theory (A) 74 (1996), 169–172.

124. See T. Lam and P. Pylyavskyy, International Math. Research No-

tices 2007 (2007), rnm125, arXiv:0705.2189 (§9). Item (c) first ap-
peared as Proposition 14 of M. Shimozono and M. Zabrocki, Stable
Grothendieck symmetric functions and Ω-calculus, unpublished manu-
script dated February 4, 2003. The result also appears as Corollary
15 of A. Amanov and D. Yeliussizov, arXiv:2003.03907v1. Closely
related results appear in D. Yeliussizov, J. Algebraic Combinatorics 45
(2017), 295–344 (§10); arXiv:1601.01581.

125. The concept of set-valued tableau is due to A. Buch, Acta Math. 189
(2002), 37–78, arXiv:math/0004137, who showed (a). For (b,c) see
Lam and Pylyavskyy, ibid. For (d), see Proposition 6 of Shimozono
and Zabrocki, ibid. A further paper of interest is J. Bandlow and J.
Morse, Electronic J. Combinatorics 19 (2012), P39; arXiv:1106.1594.
Somewhat different (yet analogous) formulas appear in T. Hudson, T.
Ikeda, T. Matsumura, and H. Naruse, Advances in Math. 320 (2017),
115–156, arXiv:1504.02828; T. Matsumura, Proc. Japan Acad. Ser.
A Math. Sci. 93 (2017), 82–85, arXiv:1611.06483; and J. S. Kim,
arXiv:2003.00540.

126. (a) Equation (13) is due to I. Gessel and C. Reutenauer, J. Combi-

natorial Theory (A) 64 (1993), 189–215 (Theorem 2.1).
(b) Immediate from (a), the definition of Lλ , and the fact that L4 =
L2,1,1 .
(c) The values of f (n) for 1 ≤ n ≤ 15 are 1, 2, 3, 4, 6, 10, 13, 19,
26, 38, 52, 70, 91, 123, 161. See OEIS A121152. For n = 4
there is one linear dependence, namely, L4 = L211 . For n = 5

58
 the unique linear dependence is L41 = L32 + L2111 . For n = 6 it’s
L6 + L33 = L321 + L3111 . For n = 7, there are two (independent)
relations: L43 = L3211 (a consequence of multiplying the relation
L4 = L211 by L3 ) and L61 + L331 = 2L43 + L322 + L31111 .
127. (a) First proof. Sum equation (13) on all λ ⊢ n. The right-hand side
becomes X
Fco(w) = pn1 .
w∈Sn
Second proof. We can give a purely computational proof, avoiding
the Gessel-Reutenauer result, as follows. By equation (7.191) and
the definition Lhkr i = hr [Lk ] of Exercise 7.89(f), for fixed k we
have X X 1 X k/d
Lhkr i = exp µ(d)pnd . (31)
r≥0 n≥1
nk
d|k

By the multiplicative property Lλ = Lh1m1 i Lh2m2 i · · · of Exer-

cise 7.89(f), we have
!
X Y X
Lλ = Lhkr i .
λ∈Par k≥1 r≥0

Hence by equation (31) we get

X XX 1 X k/d
Lλ = exp µ(d)pnd .
λ∈Par n≥1 k≥1
kn
d|k

Set N = dn and j = k/d. We get

X XX 1 j X
Lλ = exp pN µ(d).
λ∈Par N ≥1 j≥1
jN
d|N
P
Since d|N µ(d) = δ1N (Kronecker delta), we finally obtain
X X1 j
Lλ = exp p
λ∈Par j≥1
j 1
= exp log(1 − p1 )−1
1
=
1−p
X 1
= pn1 ,
n≥0

59
 and the proof follows.
(b) Similar to the second proof of (a).
(c) Also similar to the second proof of (a). Let
!
Y X
Y = (−1)(k−1)r Lhkr i .
k≥1 r≥0

Since ελ = 1 if and only if λ has an even number of even parts,

we have (using (a))
X  
1 1
Lλ = +Y
λ∈Par
2 1 = p 1
ελ =1

Now
X X (−1)(k−1)n X k/d
Y = exp µ(d)pnd .
n≥1 k≥1
kn
d|k

Making the same substitutions N = dn and j = d/k gives

XX 1 j X
Y = exp pN (−1)N (jd−1)/d µ(d).
N ≥1 j≥1
jN
d|N

Note that 
X  −1, n = 1
(−1)N/d µ(d) = 2, n = 2

d|N 0, n ≥ 3.
It follows that
X  (−1)j−1 1

Y = exp pj1 + pj2
j≥1
j j
= exp (log(1 + p1 ) − log(1 − p2 ))
1 + p1
= ,
1 − p2
and the proof follows.

128. (a) Follows readily from Problem 126 above and the formula for Lα (1m )
preceding Proposition 7.19.12.

60
 (b) Note that fj (n) = Lj (1n ). For any f, g ∈ Λ we have

f [g](1n ) = f (1n )|n→g(1n ) , (32)

i.e., take the composition of the polynomial f (1n ) with the polyno-
mial g(1n ). Equation (32) is proved by verifying it for f = pλ and
using



the linearity of f [g] with respect to f . Moreover, hk (1n ) =
n
k
(Section 7.5). The proof now follows from the definition of
Lλ in Exercise 7.89.
(c) Follows readily from Problem 127(c) and the formula for Lα (1m )
near the end of Section 7.19. This result is due to J. Fulman,
G. B. Kim, S. Lee, and T. K. Petersen, Electronic J. Comb. 28
(2021), P3.37 (Theorem 1.1). This paper contains numerous other
results related to the joint distribution of descents and signs of
permutations in the symmetric group and hyperoctahedral group.

129. (a) By Problems 126 and 127(c) we have

* +
X
γn (S) = Lλ , sBS .
λ⊢n
ελ =1
   
1 n n/2
= p + p2 , sBS .
2 1

We
D have E that hpn1 , sBS i = f BS = βn (S). In order to compute
n/2
p2 , sBS , we use the Murnaghan-Nakayama rule (version given
by Corollary 7.17.5 and equation (7.75)). Let D be the unique
domino tiling of BS . Clearly border-strip tableaux of shape BS
and type h2n/2 i correspond to standard Young tableaux of shape
BS/2 , and all have weight (−1)v(BS ) . The proof follows.
Note the curious consequence: if n is even then we can never have
γn (S) = 21 βn (S). Of course this is nontrivial only when βn (S) is
even.
D E
(n−1)/2
(b) Now we must compute p1 p2 , sBS via the Murnaghan-Naka-
yama rule. First remove a border strip of size one (i.e., a corner
square, or a square with no square below it or to the right) from
BS ; then cover the remaining squares with dominos. When we

61
 remove a corner square u the diagram BS breaks up into two
border strips BT and BU (one of which is possibly empty, or when
n = 1 both are empty). Only the case when BT (and hence also
BU ) have an even number of squares will contribute to the answer,
in which case we call u an even corner square. If BS has m squares,
then the contribution will be
 
v(BT )+v(BU ) (n − 1)/2
g(u) := (−1) βm/2 (ST )β(n−m−1)/2 (SU ).
m/2

Thus !
1 X
γn (S) = βn (S) + g(u) ,
2 u

where u ranges over all even corner squares of BS .

(c) Let n be even. This is the special case S = {1, 3, 5, . . . , n − 1}
of part (a). All n/2 dominos are vertical, so v(BS ) = (−1)n/2 .
Moreover, BS/2 is just a single row of size n/2, and the proof
follows.
Let n be odd, so S = {1, 3, 5, . . . , n − 2}. For n > 1 there is
no corner square u that splits BS into two pieces of even size, so
E ∗ (n) = 21 En .
(d) Let n be even. Thus S = {2, 4, 6, . . . , n − 2} and v(BS ) = 0.
Moreover S/2 is a single column of size n/2, and the proof follows.
Let n be odd. Then S = {2, 4, 6, . . . , n − 1}. There are (n + 1)/2
even corner squares u. Label them 0, 1, . . . , (n − 1)/2 = m from
bottom to top. When
we remove
Pm corner
square i, we get the
i m i m
contribution (−1) i . Since i=0 (−1) i = 0 for m > 1, the
proof follows.
Note. The value of En∗ and En′ when n is odd is also an immediate
consequence of Theorem 1.1 (due to F. Ruskey) or Corollary 2.2
of R. Stanley, Advances in Applied Math. 34 (2005), 880–902;
arXiv:math/0211113. It is also easy to see that the formula for
either of En∗ and En′ implies the other, since a reverse alternating
permutation in Sn is obtained from an alternating permutation in
Sn by multiplying on the right by w0 = n, n − 1, . . . , 1. (Consider
whether w0 is even or odd.)

62
 (e) The condition on S is equivalent to BS/2 = ∅. Moreover, v(BS ) =
#S. The proof follows easily.
130. Let o be an orbit of the action of Sk on Ck . Let Go (p1 , p2 , . . . ) be
the Frobenius characteristic symmetric function of the action of Sk on
o. Thus o corresponds to an unlabelled structure σ. It follows from
Theorem A2.8 that the action of Skn on n disjoint copies of σ is given
by hn [Go ]. Now it follows directly from the definition of plethysm that
if f (x1 , x2 , . . . ) ∈ Λ̂, then

pn [f ] = f [pn ] = f (xn1 , xn2 , . . . ).

Hence by equation (34),
X
Fo := hn [Go ]tkn
n≥0
X1
= exp pn [Go ]tkn
n≥1
n
X1
= exp Go (pn , p2n , p3n , . . . )tkn .
n≥1
n

It follows from Proposition 7.18.2 that

YY
Fn = Fo ,
m≥1 o

where o ranges over all orbits of the action of Sm on Cm , and the proof
follows.
See equation (20)c on page 46 of F. Bergeron, G. Labelle, and P. Leroux,
Combinatorial Species and Tree-Like Structures.
131. (a) Suppose that f (n) = β(S, T ). By Corollary 7.23.8 we have β(S, T ) =
hsBS , sBT i. Now
hsBS , sBS i − 2hsBS , sBT i + hsBT , sBT i = hsBS − sBT , sBS − sBT i ≥ 0.

Hence 21 (β(S, S) + β(T, T )) ≥ β(S, T ). Therefore either β(S, S) ≥

β(S, T ) or β(T, T ) ≥ β(S, T ), and the proof follows.
(b) This problem was raised by Ira Gessel (private communication,
2007).

63
132. (a) This result can be deduced from #126, using the fact that a multi-
set permutation (of a totally ordered set) and its standardization
have the same descent set, together with [why?]
X
hα = sS β .
Sβ ⊆Sα

(b) See Theorem 2.3 of R. Stanley, Electronic J. Combinatorics 4

(1997), R20.
(c) The set of all parking functions is a union of sets SM of all per-
mutations of a multiset M. The proof follows from (a) and the
definition of PFn .
P n/d
(d) We have Ln = L(n) = n1 d|n µ(d)pd (equation (7.191)) and
X
PFn = (n + 1)ℓ(λ)−1 zλ−1 pλ
λ⊢n

(by applying ω to the first formula of Exercise 7.48(f)). The proof

follows from the orthogonality relation hpλ , pµ i = zλ δλµ (Propos-
tition 7.9.3).
133. (a,b,d) See Section 5 (the case r = 1) of R. Stanley and Y. Wang
( ), J. Combinatorial Theory, Ser. A 159 (2018), 54–78.
(e) By Problem 132(b) above and Exercise 7.48(f), we have that the
two series

F (t) = t + PF1 t2 + PF2 t3 + · · · , and

G(t) = t − e1 t2 + e2 t3 − · · ·

are compositional inverses. Equating coefficients of tn+1 on both

sides of the identity t = F (G(t)) yields an expansion of PFn as a
polynomial in the symmetric functions (−1)n en . Doing the same
for t = G(F (t)) yields an expansion of (−1)n en as a polynomial in
the symmetric functions PFn with exactly the same coefficients.
A simple homogeneity argument shows the same is true using en
instead of (−1)n en . Since both eλ and PFλ are multiplicative
bases, it follows that Rn = Rn−1 .
(f) Immediate from Rn2 = I.

64
 (h) Follows from applying ω to Problem 6 and using Problem 132(b)
and part (f) of the present problem.
(i) It is easy to see that the e-expansion of PFn has the form PFn =
Cn en1 +· · · . The proof follows from the definition PFλ = PFλ1 PFλ2 · · · .
(j) Generalizing (i) above, it is not hard to show that
n−1
PFn = Cn en1 − Cn e2 e1n−2 + · · · .
2
Thus if λ ⊢ n, then the coefficient of e2 e1n−2 in PFλ is
ℓ(λ)
1X Y 1 Y
− (λi − 1) · Cλi = − (n − ℓ(λ) Cλi .
2 i=1 2

134. See F. Chyzak, M. Mishna, and B. Salvy, J. Combinatorial Theory,

Ser. A 112 (2005), 1–43, arXiv.math/0310132 (Proposition 9.1).
135. Answer: the column vector [χλ (ν)]λ⊢n . Once the answer is guessed, the
verification is straightforward.
136. (a) There are many approaches. We give an elementary argument.
The character χ of the defining representation is given by χ(w) =
#Fix(w), the number of fixed points of w. Thus
X
sn + sn−1,1 = zλ−1 m1 (λ)pλ ,
λ⊢n

where m1 (λ) is the number of parts of λ equal to one. Hence by

definition of internal product,
X
(sn + sn−1,1 )∗k = zλ−1 m1 (λ)k pλ .
λ⊢n
P −1
Now sn = λ⊢n zλ pλ , so
X  k
∂
zλ−1 m1 (λ)k pλ = p1 sn .
λ⊢n
∂p1

It is formal consequence of the commutation relation

∂ ∂
p1 − p1 = 1
∂p1 ∂p1

65
 (where the 1 on the right-hand side denotes the identity operator)
that  k X k
∂ ∂i
p1 = S(k, i)pi1 i . (33)
∂p1 i=1
∂p 1

∂i
(See Exercise 3.209.) Since s
∂pi1 n
= sn−i , the proof follows.
A rather similar argument, but formulated in terms of represen-
tation theory, is given by Dan Petersen at MathOverflow 284054.
The earliest related reference of which we are aware is A. Goupil
and C. Chauve, Sémin. Lothar. Comb. 54 (2005), B54j; arXiv:math/0503307.
♣ Who first looked at this problem? What are some other refer-
ences?
(b) The value of the character

of this Sn -action on a permutation of
m1
cycle type λ is 2 + m2 . Hence
 k
∗k 1 2 ∂2 ∂
(sn + sn−1,1 + sn−2,2 ) = p1 2 + p2 sn .
2 ∂p1 ∂p2

Thus in analogy with equation (33) we need to find the coefficients

cij so that
 k X
1 2 ∂2 ∂ ∂i ∂j
p1 2 + p2 = cij pi1 pj2 .
2 ∂p1 ∂p2 i,j
∂pi1 ∂pj2

∂ i sn ∂ j sn
We can then use ∂pi1
= sn−i (as before) and ∂pj2
= 2−j sn−2j .

137. Open.

138. This result is equivalent to a result of E. Egge, N. Loehr, and G.

Warrington, European J. Combin. 31 (2010), 2014–2027. An elucida-
tion was given by A. M. Garsia and J. B. Remmel, arXiv:1802.09686,
with a simplification by I. M. Gessel, Electronic J. Combin. 26 (2019),
P4.50, arXiv:1803.09271.

139. Immediate from Theorem 7.19.7 and Corollary 7.23.6 (setting f = sλ ).

140. (a) Let α = co(S) and B α the rotation of Bα by 180◦ as in Exer-

cise 7.56. Hence by this exercise we have sBα = sB α . Given an

66
 SSYT of shape B α such as
223
33
4
26

for n = 8 and S = {2, 3, 5}, simply read the entries from left-to-
right and bottom-to-top. For example above we get the sequence
26433223. This sets up a bijection between sequences u = u1 · · · un
with descent set S and terms xu1 · · · xun of sBα .
(b) Straightforward consequence of EC1, second ed., Exercise 4.40.
141. (a) Let λ ⊢ n. The largest α ∈ Comp(n) in lexicographic order such
P [Lα ]sλ 6= 0 is given by α = λ. It follows that [why?] f =
that
µ≤L λ aµ sµ , where aµ ∈ Z and ≤L denotes lex order. Similarly the
smallest β ∈ Comp(n) in lex order Psuch that [Lβ ]sλ 6= 0 is defined
by [n − 1] − Sβ = Sλ′ . Thus f = ν≥L λ bµ sµ where bµ ∈ Z. Hence
fλ = csλ for some c ∈ Q. Since the sλ ’s form an integral basis, we
must have c = 0 or 1. This result and proof are due to L. Billera.
(b) The smallest example is

s31 + s211 − s22 = L31 + L13 + L211 + L112 .

It is an open (and probably very difficult) problem to find all

L-positive symmetric functions u such that if u = f + g, where
f, g ∈ Λ and f, g are L-positive, then f = 0 or g = 0.
P P
142. Since hn = n!1 w∈Sn pρ(w) and en = n!1 w∈Sn εw pρ(w) , we get
2 X
hn + en = pρ(w) .
n! w∈A
n

Hence ZAn = hn + en = sn + s1n .

143. We have cµ = hch(χ), hµ i. Now hµ is the Frobenius characteristic

of the induction 1µ of the trivial representation 1Sµ from Sµ to Sn .
Hence hch(χ), hµ i = hχ, 1µ i. By Frobenius reciprocity this is hχ|µ , 1Sµ i,
as desired. This result for permutation representations is due to V.
Dotsenko, arXiv:0802.1340.

67
144. (a) This follows from the fact that for λ ⊢ n, ex(sλ )|t=1 = f λ /n! > 0,
while 
1, λ = (1n )
ex (pλ )|t=1 =
0, otherwise.
Here ex denotes the exponential specialization (EC2, pp. 304–306).

145. (a) Clearly Sn acts transitively on the set Sn /G of left cosets of

G. (In fact, for any finite group K, the transitive permuta-
tion representations of K correspond to the actions of K on left
cosets of subgroups G.) On the other hand, by Burnside’s lemma
(Lemma 7.24.5) and the fact that ZG = ch 1S G (equation (7.119)),
n

we have thatP the number of orbits is hZG , snλi. Thus hZG , sn i = 1.

If ZG = aλ hλ , then aλ ∈ Z since ch χ = sλ and both the
sλ ’s and hλ ’s are an integral basis. P Moreover, if λ ⊢ n then
hhλ , sn i = Kn,λ = 1. Hence if ZG = λ aλ hλ and ZG is h-positive,
then X
1 = hZG , sn i = aλ ,
λ

where each aλ ∈ N. It follows that ZG = hλ for some λ ⊢ n.

(b) Assume that ZG = hλ = ZSλ , and let ℓ = ℓ(λ). The number
of orbits of G itself acting on 1, 2, . . . , n is by Burnside’s lemma
the average number of fixed points of elements of G and hence
is determined by ZG . Since the action on left cosets of Sλ has
ℓ orbits, the same is true for G. Now Sλ contains an element of
cycle type λ, so G also contains such an element w. Since w has
exactly ℓ cycles and G has ℓ orbits, it follows that G ⊆ H, where
H is a subgroup of Sn conjugate to Sλ . But [pn1 ]ZG = 1/#G, so
#G = #H. Thus G = H, as desired.

146. The identity is equivalent to

! !
X X X
1+ ZeIn xn n!hn xn = n!hn xn .
n≥1 n≥0 n≥0

Equating coefficients of xn gives

n
X
Z̃Ik (n − k)! hn−k = n! hn .
k=1

68
 For every permutation w = a1 · · · an ∈ Sn , there is a unique 1 ≤ k ≤ n
for which u := a1 · · · ak ∈ Ik . For fixed k, the cycle indicator of all such
u is Z̃Ik . For any such u, the cycle indicator of the remaining terms
ak+1 · · · an is (n − k)! hn−k by Exercise 7.111(a). Hence for fixed k, the
cycle indicator of all such w is Z̃Ik (n − k)! hn−k , and the proof follows
by summing on k. This proof is completely analogous to the sketched
proof in the solution to Exercise 1.128(a) of EC1, second ed.
147.(a,b) This is due to Brendan Pawlowski. See MathOverflow #254782.
(c) Take n = 4 and the three partitions to be 12-3-4, 13-2-4, and
14-2-3. Take the three characters to be trivial. We get
f = p41 + 3p21 p2 + 3p1 p3 + p4 = 8s4 + 5s31 − s22 + s211 .

148. S. C. Billey, B. Rhoades, and V. Tewari, Boolean product polynomi-

als, Schur positivity, and Chern plethysm, Int. Math. Res. Not. IMRN
(2019); arXiv:1902.11165.
149. (a) Suppose that the cycle c of w1 · · · wk containing 1 intersects Aj in
ij elements, so the length of this cycle is i1 + · · · + ik − k + 1. The
cycle c will have the form
c = (1, u1, u2 , . . . , uk ),
where uj is a sequence of ij − 1 distinct elements of Aj − {1}.
Q
Hence there are kj=1 (aj − 1)ij −1 choices for c. The elements of
Aj not in c can be any permutation of size aj − ij . The generating
function by cycle type of these permutations is
X
pρ(w) = (aj − ij )!haj −ij .
w∈Saj −ij

Thus the terms of the symmetric function (15) for fixed a1 , . . . , ak , i1 , . . . , ik

yield !
Yk
(aj − 1)ij −1 (aj − ij )!
j=1

·pi1 +···+ik −k+1 xi11 · · · xikk ha1 −i1 (x1 ) · · · hak −ik (xk ).
Q
Note that (aj −1)ij −1 (aj −ij )! = (aj −1)!. Divide by (aj −1)! and
sum on i1 , . . . , ik ≥ 1 and a1 , . . . , ak ≥ 0 to complete the proof.

69
 (b) This result is due to Miriam Farber in 2015. The s-expansion
uses the Schur function expansion of hi hj and the Murnaghan-
Nakayama rule. The h-expansion uses the s-expansion and the
Jacobi-Trudi identity. Are there more conceptual proofs?
(c) G2,2,2 = 8s4 + 5s31 − s22 + s211
(d) This conjecture is due to M. Farber.
(e) Farber has a few more sporadic results and conjectures.

150. Answer. Suppose that G ⊆ SS . Suppose our set of colors is X ∪ X,

where X = {c1 , c2 , . . . } and X = {c1 , c2 , . . . }. Let f : S → X ∪ X be
a coloring of S. Define

Hf = {w ∈ G : w · f = f },

the subgroup of G fixing the coloring f , and let H f be the restriction

of Hf to f −1 (X). Call f a G-super coloring if H f does not contain
an odd permutation. For instance, let S = {1, 2, 3, 4} and let G be
generated by the 4-cycle (1, 2, 3, 4). Write c1 = a and let f be the
coloring aaaa of 1234. Then Hf = {(1)(2)(3)(4), (1, 3)(2, 4)} and H f =
{(2)(4), (2, 4)} 6⊆ A2 (although Hf ⊆ A4 ). Hence f is not a G-super
coloring.
Theorem. The coefficient of xα y β in ZG (x/y) is equal to the number
of G-orbits of G-super colorings f such that αi = #f −1 (ci ) and βi =
#f −1 (ci ) for all i.

151. (a) See R. Stanley, Advances in Applied Math. 34 (2005), 880–902;

arXiv:math/0211113 (Prop. 3.1).
(b) See R. Stanley, Problem 10969, Amer. Math. Monthly 109 (2002),
760 (published solution by O. P. Lossers, 111 (2004), 536–539).
For a generalization, see C. E. Boulet, Ramanujan J. 12 (2006),
315–320, arXiv.math/0308012, repeated in EC1, second ed., Ex-
ercise 1.83.

152. Let F (t) = ex f and G(t) = ex g. We claim that ex f [g] = F (G(t)).

Since the maps ex and f 7→ f [g] are homomorphisms, it suffices to take
f = pn , in which case the computation is straightforward.

70
153. There are many approaches. One way is to note that h2 = 21 (p21 + p2 ).
Hence
1
h2 [hn ] = (h2n + hn (x21 , x22 , . . . )).
2
Now
X 1
hn (x21 , x22 , . . . ) = Q
n≥0
(1 − x2i )
1
= Q
(1 − xi )(1 + xi )
! !
X X
= hj (−1)k hk ,
j≥0 k≥0

whence !
2n
X
1
h2 [hn ] = h2n + (−1)k hk h2n−k .
2
k=0

Expand hk h2n−k into Schur functions by Theorem 7.17.5 (Pieri’s rule)

and collect terms to get
⌊n/2⌋
X
h2 [hn ] = s(2n−2k,2k) .
k=0

This result has been extended e.g. to h3 [hn ] (see for instance S. P. O.
Plunkett, Canad. J. Math. 24 (1972), 541–552), but becomes increas-
ingly unmanageable for h4 [hn ], h5 [hn ], etc.
P
154. Since e21 = i,j xi xj and
X Y
en = (1 + xi ),
n≥0

we have X Y
en [e21 ] = (1 + xi xj ).
n≥0 i,j

Setting yi = xi in the dual Cauchy identity gives

Y X
(1 + xi xj ) = sλ (x)sλ′ (x).
i,j λ

71
 Taking the degree 2n part gives
X
en [e21 ] = sλ (x)sλ′ (x).
λ⊢n

155. Follows from the fact that the operation g 7→ g[f ] is a (continuous) ring
homomorphism and the formula
X X pn
hn tn = exp . (34)
n≥0 n≥1
n

If f and g are sums of monomials, the proof also follows

P from the fact
that when M is a multiset of monomials and r = u∈M u, then
X 1
hn [r] = Q .
n≥0 u∈M (1 − u)

See Lemma 2.3 of I. Gessel and Y. Zhuang, Adv. Math. 375 (2020),
107370; arXiv:2001.00654.
Note that the exponential specialization of equation (16) is equivalent
to ea+b = ea eb .
P P
156. (a) Answer. Let F (x) = an xn and let F (x)h−1i = bn xnPbe its
compositional inverse. Then the plethystic inverse of f is bn pn1
(easy to prove e.g. from the fact that pn1 [pm mn
1 ] = p1 ).
(b) Answer. Define δ : P → Z by δ(n) = δ1n (the Kronecker delta).
Note that δ is the identity for ∗, i.e., F ∗ δ = δ ∗ F = F for all
F . Since a1 6= 0, the function an possesses a unique Dirichlet
inverse bn , i.e., a ∗ b = δ. (For instance, if an = 1 for all n
then bn = µ(n), the number-theoretic
P Möbius function.) Then
the plethystic inverse of f is n≥1 bn pn .
157. See S. Sundaram, The plethystic inverse of the odd Lie representations
Lie2n+1 , arXiv:2003.10700.
158. Let Eij be the matrix in Mat(n, C) with a 1 in the (i, j)-position and
0’s elsewhere, as in Appendix A2, following Theorem A2.4. If A =
diag(θ1 , . . . , θn ) then AEij = θi Eij . Hence the eigenvalues of A acting
on Mat(n, C) are just θ1 , . . . , θn , n times each, so the character of the
action is just n(x1 + · · · + xn ) = ns1 (x1 , . . . , xn ).

72