Number of ways to partition a multiset into $k$ non empty submultisets.

Question

Let $A$ be a multiset with $n$ distinct elements where each element occurs exactly twice. How many ways can we partition $A$ into $k$ non-empty (unlabelled) sub multisets (denoted $T(n,k)$)?

My approach would be something similar to the Stirling Numbers. For each element $x \in A$, we can either both copies of $x$ in a set, or include them in two different sets. Therefore, we can define labelings of sets (parts), as singleton and two-element subsets of $\{1,2,3,...k\}$. There are in total $k + {{k}\choose{2}} = {{k+1}\choose{2}}$ different labeling we can assign to each element. (Note: We divide the end result by $k!$ because the labeling did not originally matter) Elements where both copies are included in the same set are labeled with a singleton, and if one element occurs in two sets, it is labeled with a two-element set.

For example, the partition of $\{\{a,a,c\},\{b,b,c\}\}$ of $\{a,a,b,b,c,c\}$ can be defined by an equivalence class or function such as $f(a)=\{1\}$, $f(b)=\{2\}$, $f(c)=\{1,2\}$.

The basic idea is to count the number of functions $f:A_s \xrightarrow{} S$ such that $|\cup_{x \in A_s} f(x)| = k$. Here, $A_s$ is the set containing only one of each element in $A$, and $S = \{ s \in \mathcal{P}(\{1,2,3,...k\})\ \mid |s| = {1,2} \}$.

Since $|S|={{k+1}\choose{2}}$, and $|A_s|=n$, we have $|S|^{|A_s|} = {{k+1}\choose{2}}^{n}$ different functions to choose from.

However, some functions may not satisfy our initial constraint that $|\cup_{x \in A_s} f(x)| = k$. We can use inclusion-exclusion for this (similar to how the Stirling Numbers of the Second Kind are derived).

What I get is something like
$$ T(n,k) = \frac{1}{k!} \sum_{i=0}^{k} (-1)^{k-i} {{k}\choose{i}} {{i+1}\choose{2}}^n $$
I think the formula is wrong though, and I can't figure out why. For example, with $k=2$, we have $T(n,2) = \frac{1}{2}(3^n - 2)$. I know that it should be $\frac{1}{2}(3^n - 1)$ because each subset of $A$ has a complement, but one set is its own complement, and we need to "add" a pair to the collection, then divide by 2.

For $k=3$, we have $T(n,k) = \frac{1}{6}(6^n - 3^{n+1} + 3)$, but manual computations show that this is incorrect. (For example, $T(3,3) = 23$, but it should be $26$, and $T(4,3) = 176$, but it should be $183$).

Could anyone please kindly give me hints on what I am missing here. I am really trying to figure it out on my own, or at least understand why my computations are incorrect? Thanks in advance!

Edit:

I realized my mistake (thanks to user2661923).

So basically, I had the counting correct, but for ordered partitions rather than unordered partitions. Basically, if we forget the ordering, some partitions have $k!$ copies, others have fewer than $k!$ duplicates. So all we need to do to fix the counting is "add" enough duplicates (for those permutations that have fewer than $k!$ copies).

For example, if $k=2$ using the formula above (ignore the $\frac{1}{k!}$), we get $T(n,k) = 3^n-2$. However, there will be one partition of the form $\{X, X\}$ (where $X$ is a multiset). There is only one copy of this partition included, so we need to "add" in another copy of it, leading to $3^n-1$, instead of $3^n-2$, which we can then divide by 2, to get the correct value of $T(n,2) = (3^n-1)/2$

