# Number of lists in which an element is repeated consecutively exactly twice

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.

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

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

• @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. – Marc van Leeuwen Sep 29 '13 at 20:27
• @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. – Kasper Middelboe Petersen Sep 29 '13 at 20:32
• I think the only challenge is computing with large integers. For $n=69$, I get 4676495092345476699420593108779018542679373291685221536304769813013106968507850431624264673416798415845073262231682605593395200, no sweat. – Marc van Leeuwen Sep 29 '13 at 20:43

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.