Вероятность того, что расположение Secret Santa приведет к идеальному сочетанию

Итак, у нас был Секретный Санта на работе.

Нас 8 человек. Каждый из нас по очереди вытащил маленький кусочек бумаги из миски с именем на нем. Единственное правило: если вы вытягиваете свое имя, вы должны положить лист бумаги обратно в чашу и попробуйте снова.

Давайте назовем людей A, B, C, D, E, F, G, H, что также является порядком, в котором они выбрали свой лист бумаги.

Мы обменялись подарками прошлой ночью.

А был секретом Ф. Санта.
Б был секретом Е, Санта.
С был секретным сыном Д.
Д был секретным С Санта.
Е был тайным секретом Санты.
F был секретным Санта Клаусом.
Г был секретным Х. Санта.
H был секретным секретом G

Видишь что случилось? Мы сделали пары.

А и Ф были друг для друга секретом Санты.
B и E были секретом друг друга Санта.
C и D были секретом друг друга Санта.
G и H были секретом друг друга Санта.

Какова вероятность этого и как вы рассчитываете это?

combinatorics odds Герман
источник

«Если вы вытянете свое имя, вы должны положить лист бумаги обратно в миску и попробовать еще раз». Что произойдет, если вы будете последним, кто выберет свое имя?

Юхо Коккала

Если человек A рисует этикетку C (скажем), а затем человек B рисует этикетку B, будет ли человек A также возвращать этикетку C обратно в шляпу и снова рисовать? Это то, что, по-видимому, подразумевают ответы, но я понимаю, что формулировка означает, что A сохраняет метку C, а B перерисовывает заголовок, содержащий метки (A, B, D, E, F, G, H).

Юхо Коккала

Ответы:

Общее количество назначений среди человек, для которых никто не назначен, составляет (Они называются расстройствами .) Значение очень близко к . $2n$

d (2 n) = (2 n)! (1 / 2 - 1 / 6 + \dots + (- 1)^{k} / k! + \dots + 1 / (2 n)!) .

$d(2n) = (2n)!(1/2 - 1/6 + \cdots + (-1)^k/k! + \cdots + 1/(2n)!).$

(2 n)! / e

$(2n)! / e$

Если они соответствуют идеальным спариваниям, то они являются продуктом непересекающихся транспозиций . Это подразумевает, что их структура цикла имеет вид

(a_{11} a_{12}) (a_{21} a_{22}) \dots (a_{n 1} a_{n 2}) .

$(a_{11}a_{12})(a_{21}a_{22})\cdots(a_{n1}a_{n2}).$

Число различных таких шаблонов - это порядок группы всех перестановок имен, деленный на порядок стабилизатора шаблона. Стабилизирующий элемент может поменять любое количество пар, а также переставитьпары, откудастабилизирующие элементы. Поэтому есть $2n$ $n!$ $2^n n!$

п (2 N) знак равно \frac{(2 N)!}{2^{N} N!}

$p(2n) = \frac{(2n)!}{2^n n!}$

такие пары.

Поскольку все такие идеальные пары - это нарушения, и все нарушения одинаково вероятны, шанс равен

\frac{п (2 N)}{d (2 N)} знак равно \frac{1}{2^{N} N! (1 - 1 / 2 + 1 / 6 - \dots + (- 1)^{К} / К! + \dots + 1 / (2 N)!)} \approx \frac{е}{2^{N} N!},

$\frac{p(2n)}{d(2n)} = \frac{1}{2^n n!(1 - 1/2 + 1/6 - \cdots + (-1)^k/k! + \cdots + 1/(2n)!)} \approx \frac{e}{2^n n!}.$

Таким образом, для человек точный ответ равен а приблизительное значение : они согласны с пятью значимыми цифрами. $2n=8$ $15/2119 \approx 0.00707881$ $e/(2^4\, 4!) \approx 0.00707886$

Чтобы проверить, это Rмоделирование рисует миллион случайных перестановок из восьми объектов, сохраняет только те, которые являются нарушениями, и подсчитывает те, которые являются идеальными парами. Он выводит свою оценку, стандартную ошибку оценки и Z-оценку, чтобы сравнить ее с теоретическим значением. Его вывод

       p.hat           se            Z 
 0.006981031  0.000137385 -0.711721705

Небольшой Z-показатель соответствует теоретическому значению. (Эти результаты будут соответствовать любому теоретическому значению между и .) $0.0066$ $0.0073$

paired <- function(x) crossprod(x[x] - 1:length(x))==0
good <- function(x) sum(x==1:length(x)) == 0

n <- 8
set.seed(17)
x <- replicate(1e6, sample(1:n, n))
i.good <- apply(x, 2, good)
i.paired <- apply(x, 2, paired)

n.deranged <- sum(i.good)
k.paired <- sum(i.good & i.paired)
p.hat <- k.paired / n.deranged
se <- sqrt(p.hat * (1-p.hat) / n.deranged)
(c(p.hat=p.hat, se=se, Z=(p.hat - 15/2119)/se))

Whuber
источник

