In Any Way but This. Pattern Avoidance. The Basics. 187
37. Let f be the bijection defined in Exercise 17. Let B
m
be the set of
permutations in the domain of f that have exactly m inversions. Give
a simple description of f (B
m
).
38. Find three patterns p, q,andr so that for all positive integers n,we
have S
n
(p, q, r)=n.
39. Are there infinitely many nontrivial pairs of patterns p and q so that
S
n
(p, q) <h
(p,q)
(n) for all n,whereh
(p,q)
(n) is a polynomial function of
n? By nontrivial pairs we mean pairs in which at least one of the two
patterns has at least two alternating runs.
40. Find a formula for the number of 132-avoiding n-permutations whose
longest decreasing subsequence is of length exactly k +1.
41. Find a formula for the number B
1
(a
1
,a
2
,a
3
) of