You are currently browsing the tag archive for the ‘bijective proof’ tag.
Let be a natural number, and let be a permutation of , drawn uniformly at random. Using the cycle decomposition, one can view as the disjoint union of cycles of varying lengths (from to ). For each , let denote the number of cycles of of length ; thus the are natural number-valued random variables with the constraint
We let be the number of cycles (of arbitrary length); this is another natural number-valued random variable, of size at most .
I recently had need to understand the distribution of the random variables and . As it turns out this is an extremely classical subject, but as an exercise I worked out what I needed using a quite tedious computation involving generating functions that I will not reproduce here. But the resulting identities I got were so nice, that they strongly suggested the existence of elementary bijective (or “double counting”) proofs, in which the identities are proven with a minimum of computation, by interpreting each side of the identity as the cardinality (or probability) of the same quantity (or event), viewed in two different ways. I then found these bijective proofs, which I found to be rather cute; again, these are all extremely classical (closely related, for instance, to Stirling numbers of the first kind), but I thought some readers might be interested in trying to find these proofs themselves as an exercise (and I also wanted a place to write the identities down so I could retrieve them later), so I have listed the identities I found below.
- For any , one has . In particular, .
- More generally, for any and with , one has .
- More generally still, for any and with , one has
- In particular, we have Cauchy’s formula: if , then the probability that for all is precisely . (This in particular leads to a reasonably tractable formula for the joint generating function of the , which is what I initially used to compute everything that I needed, before finding the slicker bijective proofs.)
- For fixed , converges in distribution as to the Poisson distribution of intensity .
- More generally, for fixed , converge in joint distribution to independent Poisson distributions of intensity respectively. (A more precise version of this claim can be found in this paper of Arratia and Tavaré.)
- One has .
- More generally, one has for all natural numbers .