Рассмотрим все матрицы из 0 и 1 размера
у которых строки попарно различны, а в каждой строке ровно
единиц. Возьмем одну из них случайно. То есть вероятность будет
Пусть
-- количество способов выбора
столбцов данной матрицы, так, что в каждой строке выбранной подматрицы будет хотя бы одна единица. Вопрос заключается в том, как найти матожидание
?
Вот попытка решения. Всего способов выбора подматрицы
есть
Пусть
-- индикатор того, что
-ый такой способ хороший, то есть в соответствующей подматрице в каждой строке хотя бы одна единица. Тогда
и матожидание
по линейности выходит как сумма матожиданий индикаторов, то есть сумма вероятностей. Но как найти вероятность того, что в случайно выбранной из описанного выше множества матрице в конкретной её подматрице
в каждой строчке будет хотя бы одна единица?