# How many permutations of a multiset have a run of length k?

### Background

$\newcommand\ms[1]{\mathsf #1}\def\msP{\ms P}\def\msS{\ms S}\def\mfS{\mathfrak S}$Suppose I have $n$ marbles of $c$ colors, where $c≤n$. Let $n_i$ denote the number of marbles of color $i$.

Let $\msP=(1^{n_1} 2^{n_2} \dots c^{n_c})$ be the multiset $\small\{\underbrace{1, \dots, 1}_{n_1},\underbrace{2,\dots,2}_{n_2},\dots,\underbrace{c,\dots,c}_{n_c}\}$ in frequency representation.

The number of distinct permutations of $\msP$ is given by the multinomial: $$\left|\mfS_{\msP}\right|=\binom{n}{n_1,n_2,\dots,n_c}=\frac{n!}{n_1!\,n_2!\cdots n_c!}=n! \prod_{i=1}^c \frac1{n_i!}.$$

### Question

How many permutations of $\msP$ have a run of length k?

Let $r_k(\msS)$ be true if a permutation $\msS$ has a run of length $k$ ($k$ marbles in a row are the same color).

For example, if I have 5 marbles (2 green, 2 blue, and 1 yellow), then:

• If $\msS$ is GBYGB, then $r_1(\msS)$ is true, but $r_2(\msS)$ is false.
• If $\msS$ is GBBYG or GGBBY, then $r_1(\msS)$ and $r_2(\msS)$ are true, but $r_3(\msS)$ is false.

Let the number of permutations of $\msP$ having a run of length $k$ be $$N(k; \msP)=\sum\limits_{\msS\in\mfS_\msP}[r_k(\msS)]$$ where $[x]$ denotes the Iverson bracket.

Is there a formula for $N(k; \msP)$?

Essentially, I would like to find a generalization of this recurrence for the case $c=2$ (Bloom 1996).

### What I have done so far

I constructed the table below, counting the permutations for configurations of up to $n=7$ marbles by brute force. The rightmost columns count the permutations having runs of length $2≤k≤n$.

Unfortunately, brute force stops being practical around $n\gtrsim 11$ (at $10^8$ permutations; see A005651).

Here is a closer look at the permutations comprising the five $n=4$ cases.

I tried to find patterns along different axes that would lead me to formulas for those specific cases, which I could then generalize, but I haven’t gotten anywhere. I then tried deriving a recurrence relation, also to no avail. My hunch, however, is that there may be a Fibonacci-like recurrence relation involved.

### Update

I have entered Andrew’s solution into Mathematica:

Ν[r_, P_] := Multinomial@@P - c[r, P]
c[r_, P_] := CoefficientRules[Π[r, P, t]] /. ({a_} -> b_) :> b a! // Total
Π[r_, P_, t_] := Product[q[r, ni, t], {ni, P}]
a[x_, r_, t_] := a[x, r, t] = Exp[t  (x - x^r)/(1 - x^r)]
q[r_, n_, t_] := q[r, n, t] = SeriesCoefficient[a[x, r, t], {x, 0, n}]


The values up to $n=5$ match the tables above:

Column@Table[
Grid@Table[
Table[Ν[r, partition], {r, 1, Max[partition]}
], {partition, IntegerPartitions[marbles]}
], {marbles, 1, 5}
]

1

1   1
2

1   1   1
3   2
6

1   1   1   1
4   4   2
6   4
12  6
24

1   1   1   1   1
5   5   4   2
10  9   3
20  18  6
30  18
60  24
120


### Table of $q_{r,n}(t)$ polynomials

$$\newcommand\f[1]{\color{gray}{#1}} \begin{array}{r|llllll} r \backslash n & 1 & 2 & 3 & 4 & 5 & 6 \\ \hline 1 & 0 & 0 & 0 & 0 & 0 & 0 \\ 2 & \f{t} & \frac{t^2}{2}-t & \frac{t^3}{6}-t^2+t & \frac{t^4}{24}-\frac{t^3}{2}+\frac{3 t^2}{2}-t & \frac{t^5}{120}-\frac{t^4}{6}+t^3-2 t^2+t & \frac{t^6}{720}-\frac{t^5}{24}+\frac{5 t^4}{12}-\frac{5t^3}{3}+\frac{5 t^2}{2}-t \\ 3 & \f{t} & \f{\frac{t^2}{2}} & \frac{t^3}{6}-t & \frac{t^4}{24}-t^2+t & \frac{t^5}{120}-\frac{t^3}{2}+t^2 & \frac{t^6}{720}-\frac{t^4}{6}+\frac{t^3}{2}+\frac{t^2}{2}-t \\ 4 & \f{t} & \f{\frac{t^2}{2}} & \f{\frac{t^3}{6}} & \frac{t^4}{24}-t & \frac{t^5}{120}-t^2+t & \frac{t^6}{720}-\frac{t^3}{2}+t^2 \\ 5 & \f{t} & \f{\frac{t^2}{2}} & \f{\frac{t^3}{6}} & \f{\frac{t^4}{24}} & \frac{t^5}{120}-t & \frac{t^6}{720}-t^2+t \\ 6 & \f{t} & \f{\frac{t^2}{2}} & \f{\frac{t^3}{6}} & \f{\frac{t^4}{24}} & \f{\frac{t^5}{120}} & \frac{t^6}{720}-t \\ \end{array}$$

### Similar questions I missed in prior searches

• Great question. I have done this same thing and never could find a formula or anything about it online. I hope someone answers this well.
– JLee
Mar 18, 2015 at 2:06
• If you have a list of the $q$-polynomials you need, a solution can actually be done by hand very easily. See the addition to my answer. Mar 19, 2015 at 11:24
• Very nice presentation of your question! +1 Mar 21, 2015 at 8:23

The number of permutations of $p$ without any run of length $r$ (or greater) is$$\int_0^\infty e^{-t}\cdot\prod_i q_{r,n_i}\!(t)\cdot\mathrm{d}t$$ where $q_{r,n}(t)$ is a polynomial in $t$ defined by $$\sum_{n=0}^\infty q_{r,n}(t)x^n=\exp\left(\frac{t(x-x^r)}{1-x^r}\right)$$

For example, $$q_{2,1}(t)=t\\ q_{2,2}(t)=\tfrac12t^2-t\\ q_{2,3}(t)=\tfrac16t^3-t^2+t\\ q_{2,4}(t)=\tfrac1{24}t^4-\tfrac12t^3+\tfrac32t^2-t\\ q_{2,5}(t)=\tfrac1{120}t^5-\tfrac16t^4+t^3-2t^2+t$$ $$q_{3,1}(t)=t\\ q_{3,2}(t)=\tfrac12t^2\\ q_{3,3}(t)=\tfrac16t^3-t\\ q_{3,4}(t)=\tfrac1{24}t^4-t^2+t\\ q_{3,5}(t)=\tfrac1{120}t^5-\tfrac12t^3+t^2$$

To compute the integral, expand the product and use the fact that $$\int_0^\infty e^{-t}\cdot t^n\cdot\mathrm{d}t=n!$$

For an explanation of how this works, I can't think of a better introduction than Jair Taylor's paper, "Counting Words with Laguerre Series".

Edit. To make it clear: the only hard part is multiplying together the polynomials. Once they have been expanded fully, the integration is easy. Cross out the integral sign, the $e^{-t}$ and $dt$, and replace every $t^n$ with $n!$ $$\require{cancel}\cancel{\int_0^\infty e^{-t}}\cdot a\cdot t^n\cdot\cancel{\mathrm{d}t}=a\cdot n!$$

Edit 2. The coefficients of $q_{r,n}(t)$ can be derived from the $n$th row of the following table: $$\begin{array}{c|ccccc} &1&t&\tfrac1{2!}t^2&\tfrac1{3!}t^3&\ldots\\ \hline x^0&1&0&0&0&\cdots\\ x^1&0&1&0&0&\ddots\\ x^2&0&&1&0&\ddots\\ x^3&0&&&1&\ddots\\ x^4&\vdots&&&&\ddots \end{array}$$ To continue the table for a given $r$, fill the blank spaces, column by column from left to right, using the rule: $$T(n,c)=\sum_{i=0}T(n-1-ri,c-1)-T(n-r-ri,c-1)$$

• Is there a closed form for $q_{r,n}(t)$? I noticed $q_{2,n}(t)=L_n^{(-1)}(t)$, but didn’t find something in general.
– hftf
Mar 20, 2015 at 21:05
• Also, just out of curiosity, were you already familiar with the Taylor paper/method before answering the question? If not, what searches did you make? I’m just a bit surprised to see the question answered with a less-than-two-year-old paper.
– hftf
Mar 20, 2015 at 23:36
• I've edited my answer to give an algorithm for a specific $r$. Essentially it's convolving the infinite sequence $1,0,0,\ldots,0,0,-1$ ($r$ terms, endlessly repeated) with itself $c$ times. Mar 22, 2015 at 14:45
• Yes, I was familiar. Mar 22, 2015 at 14:53
• @AndrewWoods: Nice answer and a very interesting reference! +1 Mar 25, 2015 at 10:11

Note: Here's an another approach based upon example III.24 Smirnov words from Analytic Combinatorics by Philippe Flajolet and Robert Sedgewick.

In order to answer OPs question we will derive a formula from scratch.

At the end I have added a few notes indicating some common aspects of this answer and the answer from @AndrewWoods regarding the highly instructive paper "Counting Words with Laguerre Series" by the MSE member Jair Taylor which is referenced there.



In the following it is convenient to rephrase OPs question in terms of words and letters.

So, instead of $n$ marbles of $c$ colors ($c\leq n$), we consider a $c$-ary Alphabet $\mathcal{A}=\{v_1,\ldots,v_c\}$ containing the $c$ letters $v_j, 1\leq j\leq c$ and words of length $n$.

According to OPs Multiset $P=(1^{n_1}2^{n_2}\ldots c^{n_c})$ with $n_1+n_2+\ldots+n_c=n$ and the number of distinct permutations of $P$ $$|\mathcal{S}_{P}|=\binom{n}{n_1,n_2,\ldots,n_c}=\frac{n!}{n_1!n_2!\cdots n_c!}$$ we are looking for a method to generate words of length $n$ from the multiset $W=(v_1^{n_1}v_2^{n_2}\ldots v_c^{n_c})$ with $n_1+n_2+\ldots+n_c=n$. And we ask:

How many words of the multiset $W$ have a run of length (at least) $k$?

Some Basics: Generating words

We want to use ordinary generating functions and start with some preliminary considerations.

Let $SEQ(v)=\{\varepsilon,v,vv,vvv,\ldots\}$ denote all words with length $\geq0$ containing only the letter $v$. The empty word is denoted with $\varepsilon$. The corresponding generating function is $$W(v)=(vz)^0+(vz)^1+(vz)^2+\ldots=\frac{1}{1-vz}$$ with the exponent of $z^n$ marking the length $n$ of a word of $v$'s and the coefficient of $z^n$ marking the number of words of length $n$. Let $SEQ^{\leq k}(v)$ be the set of all words of $v$'s with length $\leq k$. The generating function for $SEQ^{\leq k}(v)$ is $$1+(vz)+(vz)^2+\ldots+(vz)^{k}=\frac{1-(vz)^{k+1}}{1-(vz)}$$ Without loss of information and in line with Flajolet we may skip $z$ and we will simply write: $$W^{\leq k}(v)=1+v+v^2+\ldots+v^{k}=\frac{1-v^{k+1}}{1-v}$$.

Now, all words containing letters from the alphabet $\mathcal{A}=\{v_1,\ldots,v_c\}$ can be described as

$$W(v_1,\ldots,v_c)=\frac{1}{1-(v_1+\cdots+v_c)}$$

Smirnov Words: Words without runs

This is an interesting twist. Instead of looking for words having a specified run length, we consider Smirnov Words. These are words having no consecutive equal letters. They can be related to unconstrained words and vice versa in the following way:

We observe: If an unconstrained word is given, we can collaps each run of consecutive letters into a single letter associating a Smirnov word this way. Conversely, starting from a Smirnov word and substituting each letter by a sequence of length $\geq 1$ of this letter we can get all unconstrained words.

So, arbitrary words are derived from Smirnov words by a simultaneous substitution:

$$\mathcal{W}=\mathcal{S}[v_1\mapsto SEQ^{\geq 1}(v_1),\ldots,v_c\mapsto SEQ^{\geq 1}(v_c)]$$

with the generating functions

\begin{align*} W(v_1,\ldots,v_c)=S\left(\frac{v_1}{1-v_1},\ldots,\frac{v_c}{1-v_c}\right).\tag{1} \end{align*}

Observe, that relation (1) determines the generating functions $S$ for Smirnov words implicitely. Now, the inverse function of $\frac{v}{1-v}$ is $\frac{v}{1+v}$ and so we can find the solution:

\begin{align*} S(v_1,\ldots,v_c)=W\left(\frac{v_1}{1+v_1},\ldots,\frac{v_c}{1+v_c}\right)=\left(1-\sum_{j=1}^{c}\frac{v_j}{1+v_j}\right)^{-1}\tag{2} \end{align*}

Words with runs of length $< k$

Now, starting with a Smirnov word we can build from it words with runs of length $<k$ by substituting $$v_j\mapsto v_j+\cdots+v_j^{k-1}$$

Let $\mathcal{S}^{<k}(v_1,\ldots,v_c)$ denote the words containing the letters $v_1,\ldots,v_c$ and with runs of length $<k$. The corresponding generating function is

\begin{align*} S^{<k}(v_1,\ldots,v_c)&=\left(1-\sum_{j=1}^{c}\frac{v_j+\cdots+v_j^{k-1}}{1+v_j+\cdots+v_j^{k-1}}\right)^{-1} =\left(1-\sum_{j=1}^{c}v_j\frac{1-v_j^{k-1}}{1-v_j^k}\right)^{-1} \end{align*}

We introduce $z$ again and denote via the coefficient of operator $[z^n]$ the number of words of length $n$ in $S^{<k}$.

\begin{align*} [z^n]S^{<k}(zv_1,\ldots,zv_c)=[z^n]\left(1-\sum_{j=1}^{c}v_jz\frac{1-(v_jz)^{k-1}}{1-(v_jz)^k}\right)^{-1} \end{align*}

And the number of permutations of the multiset $W=(v_1^{n_1}v_2^{n_2}\ldots v_c^{n_c})$ with $n_1+n_2+\ldots+n_c=n$ and runs of length (at least) $k$ is

\begin{align*} \frac{n!}{n_1!n_2!\cdots n_c!}-[v_1^{n_1}\ldots v_c^{n_c}z^n]\left(1-\sum_{j=1}^{c}v_jz\frac{1-(v_jz)^{k-1}}{1-(v_jz)^k}\right)^{-1}\tag{3} \end{align*}

Example: We apply the formula (3) to OPs example with 4 marbles and 4 colors



Words with length $n=4$, runs with length $k<2$

We observe (with support from Wolfram Alpha)

We can focus on the leftmost summand of each line of (4) and take the coefficients $$[v_1^2v_2^2]=2,\qquad[v_1^2v_2v_3]=6\qquad\text{and}\qquad[v_1v_2v_3v_4]=24$$ We observe that these three coefficients correspond to the configurations $(2,2), (2,1,1)$ and $(1,1,1,1)$ of marbles and derive in accordance with OPs example in the column runs of length at least 2:

\begin{array}{lll} (4)&\frac{4!}{4!}-0&=1\\ (3,1)&\frac{4!}{3!1!}-0&=4\\ (2,2)&\frac{4!}{2!2!}-2&=4\\ (2,1,1)&\frac{4!}{2!1!1!}-6&=6\\ (1,1,1,1)&\frac{4!}{1!1!1!1}-24&=0 \end{array}



Words with length $n=4$, runs with length $k<3$

We observe

We can focus on the leftmost summand of each line of (5) and take the coefficients $$[v_1^3v_2]=2,[v_1^2v_2^2]=6,\qquad[v_1^2v_2v_3]=12\qquad\text{and}\qquad[v_1v_2v_3v_4]=24$$ We observe that these four coefficients correspond to the configurations $(3,1),(2,2), (2,1,1)$ and $(1,1,1,1)$ of marbles and derive in accordance with OPs example in the column runs of length at least 3:

\begin{array}{lll} (4)&\frac{4!}{4!}-0&=1\\ (3,1)&\frac{4!}{3!1!}-2&=2\\ (2,2)&\frac{4!}{2!2!}-6&=0\\ (2,1,1)&\frac{4!}{2!1!1!}-12&=0\\ (1,1,1,1)&\frac{4!}{1!1!1!1}-24&=0 \end{array}



Words with length $n=4$, runs with length $k<4$

We observe

We can focus on the leftmost summand of each line of (6) and take the coefficients $$[v_1^3v_2]=4,[v_1^2v_2^2]=6,\qquad[v_1^2v_2v_3]=12\qquad\text{and}\qquad[v_1v_2v_3v_4]=24$$ We observe that these four coefficients correspond to the configurations $(3,1),(2,2), (2,1,1)$ and $(1,1,1,1)$ of marbles and derive in accordance with OPs example in the column runs of length at least 4:

\begin{array}{lll} (4)&\frac{4!}{4!}-0&=1\\ (3,1)&\frac{4!}{3!1!}-4&=0\\ (2,2)&\frac{4!}{2!2!}-6&=0\\ (2,1,1)&\frac{4!}{2!1!1!}-12&=0\\ (1,1,1,1)&\frac{4!}{1!1!1!1}-24&=0 \end{array}

Notes:

• In order to obtain the generating functions for words with length of runs $<k$ we put the focus on Smirnov words. The same approach is done in Jair Taylor paper "Counting Words with Laguerre Series". Interestingly these words are called Carlitz words (after Leonard Carlitz) in his paper.

• Flajolet followed the treatment of Combinatorial Enumeration by Ian P Goulden and David M. Jackson. We can find this example in their book in section 2.4.16 (The Smirnov Problem).

• Based upon (2) we found the generating function for words with runs $<k$ by substituting $v_j \mapsto v_j+\cdots+v_j^{k-1}$ and we obtained

\begin{align*} S^{<k}(v_1,\ldots,v_c)=\left(1-\sum_{j=1}^{c}v_j\frac{1-v_j^{k-1}}{1-v_j^k}\right)^{-1}\tag{7} \end{align*}

If we consider the univariate problem we get the number of $c$-ary words with runs of length $<k$ and according to (7)

\begin{align*} \left(1-cz\frac{1-z^{k-1}}{1-z^k}\right)^{-1}=\frac{1-z^{k}}{1-cz+(c-1)z^{k}} \end{align*}

Jair Taylor also presents this formula in his paper at the end of section 3. While Flajolets example is based upon generating functions is Jair Taylors approach based upon Laplace transforms $\mathcal{L}$ operating on Laguerre series. He so obtains the relation

\begin{align*} \Phi\left(\exp\left(tcz\frac{1-z^{k-1}}{1-z^k}\right)\right)=\frac{1-z^{k}}{1-cz+(c-1)z^{k}} \end{align*} with $\Phi\left(e^{tf}\right)=\frac{1}{1-f}$.

• @AndrewWoods: Hi Andrew. I've added an answer with an alternate approach, which could also of interest to you. Regards, Mar 29, 2015 at 7:27
• @JairTaylor: Very instructive paper about Counting words using Laguerre Series. You might want to check the expression at the end of my answer with your text (typo +/-). Best regards, Mar 29, 2015 at 16:36
• Answer deserves many more upvotes, +1 for my part! Any idea if this c/b extended to case where one (or more) of the categories counts as "blank", that is, runs of these are not counted (see my comment on prior answer). I've been pondering that problem for some time to no avail (the a priori case was elegantly answered via Goulden-Jackson by a SE participant). Aug 4, 2015 at 18:38
• @rasher: Thanks for your nice comment! I can't answer offhand, but what about posting your question as generalisation of this one? Aug 4, 2015 at 19:22
• I think I will after pondering a bit more, and taking the time to format a question worthy of notice - the OP here set the bar for well-presented... Aug 4, 2015 at 19:41