4
$\begingroup$

This question has its genesis in a group assignment: $k$ students are to be given oral exams. Each student will be asked one distinct question from $n$ questions given to them earlier, no two students will be asked the same question. In order to save time, the group pools their answers to share before the exams. To their surprise, on the exam date, no person was asked a question that they worked on. What is the probability that this would happen? We'll assume the examiners had no knowledge of how they worked, and that every permutation of questions asked was equally likely.

Assuming that no people work together on a question, we can regard the distribution of questions among students as a partition of $n$ into $k$ parts. Then we are counting the number of ways to write $1,2,\ldots,k$ into the Young diagram with the shape of the partition, such that each number $i$ does not appear in row $i$. By including the numbers $k+1,\ldots,n$, which can be freely added to the remaining squares of the diagram in $(n-k)!$ ways, we can assume that there are $n$ students, some of whom may not contribute to any question. For a partition $\lambda$, call the number of ways to fill in the diagram $f(\lambda)$.

If every student solves one question, then $f([1^n])$ is the number of the derangements of $n$. If some student does not solve a question, then they can be placed anywhere, which gives a recurrence relation:

$$ f([a_1,a_2,\ldots,a_k]) = \sum_{i=1}^k a_if([a_1,\ldots,a_i-1,\ldots,a_k]) $$

Using this, I found the numbers $f([m,1^{n-m}])$ are given by $m!\cdot(n-m)\cdot (\text{an OEIS sequence})$ where the sequences for $m=2,\ldots,6$ are: A000153, A000261, A001909, A001910, A176732 and there are similar entries for $m=7,8,9,10$.

I could not find any formula or reference related to other simple families of partitions, or the problem in general.

Do these derangement numbers have a name?

$\endgroup$
  • $\begingroup$ Either you are over thinking this, or the actual problem is not well described by the group assignment scenario (or I am missing something). Why is the probability different from (1 -1/n)^k? $\endgroup$ – The Masked Avenger Apr 15 '15 at 17:20
  • $\begingroup$ I see one thing I missed: a student can work on more than one question. I see also that there are more questions than students. However, if no students share a question, then we get a product of k terms of the form (n-a)/n, where a is allowed to vary over sizes of a certain partition of n into k parts. Or did I miss more? $\endgroup$ – The Masked Avenger Apr 15 '15 at 17:27
  • $\begingroup$ @MaskedAvenger: questions asked are distinct, no two students will be asked the same one. So the $n-a$ available questions will decrease, or not, when one is asked, depending on whether a student worked on that question. $\endgroup$ – Zack Wolske Apr 15 '15 at 17:40
  • $\begingroup$ Ok. The last thing I missed (I hope) is that the tuple of questions asked is an initial fragment of a permutation of the questions handed out. This makes it more of a challenge. I would suggest clarifying the point that no two students will be asked the same question, and that all permutations of (the order of) the n questions are equally likely to occur. $\endgroup$ – The Masked Avenger Apr 15 '15 at 17:43
  • 1
    $\begingroup$ @Per: It's my understanding that Young tableaux are diagrams filled with anything, and standard Young tableaux are filled with $[n]$ in increasing order along rows and down columns. That may not be universal, and if it's confusing I can change it. The problem doesn't seem to me to be related to the usual representation topics that standard Young tableaux are used for, but if it is that would be good too. $\endgroup$ – Zack Wolske Apr 15 '15 at 19:00
3
$\begingroup$

Write $E_j=\sum_{i=0}^j \frac{x^i}{i!}$, and let $F_m(b_1,\dots,b_k)$ denote the coefficient of $x^m/m!$ in the product $E_{b_1}\cdots E_{b_k}$. By standard properties of exponential generating functions, $F_m(b_1,\dots b_k)$ is the number of sequences $(B_1,\dots,B_k)$ of pairwise disjoint sets whose union is $\{1,\dots,m\}$ and such that $|B_i|\leq b_i$ for all $i$. Let $\varepsilon_i$ be the vector of length $k$ with a 1 in the $i$th coordinate and 0's elsewhere. Let $\lambda = (a_1,\dots, a_k)$. It follows by Inclusion-Exclusion that the answer to the question (forgetting the factor $(n-k)!$ from the irrelevant $n-k$ students) is $$ F_k(\lambda)-\sum_{i=1}^k F_{k-1}(\lambda-\varepsilon_i) +\sum_{1\leq i<j\leq k}F_{k-2}(\lambda-\varepsilon_i -\varepsilon_j)-\cdots. $$ I doubt whether there is a simpler answer in general.

$\endgroup$

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.