# Finding out this combination

In how many ways three non-empty strings of length less than or equal to $N$ using $k$ different characters can be selected so that in each case, among the three strings, no string is prefix (not necessarily proper prefix) of one of the other two strings.

Example: Let $N=1,k=3$. Result will be $6$

$$[a, b, c]\\ [a, c, b]\\ [b, a, c]\\ [b, c, a]\\ [c, a, b]\\ [c, b, a]\\$$

I am getting stuck for the "prefix" part. Please help. I am looking for a way that is computationally cheap as much as possible as $N$ could be as big as $10^{9}$ ($k$ will be much smaller though - upto two digits) .

EDIT :

$$1\le N\le 10^9\\ 1\le k\le 50\\$$

More Example : For $N=2,k=2$ answer is $36$

• Perhaps it helps to look at the next case to understand what they mean with the "prefix part" Let $N=2,k=3$. Then you have some combinations like: $[ac, ab,c],[ac,ba,c],[ab,ba,ca],[a,b,cb],\dots$, however an example of a combination you will not have is something like $[\color{red}{a}b,\color{red}{a}c,\color{red}{a}]$ since the third entry is a prefix of the first string. May 9, 2015 at 16:02
• @JMoravitz, I actually know what they want to mean by "prefix". I just wondering how can it be realized within the formulae for finding the value. May 9, 2015 at 16:08

Too long for a comment:
If $N=1$, then your problem has $k(k-1)(k-2)$ solutions.
If $N=2$, then the string lengths are $(1,1,1),(1,1,2),(1,2,2)$ or $(2,2,2)$. The number of solutions is $$F(1,1,1)=k(k-1)(k-2)\\F(1,1,2)=k(k-1)(k-2)k\\F(1,2,2)=k(k-1)k[(k-1)k-1]\\F(2,2,2)=k^2(k^2-1)(k^2-2)$$

respectively. The total is $$F(1,1,1)+3F(1,1,2)+3F(1,2,2)+F(2,2,2)\\=k^6+3k^5-6k^4-8k^3+8k^2+2k$$ In general, it is a polynomial in $k$ of degree $3N$.
It might be simpler to do the problem for two strings, which might give you insights for the three-string problem.
(edited to reflect the change in question)
If $a\leq b\leq c$ then $F(a,b,c)=k^a(k^b-k^{b-a})(k^c-k^{c-a}-k^{c-b})\\ =k^{a+b+c}-k^{b+c}-k^{a+c}-k^{b+c}+k^{b+c-a}+k^c$
$$X(k,N)=6\sum_{a<b<c}F(a,b,c)+3\sum_{a<b}(F(a,a,b)+F(a,b,b))+\sum_aF(a,a,a)$$ The sum of $k^{a+b+c}$ over all string-lengths $(1\leq a\leq N,1\leq b\leq N,1\leq c\leq N)$ is $[(k^{N+1}-k)/(k-1)]^3$. The sum for $a<b$ of $k^{a+c}$ equals the sum for $a<b$ of $k^{c+(b-a)}$. So $$X(k,N)=\frac{(k^{N+1}-k)^3}{(k-1)^3}+6\sum_{b<c}(b-1)(-2k^{b+c}+k^c)\\ +3\sum_{a<b}(-3k^{a+b}+2k^b)\\ +3\sum_{a<b}(-k^{a+b}-2k^{2b}+k^{2b-a}+k^b)\\ +\sum_a(-3k^{2a}+2k^a)$$ Some simplifying, including the sum of $k^{2b-a}$ equals the sum of $k^{a+b}$, gives $$X(k,N)=\frac{(k^{N+1}-k)^3}{(k-1)^3}\\+\sum_{a<b}(-12a+3)k^{a+b}\\ +\sum_a(-6a+3)k^{2a}\\ +\sum_a(3a^2-1)k^a$$ WolframAlpha can handle each piece, (and gives an answer with a dozen or two terms, not $N$ or $N^2$ terms).
I think it comes to this, but I could easily have made an error: $$\frac{1}{(k-1)^3(k+3)^2}\left[-2k^4-24k^3-6k^2-2k\right.\\ +k^N((3N^2-1)k^5-(6N+6)k^4+(-6N^2+6N-19)k^3+6Nk^2+(-3N^2+6N+2)k)\\ +k^{2N}(-6Nk^5+(-6N+6)k^4+(6N+12)k^3+(6N+6)k^2)\\ \left.+k^{3N}(k+1)^2\right]$$

• Isn't your solution giving $0$ for $N=2$ and $k=2$ as there is a term $(k-2)$? May 9, 2015 at 17:26
• Yes. You can't have three of length two because the only two strings of length two are ab and ba (no string has a repeated character). The other cases are impossible because you have two starting with the same character, one of length 1. May 9, 2015 at 17:38
• ok. Sorry, I misunderstood the problem. I am removing the constraint. Thank you. May 9, 2015 at 17:58
• That's great. Can the solution be realized as a function of both $N$ and $k$ ? May 9, 2015 at 18:50
• Your solution is too much expensive computationally for big $N$ as $N$ could be equal to $10^9$ here. May 10, 2015 at 10:54

