0
$\begingroup$

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.

  • 0
    @Marc van Leeuwen : yes so what is the answer please2011-12-21

1 Answers 1

2

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.

  • 0
    I'm deapl$y$ grateful Marc!!!2011-12-22