3
$\begingroup$

There are $k$ sets of numbers: $$\lbrace0,1,2,\ldots,m_1\rbrace, \lbrace0,1,2,\ldots,m_2\rbrace, \ldots,\lbrace0,1,2,\ldots,m_k\rbrace$$ Such that $m_1 \lt m_2 \lt \cdots \lt m_k$.

  1. How many combinations of k elements can be made taken 1 element from each set such that each set has all distinct elements (no two elements are equal)?

  2. What is the probability that any two sets will have at least one element common?

I have found that the number of such permutations will be $(m_1+1)m_2(m_3-1)......(m_k-k+2)$, but what will be the number of combinations? Clearly it cannot be just = No. of permutations/$k!$.

$\endgroup$
  • $\begingroup$ I think this question was prematurely closed. Even for k=3 the analysis of the number of allowed sets is nontrivial. If the question is truly off-topic, I would like to see a (prefereably undergraduate) literature reference to where this is solved. (The general solution to the number of combinations seems to be a sum of a product of binomials, where the index of the sum is for me a challenging enumeration; I suspect no closed form exists, even if Bell and Stirling numbers are used, and would like to see one if it does.) Gerhard "Ask Me About System Design" Paseman, 2011.12.17 $\endgroup$ – Gerhard Paseman Dec 17 '11 at 17:33
  • $\begingroup$ Agree with Gerhard. The question seems non-trivial and I don't see why it's "off-topic for MO". Even if an exact answer is not possible, somebody might have something helpful to say. Of course, somebody could edit to make the question read more smoothly.... $\endgroup$ – James Martin Dec 18 '11 at 10:51
  • $\begingroup$ (Earlier comment redacted. Yes, this was prematurely closed.) $\endgroup$ – François G. Dorais Dec 18 '11 at 21:06
  • 1
    $\begingroup$ I'm pretty sure that without further information on the $m_i$'s the best one can do is the determinantal formula that comes from Gessel-Viennot. It would be hard to say more than that, unless the OP expands the question to explain a bit on the intended applications... $\endgroup$ – Gjergji Zaimi Dec 19 '11 at 1:06
  • 1
    $\begingroup$ Partial answer at mathoverflow.net/questions/85927/… ; perhaps you can edit to emphasize the second part of your question. Gerhard "Ask Me About System Design" Paseman, 2012.01.19 $\endgroup$ – Gerhard Paseman Jan 19 '12 at 8:19

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.