Put $\{1,2,3,...,N\}$ into $k$ partitions. Pick $mConsider the set of partitions of $\{1,2,3,...N\}$ into $k$ (non-empty) partitions. The number is given by $S(N,k)$ the Stirling numbers of the second kind.
Now for some $0<m\leq k$, how many of these partitions have the elements $1,2,...,m$ each in different partitions? (e.g. each pair of elements must be in a different partition) 
Let's call this number $T(N,k,m)$. This is what I'm trying to find.
I've found this for $m=1,2,3,4$ using inclusion-exclusion type arguments but for the general case it seems more difficult as there are more and more cases to consider.
For $m=1$, it's obvious that  $T(N,k,1) = S(N,k)$.
For $m=2$, we can count the number of partitions with $\{1,2\}$ in the same partition and then subtract from the total number of partitions. This is given by $S(N-1,k)$, so here we have $$T(N,k,2) = S(N,k)-S(N-1,k)$$
For $m=3$, we want $1,2,3$ in different partitions. So we can count the number of partitions with $\{1,2\}$ or $\{2,3\}$ or $\{1,3\}$ in the same partition. Each is given by $S(N-1,k)$. So, we have $3 .S(N-1,k)$. However, we've triple counted those with $\{1,2,3\}$ in the same partition so we need to subtract $2.S(N-2,k)$. So finally, the answer we seek is
$$T(N,k,3) = S(N,k)-3S(N-1,k)+2S(N-2,k).$$
For $m=4$, again we count the number of partitions where there is a pair from $\{1,2,3,4\}$ in the same partition. There are ${4\choose 2}=6$ ways of forming a pair. Let's consider the partitions with $\{1,2\}$ in same partition. This is given by $S(N-1,k)$. Now if we multiply this 6 we double count a few things. We triple count any partitions with 3 of the elements in the same partition, we count 6 times the partitions with all 4 elements in the same partition. Also, we count partitions with $\{1,2\}$ together and $\{3,4\}$ together twice. In the end I got,
$$T(N,k,4) = S(N,k)-6.S(N-1,k)+11.S(N-2,k)+2(N-3,k)$$
which may or may not be right. 
However, I'm wondering if there's another way to count this number $T(N,k,m)$ or find an asymptotic form for large $N$.
If it's easier, the thing I'm interested in is
$$\frac{1}{S(N,k)}\sum_m T(N,k,m)$$
or 
$$\frac{1}{S(N,k)} \sum_m \frac{T(N,k,m)}{m}$$
The first sum might be $\lessapprox N/(N-k)$ and the second sum might be $\lessapprox \log(N/(N-k))$ for large $N$.
 A: By way  of getting  started here are  some ideas where  I hope  I have
interpreted the  question correctly. We get  the labeled combinatorial
species
$$\mathfrak{S}_{=m}(\mathfrak{P}(\mathcal{Z}))
\mathfrak{P}_{=k-m}(\mathfrak{P}_{\ge 1}(\mathcal{Z})).$$
We get the EGF
$$G(z) = \exp(z)^m \frac{1}{(k-m)!} (\exp(z)-1)^{k-m}$$
This is
$$G(z) = \frac{1}{(k-m)!} (\exp(z)-1)^{k-m} 
\sum_{q=0}^m {m\choose q} (\exp(z)-1)^q
\\ = \frac{1}{(k-m)!} 
\sum_{q=0}^m {m\choose q} 
(k-m+q)! \frac{(\exp(z)-1)^{k-m+q}}{(k-m+q)!}.$$
Extracting coefficients we thus obtain the closed form
$$(n-m)! [z^{n-m}]
\frac{1}{(k-m)!} 
\sum_{q=0}^m {m\choose q} (k-m+q)! 
\frac{(\exp(z)-1)^{k-m+q}}{(k-m+q)!}$$
or alternatively
$$\bbox[5px,border:2px solid #00A000]{
\sum_{q=0}^m {m\choose q} {k-m+q\choose q} q! {n-m\brace k-m+q}.}$$
There  is some  Maple  code as  well, namely  a  transcription of  the
problem definition and a somewhat  improved version. Keep in mind that
with  $m$ small  compared  to $n$  the complexity  is  given by  Bell
numbers.   The
Maple code does verify the correctness of the formula.

with(combinat);

ENUM :=
proc(n, k, m)
option remember;
local part, res, diffs, setind;

    res := 0;
    diffs := {seq(q, q=1..m)};

    for part in setpartition({seq(q, q=1..n)}) do
        if nops(part) = k then
            for setind to k do
                if nops(op(setind, part) intersect diffs) > 1
                then
                    break;
                fi;
            od;

            if setind = k+1 then
                res := res + 1;
            fi;
        fi;
    od;

    res;
end;

setpart_restr :=
proc(n, k, m)
local res, resA, part;

    if k = n then return [{seq({q}, q=1..n)}] fi;

    if k = 1 then
        if m > 1 then return [];
        else return [{{seq(q, q=1..n)}}] fi;
    fi;

    if n <= m then return [] fi;

    res :=
    map(part -> part union {{n}}, setpart_restr(n-1, k-1, m));

    resA :=
    map(part ->
        seq({seq(part[q], q=1..p-1),
             part[p] union {n},
             seq(part[q], q=p+1..nops(part))}, p=1..nops(part)),
        setpart_restr(n-1, k, m));

    [op(res), op(resA)];
end;

ENUM2 :=
proc(n, k, m) option remember; nops(setpart_restr(n, k, m)); end;

X :=
(n, k, m) ->
add(binomial(m,q)*binomial(k-m+q, q)*q!*stirling2(n-m, k-m+q),
    q = 0 .. m);


