Количество способов заполнить матрицу

[kishkin]

Всем привет!

Небольшая комбинаторная задачка. Сколько существует вариантов заполнения матрицы $n \times k$ нулями и единицами (каждый элемент либо 0, либо 1) при условии, что в каждом столбце есть хотя бы одна единица, а сумма единиц в любой строке равна $l$?

$k \in [l,~nl]$

[maxal]

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

[kishkin]

Если не ошибаюсь, то без требования отсутствия нулевых столбцов задача решается так:

$N = [C_{k}^{l}]^n$

Я, честно говоря, запутался сильно, как раз применяя метод включений-исключений, - вот и спросил.

Сейчас еще разок аккуратно попробую решить.

[maxal]

Верно, только правильнее писать так:

$${k\choose l}^n$$

В дальнейшем будем рассматривать только матрицы с суммами строк равными $l$.

Пусть матрица удовлетворяет свойству $p_j$, если $j$-й столбец в ней нулевой. Положим $P=\{ p_1, p_2, \dots, p_k\}$. Тогда число матриц не удовлетворяющих ни одному из свойств по принципу включения-исключения равно:

$$\sum_{T\subset P} (-1)^{|T|} N_T$$

где $N_T$ число матриц, удовлетворяющий свойствам из множества $T$. Вам остается только вычислить чему равно $N_T$ и подставить в эту формулу. Заметьте также, что на самом деле $N_T$ зависит только от мощности $t=|T|$, но не от содержимого множества $T$. Поэтому $N_T = {k\choose t} f(t)$, где $f(t)$ - некоторая функция. Найдете эту функцию - решите задачу.

[kishkin]

maxal писал(а):

Верно, только правильнее писать так:

$$k\choose l$$

А обозначение $C_{k}^{l}$ чем плохо? Дольше писать?

Идею понял.

Добавлено спустя 10 минут 39 секунд:

Если не ошибаюсь, то

$f(t) = {k - t \choose l}^n$

Добавлено спустя 5 минут 39 секунд:

Ну и ответ соответственно

$N = \sum_{i = 0}^{k} (-1)^i {k \choose i}{k - i \choose l}^n$

Правильно?

[maxal]

Обозначение $C_{k}^{l}$ плохо тем, что оно устарело. В современной научной литературе используется ${k\choose l}$.

Ответ правильный.

[kishkin]

Ошибся.

$N = \sum_{i = 0}^{k-l} (-1)^i {k \choose i}{k - i \choose l}^n$

Добавлено спустя 1 минуту 25 секунд:

maxal писал(а):

Обозначение $C_{k}^{l}$ плохо тем, что оно устарело. В современной научной литературе используется ${k\choose l}$.

Огромное спасибо за совет и за помощь.

[maxal]

kishkin писал(а):

Ошибся.

$N = \sum_{i = 0}^{k-l} (-1)^i {k \choose i}{k - i \choose l}^n$

Ошибки не было, так как биномиальный коэффициент ${a \choose b}$ равен нулю коль скоро $0\leq a<b$. То есть в предыдущем ответе было просто несколько нулевых слагаемых, не влияющих на результат.

[kishkin]

Ясно. Еще раз спасибо.

Добавлено спустя 8 минут 12 секунд:

$N = \sum_{i = 0}^{k-l} (-1)^i {k \choose i}{k - i \choose l}^n$

Если я не ошибаюсь, то $N$ кратно $k!$ (это очевидно). Но, вроде бы, $N$ также кратно $n!$ - это из комбинаторных соображений, случай, если порядок строк не играет роли.

Подскажите, это правильное утверждение?

[maxal]

kishkin писал(а):

Если я не ошибаюсь, то $N$ кратно $k!$ (это очевидно). Но, вроде бы, $N$ также кратно $n!$ - это из комбинаторных соображений, случай, если порядок строк не играет роли.

Подскажите, это правильное утверждение?

Нет. Оба утверждения неверные. Комбинаторным соображениям здесь мешает возможное наличие равных строк в матрице. В этом случае не всякая перестановка строк будет давать уникальную матрицу.

[kishkin]

Ок. Спасибо. Был дурак.