Probability of n persons picking multiple numbers from N numbers, that all choices are different

Question

Given $N$ distinct numbers, $n$ persons each picks $x_i > 0$ numbers, what is the probability $P$ of them all picking different numbers?

The limiting case of $n > N$ is trivial, $P = 0$. Same for $\sum_{i=1}^n x_i > N$.

This question was inspired by an online ice-breaking event with new colleagues. Every person ($n = 6$) listed their interests ($x_i \approx 4$), and surprisingly there were zero match. Naturally some interests may be more popular than others, but I will leave it for now.

I wrote a simple script to test the idea for $x_i = x$:

import numpy as np

def run(N, n, x, runs):
    all_diff = 0
    for i in range(runs):
        all_diff += draw(N, n, x)
    return all_diff / runs

def draw(N, n, x):
    """Return 1 if every person picks a different number, return 0 otherwise."""
    step = 1 / N
    drawn_nums = []
    for i in range(n):
        person_i_nums = []
        j = x
        while j > 0:
            drawn_num = int(np.random.rand()//step)
            if drawn_num not in person_i_nums:
                drawn_nums.append(drawn_num)
                person_i_nums.append(drawn_num)
                j -= 1
    if len(drawn_nums) == len(set(drawn_nums)):
        return 1
    else:
        return 0

run(N=50, n=6, x=4, runs=100000) # Out: ~0.003

Forgive me if this question is a duplicate, since there are a million ways to phrase it (this may warrant yet another question...) The closest solution I found was this one, but I would like the "opposite" result (that isn't a simple $1-P$).

Answer 1

First look at your specific case with $N=50$, all $x_i=4$ and $n=6$. I will assume that each person only draws distinct numbers, which is what is needed for your application (you did not state this). So to get only distinct numbers, the first person chooses freely 4 distinct numbers from 50, then the second person 4 distinct numbers from the remaining 46,the third person 4 distinct numbers from the remaining 42, and so on. Without the restriction, each person draws 4 distinct numbers from the 50, independently. That leads to the probability $$ \frac{\binom{50}{4}\binom{46}{4}\binom{42}{4}\binom{38}{4}\binom{34}{4}\binom{30}{4} }{\binom{50}{4}\binom{50}{4}\binom{50}{4}\binom{50} {4}\binom{50}{4}\binom{50}{4}} =0.0026 $$ consistent with what you found. The generalization is now easy, and gives $$ \frac{ \binom{N}{x_1}\binom{N-x_1}{x_2} \dotsm \binom{N-x_1-x_2- \dotsm -x_{n-1}}{x_n} }{ \binom{N}{x_1}\binom{N}{x_2} \dotsm \binom{N}{x_n } } $$ To experiment with this, a simple R function:

pdiff <- function(N, x) {
    n <- length(x) ; 
    num <- N-cumsum(c(0, x))[-(n + 1)]
    exp( sum( lchoose(num, x) ) - sum( lchoose(N, x) ) )
}