How to fill a set of container by partition of set?

111 Views Asked by At

Let $\{A,B,C,D\}$ be a table with $4$ containers of sizes respectively $5,5,3,2$. Let $\pi=\{B_1,B_2,\cdots B_k\}$ a partition of a set, where $k\in \mathbb{N}$. I wonder how to enumerate the different way (non-symmetrically) to put the elements of $\cup_{i=1}^k B_i$, in the containers, with a restriction that each block of $\pi$ must be contained in a one container and each containers must be full. Note that two blocs can be contained in one container. We can interpret this problem as a way to arrange student in a building with 4 rooms $A,B,C,D$ which respectively have $5,5,3,2$ bedrooms with the constraints that some group of student must share the same room.

1

There are 1 best solutions below

0
On BEST ANSWER

A partitional species is a functor from the category of partition to the category of finite set and bijection, $$ F:\mathbb{P}\to \mathrm{Set} $$

Let's denote by $\textbf{k}$ the partitional species which assigns to each partition $(U,\pi)$, the way to put the element of $U$ inside the box which can only contain $k$ element. It's indeed a partitional species.

From the theory of partitional species of Oscar-Nava and Gian-Carlo Rota Plethysms, Categories and Combinatorics , we can resolve our problem by considering the partitional species $$ \textbf{5}^{2}.\textbf{3}.\textbf{2} $$ where $.$ is the product of partitional species.

The cycle index series of this species is given by \begin{equation} \textbf{5}^{2}.\textbf{3}.\textbf{2}(x_1,x_2,x_3,x_4,x_5)=\textbf{5}(x_1,x_2,x_3,x_4,x_5)^{2} \textbf{3}(x_1,x_2,x_3)\textbf{2}(x_1,x_2)=x_1^{15} + 4x_1^{13}x_2 + 8x_1^{11}x_2^2 + 3x_1^{12}x_3 + 10x_1^9x_2^3 + 11x_1^{10}x_2x_3 + 2x_1^{11}x_4 + 8x_1^7x_2^4 + 19x_1^8x_2^2x_3 + 3x_1^9x_3^2 + 6x_1^9x_2x_4 + 2x_1^10x_5 + 4x_1^5x_2^5 + 19x_1^6x_2^3x_3 + 10x_1^7x_2x_3^2 + 8x_1^7x_2^2x_4 + 4x_1^8x_3x_4 + 6x_1^8x_2x_5 + x_1^3x_2^6 + 11x_1^4x_2^4x_3 + 14x_1^5x_2^2x_3^2 + x_1^6x_3^3 + 6x_1^5x_2^3x_4 + 10x_1^6x_2x_3x_4 + x_1^7x_4^2 + 8x_1^6x_2^2x_5 + 4x_1^7x_3x_5 + 3x_1^2x_2^5x_3 + 10x_1^3x_2^3x_3^2 + 3x_1^4x_2x_3^3 + 2x_1^3x_2^4x_4 + 10x_1^4x_2^2x_3x_4 + 2x_1^5x_2^2x_4 + 2x_1^5x_2x_4^2 + 6x_1^4x_2^3x_5 + 10x_1^5x_2x_3x_5 + 2x_1^6x_4x_5 + 3x_1x_2^4x_3^2 + 3x_1^2x_2^2x_3^3 + 4x_1^2x_2^3x_3x_4 + 4x_1^3x_2x_3^2x_4 + x_1^3x_2^2x_4^2 + x_1^4x_3x_4^2 + 2x_1^2x_2^4x_5 + 10x_1^3x_2^2x_3x_5 + 2x_1^4x_3^2x_5 + 4x_1^4x_2x_4x_5 + x_1^5x_5^2 + x_2^3x_3^3 + 2x_1x_2^2x_3^2x_4 + x_1^2x_2x_3x_4^2 + 4x_1x_2^3x_3x_5 + 4x_1^2x_2x_3^2x_5 + 2x_1^2x_2^2x_4x_5 + 2x_1^3x_3x_4x_5 + 2x_1^3x_2x_5^2 + 2x_2^2x_3^2x_5 + 2x_1x_2x_3x_4x_5 + x_1x_2^2x_5^2 + x_1^2x_3x_5^2 + x_2x_3x_5^2. \end{equation}

Then the coefficient of $x_1^{2} x_2x_3^{2}x_5$ which is equal to $4$ represents the number of way to assigns the people $\{1,2,\cdots,15\}$ into the building where these groups must share the same room, $\{1\}$ ,$\{2\}$, $\{3,4\}$, $\{5,6,7\}$, $\{8,9,10\}$, and $\{11,12,13,14,15\}$.