# $S$ a set of strings such that no string has $\ge k-1$ $0$'s or $1$'s. Maximize $\sum_{x\in S} |x|$

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?

-
(I admit, despite my answer below I'm a little confused by the question of 'MAX' here - there's nothing to indicate what variable the maximum is being taken over. My presumption is that it's the max over all sets $S$ satisfying the condition, but there's clearly an easily-defined set $S_0$ which contains all $x$ satisfying the conditions specified, and the value of the max is then just the value of the sum over $x\in S_0$.) –  Steven Stadnicki Jul 8 '11 at 17:51

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?

-
Steven Stadnick: YES, I mean over all S, and YES I should have stated it more simply as THE set S that has all such strings. –  GASARCH Jul 8 '11 at 18:26

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.

-