Бурбаки - Книга 1. Теория множеств (947355), страница 51
Текст из файла (страница 51)
Говорят, что Ь вЂ” 1 ~„гьд есть Разложение по основанию Ь целого числа а 1). з-о 'Во всех разделах математики, где не имеются в виду численные расчеты, предложение 8 будет главным образом полезным, когда оно будет применяться к некоторому простому целому числу Ь., Когда целое число Ь достаточно мало, чтобы это было осуществимо, каждое целое число < Ь можно обозначить каким-нибудь отчетливым символом, нззываемым цифрой, причем цифрами, обозначающими О к 1, обычно бывают О и 1. Пусть а — целое число и Ь-1 ~и~ гььз Ь 1 — его разложение ло основанию ь; если целое число л, ь-о фигурирующее в этом разложении, достаточно мало, чтобы это было осуществимо, удобно ассоциировать с целым числом а последовательность символов, полученную записыванием слева нзлраво гог, ...
... гь,гь, и заменой каждого целого числа гг цифрой, которая его обозначает; так полученный символ называется числовым символом, ассоциированным с а. Число а в гермах нли соотношенияк, в которых оно фигурирует, часто заменяют е этом случае на его числовой символ. Например, если С, Я, Р, Р— цифры, числовые символы СЯ, СЯР, СогРП ассоциируются соответственно с СЬ+ Я, СЬ'+ ЯЬ+ Р, СЬ'+ +ОЬ + РЬ+ О. Из предложения 8 вытекает, чта числовой символ, ассоциированный с целым числом а, однозначен и что, если а < Ьь, ан содержит не более Ь цкфр. Заметим, что числовой символ,ассоциированный с целым числом ьь, имеет вид цифры 1 с л последующими цифрами О. Эта система изображения целых чисел числовыми символами называется системой счисления по основанию Ь.
На практике в численном анализе используют следующие системы: а) систему по основанию 2, или двоичную систему, где цифрами являются О и 1; б) деся- ') В случае, если Ь > О, что справедливо, коль скоро а > О. — Прим. род. ') Заметим, что тем самым разложение определено лишь для а > О.— дурям. ред. тичную систему, где цифрами являются О, 1, 2, 3, 4, 5=4+1.
6=5+1, 7= 6+1, 8=7+1, 9= 8+1 и где Ь есть целое чксло 9+1 (числовым символом которого в этой скстеме является, таким образом, 10). Начкиая со средних веков в численном анализе по традиции и слользуегся десятичная система, и именно ею мы будем пользоваться, ико гда нзм надо будет явно записать какое-нибудь целое число на о,пзвсле у дующих страницах этого сочинения.
Для изложения методов, о оляющих получать числовые символы, ассоциированные с суммой, р ззностью, произведением или целой частью частного двук чисел, заданных нх числовыми символами, мы отсылаем к части этого Трактата, посвященной Численному анализу. 8. 11 омбинаторный анализ Пгидложвнив 9 (принцип пастухов). Пусть Е и Р— два множества, а и Ь вЂ” их кардинальные числа, г — сюрьенция мно- -1 жестеа Е на Р, такая, что есе множества у (у) для у~ Р имеют одинановое кардинальное число с; тогда а=Ьс. -1 В самом деле, семейство (7" (у)) бг есть разбиение множества Е, каждый элемент которого есть множество с кардинальным числом С, откуда и следует предложение (9 3, следствие 2 предложения 6). Опввделвние 2.
Пусть и — целое число; обозначим через п! (читается: „и факториал') произведение И (1+ 1). 1(о Имеем 01=1 (гл. Н, 9 б, п'3) и 11=1; ясно, что для всякого целого числа и справедливо соотношение (и+ 1)!= и!(и+ 1). Это последнее соотношение, объединенное с соотношением 01=1, ха- рактеризует, как эта видно. терм и! индукцией па и, Пгвдложвнив 10. Пусть т и п — такие целые числа, что т и. Тогда п!/(п — т)! есть число инэентизных отобралсений произвольного множества А из т элементов в произвольное множество В из и элементов. Докажем индукцией по числу т . ' п элементов множества А. Для т=О предложение очевидно.
Предположим, что т+1 (и, и пусть А — множества из т+1 элементов, А' — некоторое под/ множество множества А, имеющее т элементов, и (а) = А — А . Пусть Р и Р' — множества инъективных отображений множеств А и А' соответственно в В и пусть 1о — отображение у' — ь ул, которое всякой функции ~~Р ставит в соответствие ее сужение на А .
Для — 1 всякой функции У'~Р' элемент у из р(у') своим значением У(а) определяется однозначно; так как у инъективно, необходимо у (а) ~ — 1 ~ — у'(А'). Отсюда вытекает, что Р(у') имеет та же самое число элементов и — т, что и  — у'(А'); принцип пастухов показывает 215 ГЛ. П!. УПОРЯДОЧЕННЪ|Е МНОЖЕСТВА 214 $ Ь. ВЫЧИСЛЕНИЯ С ЦЕЛЫМИ ЧИСЛАМИ тогда, что содержит (и — т), = ' элементов Р л! л! (л — т)! (л — т — 1)! в силу предположения индукции, а это доказывает предложение. Следствие. Число перестановок конечного множества иэ и элемент ов ра вн о и! В самом деле, это число равно числу инъекций множества в себя (й 4, следствие 4 предложения 2).
Пгедложенне 11. Пусть Š— конечное множество из и эле.ментов и (р,.),<|<ь — конечная последовательность целых чисел, такая, что ~~~ р;=и. Тогда число покрытий (Х,) |=! !!<!<а множества Е такими попарно непересекающимися множеь .ствами, что Сап1(Х )= р! для 1 (1 (а, равко п!/И р,!.
|=! Пусть С вЂ” множество перестановок множества Е, Р— множество покрытий (Х,), |<А, удовлетворяющих сформулированным условиям. 'Так как ~~~ р| = и, то Р не пусто. Пусть (А,),, „— элемент множества Р. Для всякой перестановки г'цС семейство (У'(А,)), <г<ь снова принадлежит к Р; обозначим его через !|(У). Для всякого элемента (Х,), ! ь множества Р найдем число элементов У~С, таких. что рД)=(Х,). Чтобы это выполнялось, необходимо и достаточно, чтобы для всякого индекса ! было г"(А!) = Х;; таким образом, множество рассматриваемых перестановок у равномощно произведению множеств биекций множества А| на Х, (гл.
П, й 4, предложение 8); -! ь следовательно, множество |у ((Х ), < ! < ь имеет П р,! элементов(след!=! стене предложения 10). Так как С имеет п1 элементов, достаточно применить принцип пастухов, чтобы получить предложение 11. Следствие 1. Пусть А — множество иэ и элементов и р— целое число (и. Число частей множества А, имеющих р элен! ментов, есть р|(л — р)! ' Достаточно применить предложение 11 к случаю а = 2, р,= р, Рг=п — Р Число подмножеств из р элементов множества из п элементов обозначается (если р (и) через ! 1 и называется (по причинам, ко- |Р) торые выясняются в Алгебре, гл.
1, й 5) биномиальным коэффициентом с индексами и и р. Из соотношения ( )= |,р) р!(л — р)! тотчас вытекает, что ы=~.—.). Это вытекает также кз того факта, что если Š— множество из л элементов, то Х-ьŠ— Х есть биекцня множества частей множества Е, нмеющнк р элементов, иа множество частей множества Е, имеющих. л — р элементов. Положим ( ) = О для всякой пары натуральных целых чисел, та/л! (р) ких, что р > л. Прн этом условии число подмножеств из р элементов /л! произвольного множества яз л элементов есть ( ) для всякого нату'1р~ рального целого числа р.
Следствие 2. Пусть Е и Р— конечные совершенно упорядоченные множества, имеющие соответственно р и и элементов. Тогда число строго возрастающих отображений множества Е в Р есть ( ). В самом деле, такое отображение есть инъекция множества Е в Р (й 1, предложение 13), и, поскольку Е и Р— вполне упорядоченные ($ 4, следствие 1 предложения 3), для всякого подмножеств! Х из р элемьнгов множества Р существует единственное строго возрастающее отображение множества Е на Х 6 2, теорема 3). Пгедложение 12.
Для всякого целого числа и ( )=2" '). э~л В самом деле, если Š— множество из и элементов, левая часть есть число подмножеств множества Е; применение предложения 12 из й 3 заканчивает доказательство. Пгедложение 13. Пусть и и р — целые числа; тогда (,л+~)=(,+ )+© Пусть Š— множество из и+ 1 элементов, Р— множество частей множества Е, имеющих р+1 элементов, а — элемент из Е и Е'= Š— (а).
Обозначим через Р' (соответственно через Рь) множество частей из р+ 1 элементов множества Е, содержащих а (соответственно не содержащих и). Множество Р" есть множество частей из р+ 1 элементов множества Е', а вначит, оно имеет. ') В оригинале вместо ~~ стоит э,', что является, по-вндкмому, опер<э чаткой. (Заметим, что истолкование ~~ как знака суммирования по всем э натуральным целым числам в данный момент невозможно, поскольку лишь в 4 6 будет установлено, что натуральные целые числа обрззуют множество.) — Прим, ред. гл. не ьпорядоченные множества 216 Урр- а з. вычисления с целымн числами 217 (, и + 1) элементов.
Отображение Х вЂ” э Х П Е' есть биекцня множег ства Р на множество частей иа р элементов множества Е'! Р' имеет, /и! таким образом. ! ) элементов. Предложение вытекает из того. ' (р/ что Р есть объедийенне непересекающихся множеств Р' и Р". Если р (л, предложеине 13 может также быть доказано несложным вычислением с использованием формулы ! ) = /лт л! (,р) рПн — р)! Предложение 14. Пусть и — целое число > 0; число ал (соот- ветственно д„) таких пар (/, у) целых чисел, что 1(/(у'<и (соответственно 1 (/(у' <и), есть — п(»+1) ') (соответственно 1 1 2 — и (и — 1)) . 2 В самом деле, дл есть число двухэлементных частей множества (1, и); ледовательно, д„= 2 л! 1 2! (и — 2)! 2 = — п(» — 1).
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