+1 за глупое лицо енота и очки ... Я немного сократил концепцию "стабилизирующего элемента", потому что я не знаю, с чего начать, но это имеет большой смысл, даже принимая этот бит интуитивно.

Антони Пареллада

@Antoni См. Например, en.wikipedia.org/wiki/Burnside's_lemma .

whuber

@Amoeba Я думал об этом, но решил сосредоточиться на текущей проблеме, так как расстройства так хорошо известны. Статья в Википедии, на которую я ссылаюсь, предоставляет несколько методов получения этой формулы. Наиболее очевидный метод использует принцип включения-исключения, что очевидно из выражения чередующейся суммы.

whuber

Предполагаете ли вы, что рисование ярлыков начинается с нуля, если кто-то рисует собственный ярлык (см. Мои комментарии к вопросу). В противном случае, я не думаю, что все нарушения одинаково вероятны.

Юхо Коккала

@Juho Это хороший вопрос, достойный дальнейших размышлений. Я ответил на основании неявного намерения процедуры рисования, которая будет заключаться в том, чтобы создать все нарушения с равной вероятностью, но не ясно, какая именно процедура использовалась или будет ли она генерировать нарушения с равномерным распределением (или это даже гарантированно удастся вызвать расстройство!).

whuber

Я был очень впечатлен элегантностью в ответе @whuber. Честно говоря, мне пришлось много знакомиться с новыми концепциями, чтобы следовать этапам его решения. Потратив на это много времени, я решил опубликовать то, что получил. Таким образом, то, что следует, является exegetical примечанием к его уже принятому ответу. Таким образом, нет никакой попытки создать оригинальность, и моя единственная цель - предоставить дополнительные точки привязки, чтобы выполнить некоторые из шагов.

Так что вот так ...

$2n$

2. Можем ли мы вывести формулу для расстройств?

$n$

$d(n)=(n-1)[d(n-2) + d(n-1)]=$

$=n\,d(n-2)-d(n-2)+n\,d(n-1)-d(n-1)$

$d(n) - n\,d(n-1) = -[d(n-1)-(n-1)\,d(n-2)]$

Теперь, заметив параллельность между LHS этого уравнения и частью RHS в скобках, мы можем продолжить рекурсивно:

$d(n) - n\,d(n-1)=-[d(n-1)-(n-1)\,d(n-2)] =$

$=(-1)^2\,[d(n-2)-(n-2)\,d(n-3)]=\cdots=(-1)^{n-2}\,d(2)-2\,d(1)$

$d(n) = n\,d(n-1)+(-1)^n$

Работа в обратном направлении:

$d(2)=1$

$d(3)= 3\,d(2)-1 =3*1\,-1$

$d(4)= 4\,d(3)+1 =4*3*1\,-4\,\,+1$

$d(5)= 5\,d(4)-1 =5*4*3*1\,-5*4\,+5\,\,-1$

$d(6)= 6\,d(5)+1 = 6*5*4*3*1\,-6*5*4\,+6*5\,-6\,+1=$

$=6!\left(\frac{1}{2}- \frac{1}{3*2}+\frac{1}{4*3*2}-\frac{1}{5*4*3*2}+\frac{1}{6!}\right)=$

$=6!\left(\frac{1}{6!}-\frac{1}{5!}+\frac{1}{4!}-\frac{1}{3!}+\frac{1}{2!}-\frac{1}{1!}+1\right)$

Так в общем,

$d(n)=n!\left(1-1+\frac{1}{2!}-\frac{1}{3!}+\frac{1}{4!}+\cdots+\frac{1}{n!}\right)$

$e^x$ $x=-1$

$d(n)\approx\frac{n!}{e}$

${a,b,c,d,e,f}$ ${b,d,a,c,f,e}$ a -> b -> d -> c after which it returns to ae -> f $(\text {a b d c})(\text{e f})$

$4$

$(2n)!$ $2n$ $2^n$ $n!$ $p(2n) = \frac{(2n)!}{2^n n!}$

Для Rсимуляции:

1. paired <- function(x) crossprod(x[x] - 1:length(x))==0

x[x] $8$ Paul -> MariaMaria -> PaulMax -> JohnJohn -> MaxMax -> MariaMaria -> MaxPaul -> JohnJohn -> Paul

i $1$

2. good <- function(x) sum(x==1:length(x)) == 0

$x$ $(1,2,3,4,5,6,7,8)$

3.k.paired <- sum(i.good & i.paired) есть ли исключить парные перестановки, подобные приведенной выше на диаграмме, которые не являются отклонениями:

v <- c(1,2,3,4,5,6,7,8)
w <- c(1,2,3,5,4,6,7,8)

(c("is v paired?" = paired(v), "is w paired?" = paired(w),
   "is v a derang?" = good(w), "is w a derang?" = good(w)))

# not all paired permutations are derangements.

Антони Пареллада
источник

e

$e$

\approx

$\approx$

=

$=$

1

$1$

- 1

$-1$

@whuber Спасибо. Я действительно дурак там. Я не очень хорош в повторяющихся индексированных задачах ... Я знал, что что-то не так. Теперь это должно быть исправлено.

Антони Пареллада