Saturated chains of subsets and a random walk (Q1114686)

This paper concerns the problem: How many of the subsets of an n element set can be partitioned into blocks each block of which has cardinality c and consists of subsets of consecutive cardinalities that nest inside one another? It is shown here that one can answer this and the similar covering problem by using the standard inductive construction of a chain partition (due to de Bruijn, et al.), until chains are of size c, and allowing those at that size to remain so as n increases. (In standard construction, as n increases by 1, each chain gives rise to two chains, and one takes the head from one and attaches it to the other; when the chain has length c here one instead leaves the two chains alone.) Asymptotic results are derived for the resulting proportion of subsets in length c chains, and for a related random walk.