#26. Counting Compositions
(Back to course page.)
Link to Slides · Link to recording
Prompts for discussion:
There are 2^{n!} subsets of S_n. It would be interesting to know, even in terms of rough estimates, how the sizes of |P \circ P| are distributed over these subsets. I wonder if subsets that are “close to being subgroups” would report values on the lower end of their range, and it would be nice if this can be quantified in terms of the “distance from being a subgroup”, which is a somewhat vague idea :)
Other ideas for algorithms that count |P \circ P|, randomized or otherwise?
Vinay suggested a nice alternate proof for the main argument that did not involve invoking SZ. This is a note-to-self to add the description to the slides and/or these notes.