If $k=3$, then we initally get $T(n,3) = 6^n - 3^{n+1} + 3$. Partitions of the form $\{X,X,Y\}$ only have $3$ copies included, so we need to "add" three more. Each element is either assigned to $\{X,X\}$ or $\{Y\}$, but all cannot be assigned the same sets, so this yields $2^n-2$ different copies we need to add (don't forget that this gives $3$ additional copies). Since we originally had $3$ different labels, we need to multiply this result by $3$. This gives $$T(n,3) = (6^n - 3^{n+1} + 3 + 3(2^n-2))/6 = (6^n - 3^{n+1} + (3)2^n - 3)/6$$

The case for $k=4$ is more complicated, but after manually checking all possible partitions which need extra copies, I get the formula:

$$T(n,4) = (10^n - (4)6^n + (6)4^n - (9)2^n + 8)/24$$

I'm not putting this as an answer because I am still not sure of a general formula that doesn't involve manually checking all possible partitions which are initially undercounted.

Answer 1

This problem can be solved using the Polya Enumeration Theorem. In fact it will appear that Power Group Enumeration is best here but plain PET is still of some value. We get very straightforwardly that the desired quantity is given by

$$[A_1^2 A_2^2 \times\cdots\times A_n^2] Z\left(S_k; -1 + \prod_{q=1}^n (1+A_q+A_q^2)\right).$$

where we refer to the cycle index of the symmetric group. We now use the recurrence by Lovasz for the cycle index $Z(S_k)$ of the multiset operator $\def\textsc#1{\dosc#1\csod} \def\dosc#1#2\csod{{\rm #1{\small #2}}} \textsc{MSET}_{=k}$ on $k$ slots, which is

$$Z(S_k) = \frac{1}{k} \sum_{l=1}^k a_l Z(S_{k-l}) \quad\text{where}\quad Z(S_0) = 1.$$

This recurrence lets us calculate the cycle index $Z(S_n)$ very easily. Note that when we replace $a_l$ by the sum of multisets in $A_q$ raising all variables to the power $l$ and $l\gt 2$ the exponents of the constituents are $\gt 2$ and cannot possibly contribute to the count. Hence we are justfied in using the following recurrence:

$$Z'(S_k) = \frac{1}{k} (a_1 Z'(S_{k-1}) + a_2 Z'(S_{k-2})).$$

It remains to decide how to make the substitution into the terms of the cycle index which have the form

$$c \times a_1^{k-2p} a_2^p.$$

Note however that the multisets have $3^n-1$ terms so that e.g. for $p=0$ we get a maximum of $(3^n-1)^k$ intermediate terms. This makes direct substitution impracticable even for small $k.$ The bottleneck here is the exponential growth when we expand the substituted cycle index and quickly hit the memory limits of our machine. It is in fact possible to compute the substituted power terms in $a_1$ and $a_2$ recursively using very little memory but we pay a different way, namely time. A better approach is needed.

The answer is Power Group Enumeration, where we count orbits with objects being distributed into slots where a permutation group permutes the slots and another the objects. This is a very simple algorithm where we just need to insert the corresponding cycle indices into the appropriate place and are ready to go. Here we have $2n$ slots that receive one of $k$ types of labels or colors, with the symmetric group acting on the colors. The color that the slot receives identifies the set it belongs to. Permutation of sets is not distinguishable, hence the symmetric group. The slot permutations represent the symmetry of the $2n$ slots as a row of $n$ adjacent pairs of slots, with the constituents of the pairs being swappable. We get the following cycle index

$$Z(Q) = \left(\frac{1}{2} a_1^2 + \frac{1}{2} a_2\right)^n.$$

This construction is the same as with ordinary Stirling numbers as shown e.g. at this MSE link. Observe that PGE will count colorings that have at most $k$ colors, so we need the difference between the outputs for $k$ and $k-1.$

The heart of the PGE algorithm is to compute the number of orbits by Burnside's lemma which says to average the number of assignments fixed by the elements of the power group. But this number is easy to compute. Suppose we have a permutation $\alpha$ from the slot permutation group $Q$ and a permutation $\beta$ from $S_k.$ If we place the appropriate number of complete, directed and consecutive copies of a cycle from $\beta$ on a cycle from $\alpha$ then this assignment is fixed under the power group action for $(\alpha,\beta)$, and this is possible iff the length of the cycle from $\beta$ divides the length of the cycle from $\alpha$. The process yields as many assignments as the length of the cycle from $\beta.$ This algorithm is implemented below. We get e.g. for $n=10$ the following sequence of partitions of $[1,1,2,2, \ldots,10,10]$ into $k$ submultisets where $k$ ranges from $1$ to $20$:

$$1, 29524, 10048683, 406850731, 4412047810, 18881865988, 39803548690, \\ 47647561072, 35716773030, 17976931224, 6390304909, 1664013058, \\ 325670575, 48708115, 5612181, 497517, 33465, 1650, 55, 1.$$

The Maple code shown below has three routines, one by enumeration, which can be used to verify that we have correctly implemented the problem definition, one by PET, which has a wider range but is limited by memory and finally PGE which produces instant results for all cases one could reasonably wish for e.g. $n=20.$

with(combinat);

pet_cycleind_symm_invl :=
proc(n)
option remember;

    if n=0 then return 1; fi;
    if n=1 then return a[1] fi;

    expand(1/n*(a[1]*pet_cycleind_symm_invl(n-1)+
                a[2]*pet_cycleind_symm_invl(n-2)));
end;


pet_cycleind_symm :=
proc(n)
local l;
option remember;

    if n=0 then return 1; fi;

    expand(1/n*add(a[l]*pet_cycleind_symm(n-l), l=1..n));
end;

pet_varinto_cind :=
proc(poly, ind)
local subs1, subs2, polyvars, indvars, v, pot, res;

    res := ind;

    polyvars := indets(poly);
    indvars := indets(ind);

    for v in indvars do
        pot := op(1, v);

        subs1 :=
        [seq(polyvars[k]=polyvars[k]^pot,
             k=1..nops(polyvars))];

        subs2 := [v=subs(subs1, poly)];

        res := subs(subs2, res);
    od;

    res;
end;

T1 :=
proc(n, k)
option remember;
local rep, q, gf;

    rep := -1 + mul(1+A[q]+A[q]^2, q=1..n);
    gf := pet_varinto_cind(rep, pet_cycleind_symm_invl(k));
    gf := expand(gf);

    for q to n do
        gf := coeff(gf, A[q], 2);
    od;

    gf;
end;

# sanity check for small arguments of the parameters
ENUM :=
proc(n,k)
option remember;
local mset, allmsets, idx, digits, dix, src, sidx;

    if k=1 then return 1 fi;

    src := [seq(V[q]$2, q=1..n)];
    allmsets := table();

    for idx from k^(2*n) to 2*k^(2*n)-1 do
        digits := convert(idx, `base`, k)[1..2*n];
        if nops(convert(digits, `set`)) = k then
            mset := table([seq(q=1, q=1..k)]);
            for sidx to 2*n do
                dix := digits[sidx] + 1;
                mset[dix] := mset[dix] * src[sidx];
            od;

            allmsets[sort([entries(mset, `nolist`)])] := 1;
        fi;
    od;

    numelems(allmsets);
end;


# best answer to problem
pet_cycleind_pairs :=
n -> expand((1/2*a[1]^2+1/2*a[2])^n);

T2aux :=
proc(n,k)
option remember;
local idx_slots, idx_colors, res, term_a, term_b,
    v_a, v_b, inst_a, inst_b, len_a, len_b, p, q;

    if k = 1 then return 1 fi;

    idx_slots := pet_cycleind_pairs(n);
    idx_colors := pet_cycleind_symm(k);

    res := 0;

    for term_a in idx_slots do
        for term_b in idx_colors do
            p := 1;

            for v_a in indets(term_a) do
                len_a := op(1, v_a);
                inst_a := degree(term_a, v_a);

                q := 0;

                for v_b in indets(term_b) do
                    len_b := op(1, v_b);
                    inst_b := degree(term_b, v_b);

                    if len_a mod len_b = 0 then
                        q := q + len_b*inst_b;
                    fi;
                od;

                p := p*q^inst_a;
            od;

            res := res +
            lcoeff(term_a)*lcoeff(term_b)*p;
        od;
    od;

    res;
end;

T2 :=
proc(n,k)
    if k=1 then return 1 fi;
    T2aux(n,k)-T2aux(n,k-1);
end;

Reference for Power Group Enumeration is the text Graphical Enumeration by Harary and Palmer.

Remark. The above analysis will also apply to multisets where we have $m$ each instances of $n$ different elements. Just replace the cycle index with

$$Z(Q) = Z(S_m)^n.$$

For example, using $m=3$ and the multiset $[1,1,1,2,2,2,\ldots,n,n,n]$ we get with $n=3$ the distribution

$$1, 31, 139, 219, 175, 86, 28, 6, 1$$

With $m=4$ and the multiset $[1,1,1,1,2,2,2,2,\ldots,n,n,n,n]$ we get for $n=3$ the distribution

$$1, 62, 513, 1399, 1857, 1513, 855, 364, 119, 31, 6, 1.$$

Observe that we get ordinary Stirling numbers of the second kind when we put $m=1.$ Indeed with $n=7$ we find

$$1, 63, 301, 350, 140, 21, 1$$

which is familiar.

Answer 2

I have finally reached the point where I have a clear understanding of the intent of the OP (i.e. original poster), and can therefore identify his fatal error. His error is in assuming that

$$\frac{\text{Satisfying distributions when multisubsets are labeled}}{\text{Satisfying distributions when multisubsets are not labeled}} = k!. \tag1 $$

The assertion in (1) above is flat wrong. For illustration purposes, I will assume that $~n = 5,~$ and
$~A = \{x_1,x_1,x_2,x_2,x_3,x_3,x_4,x_4,x_5,x_5\}.$

I will also assume that when the multisubsets are labeled, the labels are $B_1, B_2, \cdots, B_k.$

---

$\underline{\text{Example 1}}$

Assume that $k = 2$, and consider the distribution of

• $B_1 = \{x_1,x_2,x_3,x_4,x_5\}.$
• $B_2 = \{x_1,x_2,x_3,x_4,x_5\}.$

Here, $B_1,B_2$ are identical to each other. So, with this specific distribution, the ratio referred to in (1) above is in fact $\displaystyle \frac{2!}{2!} = 1$.

That is, since $B_1$ and $B_2$ are identical, permuting the labels of the submultisets, so that the first group of elements goes in $B_2$ rather than $B_1$ results in the exact same distribution.

---

$\underline{\text{Example 2}}$

Assume that $k = 3$, and consider the distribution of

• $B_1 = \{x_1,x_1,x_2,x_2\}.$
• $B_2 = \{x_3,x_3,x_4,x_5\}.$
• $B_3 = \{x_4,x_5\}.$

Here, $B_1,B_2,B_3$ are all distinct. So, with this specific distribution, the ratio referred to in (1) above is in fact $(3!)$.

That is, there are $(3)$ ways of determining which of the three submultisets will contain $\{x_1,x_1,x_2,x_2\}.$

Once this is done, there are then $(2)$ ways of determining which of the two remaining submultisets will contain $\{x_3,x_3,x_4,x_5\}.$

---

$\underline{\text{Example 3}}$

Assume that $k = 3$, and consider the distribution of

• $B_1 = \{x_1,x_1,x_2,x_2,x_3,x_3\}.$
• $B_2 = \{x_4,x_5\}.$
• $B_3 = \{x_4,x_5\}.$

Here, $B_2,B_3$ are identical to each other. So, with this specific distribution, the ratio referred to in (1) above is in fact $\displaystyle \frac{3!}{2!} = 3$.

That is, there are $(3)$ ways of determining which of the three submultisets will contain $\{x_1,x_1,x_2,x_2,x_3,x_3\}.$

Once this is done, the two remaining submultisets will each contain $\{x_4,x_5\}.$

Answer 3

Responding to the comment left by Gerry Myerson following the original posting:

I totally overlooked that point. Throughout this response, I refer to (for example) $B_1, \cdots, B_k$ as subsets, when I should be referring to them as submultisets.

---

A good case can be made that this response is defective, because I am not delving that deeply into the OP's (i.e. original poster's) analysis. I found the analysis too difficult to criticize, because I was unable to follow the OP's thinking.

