5
$\begingroup$

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$

$\endgroup$
  • $\begingroup$ 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. $\endgroup$ – JMoravitz May 9 '15 at 16:02
  • $\begingroup$ @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. $\endgroup$ – user2399614 May 9 '15 at 16:08
1
$\begingroup$

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
$\endgroup$
  • $\begingroup$ That's quite promising. Let me give it a try. $\endgroup$ – user2399614 May 11 '15 at 9:22
  • $\begingroup$ 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 $\endgroup$ – user2399614 May 11 '15 at 13:27
  • $\begingroup$ Working modulo $p$ will work fine. $\endgroup$ – mjqxxxx May 11 '15 at 13:39
2
$\begingroup$

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]$$

$\endgroup$
  • $\begingroup$ Isn't your solution giving $0$ for $N=2$ and $k=2$ as there is a term $(k-2)$? $\endgroup$ – user2399614 May 9 '15 at 17:26
  • $\begingroup$ 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. $\endgroup$ – Empy2 May 9 '15 at 17:38
  • $\begingroup$ ok. Sorry, I misunderstood the problem. I am removing the constraint. Thank you. $\endgroup$ – user2399614 May 9 '15 at 17:58
  • $\begingroup$ That's great. Can the solution be realized as a function of both $N$ and $k$ ? $\endgroup$ – user2399614 May 9 '15 at 18:50
  • $\begingroup$ Your solution is too much expensive computationally for big $N$ as $N$ could be equal to $10^9$ here. $\endgroup$ – user2399614 May 10 '15 at 10:54
1
$\begingroup$

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.

$\endgroup$
0
$\begingroup$

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:

2nd term and 3rd and 4th term combined

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

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

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