2014 dxdy logo

Научный форум dxdy

Математика, Физика, Computer Science, Machine Learning, LaTeX, Механика и Техника, Химия,
Биология и Медицина, Экономика и Финансовая Математика, Гуманитарные науки




 
 Задача по комбинаторике, матрицы из нулей и единиц
Сообщение23.05.2008, 09:38 
Всем привет!

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

Есть матрица 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$ ненулевых столбцов?

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

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

 
 
 
 Re: Задача по комбинаторике
Сообщение23.05.2008, 11:43 
2)$k \in [min\{N, 2l+n\},~min\{N, n(2l+1)\}]$ ненулевых столбцов, так?

 
 
 
 
Сообщение23.05.2008, 12:00 
Аватара пользователя
Угу.

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

 
 
 
 
Сообщение23.05.2008, 12:13 
maxal

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

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

 
 
 
 
Сообщение24.05.2008, 16:53 
Вот мысль появилась. Для начала задачку немного упростить стоит.

Есть матрица $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) Есть идеи? :)

 
 
 
 
Сообщение24.05.2008, 19:28 
Аватара пользователя
kishkin писал(а):
maxal

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

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

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

 
 
 
 
Сообщение25.05.2008, 09:05 
Доброе утро!

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


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

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

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

 
 
 
 
Сообщение27.05.2008, 14:09 
Аватара пользователя
Ну начать можете с доказательства такого утверждения:

Пусть выбраны строки с номерами $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\}.$$

 
 
 
 
Сообщение28.05.2008, 12:49 
Спасибо!

maxal писал(а):
Тогда количество ненулевых столбцов равно:
$$\sum_{i=1}^n \min\{ y_i, 2l+1\}.$$


Тут, наверное, $$\sum_{i=1}^n \min\{ y_i, l+1\}.$$

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

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

 
 
 [ Сообщений: 12 ] 


Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group