close

Вход

Забыли?

вход по аккаунту

?

О максимальном числе частей разбиения пространства r n гиперплоскостями.

код для вставкиСкачать
УДК 517.88
В. Р. КРАШЕНИННИКОВ, Н. В. САВИНОВ
О МАКСИМАЛЬНОМ ЧИСЛЕ ЧАСТЕЙ РАЗБИЕНИЯ
ПРОСТРАНСТВА R n ГИПЕРПЛОСКОСТЯМИ
При решении различных математических проблем возникает задача о количестве частей, на которые разбивается пространство R n системой гиперплоскостей (например, пространство признаков при распознавании речи [1-3]или других образов). В работах [4,5] дано общее решение этой задачи для любой системы гиперплоскостей, при любом их количестве и расположении. В настоящей
работе рассматривается случай разбиения на максимальное количество частей и даётся элементарный вывод формулы вычисления этого максимального количества. Показано, что это максимальное количество достигается, когда гиперплоскости находятся в общем положении, то есть
при k ≤ n пересечение любых k гиперплоскостей из рассматриваемой системы имеет размерность
n – k. Для некоторых частных случаев приводятся простые выражения.
Ключевые слова: многомерное пространство, гиперплоскость, разбиение, максимальное количество
частей.
Обозначим через  ( n , m ) максимальное количество частей, на которое может быть разбито пространство R n системой из m гиперплоскостей E m  {E1 , E 2 ,...., E m }.
Теорема. Пространство R n разбивается системой гиперплоскостей E m  {E1 , E2 ,...., Em } на максимальное количество частей, когда гиперплоскости находятся в общем положении.
Доказательство. Проведём доказательство индукцией по размерности n. При n  1 (то есть разбиваемое пространство – прямая, а гиперплоскости – точки) любое семейство m точек разбивает прямую на максимальное возможное количество частей, равное m  1 . Пусть теперь теорема справедлива
при некотором n  1 , и докажем её для n  1 . Рассмотрим наряду с семейством E m  {E1 , E2 ,...., E m }
гиперплоскостей общего положения подсемейства E k  { E1 , E 2 ,...., E k }, 1  k  m . В каждом из
этих подсемейств гиперплоскости также находятся в общем положении. Семейство E 1  { E 1 } (то
есть одна гиперплоскость) разбивает R n  1 на две части. Если мы покажем, что переход от E k к семейству E k  1 увеличивает число частей, на которые разбивается R n  1 , на максимально возможное
количество, то теорема будет доказана. Действительно, при переходе от E k к E k  1 количество частей разбиения пространства R n  1 , очевидно, равно количеству частей, на которые разбивается гиперплоскость E k  1 (рассматриваемая как экземпляр пространства R n ) гиперплоскостями
*
E i*  E i  E k  1 , 1  i  k . Гиперплоскости E i находятся в общем положении, как и исходные ги-
перплоскости E i . Следовательно, по предположению индукции, гиперплоскости E i* разбивают
n
2
E k  1 на максимальное количество частей. Например, при n  2 (когда R  R – плоскость, а E i –
обычные прямые на ней) прямая E k  1 будет пересекаться со всеми прямыми E1 , E2 ,..., Ek , поэтому
число точек пересечения с E k  1 будет максимально возможным, а следовательно, будет максимальным количество частей разбиения прямой E k  1 . Теорема доказана.
Следствие 1. Из доказательства теоремы следует, что при добавлении ещё одной гиперплоскости к
уже имеющимся m гиперплоскостям максимальное количество частей разбиения R n увеличивается на
максимальное число частей разбиения R n  1 также m гиперплоскостями. Отсюда получаем уравнение
 ( n , m  1 )   ( n , m )   ( n  1, m ) .
(1)
© Крашенинников В. Р., Савинов Н. В., 2015
Вестник УлГТУ 2/2015
14
Следствие 2. Из формулы (1) видно, что числа  ( n , m ) можно получить рекуррентно с помощью
схемы, приведённой в таблице 1. В этой таблице первая строка и первый столбец состоят из единиц,
поскольку  ( 0 , m )  1 и  ( n , 0 )  1 . Число в любой другой клетке равно сумме числа в клетке слева и числа в клетке по диагонали влево-вверх.
Таблица 1
Максимальное количество частей разбиения пространства гиперплоскостями
m
n
0
1
2
3
4
5
6
7
8
9
10
0
1
2
3
4
5
6
7
8
9
10
1
1
1
1
1
1
1
1
1
1
1
1
2
2
2
2
2
2
2
2
2
2
1
3
4
4
4
4
4
4
4
4
4
1
4
7
8
8
8
8
8
8
8
8
1
5
11
15
16
16
16
16
16
16
16
1
6
16
26
31
32
32
32
32
32
32
1
7
22
42
57
63
64
64
64
64
64
1
8
29
64
99
120
127
128
128
128
128
1
9
37
93
163
219
247
255
256
256
256
1
10
46
130
256
382
463
502
511
512
512
1
11
56
176
386
638
845
965
1013
1023
1024
На главной диагонали этой таблицы (и под ней) находятся числа  ( n , n )  2 n , что вполне естественно: пространство R n разбивается n гиперплоскостями (например, координатными) на максимально возможное количество 2 n частей. И это действительно максимальное количество, так как в этом
случае каждая имеющаяся часть очередной гиперплоскостью делится на две части. Видно, что
 ( n , m )   ( m , m ) при n  m , это следует из того, что дальнейшее повышение размерности пространства не может увеличить максимальное количество частей разбиения.
