3
$\begingroup$

Consider a binary string of length $n$. We call the string good if the number of zeros and ones in the string are at most $m$.

Example: Let $n=4$ and $m=2$. Then the binary string 1010 is good, while the binary string 0010 is not.

Example: Let $n=4$ and $m=1$. Then no good string exists.

To count the number of good binary strings, one can use the following formula:

$$f(n,m) = \sum_{i=n-m}^{m} \binom{n}{i}$$

Mathematica derives the following closed-form for $f$:

$$\binom{n}{n-m} \cdot {}_{2}F_{1} \Big(1; -m; 1 - m + n; -1 \Big) - \binom{n}{m+1} \cdot {}_{2}F_{1} \Big(1; 1 + m - n; 2 + m; -1 \Big) \,,$$

where ${}_{2}F_{1}(a,b;c;z)$ is the hypergeometric function.


Now consider the same problem, this time for ternary strings of length $n$: The string is good if the number of zeros, ones, and twos in the string are at most $m$.

Example: Let $n=4$ and $m=2$. Then the ternary string 0120 is good, while 0001 is not.

To count the number of good ternary strings, one can use the following formula (which uses the notation for multinomial coefficients):

$$g(n,m) = \sum_{i=n-2m}^{m} \sum_{j=n-m-i}^{m} \binom{n}{i,j,n-i-j}$$

Q1. Is it possible to write the closed-form solution for $g(n,m)$ as we did for $f(n,m)$, perhaps using generalized hypergeometric function?

Q2. More generally, is it possible to derive closed-form solutions if the string is consist of $k$ symbols? ($k=2,3$ for binary and ternary strings, respectively)

$\endgroup$
  • $\begingroup$ Haven't you found a closed formula already? $\endgroup$ – Fimpellizieri Jul 21 '17 at 18:21
  • $\begingroup$ "We call the string good if the number of zeros and ones in the string are at most $m$." This definition implies every string will be "good" if $m \geq n/2$... right? $\endgroup$ – David G. Stork Jul 21 '17 at 18:23
  • $\begingroup$ @DavidG.Stork: Yes. $\endgroup$ – M.S. Dousti Jul 21 '17 at 18:24
  • $\begingroup$ But won't every string be good under your definition, regardless of $m$, because either there will be more $1$s than $m$ or more $0$s than $m$? $\endgroup$ – David G. Stork Jul 21 '17 at 18:29
  • $\begingroup$ @DavidG.Stork: No. Assume $n=4$ and $m=2$. The string 0000 is not good, even though the number of $0$s is more than $m$. $\endgroup$ – M.S. Dousti Jul 21 '17 at 18:40

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.