Викиконспекты - Вклад участника [ru]

Обсуждение:Дискретная математика и алгоритмы

2017-10-08T08:06:41Z

94.25.229.49:

'''Я ЕЩЁ НЕ ДОДЕЛАЛ, ЭТО ЧЕРНОВИК!!!'''

В математике '''убывающим факториалом''' (англ. falling factorial) (иногда называется '''нисходящим факториалом''', '''постепенно убывающим факториалом''' или '''нижним факториалом''') обозначают:

:<tex>(x)_{n}=x^{\underline{n}}=x(x-1)(x-2)\cdots(x-n+1)=\prod_{k=1}^{n}(x-(k-1))=\prod_{k=0}^{n-1}(x-k)</tex>

'''Растущий факториал''' (rising factorial) (иногда называется '''функцией Похгаммера''', '''многочленом Похгаммера''', '''восходящим факториалом''', '''постепенно растущим произведением''' или '''верхним факториалом''') определяется следующей формулой:

:<tex>x^{(n)}=x^{\overline{n}}=x(x+1)(x+2)\cdots(x+n-1)=\prod_{k=1}^{n}(x+(k-1))=\prod_{k=0}^{n-1}(x+k). </tex>

При ''n=0'' значение принимается равным 1 (пустое произведение).

'''Символ Похгаммера''' введен Лео Августом Похгаммером в записи <tex>(x)^n</tex>, где <tex>n</tex> неотрицательное целое число. В зависимости от контекста символ Похгаммера может обозначать как растущий факториал, так и падающий факториал как определено выше. Поэтому при чтении любой статьи необходимо обратить внимание на то, какой именно из двух факториалов имеется в виду. Сам Похгаммер для себя использовал <tex>(x)^n</tex> в другом смысле - для обозначения биномиального коэффициента <tex>\tbinom xn</tex>.

В этой статье <tex>(x)_n</tex> означает убывающий факториал и <tex>(x)^n</tex> - растущий факториал. Такое же обозначение используется в комбинаторике.

Когда <tex>x</tex> неотрицательное целое число, <tex>(x)_n</tex> равняется числу инъективных отображений из множества с <tex>n</tex> элементами во множество из <tex>x</tex> элементов. Для обозначения этого числа часто применяют обозначения <tex>_x P_n</tex> и <tex>P(x,n)</tex>. Символ Похгаммера в основном используется в алгебре, где <tex>x</tex> - переменная, то есть <tex>(x)_n</tex> есть ни что иное как многочлен степени <tex>n</tex> от <tex>x</tex>.

==Примеры==
Несколько первых растущих факториалов:
:<tex>x^{(0)}=x^{\overline0}=1 </tex>
:<tex>x^{(1)}=x^{\overline1}=x </tex>
:<tex>x^{(2)}=x^{\overline2}=x(x+1)=x^2+x </tex>
:<tex>x^{(3)}=x^{\overline3}=x(x+1)(x+2)=x^3+3x^2+2x </tex>
:<tex>x^{(4)}=x^{\overline4}=x(x+1)(x+2)(x+3)=x^4+6x^3+11x^2+6x </tex>
Несколько первых убывающих факториалов:
:<tex>(x)_{0}=x^{\underline0}=1 </tex>
:<tex>(x)_{1}=x^{\underline1}=x </tex>
:<tex>(x)_{2}=x^{\underline2}=x(x-1)=x^2-x </tex>
:<tex>(x)_{3}=x^{\underline3}=x(x-1)(x-2)=x^3-3x^2+2x </tex>
:<tex>(x)_{4}=x^{\underline4}=x(x-1)(x-2)(x-3)=x^4-6x^3+11x^2-6x </tex>
Коэффициенты в выражениях являются числами Стирлинга первого рода.

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

:<tex>\frac{x^{(n)}}{n!} = {x+n-1 \choose n} \quad\mbox{and}\quad \frac{(x)_n}{n!} = {x \choose n}.</tex>

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

Растущий факториал может быть выражен как падающий факториал, начинающийся с другого конца,

:<tex>x^{(n)} = {(x + n - 1)}_n ,</tex>

или как убывающий с противоположным аргументом,

:<tex>x^{(n)} = {(-1)}^n {(-x)}_{{n}} .</tex>

Убывающий и растущий факториалы определены так же и в любом ассоциативном кольце с единицей и, следовательно, <tex>x</tex> может быть даже комплексным числом, многочленом с комплексными коэффициентами или любой функцией определенной на комплексных числах.