That is, I became confused as to the exact step by step procedure that the OP used to compute (for example) $T(n,2)$ or $T(n,3)$ or $T(n,4)$.

Unfortunately, due to my lack of intuition/experience in this area, the OP's analysis would have had to have been much more long-winded in order for me to analyze the OP's thinking, one slow careful step at a time.

If any other MathSE reviewer can critique the OP's analysis, as is, great. If not, then I would advise the OP to re-write the analysis to make it much more long-winded.

---

$\color{red}{\text{Edit - Insert}}$
I finally reached the point where I now understand the OP's thinking. Because of how long-winded this answer is, I left a 2nd answer that critiques the OP's work.

---

Anyway, while the following response is off-point, I will show how I would enumerate $T(n,k).$

---

For any set $E$, with a finite number of elements, let $|E|$ denote the number of elements in the set $E$.

Let $A(n,k)$ denote the collection of satisfying distributions, under the relaxed restriction that any of the $k$ subsets are permitted to be empty. That is, each element in the collection $A(n,k)$ represents a distribution of the $(2n)$ elements in the set $A$ into $k$ subsets, with the understanding that any of these $k$ subsets are permitted to be empty.

Label the subsets $B_1, B_2, \cdots, B_k.$

For $~m \in \{1,2,\cdots,k\},~$ let $S(n,k,m)$ denote the subset of $A(n,k)$ where each element (i.e. distribution) in $S(n,k,m)$ has subset $B_m$ empty.

