# counting the number of subsets defined by a partition

let $\nu=(\nu_1,\cdots,\nu_k)$ be a partition of $n$. to $\nu$ corresponds $\alpha=(\alpha_1,\cdots,\alpha_n)$ where $\alpha_i$ is the number of $i$ in $\nu$ for example to $\nu=(112)$ a partition of $4$ corresponds $\alpha=(2,1,0,0)$. obviously $\sum{i\alpha_i=n}$. Now my problem is the following. Consider a set $X$ with a distinguished point $*$. fix $n$ and $\alpha=(\alpha_1,\cdots,\alpha_n)$ and suppose that $*$ is one of the $\alpha_i$ elements that repeats $i$ times. I want to count all the possible subsets of $X^n$ defined by this $\alpha=(\alpha_1,\cdots,\alpha_n)$ and this multiplicity $i$ of $*$. Things will be more clear with the following example. take $n=4$. we have $5$ partitions $\nu$ and then $5$ corresponding $\alpha$.

1. $\nu=(1,1,1,1)$ so $\alpha=(4,0,0,0)$ here $*$ must be one of the $4$ elements of multiplicity $1$ and so there are 4 subsets of $X^4$ and these are : $(*,x_1,x_2,x_3),(x_1,*,x_2,x_3),(x_1,x_2,*,x_3),(x_1,x_2,x_3,*)$ here of course by $(*,x_1,x_2,x_3)$ we mean the subspace $\{(*,x_1,x_2,x_3)\;|\; x_1,x_2,x_3\in X\}$ and so on.. So here the answer is 4.

2. $\nu=(1,1,2)$ so $\alpha=(2,1,0,0)$ and here there are two cases :

Case 1. $*$ is one of the two elements of multiplicity $1$. In this case, we will arrange $\{*,x,y,y\}$ the subspaces are : $(y,y,x,*),(y,y,*,x),(y,x,y,*),(y,*,y,x)$, $(y,x,*,y),(y,*,x,y),(x,y,y,*),(*,y,y,x),(x,y,*,y)$, $(*,y,x,y),(x,*,y,y),(*,x,y,y)$ and the answer is $12$.

Case 2. $*$ is the point of multiplicity $2$. In this case we will arrange $\{x,y,*,*\}$ and the spaces are: $(*,*,x,y),(*,x,*,y),(*,x,y,*),(x,*,*,y),(x,*,y,*),(x,y,*,*)$ and the answer is $6$.

3. $\nu=(1,3)$ so $\alpha=(1,0,1,0)$ and here there are two cases :

Case 1. $*$ is the point of multiplicity $1$. In this case, we will arrange $\{*,x,x,x\}$ and we have the subspaces : $(*,x,x,x),(x,*,x,x),(x,x,*,x),(x,x,x,*)$ the answer is $4$.

Case 2. $*$ is the point of multiplicity $3$. In this case, we will arrange $\{*,*,*,x\}$ and we have the subspaces : $(*,*,*,x),(*,*,x,*),(*,x,*,*),(x,*,*,*)$ the answer is $4$.

4. $\nu=(2,2)$ so $\alpha=(0,2,0,0)$ and here we will arrange $\{*,*,x,x\}$ and the subspaces are : $(*,*,x,x),(*,x,*,x),(*,x,x,*),(x,*,*,x),(x,*,x,*),(x,x,*,*)$ and the answer is $6$.

5. $\nu=(4)$ so $\alpha=(0,0,0,1)$ and the only subspace is the point $(*,*,*,*)$ and the answer is $1$.

I want to know the answer for a given $n$ and a given $\alpha$ and a fixed choice of multipilicity of $*$ how many subspaces could be constructed in the above way of the exmaple above? thanks a lot.

-
 I am a bit confused by your notation. Is $X\subset\mathbb{N}$? What is $X^n$? Would you consider using terms such as multiplicity & multiset? Also, what is your larger combinatorial goal or context with this? Thanks. – bgins Dec 21 '11 at 12:37 $X$ is any set. it does not matter what is $X$ the problem is purely combinatorial – palio Dec 21 '11 at 12:45 I interpret the question as follows: "on an $n$ element set (here corresponding to the $n=4$ positions between the parentheses), how many set-partitions are there of a given type $\nu$ (multiset of the block sizes) and with one particular block of specified size $\nu_i$ marked?". – Marc van Leeuwen Dec 21 '11 at 13:51 actually the distinguished point $*$ is one among others to have a specified multiplicity and having a distinguished point matters because for example the set $\{(x,y,z)\;|\; x,y,z \in X\}=\{(y,x,z)\;|\; x,y,z \in X\}$ but $\{(,y,z)\;|\; y,z \in X\}\not =\{(y,,z)\;|\; y,z \in X\}$ – palio Dec 21 '11 at 14:07 @palio: Yes obviously being marked matters, and unmarked blocks of the same size are not labelled ("interchanging" two unmarked blocks of the same size makes no difference, interchanging the marked block with an unmarked block of the same size does make a change). That is what giving a set-partition and marking a block mean. – Marc van Leeuwen Dec 21 '11 at 18:28
show 1 more comment

It is simplest to count first the set-partitions of type $\nu$ with in addition all blocks marked (coloured) distinctly, which amounts to counting the permutations (anagrams) of a collection of $\nu_1$ letters 'A', $\nu_2$ letters 'B', etc. (equivalently the number of maps from an $n$-element set to $\{1,2,3,\ldots,k\}$ such that exactly $\nu_i$ of them map to the number $i$, for every $i$). That number is given by the multinomial coefficient $$\binom n{\nu_1,\nu_2,\ldots,\nu_k} = \frac{n!}{\nu_1!\,\nu_2!\,\cdots\,\nu_k!}$$
Next one must compensate for overcounting possibilities in which equal-size unmarked blocks have their colours permuted (since one does not in fact which to distinguish those). Let $(m_1,\ldots,m_l)$ be the list of multiplicities of unmarked block sizes. For instance if $\nu=(5,4,4,3,2,2,2,2,1,1,1,1)$ with one of the $4$ a blocks of size $2$ marked, then $(m_1,\ldots,m_l)=(1,2,1,3,4)$. Then the formula above must be divided by $m_1!\,\cdots\,m_l!$.
So in the end one finds $$\frac{\binom n{\nu_1,\nu_2,\ldots,\nu_k}}{m_1!\,\cdots\,m_l!} = \frac{n!}{\nu_1!\,\nu_2!\,\cdots\,\nu_k! \times m_1!\,\cdots\,m_l!}$$ For instance in case $1$ ($\nu=(1,1,1,1)$ with one singleton marked) one gets $\binom4{1,1,1,1}/3!=4$ solutions, in case $4$ ($\nu=(2,2)$ with one doubleton marked) one gets $\binom4{2,2}/0!\,1!=6$ solutions. The larger example ($\nu=(5,4,4,3,2,2,2,2,1,1,1,1)$ with one of the $4$ a blocks of size $2$ marked) would give $\binom{28}{5,4,4,3,2,2,2,2,1,1,1,1}/1!\,2!\,1!\,3!\,4! = 45947920375752595200000/288$ which gives $159541390193585400000$ solutions.