Как сделать треугольник паскаля в excel?

Комбинаторика в Excel

Комбинаторика в Excel

Комбинаторика — раздел математики, изучающий дискретные объекты, множества (сочетания, перестановки, размещения элементов) и отношения на них. Термин комбинаторика был введён в математический обиход Лейбницем, который в 1666 году опубликовал свой труд «Рассуждения о комбинаторном искусстве». Excel поддерживает ряд функций комбинаторики. Чтобы разобраться, какую формулу использовать, следует ответить на ряд вопросов:

1. Исходное множество содержит только уникальные элементы, или некоторые из них могут повторяться?
2. Операция выполняется со всеми элементами множества, или только с некоторой выборкой из них?
3. Важен ли порядок элементов в выборке?
4. После выбора элемента мы его возвращаем назад?

Рис. 1. Дерево решений, какую формулу комбинаторики использовать

Скачать заметку в формате Word или pdf, примеры в формате Excel

Перестановки без повторений

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

Рис. 2. Перестановки (картинка взята здесь)

Если все n элементы разные, то число перестановок обозначается P_n от perturbation.

С другой стороны, произведение n первых натуральных чисел называется n-факториал и обозначается n!

По определению: 1! = 1; 0! = 1.

Функция в Excel =ФАКТР(n). Факториал растет очень быстро. Существенно быстрее экспоненты (рис. 3).

Рис. 3. Расчет числа перестановок без повторений с помощью факториала

Перестановки с повторениями

Если в основном n множестве не все элементы разные, то число перестановок будет меньше n! Например, если наше множество состоит из трех яблок и одной груши, то всего возможно 4 перестановки (рис. 4). Груша может быть первой, второй, третьей или четвертой, а яблоки неразличимы).

Рис. 4. Перестановки с повторениями (картинка найдена здесь)

В общем случае, можно сказать: последовательность длины n, составленная из k разных символов, первый из которых повторяется n₁ раз, второй – n₂ раз, третий – n₃ раз, …, k-й – n_k раз (где n₁ + n₂ + … + n_k = n) называется перестановкой с повторениями из n элементов.

Пример. Сколько различных пятибуквенных слов можно составить из букв слова «манна»?

Решение. Буквы а и н повторяются 2 раза, а буква м один раз.

Размещение без повторений

Размещением из n элементов по m называется упорядоченный набор из m различных элементов, выбранных из n-элементного множества (все элементы множества уникальны; позиции элементов в выборке важны). Число размещений обозначается от arrangement.

Например, два элемента из трех можно выбрать и расположить шестью способами (рис. 4):

Рис. 5. Размещение без повторений (картинка из презентации)

Если m = n количество элементов совпадает с количеством имеющихся мест для размещения. Знаменатель в формуле (4) превращается в 0! = 1. Остается только числитель n! А это – изученная выше перестановка без повторений; см. формулу (1).

Название функции в Excel несколько обескураживает. Но… что поделаешь: =ПЕРЕСТ(n;m)

Рис. 6. Размещение без повторений; обратите внимание на смешанные ссылки, которые позволяют протянуть формулу на всю таблицу

Размещение с повторениями

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

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

Рис. 7. Размещение с повторениями

В общем случае размещение с повторениями или выборка с возвращением – это размещение «предметов» в предположении, что каждый «предмет» может участвовать в размещении несколько раз. По правилу умножения количество размещений с повторениями из n по k:

В Excel используется функция ПЕРЕСТА(n;k).

Задача. Сколько различных номеров можно составить в одном коде региона?

Подсказка. В номере используется 12 букв алфавита, также существующих и в латинском алфавите (А, В, Е, К, М, Н, О, Р, С, Т, У, Х).

Решение. Можно воспользоваться формулой для размещения с повторениями:

Каждую цифру можно выбрать 10 способами, а всего цифр 3, при этом они могут повторяться, и их порядок важен. Каждую букву можно выбрать 12 способами, при этом буквы могут повторяться, и их порядок важен.

Сочетания без повторений

