0
$\begingroup$

The number of ways one can partition an $n$-element set into exactly $k$ subsets is described by the Stirling number of the second type.

Would someone suggest some references on the problem of a set partition problem with constraints as follows?

Partitioning an $n$-element set $S$ into exactly $k$ subsets, labeled as $c_1$ to $c_k$, with the constraint that some special elements $s \in S$ belong to only a subset $C^{\prime}$ of $\{c_1, ..., c_k\}$? How many ways are there? Note that those special elements and the set $C^{\prime}$ are given. Moreover, how about extending $C^{\prime}$ to multiple $C^{\prime}_i$?

For example, partitioning set $\{1, 2, 3, 4\}$ into two subsets named $A$ and $B$, with the constraints that elements $3$ and $4$ can only be in subset $B$. This dummy example is easy to solve. If we have multiple sets $C^{\prime}_i$, it becomes difficult. Any reference and hint are appreciated. Thanks.

$\endgroup$
  • $\begingroup$ Welcome to Math.SE. Without some information about the structure of the family of subsets $C'$, a Reader can imagine a wide variety of "constraints" being proposed here, even before you venture "extending $C'$ to multiple $C_i'$?" Please try to provide a clear account of a problem you would be interested in solving. Then likely the references you seek can be identified. $\endgroup$ – hardmath Feb 26 '16 at 5:17
  • $\begingroup$ I think the Stirling numbers aren't actually appropriate here. Since the numbers are distinct this is different. a $\endgroup$ – Jason Carr Feb 26 '16 at 5:48
  • $\begingroup$ @hardmath, the subsets $C^{\prime}$ are the inputs of the problem, which is pre-determined. There is no special property of those subsets, for example, they can overlap or not. $\endgroup$ – wei wang Feb 26 '16 at 23:26
  • $\begingroup$ I suspect that the problem is so clear in your own mind that you do not appreciate the aspects that are left unclear in this Question, esp. the structure relating "special elements" to subsets $C_i'$. Perhaps by reviewing my response below you will be able to realize just what needs to be added to the problem's formulation. $\endgroup$ – hardmath Feb 27 '16 at 21:49
0
$\begingroup$

Let's consider a version of the problem described in the Question which has multiple sets $C_i'$, each associated with a nonempty subset $B_i \subset S$ which must be covered by $C_i'$ and no other part of a partition of $S$.

In the Question $S = \{1,2,3,4\}$, $B = C' = \{3,4\}$. The Question says that "those special elements and the set $C'$ are given", but the wording of the example is perhaps open to a different interpretation.

If we assume that $C'$ must be used as one part of the partition, then we are reduced to considering how many ways $S\setminus C'$ can be partitioned (if nonempty). Adjoining $C'$ to those partitions would give exactly the partitions of $S$ that satisfy the proposed constraint. The Question further restricts us to partitions of $S\setminus C'$ with exactly $k-1$ parts (since we will use $C'$ as one part in the partition of $S$).

Introducing multiple sets $C_i'$, required to be used as parts that cover nonempty subsets $B_i \subset C_i'$, does not make the problem much more difficult, as long as these constraints are consistent. If all the sets $C_i'$ are pairwise disjoint, then counting feasible partitions reduces to counting partitions of $S\setminus \cup C_i'$ with the appropriate number of parts ($k$ minus the number of distinct $C_i'$ sets prescribed). The nonemptiness of a $B_i \subset S$ implies that each $C_i'$ must be used in a constrained partition of $S$. If some pair $C_i'$ and $C_j'$ have nonempty intersection but are not equal, then no constrained partition is possible!

Yet the Comment left by the OP says, "There is no special property of those subsets, for example, they can overlap or not."

There are few ways I can imagine to adjust the interpretation of the Question to allow for this. Perhaps the OP does not intend that the $C_i'$ actually be used as parts of a partition. The original statement in the Question is:

Partitioning an $n$-element set $S$ into exactly $k$ subsets, labeled as $c_1$ to $c_k$, with the constraint that some special elements $s\in S$ belong to only a subset $C′$ of $\{c_1,\ldots,c_k\}$?

Here I have matched up "special elements" $s$ that should belong to "only a subset $C'$" into a corresponding $B \subset C'$. The generalization to several nonempty $B_i \subset C_i'$ then seems straightforward.

The reinterpretation that seems most worthy of consideration is that, despite the OP's Comment, "the subsets $C'$ are the inputs of the problem, which is pre-determined... they can overlap or not," it is only requiring the position $i$ of the part $c_i$ that is to contain some "special elements". At the least the wording of the "dummy example" seems to bear out this view, since the OP specifies $3$ and $4$ as special elements to belong to part $B$ of the partition, but does not otherwise specify what set $B \subset \{1,2,3,4\}$ is exactly.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.