Следствие 3. Числа  ( n , m ) можно получить по формуле
 (n, m )  1 
n
m ( m  1)...( m  k  1)
.
!
k
k 1
(2)

Доказательство. Заменяя в (1) m на m  1 , имеем
 ( n , m )   ( n , m  1 )   ( n  1, m  1 ) .
(3)
Последовательно применяя (3), получаем
 ( n , m )   ( n , m  1)   ( n  1, m  1)   ( n , m  2 )   ( n  1, m  2 )   ( n  1, m  1) 
  ( n , m  3 )   ( n , m  3 )   ( n  1, m  2 )   ( n  1, m  1)  ... 
  ( n , 0 )   ( n  1, 0 )   ( n  1,1)   ( n  1, 2 )  ...   ( n  1, m  2 )   ( n  1, m  1),
то есть
 ( n , m )   ( n ,0 ) 
m 1
  ( n  1, k ) .
k 0
Учитывая, что  ( n , 0 )  1 , получаем
 (n, m )  1 
m 1
  ( n  1, k ).
(4)
k 0
Таким образом, в таблице 1 число  ( n , m ) на единицу больше суммы всех чисел, находящихся в
клетках таблицы в предыдущей строке левее клетки с числом  ( n  1, m  1). Эту закономерность
таблицы легко заметить.
Получим сначала формулы для некоторых частных случаев. Очевидно, что
(5)
 (0, m )  1 .
Из (5) и (4) при n=1 получаем
 (1, m )  1 
15
m 1
m 1
k 0
k 0
  ( 0 , k ) 1   1  1  m ,
Вестник УлГТУ 2/2015
то есть
(6)
 (1, m )  m  1 .
При n=2 имеем
 (2, m )  1 
то есть
m 1
m 1
k 0
k 0

 (1, k )  1 
 (2, m ) 
Аналогично при n=3 и n=4 получаем
 ( k  1)  1 
m ( m  1)
,
2
m ( m  1)
 1.
2
(7)
m (m 2  5)
(8)
 1,
6
m ( m  1)[ m ( m  1)  10 ]
(9)
 (4, m ) 
 m  1.
24
Формулы (5)−(8) показывают, что при n  3 числа  ( n , m ) выражаются полиномом переменной m
 (3, m ) 
степени n. Это справедливо и в общем случае. Действительно, пусть  ( n  1, m ) – полиномы от m
степени n  1 , тогда (4) означает, что  ( n , m ) – сумма таких полиномов. Но сумма степеней
m 1
m 1
k 0
k 0
 (m  k ) n1  (m n1  ak 2 m n2  ak 3m n3  ...)  mm n1  ...  m n  ...
есть многочлен от m степени n, поэтому  ( n , m ) выражается полиномом степени n. Такой полином
вполне определяется любыми своими n  1 значениями, например,  ( n , m )  2 m , m  0,1,..., n. Этим
равенствам, очевидно, удовлетворяет полином (2). Итак, следствие 3 доказано.
Отметим ещё одну особенность чисел  ( n , m ) . Выражения под знаком суммы в (2) являются
биномиальными коэффициентами C mk , причём 1  C m0 . Поэтому
 (n, m ) 
n
 C mk ,
(10)
k 0
то есть  ( n , m ) равно сумме первых n биномиальных коэффициентов C mk . При этом C mk  0 , если
k  m.
СПИСОК ЛИТЕРАТУРЫ
1. Krasheninnikov V. R., Krasheninnikova N. A., Kuznetsov V. V., Lebedeva E. Yu. Optimization of dictionary and model library for recognition of speech commands// Pattern Recognition and Image Analysis. –
2011. – Vol. 21, No.3. – Pp. 505−507.
2. Krasheninnikov V. R., Krasheninnikova N. A., Kuznetsov V. V., Lebedeva E. Yu. Optimization of dictionary and model library for recognition of speech commands based on cross-correlation portraits// Pattern
Recognition and Image Analysis, 2013, Vol. 23, No. 1, pp. 80–86.
3. Крашенинников В. Р., Армер А. И., Крашенинникова Н. А., Кузнецов В. В., Хвостов А. В. Некоторые задачи, связанные с распознаванием речевых команд на фоне интенсивных шумов// Инфокоммуникационные технологии (Самара). – 2008. –№1. – С. 72−75.
4. Захаров А. В., Московченко Г. А., Южаков А. П. О числе частей и граней разбиения пространства R n гиперплоскостями // Комплексный анализ и дифференциальные операторы : сб. науч. тр. –
Красноярск : КрасГУ, 2000.– С. 20−30.
5. Московченко Г. А. О числе частей разбиения пространства R n гиперплоскостями // Вестник
Красноярского госуниверситета.− 2003. − Вып. 1.– С. 27−31.
•••••••••••••••••••
Крашенинников Виктор Ростиславович, доктор технических наук, профессор, заведующий кафедрой «Прикладная математика и информатика» УлГТУ.
Савинов Николай Васильевич, кандидат физико-математических наук, доцент кафедры «Высшая
математика» УлГТУ.
Вестник УлГТУ 2/2015
16
Документ
Категория
Без категории
Просмотров
4
Размер файла
462 Кб
Теги
пространство, гиперплоскостей, разбиение, частей, максимальной, числа
1/--страниц
Пожаловаться на содержимое документа