Какими из следующих свойств обладают биномиальные коэффициенты

В математике биномиальные коэффициенты — это коэффициенты в разложении бинома Ньютона по степеням x. Коэффициент при обозначается или и читается «биномиальный коэффициент из n по k» (или «число сочетаний из n по k», читается как «це из n по k»):

(1)

для натуральных степеней .

Биномиальные коэффициенты могут быть также определены для произвольных действительных чисел . В случае произвольного действительного числа биномиальные коэффициенты определяются как коэффициенты разложения выражения в бесконечный степенной ряд:

Для неотрицательных целых a все коэффициенты с индексами k>a в этом ряду являются нулевыми (т.е. ), и поэтому данное разложение представляет собой конечную сумму (1).

В комбинаторике биномиальный коэффициент для неотрицательных целых чисел n и k интерпретируется как количество сочетаний из n по k, то есть количество всех подмножеств (выборок) размера k в n-элементном множестве.

Биномиальные коэффициенты часто возникают в задачах комбинаторики и теории вероятностей. Обобщением биномиальных коэффициентов являются мультиномиальные коэффициенты.

Явные формулы[править | править код]

Вычисляя коэффициенты в разложении в степенной ряд, мы получим явные формулы для биномиальных коэффициентов .

Для всех действительных чисел n и целых чисел k:

где обозначает факториал числа k.

Для неотрицательных целых n и k также справедливы формулы:

Для целых отрицательных показателей степени коэффициенты разложения равны

Треугольник Паскаля[править | править код]

Визуализация биномиального коэффициента до 4 степени

Тождество

позволяет расположить биномиальные коэффициенты для неотрицательных целых чисел n, k в виде треугольника Паскаля, в котором каждое число равно сумме двух вышестоящих:

Треугольная таблица, предложенная Паскалем в «Трактате об арифметическом треугольнике» (1654), отличается от выписанной здесь поворотом на 45°. Таблицы для изображения биномиальных коэффициентов были известны и ранее (Тарталье, О. Хайяму и др.).

Строки в треугольнике Паскаля, делённые на (сумма всех чисел в строке), в пределе стремятся к функции нормального распределения.

Свойства[править | править код]

Производящие функции[править | править код]

Для фиксированного значения n производящей функцией последовательности биномиальных коэффициентов является:

Для фиксированного значения k производящей функцией последовательности биномиальных коэффициентов является:

Двумерной производящей функцией биномиальных коэффициентов для целых является:

Делимость[править | править код]

Из теоремы Люка следует, что:

Основные тождества[править | править код]

Бином Ньютона и следствия[править | править код]

или, в более общем виде,

Свёртка Вандермонда и следствия[править | править код]

Получается вычислением коэффициента при в тождестве . Сумма берётся по всем целым , для которых слагаемое отлично от нуля. Для произвольных действительных , число ненулевых слагаемых в сумме будет конечно.

Другие тождества[править | править код]

Матричные соотношения[править | править код]

Если взять квадратную матрицу, отсчитав N элементов по катетам треугольника Паскаля и повернув матрицу на любой из четырёх углов, то детерминант этих четырёх матриц равен ±1 при любом N, причём детерминант матрицы с вершиной треугольника в верхнем левом углу равен 1.

В матрице числа на диагонали i + j = const повторяют числа строк треугольника Паскаля (i, j = 0,1,…). Её можно разложить в произведение двух строго диагональных матриц: нижнетреугольной и получаемой из неё транспонированием. А именно:

где . Обратная матрица к U имеет вид:

Таким образом, можно разложить обратную матрицу к в произведение двух строго диагональных матриц: первая матрица — верхнетреугольная, а вторая получается из первой путём транспонирования, что позволяет дать явное выражение для обратных элементов:

, где i, j , m, n = 0..p.

Элементы обратной матрицы меняются при изменении её размера и, в отличие от матрицы , недостаточно приписать новую строку и столбец. Столбец j матрицы есть многочлен степени j по аргументу i, следовательно, первые p столбцов образуют полный базис в пространстве векторов длины p+1, чьи координаты могут быть интерполированы многочленом равной или меньшей степени p-1. Нижняя строка матрицы ортогональна любому такому вектору.