Then, it is desired to enumerate

$$|A(n,k)| ~~-~~ |S(n,k,1) \cup S(n,k,2) \cup \cdots \cup S(n,k,k)|.$$

Let $T(0,n,k)$ denote $|A(n,k)|.$

Let $T(1,n,k)$ denote $~\displaystyle \sum_{1 \leq i_1 \leq k} |S(n,k,i_1)|.$

Let $T(2,n,k)$ denote $~\displaystyle \sum_{1 \leq i_1 < i_2 \leq k} |S(n,k,i_1) \cap S(n,k,i_2)|.$

That is, $T(2,n,k)$ denotes the summation of $~\displaystyle \binom{k}{2}~$ terms.

Similarly, for $3 \leq r \leq (k-1),$
let $T(r,n,k)$ denote the summation of the $~\displaystyle \binom{k}{r}~$ terms,
that are given by $~\displaystyle \sum_{1 \leq i_1 < i_2 < \cdots < i_r \leq k} |S(n,k,i_1) \cap S(n,k,i_2) \cap \cdots \cap S(n,k,i_r)|.$

Then, in accordance with Inclusion-Exclusion Theory, the desired enumeration is

$$\sum_{r=0}^{k-1} (-1)^r T(r,n,k).$$

Note that the analogous term $T(k,n,k)$ must equal $0$, because it is impossible for the elements of the set $A$ to be distributed into the $k$ subsets $B_1, \cdots, B_k$, if each of these $k$ subsets is empty.

