Числа Каталана
Поделись знанием:
– А много вы нужды увидали, барин? А? – сказал вдруг маленький человек. И такое выражение ласки и простоты было в певучем голосе человека, что Пьер хотел отвечать, но у него задрожала челюсть, и он почувствовал слезы. Маленький человек в ту же секунду, не давая Пьеру времени выказать свое смущение, заговорил тем же приятным голосом.
– Э, соколик, не тужи, – сказал он с той нежно певучей лаской, с которой говорят старые русские бабы. – Не тужи, дружок: час терпеть, а век жить! Вот так то, милый мой. А живем тут, слава богу, обиды нет. Тоже люди и худые и добрые есть, – сказал он и, еще говоря, гибким движением перегнулся на колени, встал и, прокашливаясь, пошел куда то.
– Ишь, шельма, пришла! – услыхал Пьер в конце балагана тот же ласковый голос. – Пришла шельма, помнит! Ну, ну, буде. – И солдат, отталкивая от себя собачонку, прыгавшую к нему, вернулся к своему месту и сел. В руках у него было что то завернуто в тряпке.
– Вот, покушайте, барин, – сказал он, опять возвращаясь к прежнему почтительному тону и развертывая и подавая Пьеру несколько печеных картошек. – В обеде похлебка была. А картошки важнеющие!
Пьер не ел целый день, и запах картофеля показался ему необыкновенно приятным. Он поблагодарил солдата и стал есть.
– Что ж, так то? – улыбаясь, сказал солдат и взял одну из картошек. – А ты вот как. – Он достал опять складной ножик, разрезал на своей ладони картошку на равные две половины, посыпал соли из тряпки и поднес Пьеру.
– Картошки важнеющие, – повторил он. – Ты покушай вот так то.
Пьеру казалось, что он никогда не ел кушанья вкуснее этого.
– Нет, мне все ничего, – сказал Пьер, – но за что они расстреляли этих несчастных!.. Последний лет двадцати.
– Тц, тц… – сказал маленький человек. – Греха то, греха то… – быстро прибавил он, и, как будто слова его всегда были готовы во рту его и нечаянно вылетали из него, он продолжал: – Что ж это, барин, вы так в Москве то остались?
– Я не думал, что они так скоро придут. Я нечаянно остался, – сказал Пьер.
– Да как же они взяли тебя, соколик, из дома твоего?
– Нет, я пошел на пожар, и тут они схватили меня, судили за поджигателя.
– Где суд, там и неправда, – вставил маленький человек.
– А ты давно здесь? – спросил Пьер, дожевывая последнюю картошку.
– Я то? В то воскресенье меня взяли из гошпиталя в Москве.
– Ты кто же, солдат?
– Солдаты Апшеронского полка. От лихорадки умирал. Нам и не сказали ничего. Наших человек двадцать лежало. И не думали, не гадали.
Числа Катала́на — числовая последовательность, встречающаяся во многих задачах комбинаторики. Последовательность названа в честь бельгийского математика Каталана, хотя была известна ещё Л. Эйлеру.
Числа Каталана <math>C_n</math> для <math>n=0,1,2,\dots</math> образуют последовательность:
- 1, 1, 2, 5, 14, 42, 132, 429, 1430, 4862, 16796, 58786, 208012, 742900, 2674440, 9694845, 35357670, 129644790, 477638700, 1767263190, 6564120420, 24466267020, 91482563640, 343059613650, 1289904147324, 4861946401452, … (последовательность A000108 в OEIS)
Содержание
Определения
n-е число Каталана <math>C_n</math> можно определить несколькими эквивалентными способами, такими как[1]:
- Количество разбиений выпуклого (n+2)-угольника на треугольники непересекающимися диагоналями.
- Количество правильных скобочных последовательностей длины 2n, то есть таких последовательностей из n левых и n правых скобок, в которых количество открывающих скобок равно количеству закрывающих, и в любом её префиксе открывающих скобок не меньше, чем закрывающих.
- Например, для n=3 существует 5 таких последовательностей:
-
((())), ()(()), ()()(), (())(), (()())
-
- то есть <math>C_3=5</math>.
- Количество способов соединения 2n точек на окружности n непересекающимися хордами.
- Количество неизоморфных упорядоченных бинарных деревьев с корнем и n+1 листьями.
- Количество всевозможных способов линеаризации декартова произведения 2-х линейных упорядоченных множеств: из 2 и из n элементов.
Свойства
- Числа Каталана удовлетворяют рекуррентному соотношению:
- <math>C_0 = 1</math> и <math>\qquad C_n=\sum_{i=0}^{n-1}C_i C_{n-1-i}</math> для <math>n\ge 1.</math>
- Это соотношение легко получается из того, что любая непустая правильная скобочная последовательность однозначно представима в виде w=(w1)w2, где w1, w2 — правильные скобочные последовательности.
- Также существует более простое рекуррентное соотношение:
- <math>C_0 = 1</math> и <math>\qquad C_{n}=\frac{2(2n-1)}{n+1}C_{n-1}</math>
- Производящая функция чисел Каталана равна:
- <math>\sum_{n=0}^{\infty} C_n z^n = \frac{1-\sqrt{1-4 z}}{2 z}.</math>
- Числа Каталана можно выразить через биномиальные коэффициенты:
- <math>C_n = \frac{1}{n+1}{2 n \choose n} = \frac{1}{2 n+1}{2 n+1 \choose n} = \binom{2 n}{n} - \binom{2 n}{n-1}.</math>
- Другими словами, число Каталана <math>C_n</math> равно разности центрального биномиального коэффициента и соседнего с ним в той же строке треугольника Паскаля.
- Асимптотически <math>C_n \sim \frac{4^n}{n^{3/2}\sqrt{\pi}}.</math>
См. также
Напишите отзыв о статье "Числа Каталана"
Примечания
- ↑ А. Спивак. Числа Каталана. — МЦНМО.
Ссылки
- С. К. Ландо. [www.mccme.ru/ium/ancient/combs93.html Лекции по комбинаторике]. — МЦНМО, 1994.
- А. Шень. Разделы 2.6 и 2.7 // [informatics.mccme.ru/books/progbook.2.pdf Программирование: теоремы и задачи]. — M.: МЦНМО, 2004.
- Stanley, Richard P. (2013), [www-math.mit.edu/~rstan/ec/catadd.pdf Catalan addendum to Enumerative Combinatorics, Volume 2], <www-math.mit.edu/~rstan/ec/catadd.pdf>
- Weisstein, Eric W. [mathworld.wolfram.com/CatalanNumber.html Catalan Number] (англ.) на сайте Wolfram MathWorld.
|
Это заготовка статьи по математике. Вы можете помочь проекту, дополнив её. |
Отрывок, характеризующий Числа Каталана
Размотав бечевки, которыми была завязана одна нога, он аккуратно свернул бечевки и тотчас принялся за другую ногу, взглядывая на Пьера. Пока одна рука вешала бечевку, другая уже принималась разматывать другую ногу. Таким образом аккуратно, круглыми, спорыми, без замедления следовавшими одно за другим движеньями, разувшись, человек развесил свою обувь на колышки, вбитые у него над головами, достал ножик, обрезал что то, сложил ножик, положил под изголовье и, получше усевшись, обнял свои поднятые колени обеими руками и прямо уставился на Пьера. Пьеру чувствовалось что то приятное, успокоительное и круглое в этих спорых движениях, в этом благоустроенном в углу его хозяйстве, в запахе даже этого человека, и он, не спуская глаз, смотрел на него.– А много вы нужды увидали, барин? А? – сказал вдруг маленький человек. И такое выражение ласки и простоты было в певучем голосе человека, что Пьер хотел отвечать, но у него задрожала челюсть, и он почувствовал слезы. Маленький человек в ту же секунду, не давая Пьеру времени выказать свое смущение, заговорил тем же приятным голосом.
– Э, соколик, не тужи, – сказал он с той нежно певучей лаской, с которой говорят старые русские бабы. – Не тужи, дружок: час терпеть, а век жить! Вот так то, милый мой. А живем тут, слава богу, обиды нет. Тоже люди и худые и добрые есть, – сказал он и, еще говоря, гибким движением перегнулся на колени, встал и, прокашливаясь, пошел куда то.
– Ишь, шельма, пришла! – услыхал Пьер в конце балагана тот же ласковый голос. – Пришла шельма, помнит! Ну, ну, буде. – И солдат, отталкивая от себя собачонку, прыгавшую к нему, вернулся к своему месту и сел. В руках у него было что то завернуто в тряпке.
– Вот, покушайте, барин, – сказал он, опять возвращаясь к прежнему почтительному тону и развертывая и подавая Пьеру несколько печеных картошек. – В обеде похлебка была. А картошки важнеющие!
Пьер не ел целый день, и запах картофеля показался ему необыкновенно приятным. Он поблагодарил солдата и стал есть.
– Что ж, так то? – улыбаясь, сказал солдат и взял одну из картошек. – А ты вот как. – Он достал опять складной ножик, разрезал на своей ладони картошку на равные две половины, посыпал соли из тряпки и поднес Пьеру.
– Картошки важнеющие, – повторил он. – Ты покушай вот так то.
Пьеру казалось, что он никогда не ел кушанья вкуснее этого.
– Нет, мне все ничего, – сказал Пьер, – но за что они расстреляли этих несчастных!.. Последний лет двадцати.
– Тц, тц… – сказал маленький человек. – Греха то, греха то… – быстро прибавил он, и, как будто слова его всегда были готовы во рту его и нечаянно вылетали из него, он продолжал: – Что ж это, барин, вы так в Москве то остались?
– Я не думал, что они так скоро придут. Я нечаянно остался, – сказал Пьер.
– Да как же они взяли тебя, соколик, из дома твоего?
– Нет, я пошел на пожар, и тут они схватили меня, судили за поджигателя.
– Где суд, там и неправда, – вставил маленький человек.
– А ты давно здесь? – спросил Пьер, дожевывая последнюю картошку.
– Я то? В то воскресенье меня взяли из гошпиталя в Москве.
– Ты кто же, солдат?
– Солдаты Апшеронского полка. От лихорадки умирал. Нам и не сказали ничего. Наших человек двадцать лежало. И не думали, не гадали.