при , где многочлен степени a.

Если произвольный вектор длины можно интерполировать многочленом степени , то скалярное произведение со строками (нумерация с 0) матрицы равно нулю.
Используя тождество выше и равенство единицы скалярного произведения нижней строки матрицы на последний столбец матрицы , получаем:

Для показателя большего p можно задать рекуррентную формулу:

где многочлен

Для доказательства сперва доказывается тождество:

Если требуется найти формулу не для всех показателей степени, то

Старший коэффициент равен 1, потребуется a-1 значений, чтобы найти другие коэффициенты:

для

Асимптотика и оценки[править | править код]

Непосредственно из формулы Стирлинга следует, что для верно .

Целозначные полиномы[править | править код]

Нетрудно видеть, что биномиальные коэффициенты являются целозначными полиномами от , т.е. принимают целые значения при целых значениях . Более того, они образуют базис целозначных полиномов, в котором все целозначные полиномы выражаются как линейные комбинации с целыми коэффициентами.[1]

В то же время стандартный базис не позволяет выразить все целочисленные полиномы, используя только целые коэффициенты, так как уже имеет дробные коэффициенты при степенях .

Этот результат обобщается на полиномы многих переменных. А именно, если полином степени имеет вещественные коэффициенты и принимает целые значения при целых значениях переменных, то

где — полином с целыми коэффициентами.[2]

Алгоритмы вычисления[править | править код]

Биномиальные коэффициенты могут быть вычислены с помощью формулы , если на каждом шаге хранить значения при . Этот алгоритм особенно эффективен, если нужно получить все значения при фиксированном . Алгоритм требует памяти ( при вычислении всей таблицы биномиальных коэффициентов) и времени (в предположении, что каждое число занимает единицу памяти и операции с числами выполняются за единицу времени).

При фиксированном значении k биномиальные коэффициенты могут быть вычислены по рекуррентной формуле с начальным значением . Для вычисления значения этот метод требует памяти и времени.

Если требуется вычислить коэффициенты при фиксированном значении можно воспользоваться формулой при начальном задании . При каждом шаге итерации числитель уменьшается на (начальное значение ), а знаменатель соответственно увеличивается на (начальное значение ). Для вычисления значения этот метод требует памяти и времени.

См. также[править | править код]

Биномиальное распределение
Бином Ньютона
История комбинаторики
Композиция (теория чисел)
Разбиение числа
Треугольник Паскаля
Треугольное число
Теорема Люка

Примечания[править | править код]

↑ Прасолов В. В. Глава 12. Целозначные многочлены // Многочлены. — М.: МЦНМО, 1999, 2001, 2003.
↑ Ю. Матиясевич. Десятая проблема Гильберта. — Наука, 1993.

Литература[править | править код]

Биномиальные коэффициенты // Энциклопедический словарь Брокгауза и Ефрона : в 86 т. (82 т. и 4 доп.). — СПб., 1890—1907.
Фукс Д., Фукс М. Арифметика биномиальных коэффициентов // Квант. — 1970. — № 6. — С. 17—25.
Кузьмин О. В. Треугольник и пирамида Паскаля: свойства и обобщения // Соросовский Образовательный Журнал. — 2000. — Т. 6, № 5. — С. 101—109.
Ландо С. К. Теневое исчисление // VIII летняя школа «Современная математика». — Дубна, 2008.
Винберг Э. Б. Удивительные арифметические свойства биномиальных коэффициентов // Математическое просвещение. — 2008. — Вып. 12. — С. 33–42.
Дональд Кнут, Роналд Грэхем, Орен Паташник. Конкретная математика. Математические основы информатики = Concrete Mathematics. A Foundation for Computer Science. — 2-е. — М.: Мир; Бином. Лаборатория знаний; «Вильямс», 1998 — 2009. — 703, 784 с. — ISBN 95-94774-560-7, 78-5-8459-1588-7.

