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$
 A: 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]$$
A: 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.
A: 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

A: 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.