Растущий факториал может быть продолжен на вещественные значения <tex>n</tex>, но с использованием Гаммы функции при условии, что <tex>x</tex> и <tex>x+n</tex> вещественные числа, но не отрицательные целые:

:<tex>x^{(n)}=\frac{\Gamma(x+n)}{\Gamma(x)},</tex>

то же самое и про убывающий факториал:

:<tex>(x)_n=\frac{\Gamma(x+1)}{\Gamma(x-n+1)}.</tex>

Если <tex>D</tex> означает производную по <tex>x</tex>, то

:<tex>D^n(x^a) = (a)_n\,\, x^{a-n}.</tex>

== Связующие коэффициенты и тождества ==

The falling and rising factorials are related to one another through the [[Lah numbers]] and through sums for integral powers of a variable <math>x</math> involving the [[Stirling numbers of the second kind]] in the following forms where <math>\binom{r}{k} = r^{\underline{k}} / k!</math>:<ref>{{cite web|title=Introduction to the factorials and binomials|url=http://functions.wolfram.com/GammaBetaErf/Factorial/introductions/FactorialBinomials/05/|website=Wolfram Functions Site}}</ref>

:<tex>
\begin{align}
x^{\underline{n}} & = \sum_{k=1}^n \binom{n-1}{k-1} \frac{n!}{k!} \times (x)_k \\
& = (-1)^n (-x)_n = (x-n+1)_n = \frac{1}{(x+1)^{\overline{-n}}} \\
(x)_n & = \sum_{k=0}^{n} \binom{n}{k} (n-1)^{\underline{n-k}} \times x^{\underline{k}} \\
& = (-1)^n (-x)^{\underline{n}} = (x+n-1)^{\underline{n}} = \frac{1}{(x-1)^{\underline{-n}}} \\
& = \binom{-x}{n} (-1)^n n! \\
& = \binom{x+n-1}{n} n! \\
x^n & = \sum_{k=0}^{n} \left\{\begin{matrix} n \\ n-k \end{matrix} \right\} x^{\underline{n-k}} \\
& = \sum_{k=0}^{n} \left\{\begin{matrix} n \\ k \end{matrix} \right\}(-1)^{n-k} (x)_k.
\end{align}
</tex>

Since the falling factorials are a basis for the [[polynomial ring]], we can re-express the product of two of them as a linear combination of falling factorials:

:<tex>(x)_m (x)_n = \sum_{k=0}^m {m \choose k} {n \choose k} k!\, (x)_{m+n-k}.</tex>

The coefficients of the (''x'')''m''+''n''−''k'', called '''connection coefficients''', have a combinatorial interpretation as the number of ways to identify (or glue together) {{math|''k''}} elements each from a set of size {{math|''m''}} and a set of size {{math|''n''}}.
We also have a connection formula for the ratio of two Pochhammer symbols given by

:<tex>\frac{(x)_n}{(x)_i} = (x+i)_{n-i},\ n \geq i. </tex>

Additionally, we can expand generalized exponent laws and negative rising and falling powers through the following identities:

:<tex>x^{\underline{m+n}} & = x^{\underline{m}} (x-m)^{\underline{n}}</tex>
:<tex>(x)_{m+n} & = (x)_m (x+m)_n</tex>
:<tex>(x)_{-n} & = \frac{1}{(x-n)_n} = \frac{1}{(x-1)^{\underline{n}}}</tex>
:<tex>x^{\underline{-n}} & = \frac{1}{(x+1)_n} = \frac{1}{n! \binom{x+n}{n}} = \frac{1}{(x+1)(x+2) \cdots (x+n)}</tex>

Finally, [[duplication formula|duplication]] and [[multiplication formulas]] for the rising factorials provide the next relations:

:<tex>(x)_{k+mn} = (x)_k m^{mn} \prod_{j=0}^{m-1} \left(\frac{x+j+k}{m}\right)_n,\ m \in \mathbb{N} </tex>
:<tex>(ax+b)_n = x^n \prod_{k=0}^{x-1} \left(a+\frac{b+k}{x}\right)_{n/x},\ x \in \mathbb{Z}^{+} </tex>
:<tex>(2x)_{2n} = 2^{2n} (x)_n \left(x+\frac{1}{2}\right)_n. </tex>

==Альтернативные формы записи==

Альтернативная форма записи растущего факториала

:<tex>x^{\overline{m}}=\overbrace{x(x+1)\ldots(x+m-1)}^{m~\mathrm{factors}}\qquad\mbox{for integer }m\ge0,</tex>

и для убывающего факториала

:<tex>x^{\underline{m}}=\overbrace{x(x-1)\ldots(x-m+1)}^{m~\mathrm{factors}}\qquad\mbox{for integer }m\ge0;</tex>

goes back to A. Capelli (1893) and L. Toscano (1939), respectively.<ref>According to Knuth, The Art of Computer Programming, Vol. 1, 3rd ed., p. 50.</ref> Graham, Knuth and Patashnik<ref>[[Ronald L. Graham]], [[Donald E. Knuth]] and [[Oren Patashnik]] in their book ''[[Concrete Mathematics]]'' (1988), Addison-Wesley, Reading MA. {{ISBN|0-201-14236-8}}, pp. 47,48</ref> propose to pronounce these expressions as "<tex>x</tex> to the <tex>m</tex> rising" and "<tex>x</tex> to the <tex>m</tex> falling", respectively.

Другие формы записи убывающего факториала: <tex>P(x,n)</tex>, <tex>^x P_n</tex>, ,<tex>P_{x,n}</tex> или <tex>_x P_n</tex>.

Другое обозначение растущего факториала <tex>x^(n)</tex> реже встречается, чем <tex>(x)^+_n</tex>. Обозначение <tex>(x)^+_n</tex> используется для растущего факториала, запись <tex>(x)^-_n</tex> обычно применяется для обозначения убывающего факториала для избежания недоразумений.

==Обобщения==
The Pochhammer symbol has a generalized version called the [[generalized Pochhammer symbol]], used in multivariate [[Mathematical analysis|analysis]]. There is also a [[q-analog|''q''-analogue]], the [[q-Pochhammer symbol|''q''-Pochhammer symbol]].

A generalization of the falling factorial in which a function is evaluated on a descending arithmetic sequence of integers and the values are multiplied is:

:<math>[f(x)]^{k/-h}=f(x)\cdot f(x-h)\cdot f(x-2h)\cdots f(x-(k-1)h),</math>

where {{math|−''h''}} is the decrement and {{math|''k''}} is the number of factors. The corresponding generalization of the rising factorial is

:<math>[f(x)]^{k/h}=f(x)\cdot f(x+h)\cdot f(x+2h)\cdots f(x+(k-1)h).</math>

This notation unifies the rising and falling factorials, which are [''x'']''k''/1 and [''x'']''k''/−1, respectively.

For any fixed arithmetic function <math>f: \mathbb{N} \rightarrow \mathbb{C}</math> and symbolic parameters <math>x, t</math>, related generalized factorial products of the form

:<math>(x)_{n,f,t} := \prod_{k=1}^{n-1} \left(x+\frac{f(k)}{t^k}\right)</math>

may be studied from the point of view of the classes of generalized [[Stirling numbers of the first kind]] defined by the following coefficients of the powers of <math>x</math> in the expansions of <math>(x)_{n,f,t}</math> and then by the next corresponding triangular recurrence relation:

:<math>
\begin{align}
\left[\begin{matrix} n \\ k \end{matrix} \right]_{f,t} & = [x^{k-1}] (x)_{n,f,t} \\
& = f(n-1) t^{1-n} \left[\begin{matrix} n-1 \\ k \end{matrix} \right]_{f,t} + \left[\begin{matrix} n-1 \\ k-1 \end{matrix} \right]_{f,t} + \delta_{n,0} \delta_{k,0}.
\end{align}
</math>

These coefficients satisfy a number of analogous properties to those for the [[Stirling numbers of the first kind]] as well as recurrence relations and functional equations related to the ''f-harmonic numbers'', <math>F_n^{(r)}(t) := \sum_{k \leq n} t^k / f(k)^r</math>.<ref>''[https://arxiv.org/abs/1611.04708 Combinatorial Identities for Generalized Stirling Numbers Expanding f-Factorial Functions and the f-Harmonic Numbers]'' (2016).</ref>

==Источники материала==
* [http://mathworld.wolfram.com/PochhammerSymbol.html, Pochhammer Symbol]
* [https://www.scribd.com/doc/288367437/A-Compilation-of-Mathematical-Demonstrations, Elementary Proofs]

[[Категория:Дискретная математика и алгоритмы]]
[[Категория:Символ Похгаммера]]

Альтернатива Фредгольма — Шаудера

2013-05-31T14:04:04Z

94.25.229.49:

<tex>X = C[0;1]</tex>, <tex>K(u,v)</tex> непрерывен на <tex>[0;1]^2</tex>

<tex>A(x,t)=\int\limits_0^1 K(t,s) x(s) ds, x(s) \in C[0;1]</tex>

A — комплексный оператор (<tex>A \colon [0;1] \to [0;1]</tex>)

Интегральные уравнения Фредгольма: <tex>f(t) = x(t) + \lambda \int\limits_0^1 K(t,s) x(s) ds</tex> в <tex>C[0;1]</tex>.

X — B-пространство, <tex>A \colon B \to B</tex>, A — компактный. <tex>T = \lambda I - a</tex>

Задача: когда <tex>Tx=y</tex> разрешимо?

<tex>y = \lambda x - A x</tex> — операторные уравнения второго рода (явно выделен I). Уравнения первого рода (<tex>y=Bx</tex>) решаются гораздо сложней. Объясняется это достаточно просто: <tex>y = \lambda x - A x = \lambda (x - \frac 1 \lambda A)x, \frac 1 {|\lambda|} {\|A\|} < 1 </tex>, следовательно, по теореме Банаха, <tex>I - \frac 1 \lambda A</tex> непрерывно обратим, следовательно, при достаточно больших <tex>\lambda</tex>, <tex>y=\lambda x - A x</tex> разрешимо при любой левой части, причём решения x будут непрерывно зависеть от y. Интересна ситуация при <tex>|\lambda| < \|A\|</tex>. В случае комплексного A ответ даёт теория Шаудера.

Далее будем считать <tex>\lambda = 1</tex>. <tex>T = I - A,~Ker~T = \{x|x - Ax = 0\} = \{x|x=Ax\}</tex>, таким образом, ядро T — неподвижные точки A.
<tex>\overline V</tex> — единичный шар, <tex>Y = Ker~T</tex> — подпространство X. <tex>dim~Ker~T = + \infty,~\overline W = \overline V \cap Y \Rightarrow \overline W = A \overline W</tex>. Но так как A — компактный, <tex>\overline W</tex> — компакт в Y, но в бесконечномерном пространстве шар не может быть компактом, получаем противоречие. Значит, если A — компактный, то <tex>dim~Ker(I-A) < + \infty</tex>.

{{Теорема
|statement=Пусть <tex>T = I - A</tex>, A компактен <tex>\Rightarrow R(T) = Cl R(T)</tex>
|proof=Ранее (пятый семестр же?) мы доказали, что если уравнение <tex>Tx=y, y \in R(T)</tex> допускает априорную оценку (<tex>\exists \alpha~\exists x~Tx=y, \|x\|<=a\|y\|</tex>), то R(T) замкнуто. Нужно доказать, что у T есть априорная оценка.

<tex>y \in R(T), Tx=y, \forall z \in Ker~T \Rightarrow T(x+z) = y</tex>. Значит, все решения уравнения <tex>Tx=y</tex> записываются в форме <tex>x=x_0+z</tex>, где <tex>x_0</tex> — одно из решений, z принадлежит <tex>Ker~T</tex>. Но <tex>dim~Ker~T < + \infty \Rightarrow Ker~T = L \{ e_1, \ldots e_n \} \Rightarrow x = x_0 + \sum\limits_{k=1}^n \alpha_k e_k, \alpha_k \in \mathbb{R}</tex>

<tex>f(\alpha_1,\ldots,\alpha_n) = \|x_0 + \sum\limits_{k=1}^n \alpha_k e_k</tex> *Из конспекта немного непонятно, почему {{TODO| t=доказать}}* Эта функция непрерывна <tex>\Rightarrow \exists \alpha^*_1, \alpha^*_2, \ldots, \alpha^*_n : f (\overline {\alpha}^*) = \inf\limits_{\alpha} f(\alpha)</tex>

<tex>y \in R(T)</tex>, среди всех решений уравнения <tex>Tx=y</tex> существует решение с минимальной нормой. Его назовём <tex>\widehat x</tex>, и далее докажем, что эти решения допускают априорную оценку через y.
}}

Альтернатива Фредгольма — Шаудера

2013-05-31T13:24:25Z

94.25.229.49: Новая страница: «<tex>X = C[0;1]</tex>, <tex>K(u,v)</tex> непрерывен на <tex>[0;1]^2</tex> <tex>A(x,t)=\int\limits_0^1 K(t,s) x(s) ds, x(s) \in C[0;1]</tex> A — к...»