Finding a closed form is unwieldy, but it is straightforward to find the answer computationally. Let $A_{n}$ be the number of strings of length $\le n$; let $B_n$ be the number of nonprefixy ordered pairs of strings of length $\le n$ (i.e., where neither string is a prefix of the other); and let $C_n$ be the number of non-prefixy ordered triples of strings of length $\le n$. Clearly $$A_{n}=1+k+k^2+\ldots+k^{n}=\frac{k^{n+1}-1}{k-1}.$$

In any non-prefixy pair of strings of length $n$, both strings begin with a common substring of length $a$ (for which there are $k^a$ possibilities), followed by a point at which the strings differ ($k(k-1)$ possibilities for the letters), followed by two independent terminations of length $\le n-a-1$ ($A_{n-a-1}$ choices for each). Summing over the length of the initial substring gives $$B_{n}=\sum_{a=0}^{n-1}k^{a+1}(k-1)A_{n-a-1}^2 = \sum_{a=0}^{n-1}k^{n-a}(k-1)A_{a}^2.$$

Similarly, in any non-prefixy triplet of strings of length $n$, all three strings start with a common substring of length $a$, followed by a point at which either (1) one sequence diverges from the other two ($3k(k-1)$ possibilities for which sequence and which letters) or (2) all three sequences diverge simultaneously ($k(k-1)(k-2)$ possibilities). In case (1) we have a single-string termination and a two-string termination; in case (2) we have three single-string terminations. So $$C_n=\sum_{a=0}^{n-1}k^a\left(3k(k-1)A_{n-a-1}B_{n-a-1} + k(k-1)(k-2)A_{n-a-1}^3\right)=\sum_{a=0}^{n-1}k^{n-a}(k-1)A_{a}\left(3B_{a} + (k-2)A_{a}^2\right).$$ Then a few lines of code gives:

 def a(n,k): return (k**(n+1)-1)/(k-1)

def b(n,k):
return (k-1) * sum([k**(n-i)*a(i,k)**2 for i in xrange(n)])

def c(n,k):
return (k-1) * sum([k**(n-i)*a(i,k)*(3*b(i,k) + (k-2)*a(i,k)**2) for i in xrange(n)])

>>> c(2,2)
36
>>> c(10,10)
1371742105157750346175857338820L


This isn't bad, and it's clear how to generalize it to larger numbers of strings. As far as complexity goes, evaluating $C_{N}$ takes $O(N)$ evaluations of $A_{n}$ and $B_{n}$, which may not be terrible; but it appears to require $O(N)$ storage as well (assuming you're caching values for $A$ and $B$ once you've found them), which could be a problem. This isn't actually necessary. Note that $$A_{n+1}=1+kA_{n},$$ and $$B_{n+1}=\sum_{a=0}^{n}k^{n+1-a}(k-1)A_a^2 = k(k-1)A_{n}^2 + kB_{n},$$ and $$C_{n+1}=k(k-1)A_{n}\left(3B_{n} + (k-2)A_n^2\right) + kC_{n}.$$ So in fact we have a simple recursion requiring only constant storage: $$\left(\begin{matrix}A_{n+1} \\ B_{n+1} \\ C_{n+1}\end{matrix}\right)=k\left(\begin{matrix}A_{n} \\ B_{n} \\ C_{n}\end{matrix}\right) + \left(\begin{matrix}1 \\ k(k-1)A_n^2 \\ k(k-1)A_n\left(3B_n + (k-2)A_n^2\right)\end{matrix}\right),$$ with initial condition $(A_0,B_0,C_0)=(1,0,0)$.

 def c(n,k):
(a,b,cc) = (1,0,0)
for i in xrange(n):
(a,b,cc) = (k*a + 1, k*b + k*(k-1)*a*a, k*cc + k*(k-1)*a*(3*b+(k-2)*a*a))
return cc

>>> c(2,2)
36
>>> c(10,10)
1371742105157750346175857338820L

• That's quite promising. Let me give it a try. May 11, 2015 at 9:22
• Your solution is working great. Exactly what I needed. Just one more question. If,I want the answer in modulo $103$ , can I replace the loop body by (a,b,cc) = ((k*a + 1)%103, (k*b + k*(k-1)*a*a)%103, (k*cc + k*(k-1)*a*(3*b+(k-2)*a*a))%103 )  . Will the answer be incorrect ? Thank you May 11, 2015 at 13:27
• Working modulo $p$ will work fine. May 11, 2015 at 13:39

