Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

This sequence of distributions interests me and I am looking for an expression in closed form. We are looking at populations of size n!. For n=2, we divide the population in half, and assign to each half the property 2 and not-2 (I write 2'), respectively. So S_2 is

$S_{2} = \frac{1}{2!}[{1[2],1[2']}]$.

The 2, 2' are simply attributes of the elements 1,1. For the second,

$S_{3} = \frac{1}{3!}[{1[2,3],2[2,3'],2[2'3'],1[2'3]}]$

For the fourth,

$S_{4} =\frac{1}{4!}[1[2,3,4],3[2,3,4'],2[2,3'4],6[2,3'4'],6[2',3',4'],2[2',3',4],3[2',3,4'],1[2',3,4]$...

While the elements ([2,3,4], etc.) can be used to construct the next element of the sequence, I hope the inductive process here is clear.

share|cite|improve this question
It's not clear to me how you find $2[2,3']$ and $2[2',3']$ can you explain a bit more? $S_4$ is not divided by $4!$ as the other sequences? – GarouDan Nov 4 '11 at 21:45
@GarouDan.Sorry. Edited. Will explain more as soon if still unclear. Thanks for pointing out typo. – daniel Nov 4 '11 at 21:49
@GarouDan: At stage $n+1$ each of the elements from stage $n$ is split into $n+1$ copies; one copy gets the attribute $n+1$, and the other $n$ get the complementary attribute. Thus, $1[2,3,4]$ from stage $4$ will give rise to $1[2,3,4,5]$ and $4[2,3,4,5']$, while $3[2,3,4']$ will produce $3[2,3,4',5]$ and $12[2,3,4',5']$. (At least, this is consistent with what’s displayed.) – Brian M. Scott Nov 4 '11 at 22:12
up vote 1 down vote accepted

The coefficient of $[p_2,p_3,\dots,p_n]$, where $p_k$ is either $k$ or $k'$, can be determined as follows. Let $$c_k=\begin{cases}1,&p_k=k\\k-1,&p_k=k'\;;\end{cases}$$ then the coefficient of $[p_2,p_3,\dots,p_n]$ is $$\frac1{n!}\prod_{k=2}^n c_i\;.$$ This is easily proved by induction from the construction of the $S_n$. Is this enough of a closed form?

If you relabel the properties to start at $1$ instead of $2$, the entities in $S_n$ will have the form $[p_1,\dots,p_{n-1}]$, where $p_k$ is either $k$ or $k'$, and the coefficient of $[p_1,\dots,p_{n-1}]$ will be simply $$\frac1{n!}\prod\bigg\{k\in\{1,\dots,n-1\}:p_k=k'\bigg\}=\left(n\prod\bigg\{k\in\{1,\dots,n-1\};p_k=k\bigg\}\right)^{-1}.$$

share|cite|improve this answer

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

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