Подстановка переменной в программировании

• Подстановка переменной (англ. substitution) в аппликативном программировании понимается следующим образом. Для вычисления значения функции f на аргументе v применяется запись f(v)}, где f определена конструкцией f(x) = e. Запись f(v) в этом случае означает, что в выражении e происходит замещение, или подстановка переменной x на v. Выполнение замещения происходит в соответствии с семантикой вычислений.
• Подстановка переменной (англ. assignment) в программировании понимается как присваивание. Оператор присваивания является проявлением эффекта «бутылочного горлышка» фон Нейманна для традиционных языков программирования^[1]. От этого свободны аппликативные вычислительные системы.

http://math.nsc.ru/LBRT/u3/bard/fails/Brenner_Evans.pdf

21Производящие функции. Производящая функция (нумератор) и перечисляющая производящая функция для сочетаний без повторений.

Производящие функции: 1)Z-преобразования 2)генератриса 3)порождающая функция 4)производящая функция последовательности {a_r} на базисе {g_r} – функция f при разложении которой в ряд по функциям фиксированного базиса {g_r} образуется данная последовательность коэффициентов {a_r} …………*)

Данный ряд – формальный. Название формальный означает, что мы формулу *) трактуем как удобную запись нашей последовательности – в данном случае несущественно, для каких (действ и комплексных) значений он сходится. Роль t сводится к тому чтобы различать коэффициенты последовательности А0,А1,…Аr….поэтому в теории производящих функций никогда не вычисляют значения таого ряда для конкретного значения переменной t. Выполняются лишь только некоторые операции на таких рядах, а затем определяются только некоторые операции на таких рядах а затем определяются коэффициенты при отдельных степенях переменной t.

Обычно в качестве

22Производящая функция. Производящая функция (нумератор) и перечисляющая производящая функция для сочетаний с повторениями.

Производящая ф-я для :

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

1)Если эл-т типа i может входить в сочетания K₁ или K₂ или… K_iраз, то ему соотв множитель

2)F(t)=

3)Остается найти коэф. при

экспоненциальная производящая ф-я для размещений правило построения

1) Если a_i множитель входящий в размещения К1 или…или Кi раз, то ему соответствует множитель если надо найти число размещений , если надо найти сами размещения

2) E(t)=

3) Остается найти коэфпри

25) К комбинаторным числам также относятся числа Стирлинга первого и второго рода. Эти числа определяются как коэффициенты в равенствах

,

и имеют простой комбинаторный смысл — равно числу элементов группы подстановок являющихся произведениями ровно k непересекающихся циклов, а равно числу разбиений n-элементного множества на k непустых подмножеств. Очевидно, что . Аналогичная сумма чисел Стирлинга второго рода называется n-м числом Белла и равна числу всех разбиений n-элементного множества. Для чисел Белла справедлива рекуррентная формула .

При решении комбинаторных задач часто оказывается полезна формула включений—исключений

,

позволяющая находить мощность объединения множеств, если известны мощности их пересечений. Воспользуемся формулой включений—исключений для получения явной формулы для чисел Стирлинга второго рода.