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$
2
  • $\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, 2015 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$ May 9, 2015 at 16:08

4 Answers 4

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$
8
  • $\begingroup$ Isn't your solution giving $0$ for $N=2$ and $k=2$ as there is a term $(k-2)$? $\endgroup$ May 9, 2015 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, 2015 at 17:38
  • $\begingroup$ ok. Sorry, I misunderstood the problem. I am removing the constraint. Thank you. $\endgroup$ May 9, 2015 at 17:58
  • $\begingroup$ That's great. Can the solution be realized as a function of both $N$ and $k$ ? $\endgroup$ May 9, 2015 at 18:50
  • $\begingroup$ Your solution is too much expensive computationally for big $N$ as $N$ could be equal to $10^9$ here. $\endgroup$ May 10, 2015 at 10:54
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$
3
  • $\begingroup$ That's quite promising. Let me give it a try. $\endgroup$ May 11, 2015 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$ May 11, 2015 at 13:27
  • $\begingroup$ Working modulo $p$ will work fine. $\endgroup$
    – mjqxxxx
    May 11, 2015 at 13:39
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
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$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .