ISSN 0236-3933. Вестник МГТУ им. Н.Э. Баумана. Сер. “Приборостроение”. 2012
38
15
21
2
2 ;
k
< <
(3)
29
,
2 ;
s mk s
≤
≤
(4)
.
k l n
≤ ≤
(5)
Построение оценки.
Оценим вероятность
p
.
Общее число допу-
стимых в качестве строк векторов составляет
n
m
⎛ ⎞
⎜ ⎟
⎜ ⎟
⎝ ⎠
.
Число строк,
ненули которых укладываются в заданные
s
стобцов –
;
s
m
⎛ ⎞
⎜ ⎟
⎜ ⎟
⎝ ⎠
число
вариантов выбора из них
k
строк –
n
m
k
⎛
⎞ ⎛ ⎞
⎜
⎟ ⎜ ⎟ ⎜ ⎟ ⎜
⎟ ⎝ ⎠ ⎜
⎟
⎜
⎟
⎝
⎠
.
Рассмотрим выбор
остальных
l
–
k
строк. Если мы считаем количество матриц, содер-
жащих ровно
k
удовлетворяющих условию строк, то в
l
–
k
строк не
должна попасть ни одна, удовлетворяющая условию, и их надо выби-
рать из
n
m
⎛ ⎞
⎜ ⎟
⎜ ⎟
⎝ ⎠
–
s
m
⎛ ⎞
⎜ ⎟
⎜ ⎟
⎝ ⎠
возможных строк. Таким образом, для выбора
l
–
k
строк существует
n s
m m
l k
⎛
⎞
⎛ ⎞ ⎛ ⎞
⎜
⎟
− ⎜ ⎟ ⎜ ⎟
⎜ ⎟ ⎜ ⎟
⎜
⎟
⎝ ⎠ ⎝ ⎠
⎜
⎟
⎜
⎟
−⎝
⎠
вариантов. Отметим, что количество
матриц, в которых условию удовлетворяют ровно
k
строк, заведомо
меньше количества матриц, в которых условию удовлетворяют не
менее
k
строк.
При этом, количество матриц, содержащих не менее
k
строк, удо-
влетворяющих условию, можно оценить сверху следующим образом:
если при выборе
l
–
k
строк не отсекать все строки, удовлетворяющие
условию, а отсечь лишь
k
уже выбранных строк, то все матрицы, со-
держащие не менее
k
нужных строк будут подсчитаны, причем мно-
гократно. Общее число матриц без ограничений на расположение
ненулевых элементов составляет
n
m
l
⎛
⎞ ⎛ ⎞
⎜
⎟ ⎜ ⎟
⎝ ⎠ ⎜
⎟
⎜
⎟
⎝
⎠
.