Археология об основании Рима: Новые раскопки проясняют и такой острый дискуссионный вопрос, как дата самого возникновения Рима...
Состав сооружений: решетки и песколовки: Решетки – это первое устройство в схеме очистных сооружений. Они представляют...
Топ:
Процедура выполнения команд. Рабочий цикл процессора: Функционирование процессора в основном состоит из повторяющихся рабочих циклов, каждый из которых соответствует...
Оценка эффективности инструментов коммуникационной политики: Внешние коммуникации - обмен информацией между организацией и её внешней средой...
История развития методов оптимизации: теорема Куна-Таккера, метод Лагранжа, роль выпуклости в оптимизации...
Интересное:
Уполаживание и террасирование склонов: Если глубина оврага более 5 м необходимо устройство берм. Варианты использования оврагов для градостроительных целей...
Отражение на счетах бухгалтерского учета процесса приобретения: Процесс заготовления представляет систему экономических событий, включающих приобретение организацией у поставщиков сырья...
Наиболее распространенные виды рака: Раковая опухоль — это самостоятельное новообразование, которое может возникнуть и от повышенного давления...
Дисциплины:
2017-11-27 | 370 |
5.00
из
|
Заказать работу |
Число r -сочетаний с повторениями из n -множества равно
.
– доказательство с помощью рекуррентной формулы.
Метод базируется на получении формулы, позволяющей вычислять значения искомой величины шаг за шагом, исходя из известных начальных значений и значений, вычисленных на предыдущих шагах.
Рекуррентная формула r -го порядка – формула вида
an = f (n, an- 1, an- 2, …, an-r).
Формула выражает при n>r каждый член последовательности { ai } через предыдущие r членов. Построение рекуррентной формулы состоит из следующих шагов.
1. Выработка начальных условий исходя из каких-либо очевидных соотношений.
Обозначим через f (n,r). Очевидно, что
(1)
2. Логические рассуждения. Зафиксируем какой-либо элемент во множестве S. Тогда относительно любого r -сочетания с повторениями из n -множества S можно сказать, содержит ли оно данный зафиксированный элемент или нет.
Если содержит, то остальные (r -1) элемент можно выбрать f (n, r -1) способами.
Если не содержит (в выборке этого элемента нет), то r -сочетание составлено из элементов (n -1)-множества (множество S за исключением данного зафиксированного элемента). Число таких сочетаний f (n -1, r).
Т.к. эти случаи взаимоисключающие, то по правилу суммы
(2)
3. Проверка формулы на некоторых значениях и вывод общей закономерности.
1) Вычислим f (n,0). Из (2) следует
. (3)
Тогда f (n,0)= f (n,1)- f (n -1,1). Из (1) f (n,1)= n, f (n -1,1)= n -1.
Следовательно, f (n,0)= n -(n -1)=1= .
2) f (n,1) = f (n,0)+ f (n -1,1) = 1+ n- 1 = n = = .
3) f (n,2) = f (n,1)+ f (n -1,2) = n + f (n -1,1)+ f (n -2,2) = n +(n -1)+ f (n -2,1)+ f (n -3,2) = … =
= n +(n -1)+…+2+1 = .
(сумма арифметической прогрессии)
4) f (n,3) = f (n,2)+ f (n -1,3) = + f (n -1,2)+ f (n -2,3) = + + f (n -2,2)+ f (n -3,3) = … =
.
(сумма геометрической прогрессии)
5) f (n,4) =
На основе частных случаев можно предположить, что
Проверка начальных условий с помощью полученной формулы.
,
что согласуется с (1) #
19, 20) Число бинарных деревьев с n вершинами равно C(n), где C(n) – это n-ое число Каталана.
Количество бинарных деревьев из n вершин называется числом Каталана, которое обладает множеством интересных свойств. N-ое число Каталана считается по формуле (2n)! / (n+1)!n!, которая растёт экспоненциально. (В Википедии предложено несколько доказательств, что это форма числа Каталана.) Число бинарных деревьев данного размера
0 1
1 1
2 2
4 14
8 1430
12 208012
16 35357670
Подстановка
Материал из Википедии — свободной энциклопедии
Перейти к: навигация, поиск
Это статья о подстановке как о синтаксической операции над термами. Возможно, вас интересует перестановка.
В математике и компьютерных науках подстановка — это операция синтаксической замены подтермов данного терма другими термами, согласно определённым правилам. Обычно речь идёт о подстановке терма вместо переменной.
Содержание
|
Определения и обозначения
Для подстановки не существует универсальной, согласованной нотации, равно как и стандартного определения. Понятие подстановки варьируется не только в рамках разделов, но и на уровне отдельных публикаций. В целом, можно выделить контекстную подстановку и подстановку «вместо». В первом случае место в терме, где происходит замена, задаётся контекстом, то есть частью терма, «окружающим» это место. В частности, такое понятие подстановки используется в переписывании. Второй вариант более распространён. В этом случае подстановка обычно задаётся некоторой функцией из множества переменных в множество термов. Для обозначения действия подстановки, как правило, используют постфиксную нотацию. Например, означает результат действия подстановки на терм .
В подавляющем большинстве случаев требуется чтобы подстановка имела конечный носитель, то есть, чтобы множество было конечным. В таком случае её можно задать простым перечислением пар «переменная-значение». Поскольку каждую такую подстановку можно свести к последовательности подстановок, замещающих всего по одной переменной каждая, не ограничивая общности можно считать, что подстановка задаётся одной парой «переменная-значение», что обычно и делается.
Последнее определение подстановки является, видимо, самым типичным и часто используемым. Однако и для него не существует единой общепринятой нотации. Наиболее часто для обозначения подстановки a вместо x в t используется запись t [ a / x ], t [ x:= a ] или t [ x ← a ].
Подстановка переменной в λ-исчислении
В λ-исчислении, подстановка определяется структурной индукцией. Для произвольных объектов , и произвольной переменной результат замещения произвольного свободного вхождения в считается подстановкой и определяется индукцией по построению :
(i) базис: : объект совпадает с переменной . Тогда ;
(ii) базис: : объект совпадает с константой . Тогда для произвольных атомарных ;
(iii) шаг: : объект неатомарный и имеет вид аппликации . Тогда ;
(iv) шаг: : объект неатомарный и является -абстракцией . Тогда [ ;
(v) шаг: : объект неатомарный и является -абстракцией , причем . Тогда:
для и или ;
для и и .
Механическое удерживание земляных масс: Механическое удерживание земляных масс на склоне обеспечивают контрфорсными сооружениями различных конструкций...
Организация стока поверхностных вод: Наибольшее количество влаги на земном шаре испаряется с поверхности морей и океанов (88‰)...
Индивидуальные очистные сооружения: К классу индивидуальных очистных сооружений относят сооружения, пропускная способность которых...
Автоматическое растормаживание колес: Тормозные устройства колес предназначены для уменьшения длины пробега и улучшения маневрирования ВС при...
© cyberpedia.su 2017-2024 - Не является автором материалов. Исключительное право сохранено за автором текста.
Если вы не хотите, чтобы данный материал был у нас на сайте, перейдите по ссылке: Нарушение авторских прав. Мы поможем в написании вашей работы!