Источник

Опубликовано emz в вт, 10/12/2013 – 16:55

√Cnn-k=Cnk
√∑nk=0Ckn=2n
C2nn=(n!)2

Навигация по подшивке

Дискретная математика
- В группе из 15 человек 6 человек увлекаются театром, 8 человек увлекаются спортом и 3 человека увлекаются и театром, и спортом. Сколько человек в группе не увлекаются ни театром, ни спортом?
- В группе из 17 человек английский язык изучают 10 человек, французский язык изучают 6 человек и оба языка изучают 2 человека. Сколько человек в группе не изучает ни английский, ни французский языки?
- В группе из 20 человек 5 человек сдали экзамен по истории на «отлично», 7 человек сдали экзамен по высшей математике на «отлично» и 2 человека сдали экзамен по обоим предметам на «отлично». Сколько человек в группе не сдали на «отлично» ни экзамен по исто
- В кондитерском магазине продавались три сорта пироженных: эклеры, наполеоны и слоеные. Сколькими способами можно купить 4 пироженных?
- В некоторых видов спортивных соревнований исходом является определение участников, занявших первое, второе и третье места. В соревновании участвует 10 человек. Сколько возможно различных исходов?
- В почтовом отделении имеются открытки 3 видов. Сколькими способами можно купить набор из 5 открыток?
- Встретились 6 друзей, и каждый пожал руку каждому. Сколько всего было рукопожатий?
- Даны два множества: A = {a,b,c}, B = {0,1}. Каково число различных функций типа AB2→B2?
- Даны множества A = a,b,с,e,f, B = b,c,d,e,g, С = b,c,e. Отметьте верное равенство:
- Даны множества A = {a,b,d,e}, B = {b,c,e,f,g}, С = {c,f,g}. Отметьте верное равенство:
- Даны три множества: A = {1,2,3}, B = {a,b}, C = {0,1}. Каково число различных функций типа AB2→C?
- Даны три множества: A = {a,b,c}, B = {-1,1}, C = {0,1}. Каково число различных функций типа AB*C2?
- Какие из множеств замкнуты относительно сложения?
- Какие из множеств с операцией сложения образуют группу?
- Какие из множеств с указанной операцией над элементами образуют группу?
- Какие из операций ассоциативны?
- Какие из операций ассоциативны?
- Какие из операций коммутативны?
- Какие из операций коммутативны?
- Какие из операций над множествами ассоциативны?
- Какие из операций над множествами коммутативны?
- Каким может быть дополнение к отношению строгого порядка?
- Каким может быть дополнение к отношению эквивалентности?
- Какими из следующих свойств обладают биномиальные коэффициенты?
- Какими из следующих свойств обладают биномиальные коэффициенты?
- Какими из следующих свойств обладают биномиальные коэффициенты?
- Какое из множеств является конечным?
- Какой элемент является образующей в группе {-1,1} с умножением?
- Какой элемент является образующей в группе целых степеней двойки с умножением?
- Какой элемент является образующей в группе целых чисел со сложением?
- Между множествами A = {a,b,c,d} и B = {1,2,3,4} множеством пар заданы соответствия G = {(a,1),(b,1),(c,3),(d,4)} и H = {(a,1),(c,1),(c,3),(d,4)}. Какое соответствие функционально?
- Между множествами A = {a,b,c,d} и B = {1,2,3,4} множеством пар заданы соответствия G = {(a,1),(c,3),(d,3),(d,4)} и H = {(a,2),(b,1),(c,3),(d,3)}. Какое соответствие функционально?
- Множества A, B, C выражены через три других множества D, E, F следующими равенствами (знак пересечения опущен): A = D(E∪F), B = DE∪DF, C = (DE)∩(DF). Отметьте верное равенство:
- Множества A, B, C выражены через три других множества D, E, F следующими равенствами (знак пересечения опущен): A = D∪EF, B = ((DE)∪E)F, С = DF∪EF. Отметьте верное равенство:
- Множества A, B, C выражены через три других множества D, E, F следующими равенствами: A = D∩(E∪(FE)), B = (D∩E)∪(D∩F), С = D∩E∪F. Отметьте верное равенство:
- Множество A содержит 5 элементов, множество B содержит 8 элементов. Сколько элементов может содержать их пересечение?
- Множество A содержит 5 элементов, множество B содержит 8 элементов. Сколько элементов может содержать разность AB?
- Множество A содержит 6 элементов, множество B содержит 7 элементов. Сколько элементов может содержать их объединение?
- На вершину горы ведут пять дорог. Сколькими способами турист может подняться на гору и спуститься с нее?
- На множестве A = {a,b,c,d} задано бинарное отношение R = {(a,b),(a,c),(b,c),(c,d)}. Какие пары нужно добавить к R, чтобы получить его транзитивное замыкание?
- На множестве действительных чисел задано отношение |x-y|<5. Отметьте верное утверждение:
- Объединение двух отношений частичного порядка будет отношением частичного порядка …
- Отметьте дистрибутивны слева множества:
- Отметьте подмножества, которые в алгебре целых чисел с умножением образуют подалгебру:
- Отметьте подмножества, которые в алгебре целых чисел со сложением образуют подалгебру:
- Сколькими способами можно выбрать гласную и согласную буквы из слова «здание»?
- Сколькими способами можно выбрать гласную и согласную буквы из слова «пехота»?
- Сколькими способами можно выбрать гласную и согласную буквы из слова «схема»?
- Сколькими способами можно выбрать три различные краски из имеющихся пяти (порядок красоок важен)?
- Сколькими способами можно составить трехцветный полосатый флаг, если имеется материал пяти различных цветов?
- Сколько нечетных двузначных чисел можно составить из цифр 1,2,5,7,8 (цифры можно использовать только 1 раз)?
- Сколько различных слов можно получить перестановками букв в слове abc?
- Сколько различных слов можно получить перестановками букв в слове abcd?
- Сколько различных слов можно получить перестановками букв в слове abcde?
- Сколько четных двузначных чисел можно составить из цифр 2,3,6,7,9 (каждую цифру в числе можно использовать только 1 раз)?
- Слова длины 5 в алфавите {a,b,c,d} перечисляются в лексикографическом порядке. Слово ааааа имеет номер 0. Какой номер будет иметь слово abcad?
- Слова длины 5 в алфавите {a,b,c,d} перечисляются в лексикографическом порядке. Слово ааааа имеет номер 0. Какой номер будет иметь слово bcacd?
- Слова длины 5 в алфавите {a,b,c,d} перечисляются в лексикографическом порядке. Слово ааааа имеет номер 0. Какой номер будет иметь слово caabd?
- Соответствие G между множествами A = {a,b,c,d,e} и B = {1,2,3,4} задано множеством пар G = {(a,1),(b,2),(b,3),(c,1),(c,4),(e,3)}. Какое из множеств является образом элемента b при этом соответствии?
- Соответствие G между множествами A = {a,b,c,d,e} и B = {1,2,3,4} задано множеством пар G = {(a,2),(b,1),(c,3),(d,1),(d,4),(e,3)}. Какое из множеств является образом элемента d при этом соответствии?
- Соответствие G между множествами A = {a,b,c,d} и B = {1,2,3,4} задано множеством пар G = {(a,1),(b,2),(b,3),(c,1),(d,3)}. Отметьте верное утверждение:
- Соответствие G между множествами A = {a,b,c,d} и B = {1,2,3,4} задано множеством пар G = {(a,2),(b,1),(c,1),(d,4)}. Отметьте верные утверждения:
- Соответствие G между множествами A = {a,b,c,d} и B = {1,2,3,4} задано множеством пар G = {(a,2),(c,1),(c,3),(d,3),(d,4)}. Отметьте верное утверждение:
- Трое студентов сдают экзамен. Сколькими способами могут быть поставлены им отметки, если известно, что никто из них не получил неудовлетворительной отметки?
- Функция f(x1,x2) имеет тип A2*B, функция g(y1,y2) имеет тип CA*A. Какой тип имеет функция f(x1,g(y1,y2))?
- Функция f(x1,x2) имеет тип AB→C, функция g(y1,y2) имеет тип AC→A. Какой тип имеет функция f(g(y1,y2),x2)?
- Функция f(x1,x2) имеет тип AC→B, функция g(y1,y2) имеет тип AC→C. Какой тип имеет функция f(x1,g(y1,y2))?
- Чему равен единичный элемент в группе {-1,1} с умножением?
- Чему равен единичный элемент в группе целых степеней двойки с умножением?
- Чему равен единичный элемент в группе целых чисел со сложением?
- Чему равна наибольшая нижняя грань для {b,d}?
- Чему равна наибольшая нижняя грань для {c,f}?
- Чему равна наибольшая нижняя грань для {e,g}?
- Чему равна наименьшая верхняя грань для {b,f}?
- Чему равна наименьшая верхняя грань для {c,e}?
- Чему равна наименьшая верхняя грань для {c,g}?
- Чему равна проекция множества A = {(1,2),(1,3),(2,3),(3,4)} на первую координату?
- Чему равна проекция множества A = {(1,3),(2,3),(2,4),(3,1)} на вторую координату?
- Чему равна проекция множества A = {(1,4),(2,1),(2,3),(4,3)} на первую координату?
- Чему равно число таблиц размером 32 с элементами из множества мощности 3?
- Чему равно число таблиц размером 33 с элементами из множества мощности 2?