I should point out that I am assuming (for example) that having $~B_1 = \{a\}, ~B_2 = \{b\}~$ is distinct from having $~B_1 = \{b\}, ~B_2 = \{a\}.$ This distinction is based on the following excerpt from the original posting:

For example, the partition of $\{\{a,a,c\},\{b,b,c\}\}$ of $\{a,a,b,b,c,c\}$ can be defined by an equivalence class or function such as $f(a)=\{1\}$, $f(b)=\{2\}$, $f(c)=\{1,2\}$.

So, the problem has been reduced to the enumeration of $~T(r,n,k).$

---

$\underline{\text{Enumeration of} ~T(0,n,k)}$

In effect, the multiset $A$ contains the $(2n)$ elements given by
$\{x_1,x_1,x_2,x_2,\cdots,x_n,x_n\}.$

To enumerate $T(0,n,k)$, you have to determine how many of the elements $x_1,x_2,\cdots,x_n$ will be paired with their counterpart into the same subset.

For $v \in \{0,1,2,\cdots,n\}$, assume that $v$ of the elements $x_1,x_2,\cdots,x_n$ will be paired with their counterpart into the same subset.

There are $\displaystyle \binom{n}{v}$ ways of selecting the $v$ elements that will be paired with their counterpart. For each of these $v$ elements, there are then $k$ different subsets that the pair of elements may be assigned to.

