3
$\begingroup$

I have an integer list that is n long and each value can be ranging from 1 .. n.

I need a formula that tells me how many of all possible lists for a given n, that have one or more consecutive sequences of a length of exactly 2 of the same number and no other consecutive sequences that are longer than 2.

For example for n=5:

These two should count:

{ 1, 1, 5, 3, 3 }
{ 2, 3, 2, 5, 5 }

Where as these should not:

{ 1, 1, 1, 2, 2 }
{ 1, 3, 2, 5, 4 }

I've been attempting to do this by looking at the possible sequences using the following formula where x = n-1:

(n) x n n = x * n^3
x (n) x n = x^2 * n^2
n x (n) x = x^2 * n^2
n n x (n) = x * n^3

And sum these four up.

However, these also needs to take overlaps between the four into account. This is where I could use a bit of help..? What would the formulas be for excluding the overlaps?

An alternative approach would also be welcome.

Going trough all sequences counting manually is not an option - I need this to work for for n larger than what makes that approach computationally feasible.

If it helps anyone, I've written a little program that runs trough all the sequences and counts have the following results:

n = 2
L[2]: 2
L[1]: 2

n = 3
L[3]: 3
L[2]: 12
L[1]: 12

n = 4
L[4]: 4
L[3]: 24
L[2]: 120
L[1]: 108

n = 5
L[5]: 5
L[4]: 40
L[3]: 280
L[2]: 1520
L[1]: 1280

Where n = 5, L[2]: 1520 is the result I've asked for a formula to in the above question.

$\endgroup$
  • $\begingroup$ You are using the word permutation to mean something different from what the rest of us mean when we use that word. $\endgroup$ – Gerry Myerson Sep 29 '13 at 12:59
  • $\begingroup$ I rephrased it a bit - I hope it makes better sense. $\endgroup$ – Kasper Middelboe Petersen Sep 29 '13 at 13:10
  • $\begingroup$ Are ${ 2, 3, 2, 5, 5 }$ and ${ 3, 2, 2, 5, 5 }$ different sequences that both count? $\endgroup$ – miracle173 Sep 29 '13 at 13:37
  • $\begingroup$ @miracle173 yes $\endgroup$ – Kasper Middelboe Petersen Sep 29 '13 at 13:40
  • $\begingroup$ Does $1, 2, 3, 1$ count? Ie, can the doubled elements "wrap around"? $\endgroup$ – Jack M Sep 29 '13 at 13:58
2
$\begingroup$

How many sequences of length $q$ of numbers from $\{1,...,p\}$ are there such that consecutive elements are always different? For the first element of such a sequence we can selcet one of the $p$ different values of $\{1,...,p\}$. For the following $q-1$ positions we can select always all values from $\{1,...,p\}$ except the value of its predecessor in the sequence. These are $p-1$ possible values. So we have

$$ p(p-1)^{q-1}$$

different sequences.

$\Omega_n$ is the number of sequences of length $n$ with elements from $\{1,\ldots,n\}$ such that no three consecutive elements have the same value but at least one pair of consecutive elements have the same value.

$\Omega_{n,k}$ is the number of sequences of length $n$ with elements from $\{1,\ldots,n\}$ such that no three consecutive elements have the same value but exactly $k$ pairs of consecutive elements have the same value.

For arbitrary $n$ there are $k \le \frac{n}{2}$ different possible values for the number of consecutive element pairs that have equal values.

We have

$$|\Omega_{n}|=\sum_{k=1}^{\lfloor \frac{n}{2}\rfloor }|\Omega_{n,k}|$$

Now we select a $k$. Choose a sequence of $n-k$ values from $\{1,\ldots,n\}$ such that two consecutive values always differ. There are $n (n-1)^{n-k-1}$ such sequences. For such a sequence we select $k$ of its elements (there are $\binom{n-k}{k}$ such possibilities) and insert an element with the same value after each selected value. So $$|\Omega_{n,k}|=\binom{n-k}{k}n(n-1)^{n-k-1}$$ and $$|\Omega_{n}|=\sum_{k=1}^{\lfloor \frac{n}{2}\rfloor }\binom{n-k}{k}n(n-1)^{n-k-1}$$

  • For $n=3$ there are $12$ sequences.

  • For $n=4$ there are t $120$ sequences.

  • For $n=5$ there are $1520$ sequences.

