Задача по комбинаторике, матрицы из нулей и единиц

[kishkin]

Всем привет!

Столкнулся тут с задачкой. Заранее прошу прощения за корявые объяснения.

Есть матрица N \times N, задан параметр $l \in [1, [\frac{N-1}{2}]]$ заполнена следующим образом:
$\forall~i: a_{ij} = 1,~j \in [i-l, i+l].~ j \le 0$ соответствуют $N+j$. Остальные элементы $0$.

Т.е. первая строчка: $l+1$ единица, $N-2l-1$ нулей, $l$ единиц. Каждая следующая строчка получена путем циклического сдвига вправо предыдущей.

1) Сколько способов выбрать $n$ строк так, чтобы в них было $k+n, k \in [min\{N, 2l+n\},~min\{N, n(l+1)\}]$ ненулевых столбцов?

2) Сколько может быть ненулевых столбцов при выборе $n$ строк?

3) Сколькими способами можно выбрать $n$ строк, в которых будет $k+n$ ненулевых столбцов?

Подскажите, пожалуйста, метод для решения подобных задач.

[maxal]

Учтите тот факт, что если выбрана некоторая строка $i$, то некоторые $2l+1$ последовательных (циклически) столбцов автоматически будут ненулевыми.
Например, ответ на вопрос 2 вообще сразу очевиден.

[kishkin]

2)$k \in [min\{N, 2l+n\},~min\{N, n(2l+1)\}]$ ненулевых столбцов, так?

[maxal]

Угу.

Чем, кстати, вопрос 1) от вопроса 3) отличается?

[kishkin]

maxal

1) Имеется в виду, что $n$ не фиксировано, но только $k$.

3) А тут мы фиксируем и $n$, и $k$.

[kishkin]

Вот мысль появилась. Для начала задачку немного упростить стоит.

Есть матрица $N \times N$, задан параметр $l \in [1, N-1]$ заполнена следующим образом:
$\forall~i: a_{ij} = 1,~j \in [i, i+l]$. $j \ge N$ соответствуют $j-N$. Остальные элементы $0$.

Т.е. первая строчка: $l+1$ единица, $N-l-1$ нулей. Каждая следующая строчка получена путем циклического сдвига вправо предыдущей.

Считаем число ненулевых столбцов 0, при выборе $n = 0$ строк.

1) Выбрав $n, n \in [1, N]$ строк, можно получить $k, k \in [min\{N, l+1\}, min\{N, n(l+1)\}]$ ненулевых столбцов.

2') Зафиксируем $n, n \in [1, N]$. Выбрав именно $n$ строк, получить $k$ ненулевых столбцов, идущих подряд, можно количеством способов:

$$C' = (N-k-1)C_{l+1}(n,~k-n)$$

,

где $$C_{l+1}(n,~k-n)$ - количество $n$-значных чисел (допускаются числа с нулями в начале) в $(l+1)$-ичной системе счисления, у которых сумма цифр равна $k-n$ Это в терминологии, использованной в книге Н. Я. Виленкина. Существует у этого числа несколько свойств и рекуррентная формула, с помощью которых число несложно посчитать.

Но два вопроса остаются в силе:

2) Фиксируем $n, n \in [1, N]$. Сколько существует способов выбрать именно $n$ строк, чтобы получить $k$ ненулевых столбцов (не обязательно, чтобы столбцы шли подряд)?

3) Сколько существует способов выбора строк, чтобы получить $k$ ненулевых столбцов (не обязательно, чтобы столбцы шли подряд)?

4) Есть идеи?

[maxal]

kishkin писал(а):

maxal

1) Имеется в виду, что $n$ не фиксировано, но только $k$.

3) А тут мы фиксируем и $n$, и $k$.

Мне все равно непонятно. Что значит "фиксируем"?

[kishkin]

Доброе утро!

maxal писал(а):

Мне все равно непонятно. Что значит "фиксируем"?

Вы уж извините за неясность. Два разных вопроса. Может, на примерах яснее прозвучит:

1) При $n=3$ сколько существует способов получить $k=4$?

2) Не важно, чему равно $n$. Сколько существует способов получить $k=4$?

[maxal]

Ну начать можете с доказательства такого утверждения:

Пусть выбраны строки с номерами $1\leq x_1<x_2<\dots<x_n\leq N$ и пусть $y_1=N+x_1-x_n$, $y_2=x_2-x_1$, ..., $y_n=x_n-x_{n-1}$ - это расстояния между соседними выбранными строками (заметим, что $y_1+y_2+\dots+y_n=N$). Тогда количество ненулевых столбцов равно:

$$\sum_{i=1}^n \min\{ y_i, 2l+1\}.$$

[kishkin]

Спасибо!

maxal писал(а):

Тогда количество ненулевых столбцов равно:

$$\sum_{i=1}^n \min\{ y_i, 2l+1\}.$$

Тут, наверное,

$$\sum_{i=1}^n \min\{ y_i, l+1\}.$$

[maxal]

Нет, должно быть именно как я написал. По вашей формуле, например, максимум $n(2l+1)$ получается в принципе недостижим.

[kishkin]

Ну, ясно. Оба правы. Я про упрощенную задачу говорил, а вы про первоначальную.