Источник

Биномиальными коэффициентами
являются величины

которые выражают число сочетаний
из nэлементов поk.
Эти величины обладают следующими
свойствами.

Свойство
симметрии.

В формуле бинома
это означает, что коэффициенты, стоящие
на одинаковых местах от левого и правого
концов формулы, равны, например:

Действительно,
–
это количество подмножеств, содержащихkэлементов, множества, содержащегоnэлементов. А–
количество дополнительных к ним
подмножеств. Сколько подмножеств,
столько и дополнений.

Свойство
Паскаля.

Пусть
.
Число–
это количество подмножеств изkэлементов множестваX.
Разделим все подмножества на два класса:

1) подмножества,
не содержащие элемент
,
– их будет;

2) подмножества,
содержащие элемент
,
– их будет.

Т.к. эти классы
не пересекаются, то по правилу суммы
количество всех k-элементных
подмножеств множестваXбудет равно

На этом свойстве
основано построение треугольника
Паскаля (рис. 2.2), в n-ой
строке которого стоят коэффициенты
разложения бинома.

Свойство
суммы.

Подставим в
формулу бинома Ньютона

значения
.
Получим

Заметим, что с
точки зрения теории множеств сумма
выражает количество всех подмножествn-элементного
множества. По теореме о мощности булеана
(см. 1.4.4) это количество равно.

Свойство
разности.

Положим в формуле
бинома Ньютона
.
Получим в левой части,
а в правой – биномиальные коэффициенты
с чередующимися знаками, что и доказывает
свойство.

Последнее
свойство удобнее записать, перенеся
все коэффициенты с отрицательными
знаками в левую часть формулы:

тогда свойство легко запоминается
в словесной формулировке: “ сумма
биномиальных коэффициентов с нечетными
номерами равна сумме биномиальных
коэффициентов с четными номерами”.

Задача.
Найти член разложения биномане содержащийx,
если сумма биномиальных коэффициентов
с нечетными номерами равна 512.

Решение. По
свойству разности сумма биномиальных
коэффициентов с четными номерами также
равна 512, значит, сумма всех коэффициентов
равна 512+512=1024. Но по свойству суммы это
число равно.
Поэтому.
Запишем общий член разложения бинома
и преобразуем его:

при
получим:

Член разложения
не содержитx,
если
,
т.е..
Итак, девятый член разложения не содержитxи равен

Свойство
максимума. Если степень биномаn– четное число, то среди биномиальных
коэффициентов есть один максимальный
при.
Если степень бинома нечетное число, то
максимальное значение достигается для
двух биномиальных коэффициентов прии