Question 85
Let $n\in\mathbb N^*$. Let $S$ be the set of strings of $2n$ digits containing $n$ zeros and $n$ ones. Two strings are neighbors if one can be obtained from the other by moving one digit to another position. For example, 11100010 and 10110010 are neighbors: moving the first 0 of the second string two steps to the right gives the first. Let $T$ be a dense subset of minimum cardinality. Prove $$\frac{|S|}{n^2+1}\le|T|\le\frac{|S|}{n+1}.$$
Here $|A|$ denotes the cardinality of $A$.
Here $|A|$ denotes the cardinality of $A$.