This can be solved using inclusion/exclusion, to get a closed form in $N$ and $k$. The method extends to more strings, but gets complicated very quickly. (We remark that we may as well allow empty strings; since the empty string is a prefix of any string, doing so won't affect the final count.)

For each ordered pair $(i,j)$ of distinct indices from $1$ to $3$, let $P_{ij}$ be the condition that string $i$ is a prefix of string $j$. (Let $\mathcal{C}$ denote the set of the six such ordered pairs.) We want to find the number of tri-strings satisfying none of the conditions. By inclusion/exclusion, this is equal to the total number of tri-strings, minus the sum over pairs $(i,j)$ of the number of tri-strings satisfying $P_{ij}$, plus the sum over $(i,j)$ and $(i',j')$ of tri-strings satisfying both $P_{ij}$ and $P_{i'j'}$, etc. In other words, we want $$\sum_{S\subset\mathcal{C}}(-1)^{|S|} \#\{\textrm{tri-strings satisfying all conditions in } S\}.$$

In principle, there are $2^6=64$ terms, corresponding to the $2^6$ subsets of $\mathcal{C}$ (but we'll see that these can be reduced to $16$ using symmetries.) Each subset can conveniently be visualized as a directed graph on three vertices labeled $1,2,3$, with an arrow from $i$ to $j$ if $(i,j)\in S$. (Note that $(i,j)$ and $(j,i)$ are distinct conditions; if they both hold, then strings $i$ and $j$ are prefixes of each other, hence are equal.) If two such graphs are the same under some permutation of the vertices, then the corresponding sums are equal; it turns out there are $16$ digraphs on $3$ vertices, so we really only need to compute $16$ sums.

Each of the 16 terms can be computed in closed form. I'll do two of them here to get you started; if I have insomnia I'll write out the others. Here's one for which I can render the graph in $\TeX$:

$$\begin{array}{ccccc} && s\\ &\nearrow&&\searrow\\ r&&\longrightarrow&&t \end{array}$$ There are $6$ different ways to assign the vertices to the set $\{1,2,3\}$. As the graph has $3$ edges, we'll get a coefficient of $6(-1)^3=-6$ out front.

Each vertex has a label to indicate the length of the corresponding string; we'll have to sum over the values of these variables. We have the constraints $r\le s$, $s\le t$, and $r\le t$ (the last one looks redundant but it corresponds to the bottom edge so it's clearer to include it explicitly.) There are $k^r$ possible strings at vertex $r$, $k^{s-r}$ possible strings at vertex $s$, and $k^{t-s}$ possible strings at vertex $t$. Thus, the total contribution from this graph is \begin{align} &-6\sum_{0\le t\le N}\sum_{0\le s\le t}\sum_{0\le r\le s} k^r k^{s-r} k^{t-s}\\ =&-6\sum_{0\le r\le s\le t\le N}k^t\\ =&-3\frac{\left(N^2+5 N+6\right) k^{N+1}-2 \left(N^2+4 N+3\right) k^{N+2}+\left(N^2+3 N+2\right) k^{N+3}-2}{(k-1)^3}. \end{align}

Here's one more graph, just for clarity: $$\begin{array}{ccccc} && s\\ &\nearrow&&\nwarrow\\ r&&\longleftrightarrow&&t \end{array}$$ This graph has $4$ edges, and only $3$ distinct assignments of vertices, so we'll get a coefficient of $+3$. The contribution is \begin{align} &3\sum_{0\le r=t\le s\le N} k^r k^{s-r}\\ =&3\sum_{0\le r\le s\le N}k^s\\ =&3\frac{k^{N+2}-k (N+2)+N+1}{(k-1)^2}. \end{align}

You just have to do this for the other $14$ graphs and add up the results. (As a check, the absolute values of the coefficients you obtain should add up to $64$.)

Remark. The prefix relation defines a partial order on the set of strings of length at most $N$; you are asking for the number of antichains of length $3$ in this poset. In general, I believe counting antichains is hard even for "reasonable" posets, but I mention it in case someone's aware of a shortcut in this particular case.

(Added 5/13/15) It turns out you can simplify the summation substantially using two observations. The first is that the contribution for a given graph is unchanged if you collapse any strongly connected component to a point, so you can restrict attention to acyclic graphs. The second is a Gessel-Viennot-esque observation: if $G$ has a path of length at least two between two vertices $u$ and $v$, and the edge $(u,v)$ is not in $G$, then the contributions of $G$ and $G\cup e$ cancel. (Another observation is needed to take care of a situation which only arises with $4$ or more strings.) Applying the second observation gets us from $64$ terms to $24$, and collapsing scc's gets us down to $7$, and the graphs are all small, so the computation can actually be done manually. We arrive at the following formula: $$\begin{multline} \frac{k}{(k-1)^3} \left(-2 \left(3 N^2+3 N+2\right) k^{N+1}+\left(3 N^2-1\right) k^{N+2}+6 (N+1) k^{2 N+1}-6 N k^{2 N+2}+k^{3 N+2}+\left(3 N^2+6 N+2\right) k^N-2 k-2\right) \end{multline}$$ which, as a check, gives the correct values for the examples given in the question.

There is everything right about the answer given by Michael except the last expression. The correct expression will be the sum of first term and these two terms:

Adding the above three terms will give us the correct result.

Note: For k=1 the answer will be 0.