Сочетаниями из n множества по m элементов называются комбинации, составленные из данных n элементов по m элементов, которые различаются хотя бы одним элементом (в сочетаниях не учитывается порядок элементов).

Например, два элемента из 4 сочетаются 6 способами (порядок следования не важен):

Сочетания без повторений образуют знаменитый треугольник Паскаля (рис. 10). В этом треугольнике на вершине и по бокам стоят единицы. Каждое число равно сумме двух расположенных над ним чисел. Строки треугольника симметричны относительно вертикальной оси. Числа в строках, составляющие треугольник Паскаля, являются сочетаниями

где n – номер строки, m – номер элемента в строке, начиная с нулевого. Например, в строке 7:

Рис. 10. Треугольник Паскаля; чтобы увеличить изображение кликните на нем правой кнопкой мыши и выберите Открыть картинку в новой вкладке

В Excel используется функция =ЧИСЛКОМБ(n;m).

Сочетания с повторениями

Сочетания с повторениями по смыслу похожи на размещение с повторениями – это выборки из множества с возвращением выбранного элемента назад перед каждым новым выбором. При этом порядок в выборке не важен.

Например, два предмета из четырех можно выбрать 10 способами, если после каждого выбора предмет возвращается назад (рис. 11).

В общем случае, число сочетаний с повторениями:

Для нашего примера с фруктами

В Excel для подсчета числа сочетаний с повторениями используется функция =ЧИСЛКОМБА(n;m). В нашем примере =ЧИСЛКОМБА(4;2) = 10.

Построение треугольника Паскаля

Треугольник Паскаля — это просто бесконечная числовая таблица «треугольной формы», в которой на вершине и по боковым сторонам стоят единицы, каждое из остальных чисел равно сумме двух чисел, стоящих над ним слева и справа в предшествующей строке. Таблица обладает симметрией относительно оси, проходящей через его вершину.

Треугольник Паскаля часто выписывают в виде равнобедренного треугольника, в котором на вершине и по боковым сторонам стоят единицы, каждое из остальных чисел равно сумме двух чисел, стоящих над ним слева и справа в предшествующей строке. А еще проще объясняют устройство треугольника Паскаля слова: каждое число равно сумме двух расположенных над ним чисел. Все элементарно, но, сколько в этом таится чудес.

На вершине треугольника стоит 1. Треугольник можно продолжать неограниченно. Он обладает симметрией относительно вертикальной оси, проходящей через его вершину. Вдоль диагоналей параллельных сторонам треугольника (на рисунке отмечены зелеными линиями) выстроены треугольные числа и их обобщения на случай пространств всех размерностей.

Треугольные числа в самом обычном и привычном нам виде показывают, сколько касающихся кружков можно расположить в виде треугольника — как классический пример начальная расстановка шаров в бильярде. К одной монетке можно прислонить еще две — итого три — к двум можно приладить еще три — итого шесть. Продолжая наращивать ряды с сохранением формы треугольника, получим ряд 1, 3, 6, 10, 15, 21, 28, 36, 45, 55, 66. что и показывает вторая зеленая линия. Этот замечательный ряд, каждый член которого равен сумме натурального ряда чисел (55=1+2+3+4+5+6+7+8+9+10), содержит также множество знакомцев, хорошо известных любителям математики: 6 и 28 — совершенные числа, 36 — квадратное число, 8 и 21 — числа Фибоначчи.

Следующая зеленая линия покажет нам тетраэдральные числа — один шар мы можем положить на три — итого четыре, под три подложим шесть — итого десять, и так далее.

А следующая зеленая линия (1, 5, 15, 35. ) продемонстрирует попытку выкладывания гипертетраэдра в четырехмерном пространстве — один шар касается четырех, а те, в свою очередь, десяти. В нашем мире и нашем измерении это невозможно, возможно только в четырехмерном, виртуальном. И тем более пятимерный тетраэдр, о котором свидетельствует следующая зеленая линия, он может существовать только в рассуждениях топологов.

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

