We call a bijection a "permutation" of the set . Let denote the set of all the permutaions of . In particular, for a permutation of the form , for a subset of is called a "cycle of length k" or simply a "k-cycle" if for all and (the definition of a "1-cycle" being the obvious identity). Then it is easy to see that every permutation may be written uniquely (upto order of cycles) as a product of disjoint cycles. Thus it makes sense to speak of the number of cycles of an arbitrary permutation of . It may be quite interesting to note that for any (fixed) positive integer the expression
is independent of any permutation in and may be expressed as a very simple closed form (in fact a single binomial coefficient) involving nothing but and . Find this binomial coefficient and prove the relevant identity.
A Few Hints Towards a Possible Approach (Spoiler Alert, goes without saying):
Given nonnegative integers such that can you count the number of elements of whose cycle decomposition have exactly cycles of length for all .
You may need the infinite formal series:
This problem is a part of Tessellate S.T.E.M.S. (2019)