I want to know whether or not we can obtain any direct formula for the selection of $r$ objects out a set $\alpha$ that consists of $N$ objects. Where $N$ = $N_1+N_2+N_3+...+N_k$ and $\alpha$ has $N_1$ objects of one kind (all identical), $N_2$ objects of the second kind and so on... I know how to solve such questions through some procedure but I want to know whether or not that procedure has been converted to a direct formula.

  • $\begingroup$ It depends on what you consider to be a "direct formula"; but unless the procedure you learned is inefficient, it is probably about as "direct" as you can get. It's possible that if we knew what procedure you knew, someone could show a neater notation for it or a better procedure. $\endgroup$ – David K Apr 11 '16 at 20:20
  • $\begingroup$ By direct formula, I mean an explicit function of $r$ and $N_i$s. $\endgroup$ – Dvij D.C. Apr 11 '16 at 20:23

I know of two methods for doing this sort of thing in general.

One method is based on the formula $\binom{r+k-1}{k-1}$ to count the number of sets of $r$ elements of $k$ different types, but then applying the principle of inclusion-exclusion in order to eliminate sets that contain more elements of type $i$ than the original multiset contains (that is, where $x_i > N_i$ for some $i$). (I am omitting details of how to do this because to do it completely generally would take far too much work; most questions along these lines that we see on MSE have particular values of $r$, $k$, and $N_i$ for each $i$, which make it possible to apply a specific pattern of inclusion and exclusion.)

The second method uses generating functions. You would be looking for the coefficient of $x^r$ in the polynomial $$ (1 + x + x^2 + \cdots + x^{N_1}) (1 + x + x^2 + \cdots + x^{N_2})\cdots (1 + x + x^2 + \cdots + x^{N_k}). $$ For $x \neq 1$ this polynomial is equivalent to $$ \frac{(1 - x^{N_1 + 1})(1 - x^{N_2 + 1})\cdots(1 - x^{N_k + 1})}{(1-x)^k}. $$ The value you want is the coefficient of $x^r$ in the Taylor series of this function about $0$, which you can find by taking the $r$th derivative of the function at $0$ and dividing by $r!$. (Or perhaps better, have your favorite symbolic math software find the Taylor series for you and read off the coefficient of $x^r$ in that result.)

| cite | improve this answer | |

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.