So, for a specific (fixed) value of $v$, you have the partial enumeration of

$$\binom{n}{v} \times k^v.$$

Then, there will be $(n - v)$ elements from $x_1,\cdots,x_n$ that are not paired with their counterpart into the same subset. For each of these (separated) pairs of elements, there are $~\displaystyle \binom{k}{2}~$ ways that such a pair can be assigned to two of the $k$ subsets.

So, for a specific (fixed) value of $v$, you have the complete enumeration of

$$\binom{n}{v} \times k^v \times \left[\binom{k}{2}\right]^{(n-v)}.$$

Therefore,

$$T(0,n,k) = \sum_{v=0}^n \left\{ ~\binom{n}{v} \times k^v \times \left[\binom{k}{2}\right]^{(n-v)} ~\right\}$$

$$ = k^n \sum_{v=0}^n \left\{ ~\binom{n}{v} \left[\frac{k-1}{2}\right]^{(n-v)} ~\right\}.$$

By binomial expansion, you therefore have that

$$T(0,n,k) = k^n \times \left[1 + \frac{k-1}{2}\right]^n = \left[\frac{k \times (k+1)}{2}\right]^n = \left[\binom{k+1}{2}\right]^n. \tag1 $$

---

$\underline{\text{Enumeration of} ~T(1,n,k)}$

First, enumerate $|S(n,k,1)|$ which represents the subset of $A(n,k)$ that specifically has $B_1$ empty.

It is immediate that $|S(n,k,1) = |A(n,k-1,0)|$. That is, with the subset $B_1$ required to be empty, all of the elements in $A$ must be distributed into the $~(k-1)~$ subsets $B_2, B_3, \cdots, B_k.$

Further, any satisfying distribution of $A(n,k-1,0)$ that involves the $~(k-1)~$ subsets $B_2,\cdots,B_k$ corresponds to a satisfying distribution in $A(n,k,0)$ with the empty set $B_1$ appended to the other sets $B_2,B_3,\cdots,B_k.$

So, there is a clear bijection between $A(n,k-1,0)$ and $S(n,k,1).$

Further, for reasons of symmetry, it is clear that for any $i_1$ such that $2 \leq i_1 \leq k$, you have that

$|S(n,k,i_1)| = |S(n,k,1)| = |A(n,k-1,0)|.$

So, you have that

$$T(1,n,k) = \binom{n}{1} T(0,n,k-1), \tag2 $$

where the enumeration in (2) above can be completed by applying the formula in (1) above, with the value $k$ adjusted to the value $(k-1).$

---

$\underline{\text{Enumeration of} ~T(2,n,k)}$

The analysis in this section will be very similar to the analysis in the previous section.

First, enumerate $|S(n,k,1) \cap S(n,k,2)|$ which represents the subset of $A(n,k)$ that specifically has $B_1$ and $B_2$ both empty.

Similar to the analysis in the previous section, there is a clear bijection between $A(n,k-2,0)$ and $S(n,k,1) \cap S(n,k,2).$

Further, for reasons of symmetry, it is clear that for any $i_1,i_2$ such that $1 \leq i_1 < i_2 \leq k$, you have that

$|S(n,k,i_1) \cap S(n,k,i_2)| = |S(n,k,1) \cap S(n,k,2)| = |A(n,k-2,0)|.$

So, you have that

$$T(2,n,k) = \binom{n}{2} T(0,n,k-2), \tag3 $$

where the enumeration in (3) above can be completed by applying the formula in (1) above, with the value $k$ adjusted to the value $(k-2).$

---

$\underline{\text{Enumeration of} ~T(m,n,k) ~: ~3 \leq m \leq k-1}$

Again, the analysis in this section will be very similar to the analysis in the previous section.

First, enumerate $|S(n,k,1) \cap S(n,k,2) \cap \cdots \cap S(n,k,m)|$ which represents the subset of $A(n,k)$ that specifically has $B_1, B_2, \cdots, B_m$ all empty.