Даже беглого взгляда, брошенного на треугольник Паскаля, достаточно, чтобы отметить следующие любопытные факты: 10 ядер можно сложить и в виде тетраэдра и в виде плоского треугольника. А 56 гиперядер, образующих тетраэдр в пятимерном пространстве, можно уложить в обычный привычный трехмерный тетраэдр, однако, если бы мы попытались выложить из 56 ядер треугольник, то одно ядро осталось бы лишним.

А вот еще два интересных свойства треугольника Паскаля. Чтобы найти сумму чисел, стоящих на любой диагонали от начала до интересующего нас места, достаточно взглянуть на число, расположенное снизу и слева от последнего слагаемого (слева для правой диагонали, для левой диагонали будет справа, а вообще — ближе к середине треугольника). Пусть, например, мы хотим вычислить сумму чисел натурального ряда от 1 до 9. «Спустившись» по диагонали до числа 9, мы увидим слева снизу от него число 45. Оно то и дает искомую сумму. Чему равна сумма первых восьми треугольных чисел? Отыскиваем восьмое число на второй диагонали и сдвигаемся вниз и влево. Ответ: 120. Но, кстати, 120 — тетраэдральное число. Следовательно, взяв все шары, из которых сложены 8 первых треугольников, мы могли бы сложить тетраэдр.

Суммы чисел, стоящих вдоль не столь круто падающих диагоналей (на рисунке отмечены красными линиями) образуют хорошо известную последовательность Фибоначчи.

Числа Фибоначчи часто встречаются в комбинаторных задачах. Рассмотрим ряд из n стульев. Сколькими способами можно рассадить на них мужчин и женщин так, чтобы никакие две женщины не сидели рядом? При n=1, 2, 3, 4. число способов соответственно равно 2, 3, 5, 8. то есть совпадает с числами Фибоначчи. Паскаль, по-видимому, не знал, что числа Фибоначчи скрыты в его треугольнике. Это обстоятельство было обнаружено только в XIX веке. Числа, стоящие на горизонтальных строках треугольника Паскаля, — это биномиальные коэффициенты, то есть коэффициенты разложения (x+y) n по степеням x и y. Например, (x+y) 2 =x 2 +2xy+y 2 и (x+y) 3 =x 3 +3x 2 y+3xy 2 +y 3 . Коэффициенты разложения 1, 2, 2 стоят во второй строке, а 1, 3, 3, 1 — в третьей строке треугольника. Чтобы найти коэффициенты разложения (x+y) n , достаточно взглянуть на n-ую строку треугольника. Именно это фундаментальное свойство треугольника Паскаля связывает его с комбинаторикой и теорией вероятности, превращая в удобное средство проведения вычислений.

В общем случае, число, показывающее, сколькими способами можно выбрать n элементов из множества, содержащего r различных элементов, стоит на пересечении n-ной диагонали и r-ой строки. Число возможных сочетаний из n элементов по m определяется формулой

где n!=1*2*3*4*. *n так называемый факториал числа n. А значения биномиальных коэффициентов определяются по формуле

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

Технический музей Вены

Треугольник Паскаля двумерный, лежит в плоскости. Непроизвольно появляется мысль — а нельзя ли его закономерности распространить на трехмерный (и четырех -. ) аналог? Оказывается можно! Существует трехмерный аналог треугольника — пирамида Паскаля, ее связь с триномиальными коэффициентами. Пирамиду Паскаля можно строить в форме тетраэдра, а также пирамиды с различными значениями двухгранных углов, один из которых прямой.

По трем внешним ребрам пирамиды стоят единицы. Каждая из трех боковых граней представляет собой треугольник Паскаля. Любой внутренний элемент пирамиды Паскаля, стоящий в n-м сечении, равен сумме трех элементов, расположенных в углах элементарного треугольника (n-1)-го сечения пирамиды. Сечение получается из треугольника Паскаля, основанием которого служит n-я строка Паскаля, умножением элементов его строк почленно на элементы основания, повернутого против часовой стрелки на угол /2.

Если сечение пирамиды Паскаля является правильным треугольником, то при любом n оно имеет три оси симметрии. На рисунке указаны оси симметрии сечения при n = 4.