Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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?

share|improve this question
2  
(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

2 Answers 2

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?

share|improve this answer
    
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.

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.