Put $\{1,2,3,...,N\}$ into $k$ partitions. Pick $m<k$, how many partitions have each element of $\{1,2,...m\}$ in a different partition (pairwise).

Question

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

Answer 1

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);