Similar to the analysis in the previous section, there is a clear bijection between $A(n,k-m,0)$ and $S(n,k,1) \cap S(n,k,2) \cap \cdots \cap S(n,k,m).$

Further, for reasons of symmetry, it is clear that for any $i_1,i_2, \cdots, i_m$ such that $1 \leq i_1 < i_2 < \cdots < i_m \leq k$, you have that

$|S(n,k,i_1) \cap S(n,k,i_2) \cap \cdots \cap S(n,k,i_m)| = |S(n,k,1) \cap S(n,k,2) \cap \cdots \cap S(n,k,m)| = |A(n,k-m,0)|.$

So, you have that

$$T(m,n,k) = \binom{n}{m} T(0,n,k-m), \tag4 $$

where the enumeration in (4) above can be completed by applying the formula in (1) above, with the value $k$ adjusted to the value $(k-m).$

---

$\underline{\text{Final Computation of} ~T(n,k)}$

The desired enumeration is

$$T(n,k) = \sum_{r=0}^{k-1} (-1)^r T(r,n,k)$$

Where

• $\displaystyle T(0,n,k) = \left[\binom{k+1}{2}\right]^n$

• For $1 \leq r \leq k-1$:
  $\displaystyle T(r,n,k) = \binom{n}{r} \times \left[\binom{k+1-r}{2}\right]^n.$

---

$\underline{\text{Sanity Checking The Final Computation}}$

Since my computations disagree with the original poster's, I am going to be slow and careful, in this section.

Suppose that $~n=4$ and $k = 2.$

Then $T(4,2)$ represents the number of different distributions of $\{x_1,x_1,x_2,x_2,x_3,x_3,x_4,x_4\}$ into the subsets $B_1,B_2$, such that neither $B_1,B_2$ are empty.

First, consider $T(0,4,2)$ which allows, $B_1$ or $B_2$ to be empty.

For $v \in \{0,1,2,3,4\}$, consider the subset of distributions that have $v$ of the elements paired with their counterpart.

There are $\displaystyle \binom{4}{v} \times 2^v$ ways of selecting the $v$ pairs and then distributing them among $B_1,B_2$.

Then, for the other $(4-v)$ variables, one of the two components must be given to each of $B_1,B_2$.

So,

$$T(0,4,2) = \sum_{v=0}^4 \binom{4}{v} 2^v = [1 + 2]^4.$$

Clearly, $T(0,4,2) - T(4,2) = 2$, since there are exactly $(2)$ ways that one of the two subsets, $B_1,B_2$ may be empty.

Therefore,

$$T(4,2) = 3^4 - 2.$$

Now, consider the general formula for $T(n,2).$

Then $T(n,2)$ represents the number of different distributions of $\{x_1,x_1,x_2,x_2,\cdots,x_n,x_n\}$ into the subsets $B_1,B_2$, such that neither $B_1,B_2$ are empty.

First, consider $T(0,n,2)$ which allows, $B_1$ or $B_2$ to be empty.

For $v \in \{0,1,2,\cdots,n\}$, consider the subset of distributions that have $v$ of the elements paired with their counterpart.

There are $\displaystyle \binom{n}{v} \times 2^v$ ways of selecting the $v$ pairs and then distributing them among $B_1,B_2$.

Then, for the other $(n-v)$ variables, one of the two components must be given to each of $B_1,B_2$.

So,

$$T(0,n,2) = \sum_{v=0}^n \binom{n}{v} 2^v = [1 + 2]^n.$$

Clearly, $T(0,n,2) - T(n,2) = 2$, since there are exactly $(2)$ ways that one of the two subsets, $B_1,B_2$ may be empty.

Therefore,

$$T(n,2) = 3^n - 2.$$

Here, I don't think that it is a good idea to try to sanity check my results any further with the OP's results. That is, I don't see any way that I have misinterpreted the OP's intent, nor do I see any analytical mistake in my computation of $T(n,2).$

So, some resolution must be found between my $T(n,2)$ computation and the OP's, before further sanity checking can be done.