3
$\begingroup$

I will use letters as objects. In general, suppose we have objects $\underbrace{X_1, \dotsc, X_1}_{n_1}, \underbrace{X_2, \dotsc, X_2}_{n_2}, \dotsc,\dotsc, \dotsc, \underbrace{X_k, \dotsc, X_k}_{n_k}$. Then what is the number of ways we can choose and order $N$ objects $0 \leq N \leq n_1 +\dotsb + n_k$, i.e. the number of permutations? If $n_1 = \dotsb = n_k = 1$, then of course this is just a standard permutation problem. I am just curious if there is a formula for it.

Note: I initially asked about combinations, which was pointed out to be a duplicate of the question here. I have deleted the original post to ask this question, instead.

$\endgroup$
  • $\begingroup$ does a recurrence help you? $\endgroup$ – ILikeMath Aug 9 '13 at 19:51
  • $\begingroup$ Sorry for the confusion, Pratyush. I meant you should link to the question of which your original was a duplicate. A link to a deleted question won't stay active for long. $\endgroup$ – Cameron Buie Aug 9 '13 at 19:56
  • $\begingroup$ @DiegoHuerfano Of course a explicit formula is better but I would like to see your recurrence solution. $\endgroup$ – Pratyush Sarkar Aug 9 '13 at 20:02
  • $\begingroup$ "If $n_1 = \cdots n_k=1$, then of course this is just a standard permutation problem" ... only if $k=N$, no? $\endgroup$ – leonbloy Aug 9 '13 at 20:16
  • $\begingroup$ @leonbloy If $n_1 = \dotsb = n_k = 1$, then the total number of objects is $n_1 + \dotsb + n_k = 1 + \dotsb + 1 = k$ and I am choosing and ordering $N$ objects so the answer is ${}^kP_N = \frac{k!}{(k - N)!}$. For the even more special case $k = N$, its ${}^kP_k = k!$. $\endgroup$ – Pratyush Sarkar Aug 9 '13 at 20:51
0
$\begingroup$

Consider the recurrence where $n$ is the number of elements to choose, $k$ is the class that we are considering and $f(n,k)$ means the number of ways of take $n$ elements with elements of the classes $1,2,...,k$

$$f(n,k)=\sum\limits_{i=0}^{min(n,n_{k})}{ \frac{1}{i!} f(n-i,k-1)}, \space\space\space\space k>0$$ $$f(0,0)=1$$ $$f(n,0)=0,\space\space\space\space n>0.$$

We know that if we have $n$ letters and there are $k$ subclasses where each class have $n_j$ letters $L_j$ with $n_1+...+n_k=n$, then the number of all possible permutations is

$$\frac{n!}{n_1!...n_k!} \space\space\space\space(1)$$

because each $n_j$ letters $L_j$ are indistinguishable.

Now there are $n_1+...+n_k$ letters in total and first we want to choose $n$ of them without permute them, then for each class $k$ we will take $i=0$, or $i=1$,..., or $i=n_k$. So we will add up each election which yields to $f(n,k)=\sum\limits_{i=0}^{min(n,n_{k})}{ f(n-i,k-1)}$. But we want to choose them permute them, so will use the formula $(1)$ and we obtain the above recurrence. Therefore the answer will be

$$N!f(N,k).$$

$\endgroup$
  • $\begingroup$ I don't quite understand what is $f(n,k)=\sum\limits_{i=0}^{min(n,n_{k})}{ f(n-i,k-1)}$ and how you got it in the last paragraph. $\endgroup$ – Pratyush Sarkar Aug 9 '13 at 21:42
  • $\begingroup$ I think I get that equation now. But now I am not sure about the upper limit $min(n,n_{k})$ of that sum. $\endgroup$ – Pratyush Sarkar Aug 9 '13 at 21:51
  • $\begingroup$ If we are in the class $k$, we can choose $0$ elements of them, or $1$, .... So we will add up those "elections". Whenever we choose an element of the class $k$, we substract to the total elements for choose $n$ so we have $f(n,k)=f(n-0,k-1)+f(n-1,k-1)+...$. The $k-1$, if we already choose a number of elements in class $k$, we need to choose elements in the next stage ($k-1$ class). The $min(n,n_k)$ is to fix a limit, beacuse in the stage $k$ we can not choose a number of elements more than $n_k$, but we can not choose a number of elements more than $n$ (the remain). $\endgroup$ – ILikeMath Aug 9 '13 at 21:54
  • $\begingroup$ Thanks. I get it now. But now I don't understand the $\frac{1}{i!}$ factor hehe. I don't think it is needed because nothing is counted more than once. $\endgroup$ – Pratyush Sarkar Aug 9 '13 at 22:15
  • $\begingroup$ I don't think so. If we quit $\frac{1}{i!}$ factor, then the answer $N!f(N,k)$ will count more than we need. So, if we put that factor, we are using the formula $(1)$ with $\frac{N!}{i_1!...i_k!}$. $\endgroup$ – ILikeMath Aug 9 '13 at 22:20
3
$\begingroup$

Let $m_i$ be the number of objects of type $i$ that were picked. Then $0\le m_i \le n_i$ and $\sum_{i=1}^k m_i = N$. For a given set $\{m_i\}$, there are $ N!/\prod (m_i!)$ permutations. Hence the count is given by

$$ \sum_{ m_1,m2 \cdots m_k } \frac{N!}{\prod m_i!} $$

Where the sum is restricted to $0\le m_i \le n_i$ and $\sum m_i=N$. That is:

$$ N ! \sum_{m_1=0}^{\min(N,n_1)} \frac{1}{m_1!} \sum_{m_2=0}^{\min(N-m_1,n_2)} \frac{1}{m_2!} \cdots \sum_{m_{k-1}=0}^{\min(N-m_1-m_2-\cdots,n_{k-1})} \frac{1}{m_{k-1}!} \frac{[N-(m_1+m_2 + \cdots +m_{k-1})\le n_k]}{(N-(m_1+m_2 + \cdots +m_{k-1}))!} $$

$\endgroup$
  • $\begingroup$ But for each $m_i$ elements, we can choose them of $\binom{n_i}{m_i}$ ways!. $\endgroup$ – ILikeMath Aug 9 '13 at 21:10
  • $\begingroup$ mmm, no, I don't read the problem in that way, I consider the elements inside each set as undistinguishable. Say, if $n_1=5$ and I choose $m_1=3$, there are not ${5 \choose 3}$ ways of picking those 3, there is only one way. $n_1=5$ just gives me a bound on $m_1$. Of course, this is a matter of interpretation. $\endgroup$ – leonbloy Aug 9 '13 at 21:14
  • $\begingroup$ leonbloy is right. What I intended was for any $i$, $X_i, \dots, X_i$ are identical. $\endgroup$ – Pratyush Sarkar Aug 9 '13 at 21:16
  • $\begingroup$ @leonbloy If I were to find the solution in a straight forward way, your answer is the same thing I would do also but the problem is $\sum_{ m_1,m2 \cdots m_k } \frac{N!}{\prod m_i!}$ is very hard to calculate. $\endgroup$ – Pratyush Sarkar Aug 9 '13 at 21:19
  • $\begingroup$ Yes, they are identical, but I think that, for example, if we have $2$ undistinguishable objects we can choose one of them of $2$ ways no of $1$ way. $\endgroup$ – ILikeMath Aug 9 '13 at 21:19

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.