If I randomly generate a string of length N from an alphabet {A, B, C}, what's the likelihood that k characters will be the same OR BETTER? This is an addendum to a previous question found here. 
I have an alphabet: {A, B, C}.
I'm randomly generating strings of length N from that alphabet.
Examples: Examples: N=5, AACBC, AAAAA, BBCAA
What is the likelihood that k OR MORE characters of that string are the same? (k <= N)
(k corresponds to the maximum number of similar characters...
Example: With string AABCAAA: N=7, k=5 because there are 5 A's.
String AABBCC: N=6, k=2 because there are equally-sized groups of A's, B's, and C's.)
The solution for exactly k similar characters was found as follows: 
Imagine that we have three bins, each representing the number of times each character appears in a string. For AAABC, the bins would be {A:3, B:1, C:1}
For:  


*

*N = the length of the string,

*k = the maximum bin value (there can be ties),

*l = the next bin value,

*m = the last bin value, 

*d = the number of bin values that are different from k's bin value (max 2) 


*

*Examples:  


*

*ABC: bins = {A: 1, B: 1, C: 1}. d = 0

*AAA: bins = {A: 3, B: 0, C: 0}. d = 1

*AAC: bins = {A: 2, B: 0, C: 1}. d = 2



*C = the number of letters in our alphabet (always 3), 


Pr = $\frac{N!}{k!l!m!}\cdot\left(\frac{1}{3}\right)^N \cdot\frac{C!}{(C - d)!}$, k+l+m = N
Now I'm wondering how you add up the probabilities of getting k similar characters or better, as in
P(k) + P(k + 1) + ... P(k = N)
My confusion arises because this isn't as simple as recalculating with an incremented k until k=N... in the example string AAABC, k = 3, if you increment k to k = 4, you either swallow a B or a C to make AAAAC or AAAAB.
I'm unsure how to factor this in to the final solution.  
Thanks so much in advance for your help.
 A: For an alphabet with $Q$ symbols the answer is
$$Q^N - N![z^N] \sum_{q=1}^Q {Q\choose q} \left(\sum_{p=1}^{k-1} \frac{z^p}{p!}\right)^q.$$
This is  based on the observation  that it is easier  to count strings
where no symbol appears $k$ or more times.
Observe that a string of length $N$ in an alphabet of $Q$ symbols is a
partition into sets of the interval $[1,N]$ where we can have one set,
two sets, etc.  up to $Q$ sets.  Let the number of sets  be indexed by
the variable $q.$ Then we have the combinatorial species
$$\mathfrak{P}_{=q}
\left(\mathfrak{P}_{1\le \cdot\lt k }(\mathcal{Z}) \right).$$
This gives the generating function
$$\frac{1}{q!}\left(\sum_{p=1}^{k-1} \frac{z^p}{p!}\right)^q.$$
Note however that  we must choose the $q$ letters from  the set of $Q$
available ones. Once these are chosen we assign them to the sets which
are distinct, containing values from $1$ to $N$. This yields a factor
of $${Q\choose q} \times q!$$
for a species of 
$$\sum_{q=1}^Q {Q\choose q} 
\times q! \times
\mathfrak{P}_{=q}
\left(\mathfrak{P}_{1\le \cdot\lt k }(\mathcal{Z}) \right).$$
Translating to generating functions we finally have
$$\sum_{q=1}^Q {Q\choose q} \times q! \times \frac{1}{q!}
\left(\sum_{p=1}^{k-1} \frac{z^p}{p!}\right)^q$$
which simplifies to the term given in the introduction.
Observe that  when we remove the  restriction on the size  of the sets
that make up the partition  this technique will produce the generating
function
$$\sum_{q=1}^Q {Q\choose q} 
\left(\sum_{p=1}^{\infty} \frac{z^p}{p!}\right)^q
\\ = \sum_{q=1}^Q {Q\choose q} (\exp(z)-1)^q
= -1 + (\exp(z)-1+1)^Q = -1 + \exp(Qz).$$
Upon inspection this reveals the coefficient
$$N! [z^N] (-1+\exp(Qz))= N! \times \frac{Q^N}{N!} = Q^N$$
which means we definitely have the right answer.
The formula from the introduction simplifies to
$$Q^N - N![z^N]
\left(-1 + 
\left(1+\sum_{p=1}^{k-1} \frac{z^p}{p!}\right)^Q\right).$$
which for $N\ge 1$ becomes
$$Q^N - N![z^N]
\left(\sum_{p=0}^{k-1} \frac{z^p}{p!}\right)^Q.$$
We observe that we have an alternate species equation here which is
$$\mathfrak{S}_{=Q}(\mathfrak{P}_{\lt k}(\mathcal{Z})).$$
This corresponds  to the following alternate model:  instantiate a row
of slots  one for each of the  $Q$ symbols of the  alphabet.  From $N$
distinct items (labeled) distribute  these into the slots available on
the  row,  where  slots  may  be  empty. The  item  labeled  with  $m$
represents the position $m$ on  the string and the slot represents the
letter at that position.
This  is  the Maple  code  that  was used  to  verify  the formula  by
computing the count in two ways, the first being total enumeration and
the second using the generating function.

F :=
proc(Q, N,k)
    option remember;
    local ind, d, mset, p, res;

    res := 0;

    for ind from Q^N to 2*Q^N-1 do
        d := convert(ind, base, Q);

        mset := convert([seq(d[q], q=1..N)], multiset);

        for p in mset do
            if p[2] >= k then
                res := res+1;
                break;
            fi;
        od;
    od;

    res;
end;

EX2 :=
proc(Q, N, k)
    option remember;
    local gfA, gf;

    gfA := add(z^p/p!, p=0..k-1);

    Q^N-N!*coeftayl(gfA^Q, z=0, N);
end;


