Дискретная математика. Ерош И.Л - 80 стр.

UptoLike

ВУЗ: 

СПб ГУАП | Санкт-Петербург

Составители: 

Рубрика: 

80
Если раскладываются предметы нескольких типов на 2 кучки (ящи
ки, корзины, множества), то такой расклад можно выполнять неза
висимо для каждого типа предметов.
Например. Два студента, гуляя по лесу, набрали 10 васильков, 15
незабудок и 12 ромашек. При раскладке на два букета они решили,
что васильки можно разложить 11 различными способами, незабудки
16 и ромашки 13. Всего будет 11·16·13 = 2 288 различных способов.
Среди этих способов встретятся и «несправедливые», когда в одном из
букетов вообще не будет васильков, или ромашек, или незабудок, и
даже учитывается расклад, при котором один из букетов будет пустым.
Однако алгоритм более справедливого расклада мы обсудим позже.
Обобщим полученный результат. Если имеется n
1
предмет 1го
типа, n
2
предмета 2го, …, n
k
предметов kго типа и требуется разло
жить эти предметы на 2 кучки, то число вариантов расклада будет рав
но (n
1
+1)(n
2
+1)…(n
k
+1).
А теперь, используя полученное решение, найдем количество дели
телей любого целого числа N. Известно, что любое целое число одно
значно может быть представлено в так называемой канонической фор
ме, т. е. в виде произведения простых чисел в соответствующих степе
нях: N =
1
1
n
p
2
2
n
p …
k
n
k
p
. Простым числом называется такое целое чис
ло, которое не имеет никаких делителей, кроме 1 и самого себя. При
мерами простых чисел являются числа: 2, 3, 5, 7, 11, 13, 17, 19, 23,
29, 31, … Задача о нахождении количества делителей любого целого
числа N сводится к раскладке этого числа на два сомножителя. В этом
случае степени простых сомножителей раскладываются так же, как
цветы в вышеприведенной задаче. Таким образом, число делителей D
некоторого числа N равно
D(N) = (n
1
+1)(n
2
+1)(n
3
+1)…(n
k
+1). (4.16)
Пример. Найти число делителей N = 720. В канонической форме
760 = 2
3
·5
1
·19
1
. Следовательно, число делителей равно D(760) =
= (3+1)(1+1)(1+1) = 16.
Для нахождения количества делителей N, кратных некоторому чис
лу R, можно
N
R
представить в канонической форме и найти количество
делителей этого числа.
Например, найти количество делителей числа 600, кратных 15. На
ходим
600
15
= 40 = 2
3
·5
1
. Количество делителей числа 600, кратных 15,
равно D(40) = (3+1)(1+1) = 8.

Страницы