The answer to the original question is deleted

$\endgroup$
  • $\begingroup$ @KasperMiddelboePetersen The formula would be $n\sum_{k=1}^{\lfloor \frac{n}{2}\rfloor }\frac{(n-k)(n-k-1)\ldots(n-2k+1)}{k!}(n-1)^{n-k-1}$. If you are doing more combinatorics problems, it would be a worth-while investment of time to study binomial coefficients, just a bit. $\endgroup$ – Marc van Leeuwen Sep 29 '13 at 20:27
  • $\begingroup$ @MarcvanLeeuwen thanks - I'd just figured it out and deleted the comment 30 seconds before you answered :) It will be a challenge to calculate this for a large value of n though. $\endgroup$ – Kasper Middelboe Petersen Sep 29 '13 at 20:32
  • $\begingroup$ I think the only challenge is computing with large integers. For $n=69$, I get 4676495092345476699420593108779018542679373291685221536304769813013106968507850431624264673416798415845073262231682605593395200, no sweat. $\endgroup$ – Marc van Leeuwen Sep 29 '13 at 20:43
1
$\begingroup$

Here is a different solution that may interest you. Introduce three sequences $a_{n,k}$, $b_{n,k}$ and $c_{n,k}$ that count the number of strings over $\Sigma^k$ where $|\Sigma|=n,$ that end in a digit that is not repeated, a digit that is repeated twice and a digit that is repeated at least three times. In fact we take these sequences to be generating functions in two variables, where the variable $v$ counts occurrences of subsequences of length exactly two and $w$ counts occurrences of subsequences of length at least three.

This gives the following set of recurrences: $$a_{n,k} = (n-1) a_{n,k-1} + (n-1) v b_{n,k-1} + (n-1) c_{n,k-1}, $$ $$b_{n,k} = a_{n,k-1} \quad\text{and}\quad c_{n,k} = w b_{n,k-1} + c_{n,k-1}.$$

With these settings the generating function of all elements of $\Sigma^k$ classified according to the number of length 2 and length more than two subsequences is given by $$a_{n,k} + v b_{n,k} + w c_{n,k}.$$

Observe that $a_{n,1} = 1$ and $b_{n,1} = c_{n,1} = 0.$ Furthermore the last recurrence implies that $$c_{n,k} = w \sum_{q=1}^{k-1} b_{n,q} = w \sum_{q=1}^{k-2} a_{n,q}.$$

Taken together this yields a recurrence for $a_{n,k}:$ $$a_{n,k} = (n-1) a_{n,k-1} + (n-1) v a_{n,k-2} + (n-1) w \sum_{q=1}^{k-3} a_{n,q}. $$

Introduce the trivariate generating function $$G_n(z) = \sum_{k\ge 1} a_{n,k} z^k.$$

