2
$\begingroup$

Say we are forming sequences of numbers in the interval [0-9], lengths of (2x) where x is a value from [1,5]. So we form sequences of 2, 4, 6, 8, and 10 numbers. A successful sequence is a sequence where at least half of the elements, (at least x of the elements), are the same number consecutively. What is the total of 2, 4, 6, 8, and 10 number sequences that are successful?

Example: 2234 is successful. 3131 is not. 12 is successful. 2233 is successful. 2223 is successful.

Solution attempt: My original plan was to choose 1 of the 10 numbers to have x times in a row, so 10 choices.

My second step was to choose the starting location of the x-length piece, and the x-length piece can be started at either the first position, all the way up to the x+1 position in the 2x length sequence. So there are x+1 choices for the starting point of the x-length sequence.

My third step was to choose 1 of 10 letters for each of the remaining x slots, but now I realize I am double counting.

For example, the sequence 1122 could be obtained by choosing 11 as our x length sequence, placing it in the first slot, and happening to choose 2s to fill the remaining slots. 1122 could also be obtained by choosing 2 for the x length sequence, placing it in the third (x+1) slot, and happening to choose 1s to fill the rest.

I am assuming this is some sort of summation for values of x 1,2,3,4,5 or 2x, 2,4,6,8,10. However, I am unsure of how to account for double counting in a way that is applicable to the general pattern of the scenario. This isn't exactly something I feel should be solved with brute force. Any help would be greatly appreciated.

$\endgroup$
  • $\begingroup$ So a sequence is 'successful' if and only if it contains a subsequence of length $x$, which is entirely made up of one integer from [0..9]? $\endgroup$ – Akay Feb 23 '17 at 8:53
  • $\begingroup$ For example, is 345558 successful? $\endgroup$ – Akay Feb 23 '17 at 9:16
  • $\begingroup$ Yes, this is correct. $\endgroup$ – rubyquartz Feb 23 '17 at 11:06
  • $\begingroup$ At least length x, so 345555 is also successful. $\endgroup$ – rubyquartz Feb 23 '17 at 11:10
  • $\begingroup$ Did you delete your answer? I had intended to mark it accepted but you seem to have removed it. $\endgroup$ – rubyquartz Feb 23 '17 at 16:15
2
$\begingroup$

Here we use generating functions to derive the number of successful sequences of length $2x$ containing $x$ consecutive equal characters, $x\in\{2,3,4,5\}$ over a $10$ character alphabet.

But before that we consider the special, simple case $x=1$.

Case $x=1$: Each word having length $2x=2$ is a successful sequence. So there are
\begin{align*} 10^2=\color{bue}{100} \end{align*} different words.

We continue by stating a generating function which counts words of a $10$ character alphabet with no consecutive equal characters at all.

These words are called Smirnov or Carlitz words. See example III.24 Smirnov words from Analytic Combinatorics by Philippe Flajolet and Robert Sedgewick for more information.

The generating function $A(z)$ counting Smirnov words over a $10$ character alphabet is according to the reference \begin{align*} A(z)&=\left(1-\frac{10z}{1+z}\right)^{-1} \end{align*}

The coefficient of $z^n$ of $A(z)$ gives the number of Smirnov words of length $n$.

Based upon $A(z)$ we generate all words over the $10$ character alphabet which contain for $x\in \{2,3,4,5\}$ no more than $x-1$ consecutive equal characters. This means each character can be replaced with one up to $x-1$ characters.

\begin{align*} z\longrightarrow z+z^2+z^3+\cdots+z^{x-1}=\frac{z(1-z^{x-1})}{1-z} \end{align*} in the generating function $A(z)$.

We obtain this way a generating function $B(z)=A\left(\frac{z(1-z^{x-1})}{1-z}\right)$ with \begin{align*} B(z)&=\left(1-\frac{10\cdot \frac{z(1-z^{x-1})}{1-z}}{1+\frac{z(1-z^{x-1})}{1-z}}\right)^{-1}=\frac{1-z^x}{1-10z+9z^x}\\ \end{align*} The coefficient of $z^{2x}$ of $B(z)$ gives the number of words which contain less than $x$ consecutive equal characters.

The number of all words over a $10$ character alphabet is given by \begin{align*} \sum_{n=0}^\infty (10z)^j=\frac{1}{1-10z} \end{align*}

We conclude the generating function $C_x(z)$ with \begin{align*} C_x(z)=\frac{1}{1-10z}-\frac{1-z^x}{1-10z+9z^x}\qquad\qquad x\in\{2,3,4,5\} \end{align*} counts the words which contains runs of length $x$, i.e. words having at least $x$ consecutive equal characters.

The number of successful sequences of length $2x$ is \begin{align*} [z^{2x}]C_x(z)\qquad\qquad x\in\{2,3,4,5\} \end{align*}

