Let $S$ be a set of strings over $0,1$ such that if $x$ is in $S$
$x$ has $\le k-1\quad$ $0$'s
$x$ has $\le k-1\quad$ $1$'s
What is the MAX that $\sum_{x\in S} |x|$ can be?
Let $S$ be a set of strings over $0,1$ such that if $x$ is in $S$
$x$ has $\le k-1\quad$ $0$'s
$x$ has $\le k-1\quad$ $1$'s
What is the MAX that $\sum_{x\in S} |x|$ can be?
Hint: the two conditions are independent of each other; thus, if $S_{p,q}$ is the set of all strings with $p$ $0$s and $q$ $1$s, then your sum is $\Sigma_{p=0}^{k-1}\Sigma_{q=0}^{k-1}\Sigma_{x\in S_{p,q}} |x|$. What's the length of a string $x\in S_{p,q}$? How many of them are there?
Clearly there are ${{p+q} \choose p}$ strings in $S_{p,q}$, each of length $p+q$, but getting a closed form for $f(k) = \sum_{p=0}^{k-1}\sum_{q=0}^{k-1}{{p+q} \choose p}(p+q)$ still takes a bit of work.
$\begin{align*} \sum_{p=0}^{k-1}\sum_{q=0}^{k-1}{{p+q} \choose p}(p+q) &= \sum_{p=0}^{k-1}\sum_{q=0}^{k-1}{{p+q} \choose p}p + \sum_{p=0}^{k-1}\sum_{q=0}^{k-1}{{p+q} \choose p}q\\ &= \sum_{p=0}^{k-1}\sum_{q=0}^{k-1}{{p+q} \choose p}p + \sum_{p=0}^{k-1}\sum_{q=0}^{k-1}{{p+q} \choose q}q\\ &= 2 \sum_{p=0}^{k-1}\sum_{q=0}^{k-1}{{p+q} \choose p}p\\ &= 2 \sum_{p=0}^{k-1}p\sum_{q=0}^{k-1}{{p+q} \choose p}\\ &= 2 \sum_{p=1}^{k-1}p{{p+k} \choose {p+1}}\\ &= 2 \sum_{p=1}^{k-1}p{{p+k} \choose {k-1}}. \end{align*}$
Now
$\begin{align*}\sum_{p=1}^{k-1}p{{p+k} \choose {k-1}} &= \sum_{p=1}^{k-1}\sum_{i=1}^p {{p+k} \choose {k-1}}\\ &= \sum_{i=1}^{k-1}\sum_{p=i}^{k-1}{{p+k} \choose {k-1}}\\ &= \sum_{i=1}^{k-1}\left({{2k} \choose k} - {{i+k} \choose k} \right)\\ &= (k-1) {{2k} \choose k} - {{2k} \choose {k+1}} + 1\\ &= k {{2k} \choose k} - {{2k+1} \choose {k+1}} + 1\\ &= k {{2k} \choose k} - {{2k+1} \choose k} + 1, \end{align*}$ so$f(k) = 2 \left(k {{2k} \choose k} - {{2k+1} \choose k} + 1 \right) = 2k {{2k} \choose k} - 2{{2k+1} \choose k} + 2.$ Finally, $2{{2k+1} \choose k} = {{2k+1} \choose k} + {{2k+1} \choose {k+1}} = {{2k+2} \choose {k+1}}$, so$f(k) = 2k {{2k} \choose k} - {{2k+2} \choose {k+1}} + 2.$
That can be written fairly nicely in terms of Catalan numbers, though a connection isn’t immediately apparent (at least to me):$f(k) = 2k(k+1)C_k - (k+2)C_{k+1} + 2= 2(k^2-k-1)C_k + 2,$since $C_{k+1} = \frac{2(2k+1)}{k+2}C_k$.
$f(1) = 0, f(2) = 6, f(3) = 52$, and $f(4) = 310$; the sequence isn’t in OEIS, by the way.