Multiply the recurrence by $z^k$ and sum for $k\ge 4:$ $$\sum_{k\ge 4} a_{n,k} z^k = (n-1) z \sum_{k\ge 4} a_{n,k-1} z^{k-1} + (n-1) vz^2 \sum_{k\ge 4} a_{n,k-2} z^{k-2} \\+ \sum_{k\ge 4} (n-1) w z^k [z^{k-3}] \frac{1}{1-z} G_n(z). $$ Now $a_{n,1} = n, \; a_{n,2} = n(n-1)$ and $$a_{n,3} = n(n-1)^2 + n(n-1)v.$$ The equation derived from the recurrence now becomes $$ G_n(z) - (n(n-1)^2 + n(n-1)v)z^3 - n(n-1)z^2 -nz \\= (n-1)z (G_n(z) - n(n-1)z^2 -nz) + (n-1)vz^2 (G_n(z) - nz) \\ + (n-1)w z^3 \sum_{k\ge 4} z^{k-3} [z^{k-3}] \frac{1}{1-z} G_n(z).$$ The sum term simplifies to $$(n-1)w z^3 \frac{1}{1-z} G_n(z).$$ We may now solve for $G_n(z),$ getting $$G_n(z) = -{\frac {nz \left( -1+z \right) }{-nz+n{z}^{2}-{z}^{2}-v{z}^{2}n+v{z}^{3}n+v{ z}^{2}-v{z}^{3}-w{z}^{3}n+w{z}^{3}+1}}.$$ Now the generating function for $b_{n,k}$ is $$z G_n(z) \quad\text{and the one for}\; c_{n,k} \; \text{is}\quad \frac{wz^2}{1-z} G_n(z).$$ It follows that the generating function $H_n(z)$ of $a_{n,k} + v b_{n,k} + w c_{n,k}$ is $$\left(1 + vz + \frac{w z^2}{1-z}\right) G_n(z)$$ or equivalently $$H_n(z) = -{\frac {zn \left( -1+z-vz+v{z}^{2}-w{z}^{2} \right) }{-nz+n{z}^{2}-{z}^{2}-v{z}^{2}n+v{z}^{3}n+v{z}^{2}-v{z}^{3}-w{ z}^{3}n+w{z}^{3}+1}}.$$ Now we do not permit sequences of length at least three, so we take $$[w^0] H_n(z) = -{\frac { \left( vz+1 \right) nz}{v{z}^{2}n-v{z}^{2}+nz-z-1}}.$$ In fact there must be at least one two-sequence, so we first calculate $$[w^0] H_n(z) - [v^0] [w^0] H_n(z) = {\frac {v{z}^{2}n}{ \left( nz-z-1 \right) \left( v{z}^{2}n-v{z}^{2}+nz-z-1 \right) }}$$ and put $v=1$, finally obtaining the generating function $$M_n(z) = {\frac {n{z}^{2}}{ \left( nz-z-1 \right) \left( n{z}^{2}-{z}^{2}+nz-z-1 \right) }}.$$ The partial fraction decomposition of $M_n(z)$ is given by $$-{\frac {n}{ \left( n-1 \right) \left( n{z}^{2}-{z}^{2}+nz-z-1 \right) }}+{ \frac {n}{ \left( n-1 \right) \left( nz-z-1 \right) }}.$$

Now the singularities are at $$\rho_0 = \frac{1}{n-1} \quad\text{and}\quad \rho_{1,2} = -\frac{1}{2} \pm \frac{\sqrt{n^2+2n-3}}{2(n-1)}.$$ Expanding $M_n(z)$ into series we obtain the following closed form result for the number of admissible strings of length $k$ and an alphabet of $n$ symbols: $$ [z^k] M_n(z) = n\frac{\rho_0^2 \rho_1 \rho_2}{(\rho_0-\rho_1)(\rho_0-\rho_2)} \rho_0^{-k}\\ + n\frac{\rho_0\rho_1^2 \rho_2}{(\rho_1-\rho_0)(\rho_1-\rho_2)} \rho_1^{-k} + n\frac{\rho_0\rho_1 \rho_2^2}{(\rho_2-\rho_0)(\rho_2-\rho_1)} \rho_2^{-k}.$$ The reader is asked to verify that indeed $$ [z^n] M_n(z) = \sum_{k=1}^{\lfloor n/2 \rfloor} {n-k\choose k} n (n - 1)^{n-k-1}.$$ The above formula for $[z^k] M_n(z)$ is quite powerful. It gives the exact value of the number of admissible strings with any alphabet of size $n$ and of length $k$. For example, when there are $n=2$ symbols, the sequence starting at length $k=1$ is: $$0, 2, 4, 8, 14, 24, 40, 66, 108, 176.$$ With $n=7$ we get the following sequence: $$0, 7, 84, 798, 6804, 54684, 423360, 3194856, 23668848, 172939536.$$

The generating function $H_n(z)$ encapsulates the complete distribution of the $n^k$ strings classified according to the number of two-sequences (counted by $v$) and sequences of length at least three (counted by $w$).

Here is an example: $$[z^4] H_3(z) = 6\,{v}^{2}+36\,v+15\,w+24$$ for a total of $3^4=81$ terms (strings of length $4$ over $3$ symbols). Another example is: $$[z^6] H_5(z) = 80\,{v}^{3}+1920\,{v}^{2}+520\,vw+20\,{w}^{2}+6400\,v+1565\,w+5120$$ for a total of $5^6=15625$ terms (strings of length $6$ over $5$ symbols). It is a useful combinatorics excercise to verify some of these values with pen and paper. For example, a string of length four over three symbols containing a sequence of length at least three can consist of four equal symbols, giving a contribution of three, or a length three sequence at the front for a contribution of three times two or a length three sequence at the end, again for three times two, for a total of $3+6+6 = 15$ which is indeed the value from the generating function.

$\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.