In the following we obtain the series expansions below with some help of Wolfram Alpha

Case x=2:

The number of successful sequences of length $2x=4$ is \begin{align*} [z^4]C_2(x)&=[z^4]\left(\frac{1}{1-10z}-\frac{1-z^2}{1-10z+9z^2}\right)\\ &=[z^4]\left(10z^2+190z^3+2710z^4+34390z^5+\cdots\right)\\ &=\color{blue}{2710} \end{align*}

Case x=3:

The number of successful sequences of length $2x=6$ is \begin{align*} [z^6]C_3(x)&=[z^6]\left(\frac{1}{1-10z}-\frac{1-z^3}{1-10z+9z^3}\right)\\ &=[z^6]\left(10z^3+190z^4+2800z^5+36910z^6+\cdots\right)\\ &=\color{blue}{36910} \end{align*}

Case x=4:

The number of successful sequences of length $2x=8$ is \begin{align*} [z^8]C_4(x)&=[z^8]\left(\frac{1}{1-10z}-\frac{1-z^4}{1-10z+9z^4}\right)\\ &=[z^8]\left(10z^4+190z^5+2800z^6+37000z^7+459910z^8+\cdots\right)\\ &=\color{blue}{459910} \end{align*}

Case x=5:

The number of successful sequences of length $2x=10$ is \begin{align*} [z^{10}]C_5(x)&=[z^{10}]\left(\frac{1}{1-10z}-\frac{1-z^5}{1-10z+9z^5}\right)\\ &=[z^{10}]\left(10z^5+190z^6+2800z^7+37000z^8+460000z^9+5499910z^{10}+\cdots\right)\\ &=\color{blue}{5499910} \end{align*}

Adding all the results we finally obtain

The number of successful sequences is \begin{align*} 100+\sum_{j=2}^5[z^{2j}]C_j(x)&=100+2710+36910+459910+5499910\\ &=\color{blue}{5999540} \end{align*}

| cite | improve this answer | |
$\endgroup$
1
$\begingroup$

As you ask for a sequence of length x, there are not many ways to have two sequences of distinct numbers in a sequence of length 2x. Precisely, you can chose 10 numbers for the first sequence, and 9 for the second, so 90 in total.

What is more difficult are longer sequences of the same number, for instance 1112 is counted 2 times, and 1111 even 3 times.

To avoid double counting these sequences, count the number of sequences of length x, and subtract the number of sequences of length x+1. A sequence of length x+k is now counted exactly once: you add it k+1 times when you count the sequences of length x, and subtract it k times when you subtract the sequences of length x+k.

To have the answer you want, you still have to count the possibilities of x and x+1 sequences for every x, subtract the possibilities of two sequences of different numbers and add all together, but I assume this is not considered as brute force.

| cite | improve this answer | |
$\endgroup$
1
$\begingroup$

Consider a valid string containing $x$-tuple of twos, and an extra $n\ (0\leq n\leq x)$ number of twos. Thus you end up with exactly $(x-n)$ non-two symbols(of which there are $9^{x-n}$ possibilities) in the string. The $x$-tuple could be anywhere in the $(x-n+1)$ positions between/beyond these symbols.

The only positions left to be enumerated now are for the extra $n$ twos; these can go into any combination of $(x-n+2)$ places between the objects we have so far. Take a look at the partition adjacent to the $x$-tuple on the left and the one on the right. It should not matter if we assign $2$ twos to the one on the left and a single two to the one on the right, the end result is that you end up with a $(x+3)$-tuple of twos. (**Old explanation: This means we are overcounting by a factor of two. So remember to divide the above binomial coefficient by $2$. **Not true when n=0; also not true if both the partitions are assigned zero.)

So the two partitions may be combined into one. Note that multiple twos may occupy a single position here, so we are looking for the number of weak compositions of $n$ twos into $(x-n+1)$ partitions, which is: $$ \binom{n+(x-n+1)-1}{n} = \binom{x}{n} $$

Now put everything together:

$$ 10\sum_{n=0}^{x} 9^{x-n}(x-n+1) \binom{x}{n} $$ This still overcounts by exactly 90. (verified for each of $x=1,2,3,4$)

If you do a few examples by hand you'll notice that it double counts every case where a sequence consists of two parts: an $x$-tuple of one symbol, and an $x$-tuple of another symbol. For example, $x=2, n=0$: The sequence 2233 will be counted twice; once while counting sequences with $x$-tuple of $2$'s and again while counting $x$-tuple of $3$'s. Accounting for every such permutation, we have: $$ 10\sum_{n=0}^{x}\left\{ 9^{x-n}(x-n+1) \binom{x}{n} \right\} - \left(10 \right)_2 $$

| cite | improve this answer | |
$\endgroup$

Your Answer

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

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