A Lean 4 formalization of An Introduction to Algebraic Combinatorics by Darij Grinberg, built on Mathlib. Early chapters establish prerequisites (power series, generating functions, permutations); later chapters formalize important results including the Lindström–Gessel–Viennot lemma, q-binomial identities, and symmetric function theory.
This page shows all 344 formalization targets for quick side-by-side comparison of mathematical statements and their Lean proofs. For full details, see the Blueprint or the source on GitHub.
@misc{{gloecke2025textbook,
title = {{Automatic Textbook Formalization}},
author = {{Fabian Gloecke and Ahmad Rammal and Charles Arnal and
Remi Munos and Vivien Cabannes and Gabriel Synnaeve and
Amaury Hayat}},
year = {{2025}},
howpublished = {{\url{{https://github.com/facebookresearch/repoprover}}}},
}}
For any numbers \(n\) and \(k\), we set
Note that “numbers” is to be understood fairly liberally here. In particular, \(n\) can be any integer, rational, real or complex number (or, more generally, any element in a \(\mathbb {Q}\)-algebra), whereas \(k\) can be anything (although the only nonzero values of \(\binom {n}{k}\) will be achieved for \(k\in \mathbb {N}\), by the above definition).
We have
for any numbers \(m\) and \(n\).
A commutative ring means a set \(K\) equipped with three maps
and two elements \(\mathbf{0}\in K\) and \(\mathbf{1}\in K\) satisfying the following axioms:
Commutativity of addition: We have \(a\oplus b=b\oplus a\) for all \(a,b\in K\).
Associativity of addition: We have \(a\oplus \left( b\oplus c\right) =\left( a\oplus b\right) \oplus c\) for all \(a,b,c\in K\).
Neutrality of zero: We have \(a\oplus \mathbf{0}=\mathbf{0}\oplus a=a\) for all \(a\in K\).
Subtraction undoes addition: Let \(a,b,c\in K\). We have \(a\oplus b=c\) if and only if \(a=c\ominus b\).
Commutativity of multiplication: We have \(a\odot b=b\odot a\) for all \(a,b\in K\).
Associativity of multiplication: We have \(a\odot \left( b\odot c\right) =\left( a\odot b\right) \odot c\) for all \(a,b,c\in K\).
Distributivity: We have
for all \(a,b,c\in K\).
Neutrality of one: We have \(a\odot \mathbf{1}=\mathbf{1}\odot a=a\) for all \(a\in K\).
Annihilation: We have \(a\odot \mathbf{0}=\mathbf{0}\odot a=\mathbf{0}\) for all \(a\in K\).
The operations \(\oplus \), \(\ominus \) and \(\odot \) are called the addition, the subtraction and the multiplication of the ring \(K\). When confusion is unlikely, we will denote these three operations \(\oplus \), \(\ominus \) and \(\odot \) by \(+\), \(-\) and \(\cdot \), respectively, and we will abbreviate \(a\odot b=a\cdot b\) by \(ab\).
The elements \(\mathbf{0}\) and \(\mathbf{1}\) are called the zero and the unity (or the one) of the ring \(K\). We will simply call these elements \(0\) and \(1\) when confusion with the corresponding numbers is unlikely.
We will use PEMDAS conventions for the three operations \(\oplus \), \(\ominus \) and \(\odot \). These imply that the operation \(\odot \) has higher precedence than \(\oplus \) and \(\ominus \), while the operations \(\oplus \) and \(\ominus \) are left-associative.
Let \(K\) be a commutative ring.
A \(K\)-module means a set \(M\) equipped with three maps
(notice that the third map has domain \(K\times M\), not \(M\times M\)) and an element \(\overrightarrow {0}\in M\) satisfying the following axioms:
Commutativity of addition: We have \(a\oplus b=b\oplus a\) for all \(a,b\in M\).
Associativity of addition: We have \(a\oplus \left( b\oplus c\right) =\left( a\oplus b\right) \oplus c\) for all \(a,b,c\in M\).
Neutrality of zero: We have \(a\oplus \overrightarrow {0}=\overrightarrow {0}\oplus a=a\) for all \(a\in M\).
Subtraction undoes addition: Let \(a,b,c\in M\). We have \(a\oplus b=c\) if and only if \(a=c\ominus b\).
Associativity of scaling: We have \(u\rightharpoonup \left( v\rightharpoonup a\right) =\left( uv\right) \rightharpoonup a\) for all \(u,v\in K\) and \(a\in M\).
Left distributivity: We have \(u\rightharpoonup \left( a\oplus b\right) =\left( u\rightharpoonup a\right) \oplus \left( u\rightharpoonup b\right) \) for all \(u\in K\) and \(a,b\in M\).
Right distributivity: We have \(\left( u+v\right) \rightharpoonup a=\left( u\rightharpoonup a\right) \oplus \left( v\rightharpoonup a\right) \) for all \(u,v\in K\) and \(a\in M\).
Neutrality of one: We have \(1\rightharpoonup a=a\) for all \(a\in M\).
Left annihilation: We have \(0\rightharpoonup a=\overrightarrow {0}\) for all \(a\in M\).
Right annihilation: We have \(u\rightharpoonup \overrightarrow {0}=\overrightarrow {0}\) for all \(u\in K\).
The operations \(\oplus \), \(\ominus \) and \(\rightharpoonup \) are called the addition, the subtraction and the scaling (or the \(K\)-action) of the \(K\)-module \(M\). When confusion is unlikely, we will denote these three operations \(\oplus \), \(\ominus \) and \(\rightharpoonup \) by \(+\), \(-\) and \(\cdot \), respectively, and we will abbreviate \(a\rightharpoonup b=a\cdot b\) by \(ab\).
The element \(\overrightarrow {0}\) is called the zero (or the zero vector) of the \(K\)-module \(M\). We will usually just call it \(0\).
When \(M\) is a \(K\)-module, the elements of \(M\) are called vectors, while the elements of \(K\) are called scalars.
We will use PEMDAS conventions for the three operations \(\oplus \), \(\ominus \) and \(\rightharpoonup \), with the operation \(\rightharpoonup \) having higher precedence than \(\oplus \) and \(\ominus \).
A formal power series (or, short, FPS) in \(1\) indeterminate over \(K\) means a sequence \(\left(a_{0},a_{1},a_{2},\ldots \right) = \left(a_{n}\right)_{n\in \mathbb {N}} \in K^{\mathbb {N}}\) of elements of \(K\).
(a) The sum of two FPSs \(\mathbf{a}=\left( a_{0},a_{1},a_{2},\ldots \right)\) and \(\mathbf{b}=\left(b_{0},b_{1},b_{2},\ldots \right)\) is defined to be the FPS
It is denoted by \(\mathbf{a}+\mathbf{b}\).
(b) The difference of two FPSs \(\mathbf{a}=\left(a_{0},a_{1},a_{2},\ldots \right)\) and \(\mathbf{b}=\left(b_{0},b_{1},b_{2},\ldots \right)\) is defined to be the FPS
It is denoted by \(\mathbf{a}-\mathbf{b}\).
(c) If \(\lambda \in K\) and if \(\mathbf{a}=\left(a_{0},a_{1},a_{2},\ldots \right)\) is an FPS, then we define an FPS
(d) The product of two FPSs \(\mathbf{a}=\left(a_{0},a_{1},a_{2},\ldots \right)\) and \(\mathbf{b}=\left(b_{0},b_{1},b_{2},\ldots \right)\) is defined to be the FPS \(\left(c_{0},c_{1},c_{2},\ldots \right)\), where
This product is denoted by \(\mathbf{a}\cdot \mathbf{b}\) or just by \(\mathbf{ab}\).
(e) For each \(a\in K\), we define \(\underline{a}\) to be the FPS \(\left(a,0,0,0,\ldots \right)\). An FPS of the form \(\underline{a}\) for some \(a\in K\) (that is, an FPS \(\left(a_{0},a_{1},a_{2},\ldots \right)\) satisfying \(a_{1}=a_{2}=a_{3}=\cdots =0\)) is said to be constant.
(f) The set of all FPSs (in \(1\) indeterminate over \(K\)) is denoted \(K\left[\left[x\right]\right]\).
(a) The set \(K\left[\left[x\right]\right]\) is a commutative ring (with its operations \(+\), \(-\) and \(\cdot \) defined in Definition 1.74). Its zero and its unity are the FPSs \(\underline{0}=\left(0,0,0,\ldots \right)\) and \(\underline{1}=\left( 1,0,0,0,\ldots \right)\). This means, concretely, that the following facts hold:
Commutativity of addition: We have \(\mathbf{a}+\mathbf{b}=\mathbf{b}+\mathbf{a}\) for all \(\mathbf{a},\mathbf{b}\in K\left[\left[ x\right]\right]\).
Associativity of addition: We have \(\mathbf{a}+\left( \mathbf{b}+\mathbf{c}\right) =\left(\mathbf{a}+\mathbf{b}\right) +\mathbf{c}\) for all \(\mathbf{a},\mathbf{b},\mathbf{c}\in K\left[\left[ x\right]\right]\).
Neutrality of zero: We have \(\mathbf{a}+\underline{0}=\underline{0}+\mathbf{a}=\mathbf{a}\) for all \(\mathbf{a}\in K\left[\left[ x\right]\right]\).
Subtraction undoes addition: Let \(\mathbf{a},\mathbf{b},\mathbf{c}\in K\left[\left[x\right]\right]\). We have \(\mathbf{a}+\mathbf{b}=\mathbf{c}\) if and only if \(\mathbf{a}=\mathbf{c}-\mathbf{b}\).
Commutativity of multiplication: We have \(\mathbf{ab}=\mathbf{ba}\) for all \(\mathbf{a},\mathbf{b}\in K\left[\left[x\right] \right]\).
Associativity of multiplication: We have \(\mathbf{a}\left( \mathbf{bc}\right) =\left(\mathbf{ab}\right)\mathbf{c}\) for all \(\mathbf{a},\mathbf{b},\mathbf{c}\in K\left[\left[x\right]\right]\).
Distributivity: We have
for all \(\mathbf{a},\mathbf{b},\mathbf{c}\in K\left[\left[x\right] \right]\).
Neutrality of one: We have \(\mathbf{a}\cdot \underline{1}=\underline{1}\cdot \mathbf{a}=\mathbf{a}\) for all \(\mathbf{a}\in K\left[ \left[x\right]\right]\).
Annihilation: We have \(\mathbf{a}\cdot \underline{0}=\underline{0}\cdot \mathbf{a}=\underline{0}\) for all \(\mathbf{a}\in K\left[ \left[x\right]\right]\).
(b) Furthermore, \(K\left[\left[x\right]\right]\) is a \(K\)-module (with its scaling being the map that sends each \(\left( \lambda ,\mathbf{a}\right) \in K\times K\left[\left[x\right]\right]\) to the FPS \(\lambda \mathbf{a}\) defined in Definition 1.74 (c)). Its zero vector is \(\underline{0}\). Concretely, this means that:
Associativity of scaling: We have \(\lambda \left( \mu \mathbf{a}\right) =\left( \lambda \mu \right) \mathbf{a}\) for all \(\lambda ,\mu \in K\) and \(\mathbf{a}\in K\left[\left[x\right]\right]\).
Left distributivity: We have \(\lambda \left( \mathbf{a}+\mathbf{b}\right) =\lambda \mathbf{a}+\lambda \mathbf{b}\) for all \(\lambda \in K\) and \(\mathbf{a},\mathbf{b}\in K\left[\left[x\right]\right]\).
Right distributivity: We have \(\left( \lambda +\mu \right) \mathbf{a}=\lambda \mathbf{a}+\mu \mathbf{a}\) for all \(\lambda ,\mu \in K\) and \(\mathbf{a}\in K\left[\left[x\right]\right]\).
Neutrality of one: We have \(1\mathbf{a}=\mathbf{a}\) for all \(\mathbf{a}\in K\left[\left[x\right]\right]\).
Left annihilation: We have \(0\mathbf{a}=\underline{0}\) for all \(\mathbf{a}\in K\left[\left[x\right]\right]\).
Right annihilation: We have \(\lambda \underline{0}=\underline{0}\) for all \(\lambda \in K\).
(c) We have \(\lambda \left(\mathbf{a}\cdot \mathbf{b}\right) =\left(\lambda \mathbf{a}\right)\cdot \mathbf{b}=\mathbf{a}\cdot \left( \lambda \mathbf{b}\right)\) for all \(\lambda \in K\) and \(\mathbf{a},\mathbf{b}\in K\left[\left[x\right]\right]\).
(d) Finally, we have \(\lambda \mathbf{a}=\underline{\lambda }\cdot \mathbf{a}\) for all \(\lambda \in K\) and \(\mathbf{a}\in K\left[\left[ x\right]\right]\).
If \(n\in \mathbb {N}\), and if \(\mathbf{a}=\left( a_{0},a_{1},a_{2},\ldots \right) \in K\left[\left[x\right]\right]\) is an FPS, then we define an element \(\left[x^{n}\right]\mathbf{a}\in K\) by
This is called the coefficient of \(x^{n}\) in \(\mathbf{a}\), or the \(n\)-th coefficient of \(\mathbf{a}\), or the \(x^{n}\)-coefficient of \(\mathbf{a}\).
(a) A family \(\left(a_{i}\right)_{i\in I}\in K^{I}\) of elements of \(K\) is said to be essentially finite if all but finitely many \(i\in I\) satisfy \(a_{i}=0\) (in other words, if the set \(\left\{ i\in I\ \mid \ a_{i}\neq 0\right\} \) is finite).
(b) Let \(\left(a_{i}\right)_{i\in I}\in K^{I}\) be an essentially finite family of elements of \(K\). Then, the infinite sum \(\sum _{i\in I}a_{i}\) is defined to equal the finite sum \(\sum _{\substack {i\in I;\\ a_{i}\neq 0}}a_{i}\). Such an infinite sum is said to be essentially finite.
A (possibly infinite) family \(\left(\mathbf{a}_{i}\right)_{i\in I}\) of FPSs is said to be summable (or entrywise essentially finite) if
In this case, the sum \(\sum _{i\in I}\mathbf{a}_{i}\) is defined to be the FPS with
Let \(\left(\mathbf{a}_{i}\right)_{i\in I}\) be a summable family of FPSs. Then, any subfamily of \(\left(\mathbf{a}_{i}\right)_{i\in I}\) is summable as well.
Sums of summable families of FPSs satisfy the usual rules for sums (such as the breaking-apart rule \(\sum _{i\in S}a_{s}=\sum _{i\in X}a_{s}+\sum _{i\in Y}a_{s}\) when a set \(S\) is the union of two disjoint sets \(X\) and \(Y\)). See [ 19s , Proposition 7.2.11 ] for details. Again, the only caveat is about interchange of summation signs: The equality
holds when the family \(\left(\mathbf{a}_{i,j}\right)_{\left(i,j\right) \in I\times J}\) is summable (i.e., when for each \(n\in \mathbb {N}\), all but finitely many pairs \(\left(i,j\right) \in I\times J\) satisfy \(\left[x^{n}\right]\mathbf{a}_{i,j}=0\)); it does not generally hold if we merely assume that the sums \(\sum _{i\in I}\ \ \sum _{j\in J}\mathbf{a}_{i,j}\) and \(\sum _{j\in J}\ \ \sum _{i\in I}\mathbf{a}_{i,j}\) are summable.
Let \(x\) denote the FPS \(\left(0,1,0,0,0,\ldots \right)\). In other words, let \(x\) denote the FPS with \(\left[x^{1}\right]x=1\) and \(\left[x^{i}\right]x=0\) for all \(i\neq 1\).
Let \(\mathbf{a}=\left(a_{0},a_{1},a_{2},\ldots \right)\) be an FPS. Then, \(x\cdot \mathbf{a}=\left(0,a_{0},a_{1},a_{2},\ldots \right)\).
We have
Any FPS \(\left(a_{0},a_{1},a_{2},\ldots \right) \in K\left[\left[x\right]\right]\) satisfies
In particular, the right hand side here is well-defined, i.e., the family \(\left(a_{n}x^{n}\right)_{n\in \mathbb {N}}\) is summable.
Let \(a,b\in \mathbb {N}\), and let \(n\in \mathbb {N}\). Then,
Let \(a,b\in \mathbb {C}\), and let \(n\in \mathbb {N}\). Then,
Let \(L\) be a commutative ring. Let \(a\in L\). Then:
(a) An inverse (or multiplicative inverse) of \(a\) means an element \(b\in L\) such that \(ab=ba=1\).
(b) We say that \(a\) is invertible in \(L\) (or a unit of \(L\)) if \(a\) has an inverse.
Let \(L\) be a commutative ring. Let \(a\in L\). Assume that \(a\) is invertible. Then:
(a) The inverse of \(a\) is called \(a^{-1}\).
(b) For any \(b\in L\), the product \(b\cdot a^{-1}\) is called \(\frac{b}{a}\) (or \(b/a\)).
(c) For any negative integer \(n\), we define \(a^{n}\) to be \(\left( a^{-1}\right)^{-n}\). Thus, the \(n\)-th power \(a^{n}\) is defined for each \(n\in \mathbb {Z}\).
Let \(L\) be a commutative ring. Then:
(a) Any invertible element \(a\in L\) satisfies \(a^{-1}=1/a\).
(b) For any invertible elements \(a,b\in L\), the element \(ab\) is invertible as well, and satisfies \(\left(ab\right)^{-1}=b^{-1}a^{-1}=a^{-1}b^{-1}\).
(c) If \(a\in L\) is invertible, and if \(n\in \mathbb {Z}\) is arbitrary, then \(a^{-n}=\left(a^{-1}\right)^{n}=\left(a^{n}\right)^{-1}\).
(d) Laws of exponents hold for negative exponents as well: If \(a\) and \(b\) are invertible elements of \(L\), then
(e) Laws of fractions hold: If \(a\) and \(c\) are two invertible elements of \(L\), and if \(b\) and \(d\) are any two elements of \(L\), then
(f) Division undoes multiplication: If \(a,b,c\) are three elements of \(L\) with \(a\) being invertible, then the equality \(\frac{c}{a}=b\) is equivalent to \(c=ab\).
Let \(a\in K[[x]]\). Then, the FPS \(a\) is invertible in \(K[[x]]\) if and only if its constant term \([x^{0}]a\) is invertible in \(K\).
Assume that \(K\) is a field. Let \(a\in K[[x]]\). Then, the FPS \(a\) is invertible in \(K[[x]]\) if and only if \([x^{0}]a\neq 0\).
The FPS \(1+x\in K[[x]]\) is invertible, and its inverse is
For each \(n\in \mathbb {Z}\), we have
Let \(n\in \mathbb {C}\) and \(k\in \mathbb {Z}\). Then,
For each \(n\in \mathbb {N}\), we have
For each \(n\in \mathbb {N}\), we have
Let \(a=\left(a_{0},a_{1},a_{2},\ldots \right)\) be an FPS whose constant term \(a_{0}\) is \(0\). Then, \(\frac{a}{x}\) is defined to be the FPS \(\left(a_{1},a_{2},a_{3},\ldots \right)\).
Let \(a,b\in K[[x]]\) be two FPSs. Then, \(a=xb\) if and only if \(\left[x^{0}\right]a=0\) and \(b=\frac{a}{x}\).
Let \(a\in K[[x]]\) be an FPS with \(\left[x^{0}\right]a=0\). Then, there exists an \(h\in K[[x]]\) such that \(a=xh\).
Let \(k\in \mathbb {N}\). Let \(a\in K[[x]]\) be any FPS. Then, the first \(k\) coefficients of the FPS \(x^{k}a\) are \(0\).
Let \(k\in \mathbb {N}\). Let \(f\in K[[x]]\) be any FPS. Then, the first \(k\) coefficients of \(f\) are \(0\) if and only if \(f\) is a multiple of \(x^{k}\).
Let \(a,f,g\in K[[x]]\) be three FPSs. Let \(n\in \mathbb {N}\). Assume that \([x^{m}]f=[x^{m}]g\) for each \(m\in \{ 0,1,\ldots ,n\} \). Then, \([x^{m}](af)=[x^{m}](ag)\) for each \(m\in \{ 0,1,\ldots ,n\} \).
Let \(u,v\in K[[x]]\) be two FPSs such that \(v\) is a multiple of \(u\). Let \(n\in \mathbb {N}\). Assume \([x^{m}]u=0\) for each \(m\in \{ 0,1,\ldots ,n\} \). Then \([x^{m}]v=0\) for each \(m\in \{ 0,1,\ldots ,n\} \).
If \(a\overset {x^n}{\equiv } b\) and \(c\overset {x^n}{\equiv } d\), then \(ac\overset {x^n}{\equiv } bd\). In other words, \(x^n\)-equivalence is preserved under multiplication.
(a) An FPS \(a\in K\left[ \left[ x\right] \right] \) is said to be a polynomial if all but finitely many \(n\in \mathbb {N}\) satisfy \(\left[ x^{n}\right] a=0\) (that is, if all but finitely many coefficients of \(a\) are \(0\)).
(b) We let \(K\left[ x\right] \) be the set of all polynomials \(a\in K\left[ \left[ x\right] \right] \). This set \(K\left[ x\right] \) is a subring of \(K\left[ \left[ x\right] \right] \) (according to Theorem 1.148 below), and is called the univariate polynomial ring over \(K\).
The set \(K\left[ x\right] \) is a subring of \(K\left[ \left[ x\right] \right] \) (that is, it is closed under addition, subtraction and multiplication, and contains the zero \(\underline{0}\) and the unity \(\underline{1}\)) and is a \(K\)-submodule of \(K\left[ \left[ x\right] \right] \) (that is, it is closed under addition and scaling by elements of \(K\)).
A \(K\)-algebra is a set \(A\) equipped with four maps
and two elements \(\overrightarrow {0}\in A\) and \(\overrightarrow {1}\in A\) satisfying the following properties:
The set \(A\), equipped with the maps \(\oplus \), \(\ominus \) and \(\odot \) and the two elements \(\overrightarrow {0}\) and \(\overrightarrow {1}\), is a (noncommutative) ring.
The set \(A\), equipped with the maps \(\oplus \), \(\ominus \) and \(\rightharpoonup \) and the element \(\overrightarrow {0}\), is a \(K\)-module.
We have
for all \(\lambda \in K\) and \(a,b\in A\).
(Thus, in a nutshell, a \(K\)-algebra is a set \(A\) that is simultaneously a ring and a \(K\)-module, with the property that the ring \(A\) and the \(K\)-module \(A\) have the same addition, the same subtraction and the same zero, and satisfy the additional compatibility property (14).)
Let \(f\in K\left[ x\right] \) be a polynomial. Let \(A\) be any \(K\)-algebra. Let \(a\in A\) be any element. We then define an element \(f\left[ a\right] \in A\) as follows:
Write \(f\) in the form \(f=\sum _{n\in \mathbb {N}}f_{n}x^{n}\) with \(f_{0},f_{1},f_{2},\ldots \in K\). (That is, \(f_{n}=\left[ x^{n}\right] f\) for each \(n\in \mathbb {N}\).) Then, set
(This sum is essentially finite, since \(f\) is a polynomial.)
The element \(f\left[ a\right] \) is also denoted by \(f\circ a\) or by \(f\left( a\right) \), and is called the value of \(f\) at \(a\) (or the evaluation of \(f\) at \(a\), or the result of substituting \(a\) for \(x\) in \(f\)).
Let \(A\) be a \(K\)-algebra. Let \(a\in A\). Then:
(a) Any \(f,g\in K\left[ x\right] \) satisfy
(b) Any \(\lambda \in K\) and \(f\in K\left[ x\right] \) satisfy
(c) Any \(\lambda \in K\) satisfies \(\underline{\lambda }\left[ a\right] =\lambda \cdot 1_{A}\), where \(1_{A}\) is the unity of the ring \(A\).
(d) We have \(x\left[ a\right] =a\).
(e) We have \(x^{i}\left[ a\right] =a^{i}\) for each \(i\in \mathbb {N}\).
(f) Any \(f,g\in K\left[ x\right] \) satisfy \(f\left[ g\left[ a\right] \right] =\left( f\left[ g\right] \right) \left[ a\right] \).
Let \(f\) and \(g\) be two FPSs in \(K[[x]]\). Assume that \([x^0]g = 0\) (that is, \(g = g_1 x + g_2 x^2 + g_3 x^3 + \cdots \) for some \(g_1, g_2, g_3, \ldots \in K\)).
We then define an FPS \(f[g] \in K[[x]]\) as follows:
Write \(f\) in the form \(f = \sum _{n \in \mathbb {N}} f_n x^n\) with \(f_0, f_1, f_2, \ldots \in K\). (That is, \(f_n = [x^n]f\) for each \(n \in \mathbb {N}\).) Then, set
(This sum is well-defined, as we will see in Proposition 1.163 (b) below.)
This FPS \(f[g]\) is also denoted by \(f \circ g\), and is called the composition of \(f\) with \(g\), or the result of substituting \(g\) for \(x\) in \(f\).
Equivalently, the \(n\)-th coefficient of \(f[g]\) is the finite sum
Let \(f\) and \(g\) be two FPSs in \(K[[x]]\). Assume that \([x^0]g = 0\). Write \(f\) in the form \(f = \sum _{n \in \mathbb {N}} f_n x^n\) with \(f_0, f_1, f_2, \ldots \in K\). Then:
(a) For each \(n \in \mathbb {N}\), the first \(n\) coefficients of the FPS \(g^n\) are \(0\).
(b) The sum \(\sum _{n \in \mathbb {N}} f_n g^n\) is well-defined, i.e., the family \((f_n g^n)_{n \in \mathbb {N}}\) is summable.
(c) We have \([x^0](\sum _{n \in \mathbb {N}} f_n g^n) = f_0\).
Composition of FPSs satisfies the rules you would expect it to satisfy:
(a) If \(f_1, f_2, g \in K[[x]]\) satisfy \([x^0]g = 0\), then \((f_1 + f_2) \circ g = f_1 \circ g + f_2 \circ g\).
(b) If \(f_1, f_2, g \in K[[x]]\) satisfy \([x^0]g = 0\), then \((f_1 \cdot f_2) \circ g = (f_1 \circ g) \cdot (f_2 \circ g)\).
(c) If \(f_1, f_2, g \in K[[x]]\) satisfy \([x^0]g = 0\), then \(\frac{f_1}{f_2} \circ g = \frac{f_1 \circ g}{f_2 \circ g}\), as long as \(f_2\) is invertible. (In particular, \(f_2 \circ g\) is automatically invertible under these assumptions.)
(d) If \(f, g \in K[[x]]\) satisfy \([x^0]g = 0\), then \(f^k \circ g = (f \circ g)^k\) for each \(k \in \mathbb {N}\).
(e) If \(f, g, h \in K[[x]]\) satisfy \([x^0]g = 0\) and \([x^0]h = 0\), then \([x^0](g \circ h) = 0\) and \((f \circ g) \circ h = f \circ (g \circ h)\).
(f) We have \(\underline{a} \circ g = \underline{a}\) for each \(a \in K\) and \(g \in K[[x]]\).
(g) We have \(x \circ g = g \circ x = g\) for each \(g \in K[[x]]\).
(h) If \((f_i)_{i \in I} \in K[[x]]^I\) is a summable family of FPSs, and if \(g \in K[[x]]\) is an FPS satisfying \([x^0]g = 0\), then the family \((f_i \circ g)_{i \in I} \in K[[x]]^I\) is summable as well and we have \((\sum _{i \in I} f_i) \circ g = \sum _{i \in I} f_i \circ g\).
Let \(f, g \in K[[x]]\) satisfy \([x^0]g = 0\). Let \(k \in \mathbb {N}\) be such that the first \(k\) coefficients of \(f\) are \(0\). Then, the first \(k\) coefficients of \(f \circ g\) are \(0\).
If \(i\) and \(j\) are any objects, then \(\delta _{i,j}\) means the element
of \(K\).
Let \(f\in K\left[ \left[ x\right] \right] \) be an FPS. Then, the derivative \(f^{\prime }\) of \(f\) is an FPS defined as follows: Write \(f\) as \(f=\sum _{n\in \mathbb {N}}f_{n}x^{n}\) (with \(f_{0},f_{1},f_{2},\ldots \in K\)), and set
(a) We have \(\left( f+g\right) ^{\prime }=f^{\prime }+g^{\prime }\) for any \(f,g\in K\left[ \left[ x\right] \right] \).
(b) If \(\left( f_{i}\right) _{i\in I}\) is a summable family of FPSs, then the family \(\left( f_{i}^{\prime }\right) _{i\in I}\) is summable as well, and we have
(c) We have \(\left( cf\right) ^{\prime }=cf^{\prime }\) for any \(c\in K\) and \(f\in K\left[ \left[ x\right] \right] \).
(d) We have \(\left( fg\right) ^{\prime }=f^{\prime }g+fg^{\prime }\) for any \(f,g\in K\left[ \left[ x\right] \right] \). (This is known as the Leibniz rule.)
(e) If \(f,g\in K\left[ \left[ x\right] \right] \) are two FPSs such that \(g\) is invertible, then
(This is known as the quotient rule.)
(f) If \(g\in K\left[ \left[ x\right] \right] \) is an FPS, then \(\left( g^{n}\right) ^{\prime }=ng^{\prime }g^{n-1}\) for any \(n\in \mathbb {N}\) (where the expression \(ng^{\prime }g^{n-1}\) is to be understood as \(0\) if \(n=0\)).
(g) Given two FPSs \(f,g\in K\left[ \left[ x\right] \right] \), we have
if \(f\) is a polynomial or if \(\left[ x^{0}\right] g=0\). (This is known as the chain rule.)
(h) If \(K\) is a \(\mathbb {Q}\)-algebra, and if two FPSs \(f,g\in K\left[ \left[ x\right] \right] \) satisfy \(f^{\prime }=g^{\prime }\), then \(f-g\) is constant.
Define three FPS \(\exp \), \(\overline{\log }\) and \(\overline{\exp }\) in \(K\left[\left[x\right]\right]\) by
(The last equality sign here follows from \(\exp =\sum _{n\in \mathbb {N}}\frac{1}{n!}x^{n}=\underbrace{\frac{1}{0!}}_{=1}\underbrace{x^{0}}_{=1} +\sum _{n\geq 1}\frac{1}{n!}x^{n}=1+\sum _{n\geq 1}\frac{1}{n!}x^{n}\).)
Let \(g\in K\left[\left[x\right]\right]\) with \(\left[x^{0}\right]g=0\). Then:
(a) We have
(b) We have
Let \(f,g\in K\left[\left[x\right] \right]\) be two FPSs with \(\left[x^{0}\right]g=0\). Then, \(\left[ x^{0}\right]\left(f\circ g\right)=\left[x^{0}\right]f\).
We have
(a) We let \(K\left[\left[x\right] \right]_{0}\) denote the set of all FPSs \(f\in K\left[\left[x\right] \right]\) with \(\left[x^{0}\right]f=0\).
(b) We let \(K\left[\left[x\right]\right]_{1}\) denote the set of all FPSs \(f\in K\left[\left[x\right]\right]\) with \(\left[ x^{0}\right]f=1\).
(c) We define two maps
and
(These two maps are well-defined according to parts (c) and (d) of Lemma 1.223 below.)
(a) For any \(f,g\in K\left[\left[ x\right]\right]_{0}\), we have \(f\circ g\in K\left[\left[x\right] \right]_{0}\).
(b) For any \(f\in K\left[\left[x\right]\right]_{1}\) and \(g\in K\left[\left[x\right]\right]_{0}\), we have \(f\circ g\in K\left[ \left[x\right]\right]_{1}\).
(c) For any \(g\in K\left[\left[x\right]\right]_{0}\), we have \(\exp \circ g\in K\left[\left[x\right]\right]_{1}\).
(d) For any \(f\in K\left[\left[x\right]\right]_{1}\), we have \(f-1\in K\left[\left[x\right]\right]_{0}\) and \(\overline{\log } \circ \left(f-1\right)\in K\left[\left[x\right]\right]_{0}\).
(a) For any \(f,g\in K\left[\left[ x\right]\right]_{0}\), we have
(b) For any \(f,g\in K\left[\left[x\right]\right]_{1}\), we have
(a) The subset \(K\left[\left[ x\right]\right]_{0}\) of \(K\left[\left[x\right]\right]\) is closed under addition and subtraction and contains \(0\), and thus forms a group \(\left(K\left[\left[x\right]\right]_{0},+,0\right)\).
(b) The subset \(K\left[\left[x\right]\right]_{1}\) of \(K\left[\left[x\right]\right]\) is closed under multiplication and division and contains \(1\), and thus forms a group \(\left(K\left[\left[ x\right]\right]_{1},\cdot ,1\right)\).
The maps
and
are mutually inverse group isomorphisms.
In this definition, we do not use Convention 1.210; thus, \(K\) can be an arbitrary commutative ring. However, we set \(K\left[\left[x\right]\right]_{1}=\left\{ f\in K\left[\left[x\right]\right]\ \mid \ \left[x^{0}\right]f=1\right\} \).
For any FPS \(f\in K\left[\left[x\right]\right]_{1}\), we define the logarithmic derivative \(\operatorname {loder}f\in K\left[\left[ x\right]\right]\) to be the FPS \(\frac{f^{\prime }}{f}\). (This is well-defined, since \(f\) is easily seen to be invertible.)
Let \(K\) be a commutative \(\mathbb {Q}\)-algebra. Let \(f\in K\left[\left[x\right]\right]_{1}\) be an FPS. Then, \(\operatorname {loder}f=\left(\operatorname {Log}f\right)^{\prime }\).
Let \(f,g\in K\left[\left[x\right]\right] _{1}\) be two FPSs. Then, \(\operatorname {loder}\left(fg\right) =\operatorname {loder}f+\operatorname {loder}g\).
(Here, we do not use Convention 1.210; thus, \(K\) can be an arbitrary commutative ring.)
Let \(f_{1},f_{2},\ldots ,f_{k}\) be any \(k\) FPSs in \(K\left[\left[x\right]\right]_{1}\). Then,
(Here, we do not use Convention 1.210; thus, \(K\) can be an arbitrary commutative ring.)
Let \(f\) be any FPS in \(K\left[\left[x\right] \right]_{1}\). Then, \(\operatorname {loder}\left(f^{-1}\right) =-\operatorname {loder}f\).
(Here, we do not use Convention 1.210; thus, \(K\) can be an arbitrary commutative ring.)
Assume that \(K\) is a commutative \(\mathbb {Q}\)-algebra. Let \(f\in K\left[ \left[ x\right] \right] _{1}\) and \(c\in K\). Then, we define an FPS
Assume that \(K\) is a commutative \(\mathbb {Q}\)-algebra. For any \(a,b\in K\) and \(f,g\in K\left[ \left[ x\right] \right] _{1}\), we have
Assume that \(K\) is a commutative \(\mathbb {Q}\)-algebra. Let \(c\in K\). Then,
Let \(n\in \mathbb {C}\) and \(k\in \mathbb {N}\). Then,
(a) An (integer) composition means a (finite) tuple of positive integers.
(b) The size of an integer composition \(\alpha =\left( \alpha _{1},\alpha _{2},\ldots ,\alpha _{m}\right) \) is defined to be the integer \(\alpha _{1}+\alpha _{2}+\cdots +\alpha _{m}\). It is written \(\left\vert \alpha \right\vert \).
(c) The length of an integer composition \(\alpha =\left( \alpha _{1},\alpha _{2},\ldots ,\alpha _{m}\right) \) is defined to be the integer \(m\). It is written \(\ell \left( \alpha \right) \).
(d) Let \(n\in \mathbb {N}\). A composition of \(n\) means a composition whose size is \(n\).
(e) Let \(n\in \mathbb {N}\) and \(k\in \mathbb {N}\). A composition of \(n\) into \(k\) parts is a composition whose size is \(n\) and whose length is \(k\).
Let \(n,k\in \mathbb {N}\). Then, the # of compositions of \(n\) into \(k\) parts is
Let \(n\in \mathbb {N}\). Then, the # of compositions of \(n\) is
(a) An (integer) weak composition means a (finite) tuple of nonnegative integers.
(b) The size of a weak composition \(\alpha =\left( \alpha _{1},\alpha _{2},\ldots ,\alpha _{m}\right) \) is defined to be the integer \(\alpha _{1}+\alpha _{2}+\cdots +\alpha _{m}\). It is written \(\left\vert \alpha \right\vert \).
(c) The length of a weak composition \(\alpha =\left( \alpha _{1},\alpha _{2},\ldots ,\alpha _{m}\right) \) is defined to be the integer \(m\). It is written \(\ell \left( \alpha \right) \).
(d) Let \(n\in \mathbb {N}\). A weak composition of \(n\) means a weak composition whose size is \(n\).
(e) Let \(n\in \mathbb {N}\) and \(k\in \mathbb {N}\). A weak composition of \(n\) into \(k\) parts is a weak composition whose size is \(n\) and whose length is \(k\).
Let \(n,k\in \mathbb {N}\). Then, the # of weak compositions of \(n\) into \(k\) parts is
Let \(n,k,p\in \mathbb {N}\). Then, the # of \(k\)-tuples \(\left( \alpha _{1},\alpha _{2},\ldots ,\alpha _{k}\right) \in \left\{ 0,1,\ldots ,p-1\right\} ^{k}\) satisfying \(\alpha _{1}+\alpha _{2}+\cdots +\alpha _{k}=n\) is
Let \(n,k\in \mathbb {N}\). Then,
Let \(n\in \mathbb {N}\). Let \(f,g\in K\left[\left[x\right]\right]\) be two FPSs. We write \(f\overset {x^{n}}{\equiv }g\) if and only if
Thus, we have defined a binary relation \(\overset {x^{n}}{\equiv }\) on the set \(K\left[\left[x\right]\right]\). We say that an FPS \(f\) is \(x^{n}\)-equivalent to an FPS \(g\) if and only if \(f\overset {x^{n}}{\equiv }g\).
Let \(n\in \mathbb {N}\).
(a) The relation \(\overset {x^{n}}{\equiv }\) on \(K\left[\left[ x\right]\right]\) is an equivalence relation. In other words:
This relation is reflexive (i.e., we have \(f\overset {x^{n}}{\equiv }f\) for each \(f\in K\left[\left[x\right]\right]\)).
This relation is transitive (i.e., if three FPSs \(f,g,h\in K\left[ \left[x\right]\right]\) satisfy \(f\overset {x^{n}}{\equiv }g\) and \(g\overset {x^{n}}{\equiv }h\), then \(f\overset {x^{n}}{\equiv }h\)).
This relation is symmetric (i.e., if two FPSs \(f,g\in K\left[\left[ x\right]\right]\) satisfy \(f\overset {x^{n}}{\equiv }g\), then \(g\overset {x^{n}}{\equiv }f\)).
(b) If \(a,b,c,d\in K\left[\left[x\right]\right]\) are four FPSs satisfying \(a\overset {x^{n}}{\equiv }b\) and \(c\overset {x^{n}}{\equiv }d\), then we also have
(c) If \(a,b\in K\left[\left[x\right]\right]\) are two FPSs satisfying \(a\overset {x^{n}}{\equiv }b\), then \(\lambda a\overset {x^{n}}{\equiv }\lambda b\) for each \(\lambda \in K\).
(d) If \(a,b\in K\left[\left[x\right]\right]\) are two invertible FPSs satisfying \(a\overset {x^{n}}{\equiv }b\), then \(a^{-1} \overset {x^{n}}{\equiv }b^{-1}\).
(e) If \(a,b,c,d\in K\left[\left[x\right]\right]\) are four FPSs satisfying \(a\overset {x^{n}}{\equiv }b\) and \(c\overset {x^{n}}{\equiv }d\), and if the FPSs \(c\) and \(d\) are invertible, then we also have
(f) Let \(S\) be a finite set. Let \(\left(a_{s}\right)_{s\in S}\in K\left[\left[x\right]\right]^{S}\) and \(\left(b_{s}\right)_{s\in S}\in K\left[\left[x\right]\right]^{S}\) be two families of FPSs such that
Then, we have
Let \(n\in \mathbb {N}\). Let \(f,g\in K\left[\left[x\right]\right]\) be two FPSs. Then, we have \(f\overset {x^{n}}{\equiv }g\) if and only if the FPS \(f-g\) is a multiple of \(x^{n+1}\).
Let \(n\in \mathbb {N}\). Let \(a,b,c,d\in K\left[\left[x\right]\right]\) be four FPSs satisfying \(a\overset {x^{n}}{\equiv }b\) and \(c\overset {x^{n}}{\equiv }d\) and \([x^{0}]c=0\) and \([x^{0}]d=0\). Then,
Let \(\left(\mathbf{a}_{i}\right)_{i\in I}\in K\left[\left[x\right]\right]^{I}\) be a (possibly infinite) family of FPSs. Let \(n\in \mathbb {N}\). Let \(M\) be a finite subset of \(I\).
(a) We say that \(M\) determines the \(x^{n}\)-coefficient in the sum of \(\left(\mathbf{a}_{i}\right)_{i\in I}\) if every finite subset \(J\) of \(I\) satisfying \(M\subseteq J\subseteq I\) satisfies
(b) We say that \(M\) determines the \(x^{n}\)-coefficient in the product of \(\left(\mathbf{a}_{i}\right)_{i\in I}\) if every finite subset \(J\) of \(I\) satisfying \(M\subseteq J\subseteq I\) satisfies
Let \(\left(\mathbf{a}_{i}\right)_{i\in I}\in K\left[\left[x\right]\right]^{I}\) be a (possibly infinite) family of FPSs. Let \(n\in \mathbb {N}\).
(a) We say that the \(x^{n}\)-coefficient in the sum of \(\left(\mathbf{a}_{i}\right)_{i\in I}\) is finitely determined if there is a finite subset \(M\) of \(I\) that determines the \(x^{n}\)-coefficient in the sum of \(\left(\mathbf{a}_{i}\right)_{i\in I}\).
(b) We say that the \(x^{n}\)-coefficient in the product of \(\left(\mathbf{a}_{i}\right)_{i\in I}\) is finitely determined if there is a finite subset \(M\) of \(I\) that determines the \(x^{n}\)-coefficient in the product of \(\left(\mathbf{a}_{i}\right)_{i\in I}\).
Let \(\left(\mathbf{a}_{i}\right)_{i\in I}\in K\left[\left[x\right]\right]^{I}\) be a (possibly infinite) family of FPSs. Then:
(a) The family \(\left(\mathbf{a}_{i}\right)_{i\in I}\) is summable if and only if each coefficient in its sum is finitely determined (i.e., for each \(n\in \mathbb {N}\), the \(x^{n}\)-coefficient in the sum of \(\left(\mathbf{a}_{i}\right)_{i\in I}\) is finitely determined).
(b) If the family \(\left(\mathbf{a}_{i}\right)_{i\in I}\) is summable, then its sum \(\sum _{i\in I}\mathbf{a}_{i}\) is the FPS whose \(x^{n}\)-coefficient (for any \(n\in \mathbb {N}\)) can be computed as follows: If \(n\in \mathbb {N}\), and if \(M\) is a finite subset of \(I\) that determines the \(x^{n}\)-coefficient in the sum of \(\left(\mathbf{a}_{i}\right)_{i\in I}\), then
Let \(\left(\mathbf{a}_{i}\right)_{i\in I}\) be a (possibly infinite) family of FPSs. Then:
(a) The family \(\left(\mathbf{a}_{i}\right)_{i\in I}\) is said to be multipliable if and only if each coefficient in its product is finitely determined.
(b) If the family \(\left(\mathbf{a}_{i}\right)_{i\in I}\) is multipliable, then its product \(\prod _{i\in I}\mathbf{a}_{i}\) is defined to be the FPS whose \(x^{n}\)-coefficient (for any \(n\in \mathbb {N}\)) can be computed as follows: If \(n\in \mathbb {N}\), and if \(M\) is a finite subset of \(I\) that determines the \(x^{n}\)-coefficient in the product of \(\left( \mathbf{a}_{i}\right)_{i\in I}\), then
This definition of \(\prod _{i\in I}\mathbf{a}_{i}\) is well-defined – i.e., the coefficient \(\left[x^{n}\right]\left(\prod _{i\in M}\mathbf{a}_{i}\right)\) does not depend on \(M\) (as long as \(M\) is a finite subset of \(I\) that determines the \(x^{n}\)-coefficient in the product of \(\left(\mathbf{a}_{i}\right)_{i\in I}\)).
Let \(\left(\mathbf{a}_{i}\right)_{i\in I}\) be a finite family of FPSs. Then, the product \(\prod _{i\in I}\mathbf{a}_{i}\) defined according to Definition 1.343 (b) equals the finite product \(\prod _{i\in I}\mathbf{a}_{i}\) defined in the usual way (i.e., defined as in any commutative ring).
Let \(a,f\in K\left[\left[x\right]\right]\) be two FPSs. Let \(n\in \mathbb {N}\). Assume that
Then,
Let \(a\in K\left[\left[x\right]\right]\) be an FPS. Let \(\left(f_{i}\right)_{i\in J} \in K\left[\left[x\right]\right]^{J}\) be a finite family of FPSs. Let \(n\in \mathbb {N}\). Assume that each \(i\in J\) satisfies
Then,
Let \(\left(f_{i}\right)_{i\in I}\in K\left[\left[x\right]\right]^{I}\) be a (possibly infinite) summable family of FPSs. Then, the family \(\left(1+f_{i}\right)_{i\in I}\) is multipliable.
If all but finitely many entries of a family \(\left(\mathbf{a}_{i}\right)_{i\in I}\in K\left[\left[x\right]\right]^{I}\) equal \(1\) (that is, if all but finitely many \(i\in I\) satisfy \(\mathbf{a}_{i}=1\)), then this family is multipliable.
Let \(\left(\mathbf{a}_{i}\right)_{i\in I}\in K\left[\left[x\right]\right]^{I}\) be a family of FPSs. Let \(n\in \mathbb {N}\). An \(x^{n}\)-approximator for \(\left(\mathbf{a}_{i}\right)_{i\in I}\) means a finite subset \(M\) of \(I\) that determines the first \(n+1\) coefficients in the product of \(\left(\mathbf{a}_{i}\right)_{i\in I}\). (In other words, \(M\) has to determine the \(x^{m}\)-coefficient in the product of \(\left(\mathbf{a}_{i}\right)_{i\in I}\) for each \(m\in \left\{ 0,1,\ldots ,n\right\} \).)
Let \(\left(\mathbf{a}_{i}\right)_{i\in I}\in K\left[\left[x\right]\right]^{I}\) be a multipliable family of FPSs. Let \(n\in \mathbb {N}\). Then, there exists an \(x^{n}\)-approximator for \(\left(\mathbf{a}_{i}\right)_{i\in I}\).
Let \(\left(\mathbf{a}_{i}\right)_{i\in I}\in K\left[\left[x\right]\right]^{I}\) be a family of FPSs. Let \(n\in \mathbb {N}\). Let \(M\) be an \(x^{n}\)-approximator for \(\left(\mathbf{a}_{i}\right)_{i\in I}\). Then:
(a) Every finite subset \(J\) of \(I\) satisfying \(M\subseteq J\subseteq I\) satisfies
(b) If the family \(\left(\mathbf{a}_{i}\right)_{i\in I}\) is multipliable, then
Let \(\left(\mathbf{a}_{i}\right)_{i\in I}\in K\left[\left[x\right]\right]^{I}\) be a family of FPSs. Let \(J\) be a subset of \(I\). Assume that the subfamilies \(\left(\mathbf{a}_{i}\right)_{i\in J}\) and \(\left(\mathbf{a}_{i}\right)_{i\in I\setminus J}\) are multipliable. Then:
(a) The entire family \(\left(\mathbf{a}_{i}\right)_{i\in I}\) is multipliable.
(b) We have
Let \(\left(\mathbf{a}_{i}\right)_{i\in I}\in K\left[\left[x\right]\right]^{I}\) and \(\left(\mathbf{b}_{i}\right)_{i\in I}\in K\left[\left[x\right]\right]^{I}\) be two multipliable families of FPSs. Then:
(a) The family \(\left(\mathbf{a}_{i}\mathbf{b}_{i}\right)_{i\in I}\) is multipliable.
(b) We have
Let \(\left(\mathbf{a}_{i}\right)_{i\in I}\in K\left[\left[x\right]\right]^{I}\) and \(\left(\mathbf{b}_{i}\right)_{i\in I}\in K\left[\left[x\right]\right]^{I}\) be two multipliable families of FPSs. Assume that the FPS \(\mathbf{b}_{i}\) is invertible for each \(i\in I\). Then:
(a) The family \(\left(\frac{\mathbf{a}_{i}}{\mathbf{b}_{i}}\right)_{i\in I}\) is multipliable.
(b) We have
Let \(\left(\mathbf{a}_{i}\right)_{i\in I}\in K\left[\left[x\right]\right]^{I}\) be a multipliable family of invertible FPSs. Then, any subfamily of \(\left(\mathbf{a}_{i}\right)_{i\in I}\) is multipliable.
Let \(S\) and \(T\) be two sets. Let \(f:S\rightarrow T\) be a bijection. Let \(\left(\mathbf{a}_{t}\right)_{t\in T}\in K\left[\left[x\right]\right]^{T}\) be a multipliable family of FPSs. Then,
(and, in particular, the product on the right hand side is well-defined, i.e., the family \(\left(\mathbf{a}_{f\left(s\right)}\right)_{s\in S}\) is multipliable).
Let \(\left(\mathbf{a}_{s}\right)_{s\in S}\in K\left[\left[x\right]\right]^{S}\) be a multipliable family of FPSs. Let \(W\) be a set. Let \(f:S\rightarrow W\) be a map. Assume that for each \(w\in W\), the family \(\left(\mathbf{a}_{s}\right)_{s\in S,\; f(s)=w}\) is multipliable. Then,
(In particular, the right hand side is well-defined – i.e., the family \(\left(\prod _{\substack {s\in S;\\ f(s)=w}}\mathbf{a}_{s}\right)_{w\in W}\) is multipliable.)
Note: The Lean formalization of this proposition (without sorry) requires the additional assumption that all FPSs are invertible (i.e., \([x^0]\mathbf{a}_s\) is a unit for each \(s\)), which is used through Proposition 1.369 to guarantee multipliability of subfamilies. The versions without this invertibility hypothesis are formalized with sorry.
Let \(I\) and \(J\) be two sets. Let \(\left(\mathbf{a}_{(i,j)}\right)_{(i,j)\in I\times J}\in K\left[\left[x\right]\right]^{I\times J}\) be a multipliable family of FPSs. Assume that for each \(i\in I\), the family \(\left(\mathbf{a}_{(i,j)}\right)_{j\in J}\) is multipliable. Assume that for each \(j\in J\), the family \(\left(\mathbf{a}_{(i,j)}\right)_{i\in I}\) is multipliable. Then,
(In particular, all the products appearing in this equality are well-defined.)
Let \(I\) and \(J\) be two sets. Let \(\left(\mathbf{a}_{(i,j)}\right)_{(i,j)\in I\times J}\in K\left[\left[x\right]\right]^{I\times J}\) be a multipliable family of invertible FPSs. Then,
(In particular, all the products appearing in this equality are well-defined.)
Let \(L\) be a commutative ring. For every \(n\in \mathbb {N}\), let \(\left[ n\right] \) denote the set \(\left\{ 1,2,\ldots ,n\right\} \).
Let \(n\in \mathbb {N}\). For every \(i\in \left[ n\right] \), let \(p_{i,1},p_{i,2},\ldots ,p_{i,m_{i}}\) be finitely many elements of \(L\). Then,
For every \(n\in \mathbb {N}\), let \(\left[ n\right] \) denote the set \(\left\{ 1,2,\ldots ,n\right\} \).
Let \(n\in \mathbb {N}\). For every \(i\in \left[ n\right] \), let \(\left( p_{i,k}\right) _{k\in S_{i}}\) be a summable family of elements of \(K\left[ \left[ x\right] \right] \). Then,
In particular, the family \(\left( \prod _{i=1}^{n}p_{i,k_{i}}\right) _{\left( k_{1},k_{2},\ldots ,k_{n}\right) \in S_{1}\times S_{2}\times \cdots \times S_{n}}\) is summable.
(a) A sequence \(\left( k_{1},k_{2},k_{3},\ldots \right) \) is said to be essentially finite if all but finitely many \(i\in \left\{ 1,2,3,\ldots \right\} \) satisfy \(k_{i}=0\).
(b) A family \(\left( k_{i}\right) _{i\in I}\) is said to be essentially finite if all but finitely many \(i\in I\) satisfy \(k_{i}=0\).
Let \(S_{1},S_{2},S_{3},\ldots \) be infinitely many sets that all contain the number \(0\). Set
For any \(i\in \left\{ 1,2,3,\ldots \right\} \) and any \(k\in S_{i}\), let \(p_{i,k}\) be an element of \(K\left[ \left[ x\right] \right] \). Assume that
Assume further that the family \(\left( p_{i,k}\right) _{\left( i,k\right) \in \overline{S}}\) is summable. Then, the product \(\prod _{i=1}^{\infty }\ \ \sum _{k\in S_{i}}p_{i,k}\) is well-defined (i.e., the family \(\left( p_{i,k}\right) _{k\in S_{i}}\) is summable for each \(i\in \left\{ 1,2,3,\ldots \right\} \), and the family \(\left( \sum _{k\in S_{i}}p_{i,k}\right) _{i\in \left\{ 1,2,3,\ldots \right\} }\) is multipliable), and we have
In particular, the family \(\left( \prod _{i=1}^{\infty }p_{i,k_{i}}\right) _{\left( k_{1},k_{2},k_{3},\ldots \right) \in S_{1}\times S_{2}\times S_{3}\times \cdots \text{ is essentially finite}}\) is summable.
Let \(I\) be a set. For any \(i\in I\), let \(S_{i}\) be a set that contains the number \(0\). Set
For any \(i\in I\) and any \(k\in S_{i}\), let \(p_{i,k}\) be an element of \(K\left[ \left[ x\right] \right] \). Assume that
Assume further that the family \(\left( p_{i,k}\right) _{\left( i,k\right) \in \overline{S}}\) is summable. Then, the product \(\prod _{i\in I}\ \ \sum _{k\in S_{i}}p_{i,k}\) is well-defined (i.e., the family \(\left( p_{i,k}\right) _{k\in S_{i}}\) is summable for each \(i\in I\), and the family \(\left( \sum _{k\in S_{i}}p_{i,k}\right) _{i\in I}\) is multipliable), and we have
In particular, the family \(\left( \prod _{i\in I}p_{i,k_{i}}\right) _{\left( k_{i}\right) _{i\in I}\in \prod _{i\in I}S_{i}\text{ is essentially finite}}\) is summable.
Let \(N\) be a finite set. For any \(i\in N\), let \(\left( p_{i,k}\right) _{k\in S_{i}}\) be a summable family of elements of \(K\left[ \left[ x\right] \right] \). Then,
In particular, the family \(\left( \prod _{i\in N}p_{i,k_{i}}\right) _{\left( k_{i}\right) _{i\in N}\in \prod _{i\in N}S_{i}}\) is summable.
Let \(a\in K\left[ \left[ x\right] \right] \) be an FPS. Let \(\left( f_{i}\right) _{i\in J}\in K\left[ \left[ x\right] \right] ^{J}\) be a summable family of FPSs. Let \(n\in \mathbb {N}\). Assume that each \(i\in J\) satisfies
Then,
We have
Let \(n\in \mathbb {N}\). Then, \(d_{n}=o_{n}\), where
\(d_{n}\) is the number of ways to write \(n\) as a sum of distinct positive integers, without regard to the order;
\(o_{n}\) is the number of ways to write \(n\) as a sum of (not necessarily distinct) odd positive integers, without regard to the order.
If \(\left( f_{i}\right) _{i\in I}\in K\left[ \left[ x\right] \right] ^{I}\) is a multipliable family of FPSs, and if \(g\in K\left[ \left[ x\right] \right] \) is an FPS satisfying \(\left[ x^{0}\right] g=0\), then the family \(\left( f_{i}\circ g\right) _{i\in I}\in K\left[ \left[ x\right] \right] ^{I}\) is multipliable as well and we have \(\left( \prod _{i\in I}f_{i}\right) \circ g=\prod _{i\in I}\left( f_{i}\circ g\right) \).
Assume that \(K\) is a commutative \(\mathbb {Q}\)-algebra. Let \(\left( f_{i}\right) _{i\in I}\in K\left[ \left[ x\right] \right] ^{I}\) be a summable family of FPSs in \(K\left[ \left[ x\right] \right] _{0}\). Then, \(\left( \operatorname {Exp}f_{i}\right) _{i\in I}\) is a multipliable family of FPS in \(K\left[ \left[ x\right] \right] _{1}\), and we have \(\sum _{i\in I}f_{i}\in K\left[ \left[ x\right] \right] _{0}\) and
Assume that \(K\) is a commutative \(\mathbb {Q}\)-algebra. Let \(\left( f_{i}\right) _{i\in I}\in K\left[ \left[ x\right] \right] ^{I}\) be a multipliable family of FPSs in \(K\left[ \left[ x\right] \right] _{1}\). Then, \(\left( \operatorname {Log}f_{i}\right) _{i\in I}\) is a summable family of FPS in \(K\left[ \left[ x\right] \right] _{0}\), and we have \(\prod \limits _{i\in I}f_{i}\in K\left[ \left[ x\right] \right] _{1}\) and
(a) A weighted set is a set \(A\) equipped with a function \(w:A\rightarrow \mathbb {N}\), which is called the weight function of this weighted set. For each \(a\in A\), the value \(w\left( a\right) \) is denoted \(\left\vert a\right\vert \) and is called the weight of \(a\) (in our weighted set).
Usually, instead of explicitly specifying the weight function \(w\) as a function, we will simply specify the weight \(\left\vert a\right\vert \) for each \(a\in A\). The weighted set consisting of the set \(A\) and the weight function \(w\) will be called \(\left( A,w\right) \) or simply \(A\) when the weight function \(w\) is clear from the context.
(b) A weighted set \(A\) is said to be finite-type if for each \(n\in \mathbb {N}\), there are only finitely many \(a\in A\) having weight \(\left\vert a\right\vert =n\).
(c) If \(A\) is a finite-type weighted set, then the weight generating function of \(A\) is defined to be the FPS
This FPS is denoted by \(\overline{A}\).
(d) An isomorphism between two weighted sets \(A\) and \(B\) means a bijection \(\rho :A\rightarrow B\) that preserves the weight (i.e., each \(a\in A\) satisfies \(\left\vert \rho \left( a\right) \right\vert =\left\vert a\right\vert \)).
(e) We say that two weighted sets \(A\) and \(B\) are isomorphic (this is written \(A\cong B\)) if there exists an isomorphism between \(A\) and \(B\).
The underlying bijection
The bijection preserves weights
Let \(A\) and \(B\) be two isomorphic finite-type weighted sets. Then, \(\overline{A}=\overline{B}\).
Let \(A\) and \(B\) be two weighted sets. Then, the weighted set \(A+B\) is defined to be the disjoint union of \(A\) and \(B\), with the weight function inherited from \(A\) and \(B\) (meaning that each element of \(A\) has the same weight that it had in \(A\), and each element of \(B\) has the same weight that it had in \(B\)). Formally speaking, this means that \(A+B\) is the set \(\left( \left\{ 0\right\} \times A\right) \cup \left( \left\{ 1\right\} \times B\right) \), with the weight function given by
and
Let \(A\) and \(B\) be two finite-type weighted sets. Then, \(A+B\) is finite-type, too, and satisfies \(\overline{A+B}=\overline{A}+\overline{B}\).
Let \(A\) and \(B\) be two weighted sets. Then, the weighted set \(A\times B\) is defined to be the Cartesian product of the sets \(A\) and \(B\) (that is, the set \(\left\{ \left( a,b\right) \ \mid \ a\in A\text{ and }b\in B\right\} \)), with the weight function defined as follows: For any \(\left( a,b\right) \in A\times B\), we set
Let \(A\) be a weighted set. Then, \(A^{k}\) (for \(k\in \mathbb {N}\)) means the weighted set \(\underbrace{A\times A\times \cdots \times A}_{k\text{ times}}\).
Let \(A\) be a finite-type weighted set. Let \(k\in \mathbb {N}\). Then, \(A^{k}\) is finite-type, too, and satisfies \(\overline{A^{k}}=\overline{A}^{k}\).
(a) A shape means a subset of \(\mathbb {Z}^{2}\).
We draw each \(\left( i,j\right) \in \mathbb {Z}^{2}\) as a unit square with center at the point \(\left( i,j\right) \) (in Cartesian coordinates); thus, a shape can be drawn as a cluster of squares.
(b) For any \(n,m\in \mathbb {N}\), the shape \(R_{n,m}\) (called the \(n\times m\)-rectangle) is defined to be
(c) A domino means a size-\(2\) shape of the form
for some \(\left( i,j\right) \in \mathbb {Z}^{2}\).
(d) A domino tiling of a shape \(S\) is a set partition of \(S\) into dominos (i.e., a set of disjoint dominos whose union is \(S\)).
(e) For any \(n,m\in \mathbb {N}\), let \(d_{n,m}\) be the # of domino tilings of \(R_{n,m}\).
The set of dominos in the tiling
The dominos are pairwise disjoint
The union of dominos equals the shape
Any domino tiling of a height-\(2\) rectangle can be decomposed uniquely into a tuple of faultfree tilings of (usually smaller) height-\(2\) rectangles, by cutting it along its faults. (If the original tiling was faultfree, then it decomposes into a \(1\)-tuple. If the original tiling was empty, then it decomposes into a \(0\)-tuple.)
Moreover, the sum of the weights of the faultfree tilings in the tuple is the weight of the original tiling. (In other words, if a tiling \(T\) decomposes into the tuple \(\left( T_{1},T_{2},\ldots ,T_{k}\right) \), then \(\left\vert T\right\vert =\left\vert T_{1}\right\vert +\left\vert T_{2}\right\vert +\cdots +\left\vert T_{k}\right\vert \).)
In the language of weighted sets, this yields an isomorphism
and therefore, by the infinite analogue of Proposition 1.405,
By Proposition 1.409, this equals
Let \(\left( a_{i}\right) _{i\in \mathbb {N}}=\left( a_{0},a_{1},a_{2},\ldots \right) \in K^{\mathbb {N}}\) be a sequence of elements of \(K\). Let \(a\in K\).
We say that the sequence \(\left( a_{i}\right) _{i\in \mathbb {N}}\) stabilizes to \(a\) if there exists some \(N\in \mathbb {N}\) such that
If \(a_{i}\) stabilizes to \(a\) as \(i\rightarrow \infty \), then we write \(\lim \limits _{i\rightarrow \infty }a_{i}=a\) and say that \(a\) is the limit (or eventual value) of \(\left( a_{i}\right) _{i\in \mathbb {N}}\). This is legitimate, since \(a\) is uniquely determined by the sequence \(\left( a_{i}\right) _{i\in \mathbb {N}}\).
Let \(\left( f_{i}\right) _{i\in \mathbb {N}}\in K\left[ \left[ x\right] \right] ^{\mathbb {N}}\) be a sequence of FPSs over \(K\). Let \(f\in K\left[ \left[ x\right] \right] \) be an FPS.
We say that \(\left( f_{i}\right) _{i\in \mathbb {N}}\) coefficientwise stabilizes to \(f\) if for each \(n\in \mathbb {N}\),
If \(f_{i}\) coefficientwise stabilizes to \(f\) as \(i\rightarrow \infty \), then we write \(\lim \limits _{i\rightarrow \infty }f_{i}=f\) and say that \(f\) is the limit of \(\left( f_{i}\right) _{i\in \mathbb {N}}\). This is legitimate, because \(f\) is uniquely determined by the sequence \(\left( f_{i}\right) _{i\in \mathbb {N}}\).
Let \(\left( f_{i}\right) _{i\in \mathbb {N}}\in K\left[ \left[ x\right] \right] ^{\mathbb {N}}\) be a sequence of FPSs. Assume that for each \(n\in \mathbb {N}\), there exists some \(g_{n}\in K\) such that the sequence \(\left( \left[ x^{n}\right] f_{i}\right) _{i\in \mathbb {N}}\) stabilizes to \(g_{n}\). Then, the sequence \(\left( f_{i}\right) _{i\in \mathbb {N}}\) coefficientwise stabilizes to \(\sum _{n\in \mathbb {N}}g_{n}x^{n}\). (That is, \(\lim \limits _{i\rightarrow \infty }f_{i}=\sum _{n\in \mathbb {N}}g_{n}x^{n}\).)
Assume that \(\left( f_{i}\right) _{i\in \mathbb {N}}\) is a sequence of FPSs, and that \(f\) is an FPS such that \(\lim \limits _{i\rightarrow \infty }f_{i}=f\). Then, for each \(n\in \mathbb {N}\), there exists some integer \(N\in \mathbb {N}\) such that
Assume that \(\left( f_{i}\right) _{i\in \mathbb {N}}\) and \(\left( g_{i}\right) _{i\in \mathbb {N}}\) are two sequences of FPSs, and that \(f\) and \(g\) are two FPSs such that
Then,
Let \(k\in \mathbb {N}\). For each \(i\in \left\{ 1,2,\ldots ,k\right\} \), let \(f_{i}\) be an FPS, and let \(\left( f_{i,n}\right) _{n\in \mathbb {N}}\) be a sequence of FPSs such that
(note that it is \(n\), not \(i\), that goes to \(\infty \) here!). Then,
Assume that \(\left( f_{i}\right) _{i\in \mathbb {N}}\) and \(\left( g_{i}\right) _{i\in \mathbb {N}}\) are two sequences of FPSs, and that \(f\) and \(g\) are two FPSs such that
Assume that each FPS \(g_{i}\) is invertible. Then, \(g\) is also invertible, and we have
Assume that \(\left( f_{i}\right) _{i\in \mathbb {N}}\) and \(\left( g_{i}\right) _{i\in \mathbb {N}}\) are two sequences of FPSs, and that \(f\) and \(g\) are two FPSs such that
Assume that \(\left[ x^{0}\right] g_{i}=0\) for each \(i\in \mathbb {N}\). Then, \(\left[ x^{0}\right] g=0\) and
Let \(\left( f_{n}\right) _{n\in \mathbb {N}}\) be a sequence of FPSs, and let \(f\) be an FPS such that
Then,
Let \(\left( f_{n}\right) _{n\in \mathbb {N}}\) be a summable sequence of FPSs. Then,
In other words, the infinite sum \(\sum _{n\in \mathbb {N}}f_{n}\) is the limit of the finite partial sums \(\sum _{n=0}^{i}f_{n}\).
Let \(\left( f_{n}\right) _{n\in \mathbb {N}}\) be a multipliable sequence of FPSs. Then,
In other words, the infinite product \(\prod _{n\in \mathbb {N}}f_{n}\) is the limit of the finite partial products \(\prod _{n=0}^{i}f_{n}\).
Each FPS is a limit of a sequence of polynomials. Indeed, if \(a=\sum _{n\in \mathbb {N}}a_{n}x^{n}\) (with \(a_{n}\in K\)), then
More precisely, the sequence of truncations \((\operatorname {trunc}_{i+1}(a))_{i \in \mathbb {N}}\) coefficientwise stabilizes to \(a\).
Let \(\left( f_{0},f_{1},f_{2},\ldots \right) \) be a sequence of FPSs such that \(\lim \limits _{i\rightarrow \infty }\sum _{n=0}^{i}f_{n}\) exists. Then, the family \(\left( f_{n}\right) _{n\in \mathbb {N}}\) is summable, and satisfies
Let \(\left( f_{0},f_{1},f_{2},\ldots \right) \) be a sequence of FPSs such that \(\lim \limits _{i\rightarrow \infty }\prod _{n=0}^{i}f_{n}\) exists. Then, the family \(\left( f_{n}\right) _{n\in \mathbb {N}}\) is multipliable, and satisfies
Let \(K\left[ \left[ x^{\pm }\right] \right] \) be the \(K\)-module \(K^{\mathbb {Z}}\) of all families \(\left( a_{n}\right) _{n\in \mathbb {Z}}=\left( \ldots ,a_{-2},a_{-1},a_{0},a_{1},a_{2},\ldots \right) \) of elements of \(K\). Its addition and its scaling are defined entrywise:
An element of \(K\left[ \left[ x^{\pm }\right] \right] \) will be called a doubly infinite power series. We use the notation \(\sum _{n\in \mathbb {Z}}a_{n}x^{n}\) for a family \(\left( a_{n}\right) _{n\in \mathbb {Z}}\in K\left[ \left[ x^{\pm }\right] \right] \).
Let \(K\left[ x^{\pm }\right] \) be the \(K\)-submodule of \(K\left[ \left[ x^{\pm }\right] \right] \) consisting of all essentially finite families \(\left( a_{n}\right) _{n\in \mathbb {Z}}\). The elements of \(K\left[ x^{\pm }\right] \) are called Laurent polynomials in the indeterminate \(x\) over \(K\).
We define a multiplication on \(K\left[ x^{\pm }\right] \) by setting
The sum \(\sum _{i\in \mathbb {Z}}a_{i}b_{n-i}\) is well-defined because it is essentially finite.
We define an element \(x\in K\left[ x^{\pm }\right] \) by
In Mathlib, Laurent polynomials are represented as finitely supported functions \(\mathbb {Z} \to K\) (the group algebra of \(\mathbb {Z}\) over \(K\)).
The \(K\)-module \(K\left[ x^{\pm }\right] \), equipped with the multiplication defined above, is a commutative \(K\)-algebra. Its unity is \(\left( \delta _{i,0}\right) _{i\in \mathbb {Z}}\). The element \(x\) is invertible in this \(K\)-algebra.
Any doubly infinite power series \(a=\left( a_{i}\right) _{i\in \mathbb {Z}}\in K\left[ \left[ x^{\pm }\right] \right] \) satisfies
Here, the powers \(x^{i}\) are taken in the Laurent polynomial ring \(K\left[ x^{\pm }\right] \), but the infinite sum \(\sum _{i\in \mathbb {Z}}a_{i}x^{i}\) is taken in the \(K\)-module \(K\left[ \left[ x^{\pm }\right] \right] \).
For Laurent polynomials, the sum is finite and the identity holds in \(K[x^{\pm }]\) itself. For Laurent series, the identity is formalized using a summable family construction.
We let \(K\left( \left( x\right) \right) \) be the subset of \(K\left[ \left[ x^{\pm }\right] \right] \) consisting of all families \(\left( a_{i}\right) _{i\in \mathbb {Z}}\in K\left[ \left[ x^{\pm }\right] \right] \) such that the sequence \(\left( a_{-1},a_{-2},a_{-3},\ldots \right) \) is essentially finite – i.e., such that all sufficiently low \(i\in \mathbb {Z}\) satisfy \(a_{i}=0\).
The elements of \(K\left( \left( x\right) \right) \) are called Laurent series in one indeterminate \(x\) over \(K\).
In Mathlib, Laurent series are implemented as Hahn series over \(\mathbb {Z}\) with coefficients in \(K\), which are functions \(\mathbb {Z} \to K\) whose support is well-founded (equivalently, bounded below). The formalization also provides a predicate on doubly infinite power series that captures this textbook definition.
The subset \(K\left( \left( x\right) \right) \) is a \(K\)-submodule of \(K\left[ \left[ x^{\pm }\right] \right] \). It has a multiplication given by the same convolution rule as \(K\left[ x^{\pm }\right] \): namely,
The sum \(\sum _{i\in \mathbb {Z}}a_{i}b_{n-i}\) is well-defined because for sufficiently low \(i\) we have \(a_i = 0\), and for sufficiently high \(i\) we have \(b_{n-i} = 0\).
Equipped with this multiplication, \(K\left( \left( x\right) \right) \) is a commutative \(K\)-algebra with unity \(\left( \delta _{i,0}\right) _{i\in \mathbb {Z}}\). The element \(x\) is invertible in this algebra.
Let \(f_{0},f_{1},f_{2},\ldots \) and \(g_{0},g_{1},g_{2},\ldots \) be FPSs in a single variable \(x\) such that
Then, \(f_{k}=g_{k}\) for each \(k\in \mathbb {N}\).
(a) An (integer) partition means a (finite) weakly decreasing tuple of positive integers – i.e., a finite tuple \(\left( \lambda _{1},\lambda _{2},\ldots ,\lambda _{m}\right) \) of positive integers such that \(\lambda _{1}\geq \lambda _{2}\geq \cdots \geq \lambda _{m}\).
Thus, partitions are the same as weakly decreasing compositions. Hence, the notions of size and length of a partition are automatically defined, since we have defined them for compositions (in Definition 1.291).
(b) The parts of a partition \(\left( \lambda _{1},\lambda _{2},\ldots ,\lambda _{m}\right) \) are simply its entries \(\lambda _{1},\lambda _{2},\ldots ,\lambda _{m}\).
(c) Let \(n\in \mathbb {Z}\). A partition of \(n\) means a partition whose size is \(n\).
(d) Let \(n\in \mathbb {Z}\) and \(k\in \mathbb {N}\). A partition of \(n\) into \(k\) parts is a partition whose size is \(n\) and whose length is \(k\).
(a) Let \(n\in \mathbb {Z}\) and \(k\in \mathbb {N}\). Then, we set
(b) Let \(n\in \mathbb {Z}\). Then, we set
This is called the \(n\)-th partition number.
We will use the Iverson bracket notation: If \(\mathcal{A}\) is a logical statement, then \(\left[ \mathcal{A} \right]\) means the truth value of \(\mathcal{A}\); this is the integer \(\begin{cases} 1, & \text{if }\mathcal{A}\text{ is true};\\ 0, & \text{if }\mathcal{A}\text{ is false}. \end{cases} \)
Note that the Kronecker delta notation is a particular case of the Iverson bracket: We have
We agree to say that the largest part of the empty partition \(\left( {}\right) \) is \(0\) (even though this partition has no parts).
Let \(n\in \mathbb {Z}\) and \(k\in \mathbb {N}\).
(a) We have \(p_{k}\left( n\right) =0\) whenever \(n{\lt}0\) and \(k\in \mathbb {N}\).
(b) We have \(p_{k}\left( n\right) =0\) whenever \(k{\gt}n\).
(c) We have \(p_{0}\left( n\right) =\left[ n=0 \right]\).
(d) We have \(p_{1}\left( n\right) =\left[ n{\gt}0 \right]\).
(e) We have \(p_{k}\left( n\right) =p_{k}\left( n-k\right) +p_{k-1}\left( n-1\right) \) whenever \(k{\gt}0\).
(f) We have \(p_{2}\left( n\right) =\left\lfloor n/2\right\rfloor \) whenever \(n\in \mathbb {N}\).
(g) We have \(p\left( n\right) =p_{0}\left( n\right) +p_{1}\left( n\right) +\cdots +p_{n}\left( n\right) \) whenever \(n\in \mathbb {N}\).
(h) We have \(p\left( n\right) =0\) whenever \(n{\lt}0\).
In the FPS ring \(\mathbb {Z}\left[ \left[ x\right] \right] \), we have
(The product on the right hand side is well-defined, since multiplying a FPS by \(\frac{1}{1-x^{k}}\) does not affect its first \(k\) coefficients.)
Let \(m\in \mathbb {N}\). For each \(n\in \mathbb {N}\), let \(p_{\operatorname {parts}\leq m}\left( n\right) \) be the # of partitions \(\lambda \) of \(n\) such that all parts of \(\lambda \) are \(\leq m\). Then,
Let \(I\) be a subset of \(\left\{ 1,2,3,\ldots \right\} \). For each \(n\in \mathbb {N}\), let \(p_{I}\left( n\right) \) be the # of partitions \(\lambda \) of \(n\) such that all parts of \(\lambda \) belong to \(I\). Then,
Let \(n\in \mathbb {Z}\).
(a) A partition of \(n\) into odd parts means a partition of \(n\) whose all parts are odd.
(b) A partition of \(n\) into distinct parts means a partition of \(n\) whose parts are distinct.
(c) Let
We have \(p_{\operatorname {odd}}\left( n\right) =p_{\operatorname {dist}}\left( n\right) \) for each \(n\in \mathbb {N}\).
Let \(n\in \mathbb {N}\) and \(k\in \mathbb {N}\). Then,
Let \(n\in \mathbb {N}\) and \(k\in \mathbb {N}\). Then,
Let \(m\in \mathbb {N}\). Then,
For any positive integer \(n\), let \(\sigma \left( n\right) \) denote the sum of all positive divisors of \(n\). (For example, \(\sigma \left( 6\right) =1+2+3+6=12\) and \(\sigma \left( 7\right) =1+7=8\).)
For any \(n\in \mathbb {N}\), we have
Let \(I\) be a subset of \(\left\{ 1,2,3,\ldots \right\} \). For each \(n\in \mathbb {N}\), let \(p_{I}\left( n\right) \) be the # of partitions \(\lambda \) of \(n\) such that all parts of \(\lambda \) belong to \(I\).
For any positive integer \(n\), let \(\sigma _{I}\left( n\right) \) denote the sum of all positive divisors of \(n\) that belong to \(I\).
For any \(n\in \mathbb {N}\), we have
For any \(k\in \mathbb {Z}\), define a nonnegative integer \(w_{k}\in \mathbb {N}\) by
This is called the \(k\)-th pentagonal number.
We have
For each positive integer \(n\), we have
In the ring \(\left( \mathbb {Z}\left[ z^{\pm }\right] \right) \left[ \left[ q\right] \right] \), we have
Let \(a\) and \(b\) be two integers such that \(a{\gt}0\) and \(a\geq \left\vert b\right\vert \). Let \(u,v\in \mathbb {Q}\) be rational numbers with \(v\neq 0\). In the ring \(\mathbb {Q}\left[\left[ x\right]\right] \), set \(q=ux^{a}\) and \(z=vx^{b}\). Then,
Let \(K\) be a commutative ring. Let \(f\) and \(g\) be two FPSs in \(K[[x]]\). Assume that \(f[x^{2}]=g[x^{2}]\). Then, \(f=g\).
For any positive integer \(n\), let \(\sigma (n)\) denote the sum of all positive divisors of \(n\).
Then, for each positive integer \(n\), we have
(Here, \(w_{k}\) is the \(k\)-th pentagonal number, defined in Definition 2.67.)
For any positive integers \(k\) and \(\ell \), we have
Let \(n\in \mathbb {N}\) and \(k\in \mathbb {Z}\).
(a) The \(q\)-binomial coefficient (or Gaussian binomial coefficient) \(\binom {n}{k}_{q}\) is defined to be the polynomial
(b) If \(a\) is any element of a ring \(A\), then we set
Let \(n\in \mathbb {N}\) and \(k\in \mathbb {Z}\).
(a) We have
Here, the sum ranges over all weakly increasing \(k\)-tuples \((i_{1},i_{2},\ldots ,i_{k}) \in \{ 0,1,\ldots ,n-k\} ^{k}\). If \(k{\gt}n\), then this is an empty sum. If \(k{\lt}0\), then this is also an empty sum.
(b) Set \(\operatorname {sum}S=\sum _{s\in S}s\) for any finite set \(S\) of integers. Then, we have
(c) We have
Let \(n,k\in \mathbb {N}\) satisfy \(k{\gt}n\). Then, \(\binom {n}{k}_{q}=0\).
Let \(n\in \mathbb {N}\). For any \(k\notin \mathbb {Z}\), we set \(\binom {n}{k}_{q}:=0\).
Let \(n\) be a positive integer. Let \(k\in \mathbb {N}\). Then:
(a) We have
(b) We have
Let \(n,k\in \mathbb {N}\) satisfy \(n\geq k\). Then:
(a) We have
(b) We have
(in the ring \(\mathbb {Z}[[q]]\) or in the field of rational functions over \(\mathbb {Q}\)).
(a) For any \(n\in \mathbb {N}\), define the \(q\)-integer \([n]_{q}\) to be
(b) For any \(n\in \mathbb {N}\), define the \(q\)-factorial \([n]_{q}!\) to be
(c) As usual, if \(a\) is an element of a ring \(A\), then \([n]_{a}\) and \([n]_{a}!\) will mean the results of substituting \(a\) for \(q\) in \([n]_{q}\) and \([n]_{q}!\), respectively. Thus, explicitly, \([n]_{a}=a^{0}+a^{1}+\cdots +a^{n-1}\) and \([n]_{a}!=[1]_{a}[2]_{a}\cdots [n]_{a}\).
Let \(n,k\in \mathbb {N}\) with \(n\geq k\). Then,
(in the ring \(\mathbb {Z}[[q]]\) or in the ring of rational functions over \(\mathbb {Q}\)).
Let \(K\) be a commutative ring. Let \(a,b\in K\) and \(n\in \mathbb {N}\). In the polynomial ring \(K\left[ q\right] \), we have
Let \(L\) be a commutative ring. Let \(n\in \mathbb {N}\). Let \(\left[ n\right] \) denote the set \(\left\{ 1,2,\ldots ,n\right\} \). Let \(a_{1},a_{2},\ldots ,a_{n}\) be \(n\) elements of \(L\). Let \(b_{1},b_{2},\ldots ,b_{n}\) be \(n\) further elements of \(L\). Then,
Let \(L\) be a commutative ring. Let \(\omega \in L\). Let \(A\) be a noncommutative \(L\)-algebra. Let \(a,b\in A\) be such that \(ba=\omega ab\). Then,
Let \(F\) be a finite field. Let \(n,k\in \mathbb {N}\). Let \(V\) be an \(n\)-dimensional \(F\)-vector space. Then,
Let \(F\) be a field. Let \(V\) be an \(F\)-vector space. Let \(\left( v_{1},v_{2},\ldots ,v_{k}\right) \) be a \(k\)-tuple of vectors in \(V\). Then, \(\left( v_{1},v_{2},\ldots ,v_{k}\right) \) is linearly independent if and only if each \(i\in \left\{ 1,2,\ldots ,k\right\} \) satisfies \(v_{i}\notin \operatorname {span}\left( v_{1},v_{2},\ldots ,v_{i-1}\right) \) (where the span \(\operatorname {span}\left( {}\right) \) of an empty list is understood to be the set \(\left\{ \mathbf{0}\right\} \) consisting only of the zero vector \(\mathbf{0}\)). In other words, \(\left( v_{1},v_{2},\ldots ,v_{k}\right) \) is linearly independent if and only if we have
Let \(F\) be a finite field. Let \(n,k\in \mathbb {N}\). Let \(V\) be an \(n\)-dimensional \(F\)-vector space. Then,
Let \(A\) and \(B\) be two finite sets. Let \(m\in \mathbb {N}\). Let \(f:A\rightarrow B\) be any map. Assume that each \(b\in B\) has exactly \(m\) preimages under \(f\) (that is, for each \(b\in B\), there are exactly \(m\) many elements \(a\in A\) such that \(f\left( a\right) =b\)). Then,
Let \(k\in \mathbb {N}\) be fixed. Then,
(See Definition 2.10 (a) for the meaning of \(p_{i}\left( n\right) \).)
Let \(X\) be a set.
(a) A permutation of \(X\) means a bijection from \(X\) to \(X\).
(b) It is known that the set of all permutations of \(X\) is a group under composition. This group is called the symmetric group of \(X\), and is denoted by \(S_X\). Its neutral element is the identity map \(\operatorname {id}_X : X \to X\). Its size is \(|X|!\) when \(X\) is finite.
(c) As usual in group theory, we will write \(\alpha \beta \) for the composition \(\alpha \circ \beta \) when \(\alpha , \beta \in S_X\). This is the map that sends each \(x \in X\) to \(\alpha (\beta (x))\).
(d) If \(\alpha \in S_X\) and \(i \in \mathbb {Z}\), then \(\alpha ^i\) shall denote the \(i\)-th power of \(\alpha \) in the group \(S_X\). Note that \(\alpha ^i = \underbrace{\alpha \circ \alpha \circ \cdots \circ \alpha }_{i\text{ times}}\) if \(i \ge 0\). Also, \(\alpha ^0 = \operatorname {id}_X\). Also, \(\alpha ^{-1}\) is the inverse of \(\alpha \) in the group \(S_X\), that is, the inverse of the map \(\alpha \).
Let \(n \in \mathbb {Z}\). Then, \([n]\) shall mean the set \(\{ 1, 2, \ldots , n\} \). This is an \(n\)-element set if \(n \ge 0\), and is an empty set if \(n \le 0\).
The symmetric group \(S_{[n]}\) (consisting of all permutations of \([n]\)) will be denoted \(S_n\) and called the \(n\)-th symmetric group. Its size is \(n!\) (when \(n \ge 0\)).
Let \(X\) and \(Y\) be two sets, and let \(f : X \to Y\) be a bijection. Then, for each permutation \(\sigma \) of \(X\), the map \(f \circ \sigma \circ f^{-1} : Y \to Y\) is a permutation of \(Y\). Furthermore, the map
is a group isomorphism; thus, we obtain \(S_X \cong S_Y\).
Let \(n \in \mathbb {N}\) and \(\sigma \in S_n\). We introduce three notations for \(\sigma \):
(a) A two-line notation of \(\sigma \) means a \(2 \times n\)-array
where the entries \(p_1, p_2, \ldots , p_n\) of the top row are the \(n\) elements of \([n]\) in some order. Commonly, we pick \(p_i = i\).
(b) The one-line notation (short, OLN) of \(\sigma \) means the \(n\)-tuple \((\sigma (1), \sigma (2), \ldots , \sigma (n))\).
(c) The cycle digraph of \(\sigma \) is the directed graph with vertices \(1, 2, \ldots , n\) and arcs \(i \to \sigma (i)\) for all \(i \in [n]\).
Let \(i\) and \(j\) be two distinct elements of a set \(X\).
Then, the transposition \(t_{i,j}\) is the permutation of \(X\) that sends \(i\) to \(j\), sends \(j\) to \(i\), and leaves all other elements of \(X\) unchanged.
Let \(n \in \mathbb {N}\) and \(i \in [n-1]\). Then, the simple transposition \(s_i\) is defined by
Let \(n \in \mathbb {N}\).
(a) We have \(s_i^2 = \operatorname {id}\) for all \(i \in [n-1]\). In other words, we have \(s_i = s_i^{-1}\) for all \(i \in [n-1]\).
(b) We have \(s_i s_j = s_j s_i\) for any \(i, j \in [n-1]\) with \(|i - j| {\gt} 1\).
(c) We have \(s_i s_{i+1} s_i = s_{i+1} s_i s_{i+1}\) for any \(i \in [n-2]\).
Let \(X\) be a set. Let \(i_1, i_2, \ldots , i_k\) be \(k\) distinct elements of \(X\). Then,
means the permutation of \(X\) that sends
and leaves all other elements of \(X\) unchanged. In other words, \(\operatorname {cyc}_{i_1, i_2, \ldots , i_k}\) means the permutation of \(X\) that satisfies
for every \(p \in X\), where \(i_{k+1}\) means \(i_1\).
This permutation is called a \(k\)-cycle.
Let \(X\) be a set. An involution of \(X\) means a map \(f : X \to X\) that satisfies \(f \circ f = \operatorname {id}\). Clearly, an involution is always a permutation, and equals its own inverse.
Let \(n\in \mathbb {N}\) and \(\sigma \in S_{n}\).
(a) An inversion of \(\sigma \) means a pair \(\left(i,j\right)\) of elements of \(\left[n\right]\) such that \(i{\lt}j\) and \(\sigma \left(i\right) {\gt}\sigma \left(j\right)\).
(b) The length (also known as the Coxeter length) of \(\sigma \) is the # of inversions of \(\sigma \). It is called \(\ell \left( \sigma \right)\).
Let \(n\in \mathbb {N}\).
(a) For any \(\sigma \in S_{n}\), we have \(\ell \left(\sigma \right) \in \left\{ 0,1,\ldots ,\binom {n}{2}\right\} \).
(b) We have
Indeed, the only permutation \(\sigma \in S_{n}\) with \(\ell \left( \sigma \right)=0\) is the identity map \(\operatorname {id}\).
(c) We have
Indeed, the only permutation \(\sigma \in S_{n}\) with \(\ell \left( \sigma \right)=\binom {n}{2}\) is the permutation with OLN \(n\left( n-1\right)\left(n-2\right)\cdots 21\), often called \(w_{0}\).
(d) If \(n\geq 1\), then
Indeed, the only permutations \(\sigma \in S_{n}\) with \(\ell \left( \sigma \right)=1\) are the simple transpositions \(s_{i}\) with \(i\in \left[ n-1\right]\).
(e) If \(n\geq 2\), then
Indeed, the only permutations \(\sigma \in S_{n}\) with \(\ell \left( \sigma \right)=2\) are the products \(s_{i}s_{j}\) with \(1\leq i{\lt}j{\lt}n\) as well as the products \(s_{i}s_{i-1}\) with \(i\in \left\{ 2,3,\ldots ,n-1\right\} \). If \(n\geq 2\), then there are \(\frac{\left(n-2\right)\left(n+1\right)}{2}\) such products (and they are all distinct).
(f) For any \(k\in \mathbb {Z}\), we have
Let \(n\in \mathbb {N}\). Then,
Let \(n\in \mathbb {N}\).
(a) For each \(\sigma \in S_{n}\) and \(i\in \left[n\right]\), we set
(b) For each \(m\in \mathbb {Z}\), we let \(\left[m\right]_{0}\) denote the set \(\left\{ 0,1,\ldots ,m\right\} \). (This is an empty set when \(m{\lt}0\).)
(c) We let \(H_{n}\) denote the set
This set \(H_{n}\) has size \(n!\).
(d) Each \(\sigma \in S_n\) and each \(i\in [n]\) satisfy \(\ell _i(\sigma ) \in \{ 0,1,\ldots ,n-i\} = [n-i]_0\).
(e) We define the map
If \(\sigma \in S_{n}\) is a permutation, then the \(n\)-tuple \(L\left(\sigma \right)\) is called the Lehmer code (or just the code) of \(\sigma \).
Let \(n\in \mathbb {N}\) and \(\sigma \in S_{n}\). Then, \(\ell \left(\sigma \right)=\ell _{1}\left(\sigma \right)+\ell _{2}\left( \sigma \right)+\cdots +\ell _{n}\left(\sigma \right)\).
Let \(n\in \mathbb {N}\). Then, the map \(L:S_{n}\rightarrow H_{n}\) is a bijection.
Let \(\left(a_{1},a_{2},\ldots ,a_{n}\right)\) and \(\left(b_{1},b_{2},\ldots ,b_{n}\right)\) be two \(n\)-tuples of integers. We say that
if and only if
there exists some \(k\in \left[n\right]\) such that \(a_{k}\neq b_{k}\), and
the smallest such \(k\) satisfies \(a_{k}{\lt}b_{k}\).
The relation \({\lt}_{\operatorname {lex}}\) is a strict total order on \(\mathbb {Z}^n\) (the lexicographic order).
If \(\mathbf{a}\) and \(\mathbf{b}\) are two distinct \(n\)-tuples of integers, then we have either \(\mathbf{a} {\lt}_{\operatorname {lex}}\mathbf{b}\) or \(\mathbf{b}{\lt}_{\operatorname {lex}} \mathbf{a}\).
Let \(\sigma \in S_{n}\) and \(\tau \in S_{n}\) be such that
Then,
(In other words, \(L\left(\sigma \right) {\lt}_{\operatorname {lex}} L\left( \tau \right)\).)
Let \(n \in \mathbb {N}\), \(\sigma \in S_n\) and \(k \in [n-1]\). Then:
(a) We have
(b) We have
Let \(n \in \mathbb {N}\) and \(\sigma \in S_n\). Let \(i\) and \(j\) be two elements of \([n]\) such that \(i {\lt} j\). Then:
(a) We have \(\ell (\sigma t_{i,j}) {\lt} \ell (\sigma )\) if \(\sigma (i) {\gt} \sigma (j)\). We have \(\ell (\sigma t_{i,j}) {\gt} \ell (\sigma )\) if \(\sigma (i) {\lt} \sigma (j)\).
(b) We have
where
Let \(n \in \mathbb {N}\) and \(\sigma \in S_n\). Then:
(a) We can write \(\sigma \) as a composition (i.e., product) of \(\ell (\sigma )\) simples.
(b) The number \(\ell (\sigma )\) is the smallest \(p \in \mathbb {N}\) such that we can write \(\sigma \) as a composition of \(p\) simples.
Keep in mind: The composition of \(0\) simples is \(\mathrm{id}\), since \(\mathrm{id}\) is the neutral element of the group \(S_n\).
Let \(n \in \mathbb {N}\).
(a) We have \(\ell (\sigma \tau ) \equiv \ell (\sigma ) + \ell (\tau ) \pmod{2}\) for all \(\sigma , \tau \in S_n\).
(b) We have \(\ell (\sigma \tau ) \leq \ell (\sigma ) + \ell (\tau )\) for all \(\sigma , \tau \in S_n\).
(c) Let \(k_1, k_2, \ldots , k_q \in [n-1]\), and let \(\sigma = s_{k_1} s_{k_2} \cdots s_{k_q}\). Then \(q \geq \ell (\sigma )\) and \(q \equiv \ell (\sigma ) \pmod{2}\).
Let \(n \in \mathbb {N}\) and \(\sigma \in S_n\). For each \(i \in [n]\), set
where \(i' = i + \ell _i(\sigma )\). Then \(\sigma = a_0 a_1 \cdots a_{n-1}\).
In other words, the product of the canonical reduced word equals \(\sigma \).
Let \(n \in \mathbb {N}\). The sign of a permutation \(\sigma \in S_n\) is defined to be the integer \((-1)^{\ell (\sigma )}\).
It is denoted by \((-1)^{\sigma }\) or \(\operatorname {sgn}(\sigma )\) or \(\operatorname {sign}(\sigma )\) or \(\varepsilon (\sigma )\). It is also known as the signature of \(\sigma \).
Let \(n \in \mathbb {N}\).
(a) The sign of the identity permutation \(\operatorname {id} \in S_n\) is \((-1)^{\operatorname {id}} = 1\).
(b) For any two distinct elements \(i\) and \(j\) of \([n]\), the transposition \(t_{i,j} \in S_n\) has sign \((-1)^{t_{i,j}} = -1\).
(c) For any positive integer \(k\) and any distinct elements \(i_1, i_2, \ldots , i_k \in [n]\), the \(k\)-cycle \(\operatorname {cyc}_{i_1, i_2, \ldots , i_k}\) has sign \((-1)^{\operatorname {cyc}_{i_1, i_2, \ldots , i_k}} = (-1)^{k-1}\).
(d) We have \((-1)^{\sigma \tau } = (-1)^{\sigma } \cdot (-1)^{\tau }\) for any \(\sigma \in S_n\) and \(\tau \in S_n\).
(e) We have \((-1)^{\sigma _1 \sigma _2 \cdots \sigma _p} = (-1)^{\sigma _1} (-1)^{\sigma _2} \cdots (-1)^{\sigma _p}\) for any \(\sigma _1, \sigma _2, \ldots , \sigma _p \in S_n\).
(f) We have \((-1)^{\sigma ^{-1}} = (-1)^{\sigma }\) for any \(\sigma \in S_n\). (The left hand side here has to be understood as \((-1)^{(\sigma ^{-1})}\).)
(g) We have
(The product sign “\(\prod _{1 \leq i {\lt} j \leq n}\)” means a product over all pairs \((i,j)\) of integers satisfying \(1 \leq i {\lt} j \leq n\). There are \(\binom {n}{2}\) such pairs.)
(h) If \(x_1, x_2, \ldots , x_n\) are any elements of some commutative ring, and if \(\sigma \in S_n\), then
Let \(n \in \mathbb {N}\). The map
is a group homomorphism from the symmetric group \(S_n\) to the order-\(2\) group \(\{ 1, -1\} \). (Of course, \(\{ 1, -1\} \) is a group with respect to multiplication.)
Let \(n \in \mathbb {N}\). A permutation \(\sigma \in S_n\) is said to be
even if \((-1)^{\sigma } = 1\) (that is, if \(\ell (\sigma )\) is even);
odd if \((-1)^{\sigma } = -1\) (that is, if \(\ell (\sigma )\) is odd).
Let \(n \in \mathbb {N}\). The set of all even permutations in \(S_n\) is a normal subgroup of \(S_n\).
Let \(n \geq 2\). Then,
Let \(X\) be a finite set. We want to define the sign of any permutation of \(X\).
Fix a bijection \(\phi : X \to [n]\) for some \(n \in \mathbb {N}\). (Such a bijection always exists, since \(X\) is finite.) For every permutation \(\sigma \) of \(X\), set
Here, the right hand side is well-defined, since \(\phi \circ \sigma \circ \phi ^{-1}\) is a permutation of \([n]\). Now:
(a) This number \((-1)_{\phi }^{\sigma }\) depends only on the permutation \(\sigma \), but not on the bijection \(\phi \). (In other words, if \(\phi _1\) and \(\phi _2\) are two bijections from \(X\) to \([n]\), then \((-1)_{\phi _1}^{\sigma } = (-1)_{\phi _2}^{\sigma }\).)
Thus, we shall denote \((-1)_{\phi }^{\sigma }\) by \((-1)^{\sigma }\) from now on. We refer to this number \((-1)^{\sigma }\) as the sign of the permutation \(\sigma \in S_X\). (When \(X = [n]\), this notation does not clash with Definition 3.109, since we can pick the bijection \(\phi = \operatorname {id}\) and obtain \((-1)_{\phi }^{\sigma } = (-1)^{\operatorname {id} \circ \sigma \circ \operatorname {id}^{-1}} = (-1)^{\sigma }\).)
(b) The identity permutation \(\operatorname {id} : X \to X\) satisfies \((-1)^{\operatorname {id}} = 1\).
(c) We have \((-1)^{\sigma \tau } = (-1)^{\sigma } \cdot (-1)^{\tau }\) for any two permutations \(\sigma \) and \(\tau \) of \(X\).
Let \(X\) be a finite set. Let \(\sigma \) be a permutation of \(X\). Then:
(a) There is a list
of nonempty lists of elements of \(X\) such that:
each element of \(X\) appears exactly once in the composite list
and
we have
Such a list is called a disjoint cycle decomposition (or short DCD) of \(\sigma \). Its entries (which themselves are lists of elements of \(X\)) are called the cycles of \(\sigma \).
(b) Any two DCDs of \(\sigma \) can be obtained from each other by (repeatedly) swapping the cycles with each other, and rotating each cycle (i.e., replacing \(\left( a_{i,1},a_{i,2},\ldots ,a_{i,n_{i}}\right) \) by \(\left( a_{i,2},a_{i,3},\ldots ,a_{i,n_{i}},a_{i,1}\right) \)).
(c) Now assume that \(X\) is a set of integers (or, more generally, any totally ordered finite set). Then, there is a unique DCD
of \(\sigma \) that satisfies the additional requirements that
we have \(a_{i,1}\leq a_{i,p}\) for each \(i\in \left[ k\right] \) and each \(p\in \left[ n_{i}\right] \) (that is, each cycle in this DCD is written with its smallest entry first), and
we have \(a_{1,1}{\gt}a_{2,1}{\gt}\cdots {\gt}a_{k,1}\) (that is, the cycles appear in this DCD in the order of decreasing first entries).
Let \(X\) be a finite set. Let \(\sigma \) be a permutation of \(X\).
(a) The cycles of \(\sigma \) are defined to be the cycles in the DCD of \(\sigma \) (as defined in Theorem 3.123 (a)). (This includes \(1\)-cycles, if there are any in the DCD of \(\sigma \).)
We shall equate a cycle of \(\sigma \) with any of its cyclic rotations; thus, for example, \(\left( 3,1,4\right) \) and \(\left( 1,4,3\right) \) shall be regarded as being the same cycle (but \(\left( 3,1,4\right) \) and \(\left( 3,4,1\right) \) shall not).
(b) The cycle lengths partition of \(\sigma \) shall denote the partition of \(\left\vert X\right\vert \) obtained by writing down the lengths of the cycles of \(\sigma \) in weakly decreasing order.
Let \(X\) be a finite set. Let \(i,j\in X\). Let \(\sigma \) be a permutation of \(X\). Then, we have the following chain of equivalences:
Let \(n\in \mathbb {N}\). Let \(\sigma \in S_{n}\). Let \(k\in \mathbb {N}\) be such that \(\sigma \) has exactly \(k\) cycles (including the \(1\)-cycles). Then, \(\left( -1\right) ^{\sigma }=\left( -1\right) ^{n-k}\).
Let \(n\in \mathbb {C}\) and \(m\in \mathbb {N}\). Then,
Let \(\mathcal{A}\) be a finite set. Let \(\mathcal{X}\) be a subset of \(\mathcal{A}\).
For each \(I \in \mathcal{A}\), let \(\operatorname {sign} I\) be an element of an additive abelian group \(R\) with no \(2\)-torsion (i.e., \(2a = 0\) implies \(a = 0\)). Let \(f : \mathcal{X} \to \mathcal{X}\) be a bijection with the property that
(Such a bijection \(f\) is called sign-reversing.) Then,
Let \(\mathcal{A}\) be a finite set. Let \(\mathcal{X}\) be a subset of \(\mathcal{A}\).
For each \(I \in \mathcal{A}\), let \(\operatorname {sign} I\) be an element of some additive abelian group. Let \(f : \mathcal{X} \to \mathcal{X}\) be an involution (i.e., a map satisfying \(f \circ f = \operatorname {id}\)) that has no fixed points. Assume that
Then,
Let \(\mathcal{A}\) be a finite set. Let \(\mathcal{X}\) be a subset of \(\mathcal{A}\).
For each \(I \in \mathcal{A}\), let \(\operatorname {sign} I\) be an element of some additive abelian group. Let \(f : \mathcal{X} \to \mathcal{X}\) be an involution (i.e., a map satisfying \(f \circ f = \operatorname {id}\)). Assume that
Assume furthermore that
Then,
Let \(K\) be a field. Let \(d\) be a positive integer.
(a) A \(d\)-th root of unity in \(K\) means an element \(\omega \) of \(K\) satisfying \(\omega ^d = 1\).
(b) A primitive \(d\)-th root of unity in \(K\) means an element \(\omega \) of \(K\) satisfying \(\omega ^d = 1\) but \(\omega ^i \neq 1\) for each \(i \in \{ 1, 2, \ldots , d-1\} \). In other words, a primitive \(d\)-th root of unity in \(K\) means an element of the multiplicative group \(K^{\times }\) whose order is \(d\).
Let \(K\) be a field. Let \(d\) be a positive integer. Let \(\omega \) be a primitive \(d\)-th root of unity in \(K\). Let \(n, k \in \mathbb {N}\). Let \(q\) and \(u\) be the quotients obtained when dividing \(n\) and \(k\) by \(d\) with remainder, and let \(r\) and \(v\) be the respective remainders. Then,
Let \(n \in \mathbb {N}\). Let \(U\) be a finite set. Let \(A_1, A_2, \ldots , A_n\) be \(n\) subsets of \(U\). Then,
Equivalently,
where \(\bigcap _{i \in I} A_i\) denotes \(\{ u \in U \mid u \in A_i \text{ for all } i \in I\} \) (so that \(\bigcap _{i \in \varnothing } A_i = U\)).
Let \(n, m \in \mathbb {N}\). Then,
Let \(n \in \mathbb {N}\). Then:
(a) We have \(\sum _{k=0}^{n} (-1)^k \binom {n}{k} (n-k)^m = 0\) for any \(m \in \mathbb {N}\) satisfying \(m {\lt} n\).
(b) We have \(\sum _{k=0}^{n} (-1)^k \binom {n}{k} (n-k)^n = n!\).
(c) We have \(\sum _{k=0}^{n} (-1)^k \binom {n}{k} (n-k)^m \geq 0\) for each \(m \in \mathbb {N}\).
(d) We have \(n! \mid \sum _{k=0}^{n} (-1)^k \binom {n}{k} (n-k)^m\) for each \(m \in \mathbb {N}\).
A derangement of a set \(X\) means a permutation of \(X\) that has no fixed points.
Let \(n \in \mathbb {N}\). Then, the number of derangements of \([n]\) is
Let \(c\) be a positive integer with prime factorization \(p_1^{a_1} p_2^{a_2} \cdots p_n^{a_n}\), where \(p_1, p_2, \ldots , p_n\) are distinct primes and \(a_1, a_2, \ldots , a_n\) are positive integers. Then,
Let \(n \in \mathbb {N}\), and let \(U\) be a finite set. Let \(A_1, A_2, \ldots , A_n\) be \(n\) subsets of \(U\). Let \(G\) be any additive abelian group. Let \(w\colon U \to G\) be any map. Then,
Let \(S\) be a finite set. Let \(A\) be any additive abelian group.
For each subset \(I\) of \(S\), let \(a_{I}\) and \(b_{I}\) be two elements of \(A\).
Assume that
Then, we also have
Let \(P \subseteq Q\) be two finite sets.
(a) We have
(b) We have
Let \(n\in \mathbb {N}\) and \(d\in \mathbb {N}\). Then, the number of all all-even \(n\)-tuples \(\left( x_{1},x_{2},\ldots ,x_{n}\right) \in \left[ d\right] ^{n}\) is
More precisely (avoiding division), the number of all-even \(n\)-tuples multiplied by \(2^d\) equals \(\sum _{k=0}^{d}\binom {d}{k}(d-2k)^n\).
Let \(n,d\in \mathbb {N}\). Then,
Let \(n,d\in \mathbb {N}\). Let \(\left( x_{1},x_{2},\ldots ,x_{n}\right) \in \left[ d\right] ^{n}\).
(a) If the \(n\)-tuple \(\left( x_{1},x_{2},\ldots ,x_{n}\right)\) is not all-even, then \(\sum _{\left( e_{1},\ldots ,e_{d}\right) \in \left\{ 1,-1\right\} ^{d}} e_{x_{1}}e_{x_{2}}\cdots e_{x_{n}}=0\).
(b) If the \(n\)-tuple \(\left( x_{1},x_{2},\ldots ,x_{n}\right)\) is all-even, then \(\sum _{\left( e_{1},\ldots ,e_{d}\right) \in \left\{ 1,-1\right\} ^{d}} e_{x_{1}}e_{x_{2}}\cdots e_{x_{n}}=2^{d}\).
Let \(n \in \mathbb {N}\). Let \(A \in K^{n \times n}\) be an \(n \times n\)-matrix. The determinant \(\det A\) of \(A\) is defined to be the element
of \(K\). Here:
we let \(S_n\) denote the \(n\)-th symmetric group (i.e., the group of permutations of \([n] = \{ 1, 2, \ldots , n\} \));
we let \((-1)^{\sigma }\) denote the sign of the permutation \(\sigma \) (as defined in Definition 3.109).
Let \(n \in \mathbb {N}\) be such that \(n \geq 2\). Let \(x_1, x_2, \ldots , x_n \in K\) and \(y_1, y_2, \ldots , y_n \in K\). Then,
Let \(n \in \mathbb {N}\) be such that \(n \geq 3\). Let \(x_1, x_2, \ldots , x_n \in K\) and \(y_1, y_2, \ldots , y_n \in K\). Then,
Let \(n \in \mathbb {N}\). If \(A \in K^{n \times n}\) is any \(n \times n\)-matrix, then \(\det (A^T) = \det A\).
Let \(n \in \mathbb {N}\). Let \(A \in K^{n \times n}\) be a triangular (i.e., lower-triangular or upper-triangular) \(n \times n\)-matrix. Then, the determinant of the matrix \(A\) is the product of its diagonal entries. That is,
Let \(n \in \mathbb {N}\). Let \(A \in K^{n \times n}\) be an \(n \times n\)-matrix. Then:
(a) If we swap two rows of \(A\), then \(\det A\) gets multiplied by \(-1\).
(b) If \(A\) has a zero row (i.e., a row that consists entirely of zeroes), then \(\det A = 0\).
(c) If \(A\) has two equal rows, then \(\det A = 0\).
(d) Let \(\lambda \in K\). If we multiply a row of \(A\) by \(\lambda \) (that is, we multiply all entries of this one row by \(\lambda \), while leaving all other entries of \(A\) unchanged), then \(\det A\) gets multiplied by \(\lambda \).
(e) If we add a row of \(A\) to another row of \(A\) (that is, we add each entry of the former row to the corresponding entry of the latter), then \(\det A\) stays unchanged.
(f) Let \(\lambda \in K\). If we add \(\lambda \) times a row of \(A\) to another row of \(A\) (that is, we add \(\lambda \) times each entry of the former row to the corresponding entry of the latter), then \(\det A\) stays unchanged.
(g) Let \(B, C \in K^{n \times n}\) be two further \(n \times n\)-matrices. Let \(k \in [n]\). Assume that
whereas each \(i \neq k\) satisfies
Then,
Let \(n \in \mathbb {N}\). Let \(A \in K^{n \times n}\) and \(\tau \in S_n\). Then,
and
Let \(n \in \mathbb {N}\). Let \(A, B \in K^{n \times n}\) be two \(n \times n\)-matrices. Then,
Let \(n \in \mathbb {N}\). Let \(A \in K^{n \times n}\) and \(d_1, d_2, \ldots , d_n \in K\). Then,
and
Let \(n,m\in \mathbb {N}\). Let \(A\in K^{n\times m}\) be an \(n\times m\)-matrix, and let \(B\in K^{m\times n}\) be an \(m\times n\)-matrix. Then,
Here, \(\operatorname {cols}_{g_1,\ldots ,g_n} A\) is the \(n\times n\)-matrix obtained from \(A\) by keeping only columns \(g_1,g_2,\ldots ,g_n\), and \(\operatorname {rows}_{g_1,\ldots ,g_n} B\) is the \(n\times n\)-matrix obtained from \(B\) by keeping only rows \(g_1,g_2,\ldots ,g_n\).
Equivalently, the sum runs over all \(n\)-element subsets \(S\) of \([m]\):
Let \(n,m\in \mathbb {N}\). Let \(A\) be an \(n\times m\)-matrix.
Let \(U\) be a subset of \([n]\). Let \(V\) be a subset of \([m]\).
Writing the two sets \(U\) and \(V\) as
with
we set
Roughly speaking, \(\operatorname {sub}_U^V A\) is the matrix obtained from \(A\) by focusing only on the \(i\)-th rows for \(i\in U\) (that is, removing all the other rows) and only on the \(j\)-th columns for \(j\in V\) (that is, removing all the other columns).
This matrix \(\operatorname {sub}_U^V A\) is called the submatrix of \(A\) obtained by restricting to the \(U\)-rows and the \(V\)-columns. If this matrix is square (i.e., if \(|U|=|V|\)), then its determinant \(\det (\operatorname {sub}_U^V A)\) is called a minor of \(A\).
Let \(n\in \mathbb {N}\). For any subset \(I\) of \([n]\), let \(\widetilde{I} = [n]\setminus I\) denote its complement.
Let \(A\) and \(B\) be two \(n\times n\)-matrices in \(K^{n\times n}\). Then,
Let \(n\in \mathbb {N}\). Let \(d_1,d_2,\ldots ,d_n\in K\). Let
(a) We have \(\det (\operatorname {sub}_P^P D) = \prod _{i\in P} d_i\) for any subset \(P\) of \([n]\).
(b) Let \(P\) and \(Q\) be two distinct subsets of \([n]\) satisfying \(|P|=|Q|\). Then, \(\det (\operatorname {sub}_P^Q D) = 0\).
Let \(n\in \mathbb {N}\). Let \(A\) and \(D\) be two \(n\times n\)-matrices in \(K^{n\times n}\) such that the matrix \(D\) is diagonal. Let \(d_1,d_2,\ldots ,d_n\) be the diagonal entries of the diagonal matrix \(D\). Then,
The minors \(\det (\operatorname {sub}_P^P A)\) are called the principal minors of \(A\).
Let \(n\in \mathbb {N}\). Let \(d_1,d_2,\ldots ,d_n\in K\) and \(x\in K\). Let \(F\) be the \(n\times n\)-matrix
Then,
where the hat over “\(d_i\)” means “omit the \(d_i\) factor.”
Let \(n\in \mathbb {N}\). Let \(A\in K^{n\times n}\) be an \(n\times n\)-matrix. Let \(x\in K\). Let \(I_n\) denote the \(n\times n\) identity matrix. Then,
Let \(n\in \mathbb {N}\). Let \(A\) be the \(n\times n\)-matrix
Then \(\det A = 1\).
Let \(n \in \mathbb {N}\). Let \(a_1, a_2, \ldots , a_n\) be \(n\) elements of \(K\). Then:
(a) We have
(b) We have
(c) We have
(d) We have
Let \(n \in \mathbb {N}\). Consider the polynomial ring \(\mathbb {Z}[x_1, x_2, \ldots , x_n]\) in \(n\) indeterminates \(x_1, x_2, \ldots , x_n\) with integer coefficients. In this ring, we have
Let \(n \in \mathbb {N}\). Let \(A\) be an \(n \times n\)-matrix. Let \(i, j \in [n]\). Then, we set
This is the \((n-1) \times (n-1)\)-matrix obtained from \(A\) by removing its \(i\)-th row and its \(j\)-th column.
Let \(n \in \mathbb {N}\). Let \(A \in K^{n \times n}\) be an \(n \times n\)-matrix.
(a) For every \(p \in [n]\), we have
(b) For every \(q \in [n]\), we have
Let \(n \in \mathbb {N}\). Let \(A \in K^{n \times n}\) be an \(n \times n\)-matrix. Let \(r \in [n]\).
(a) For every \(p \in [n]\) satisfying \(p \neq r\), we have
(b) For every \(q \in [n]\) satisfying \(q \neq r\), we have
Let \(n \in \mathbb {N}\). Let \(A \in K^{n \times n}\) be an \(n \times n\)-matrix. We define a new \(n \times n\)-matrix \(\operatorname {adj} A \in K^{n \times n}\) by
This matrix \(\operatorname {adj} A\) is called the adjugate (or classical adjoint) of the matrix \(A\). Note the index swap: the \((i,j)\) entry involves removing row \(j\) and column \(i\).
The formalization shows that this definition equals Mathlib’s Matrix.adjugate, which is defined via \((\operatorname {adj} A)_{i,j} = \det (A')\) where \(A'\) is the matrix \(A\) with row \(j\) replaced by the \(i\)-th standard basis vector.
For any subset \(I\) of \([n]\), we write \(\widetilde{I} = [n] \setminus I\) for its complement, and \(\operatorname {sum} S = \sum _{s \in S} s\) for any finite set \(S\) of integers.
Let \(n \in \mathbb {N}\). Let \(A \in K^{n \times n}\) be an \(n \times n\)-matrix.
(a) For every subset \(P\) of \([n]\), we have
(b) For every subset \(Q\) of \([n]\), we have
Let \(n \in \mathbb {N}\) be such that \(n \geq 2\). Let \(A \in K^{n \times n}\) be an \(n \times n\)-matrix.
Let \(A'\) be the \((n-2) \times (n-2)\)-matrix
(This is what remains of \(A\) when we remove the first row, the last row, the first column and the last column.) Then,
Let \(n \in \mathbb {N}\) be such that \(n \geq 2\). Let \(p, q, u, v\) be four elements of \([n]\) such that \(p {\lt} q\) and \(u {\lt} v\). Let \(A\) be an \(n \times n\)-matrix. Then,
Let \(n \in \mathbb {N}\). For any subset \(I\) of \([n]\), let \(\widetilde{I}\) denote the complement \([n] \setminus I\). Set \(\operatorname {sum} S = \sum _{s \in S} s\) for any finite set \(S\) of integers.
Let \(A \in K^{n \times n}\) be an \(n \times n\)-matrix. Let \(P\) and \(Q\) be two subsets of \([n]\) such that \(|P| = |Q| \geq 1\). Then,
We consider the infinite simple digraph with vertex set \(\mathbb {Z}^{2}\) (so the vertices are pairs of integers) and arcs
and
The arcs of the first form are called east-steps or right-steps; the arcs of the second form are called north-steps or up-steps.
The vertices of this digraph will be called lattice points or grid points or simply points.
The entire digraph will be denoted by \(\mathbb {Z}^{2}\) and called the integer lattice or integer grid.
Any path is uniquely determined by its starting point and its step sequence.
Let \(\left( a,b\right) \in \mathbb {Z}^{2}\) and \(\left( c,d\right) \in \mathbb {Z}^{2}\) be two points. Then,
Let \(k\in \mathbb {N}\).
(a) A \(k\)-vertex means a \(k\)-tuple of lattice points.
(b) If \(\mathbf{A}=\left( A_{1},A_{2},\ldots ,A_{k}\right) \) is a \(k\)-vertex, and if \(\sigma \in S_{k}\) is a permutation, then \(\sigma \left( \mathbf{A}\right) \) shall denote the \(k\)-vertex \(\left( A_{\sigma \left( 1\right) },A_{\sigma \left( 2\right) },\ldots ,A_{\sigma \left( k\right) }\right) \).
(c) If \(\mathbf{A}=\left( A_{1},A_{2},\ldots ,A_{k}\right) \) and \(\mathbf{B}=\left( B_{1},B_{2},\ldots ,B_{k}\right) \) are two \(k\)-vertices, then a path tuple from \(\mathbf{A}\) to \(\mathbf{B}\) means a \(k\)-tuple \(\left( p_{1},p_{2},\ldots ,p_{k}\right) \), where each \(p_{i}\) is a path from \(A_{i}\) to \(B_{i}\).
(d) A path tuple \(\left( p_{1},p_{2},\ldots ,p_{k}\right) \) is said to be non-intersecting if no two of the paths \(p_{1},p_{2},\ldots ,p_{k}\) have any vertex in common. We abbreviate “non-intersecting path tuple” as nipat.
(e) A path tuple \(\left( p_{1},p_{2},\ldots ,p_{k}\right) \) is said to be intersecting if it is not non-intersecting (i.e., if two of its paths have a vertex in common). We abbreviate “intersecting path tuple” as ipat.
The i-th path in the tuple
Each path goes from A_i to B_i
Let \(\left( A,A^{\prime }\right) \) and \(\left( B,B^{\prime }\right) \) be two \(2\)-vertices (i.e., let \(A,A^{\prime },B,B^{\prime }\) be four lattice points). Then,
Let \(A\), \(B\), \(A^{\prime }\) and \(B^{\prime }\) be four lattice points satisfying
(That is, \(A'\) is weakly northwest of \(A\), and \(B'\) is weakly northwest of \(B\).)
Let \(p\) be any path from \(A\) to \(B^{\prime }\). Let \(p^{\prime }\) be any path from \(A^{\prime }\) to \(B\). Then, \(p\) and \(p^{\prime }\) have a vertex in common.
In particular, there are no nipats from \((A, A')\) to \((B', B)\).
Let \(k\in \mathbb {N}\). Let \(\mathbf{A}=\left( A_{1},A_{2},\ldots ,A_{k}\right) \) and \(\mathbf{B}=\left( B_{1},B_{2},\ldots ,B_{k}\right) \) be two \(k\)-vertices. Then,
Let \(K\) be a commutative ring.
For each arc \(a\) of the digraph \(\mathbb {Z}^{2}\), let \(w(a)\) be an element of \(K\). We call \(w(a)\) the weight of \(a\).
For each path \(p\) of \(\mathbb {Z}^{2}\), define the weight \(w(p)\) of \(p\) by
For each path tuple \(\mathbf{p} = (p_1, p_2, \ldots , p_k)\), define the weight \(w(\mathbf{p})\) of \(\mathbf{p}\) by
Let \(k \in \mathbb {N}\). Let \(\mathbf{A} = (A_1, A_2, \ldots , A_k)\) and \(\mathbf{B} = (B_1, B_2, \ldots , B_k)\) be two \(k\)-vertices. Then,
Here, “\(p : A_i \to B_j\)” means “\(p\) is a path from \(A_i\) to \(B_j\)”.
Let \(K\) be a commutative ring.
Let \(D\) be a path-finite (but possibly infinite) acyclic digraph.
For each arc \(a\) of \(D\), let \(w(a) \in K\). For each path \(p\) of \(D\), define \(w(p) := \prod _{a \text{ is an arc of } p} w(a)\). For each path tuple \(\mathbf{p} = (p_1, \ldots , p_k)\), define \(w(\mathbf{p}) := w(p_1) \cdots w(p_k)\).
Let \(k \in \mathbb {N}\). Let \(\mathbf{A} = (A_1, \ldots , A_k)\) and \(\mathbf{B} = (B_1, \ldots , B_k)\) be two \(k\)-tuples of vertices of \(D\). Then,
Consider the setting of Theorem 5.154, but additionally assume that
Here, \(\operatorname {x}(P)\) and \(\operatorname {y}(P)\) denote the two coordinates of any point \(P \in \mathbb {Z}^2\).
Then, there are no nipats from \(\mathbf{A}\) to \(\sigma (\mathbf{B})\) when \(\sigma \in S_k\) is not the identity permutation \(\operatorname {id} \in S_k\). Therefore, the claim of Theorem 5.154 simplifies to
Let \(k \in \mathbb {N}\). Let \(a_1, a_2, \ldots , a_k\) and \(b_1, b_2, \ldots , b_k\) be nonnegative integers such that
Then,
(a) Let \(\mathcal{P}\) be the polynomial ring \(K[x_1, x_2, \ldots , x_N]\) in \(N\) variables over \(K\). This is not just a ring; it is a commutative \(K\)-algebra.
(b) The symmetric group \(S_N\) acts on the set \(\mathcal{P}\) according to the formula
Here, \(f[a_1, a_2, \ldots , a_N]\) means the result of substituting \(a_1, a_2, \ldots , a_N\) for the indeterminates \(x_1, x_2, \ldots , x_N\) in a polynomial \(f \in \mathcal{P}\).
Roughly speaking, the group \(S_N\) is thus acting on \(\mathcal{P}\) by permuting variables: A permutation \(\sigma \in S_N\) transforms a polynomial \(f\) by substituting \(x_{\sigma (i)}\) for each \(x_i\).
Note that this action of \(S_N\) on \(\mathcal{P}\) is a well-defined group action (as we will see in Proposition 6.3 below).
(c) A polynomial \(f \in \mathcal{P}\) is said to be symmetric if it satisfies
(d) We let \(\mathcal{S}\) be the set of all symmetric polynomials \(f \in \mathcal{P}\).
The action of \(S_N\) on \(\mathcal{P}\) is a well-defined group action. In other words, the following holds:
(a) We have \(\operatorname {id}_{[N]} \cdot f = f\) for every \(f \in \mathcal{P}\).
(b) We have \((\sigma \tau ) \cdot f = \sigma \cdot (\tau \cdot f)\) for every \(\sigma , \tau \in S_N\) and \(f \in \mathcal{P}\).
The group \(S_N\) acts on \(\mathcal{P}\) by \(K\)-algebra automorphisms. In other words, for each \(\sigma \in S_N\), the map
is a \(K\)-algebra automorphism of \(\mathcal{P}\).
The \(K\)-subalgebra \(\mathcal{S}\) of \(\mathcal{P}\) is called the ring of symmetric polynomials in \(N\) variables over \(K\).
(a) A monomial is an expression of the form \(x_1^{a_1} x_2^{a_2} \cdots x_N^{a_N}\) with \(a_1, a_2, \ldots , a_N \in \mathbb {N}\).
(b) The degree \(\deg \mathfrak {m}\) of a monomial \(\mathfrak {m} = x_1^{a_1} x_2^{a_2} \cdots x_N^{a_N}\) is defined to be \(a_1 + a_2 + \cdots + a_N \in \mathbb {N}\).
(c) A monomial \(\mathfrak {m} = x_1^{a_1} x_2^{a_2} \cdots x_N^{a_N}\) is said to be squarefree if \(a_1, a_2, \ldots , a_N \in \{ 0,1\} \). (This is saying that no square or higher power of an indeterminate appears in \(\mathfrak {m}\); thus the name “squarefree”.)
(d) A monomial \(\mathfrak {m} = x_1^{a_1} x_2^{a_2} \cdots x_N^{a_N}\) is said to be primal if there is at most one \(i \in [N]\) satisfying \(a_i {\gt} 0\). (This is saying that the monomial \(\mathfrak {m}\) contains no two distinct indeterminates. Thus, a primal monomial is just \(1\) or a power of an indeterminate.)
(a) For each \(n \in \mathbb {Z}\), define a symmetric polynomial \(e_n \in \mathcal{S}\) by
This \(e_n\) is called the \(n\)-th elementary symmetric polynomial in \(x_1, x_2, \ldots , x_N\).
(b) For each \(n \in \mathbb {Z}\), define a symmetric polynomial \(h_n \in \mathcal{S}\) by
This \(h_n\) is called the \(n\)-th complete homogeneous symmetric polynomial in \(x_1, x_2, \ldots , x_N\).
(c) For each \(n \in \mathbb {Z}\), define a symmetric polynomial \(p_n \in \mathcal{S}\) by
This \(p_n\) is called the \(n\)-th power sum in \(x_1, x_2, \ldots , x_N\).
For any positive integer \(n\), we have
(a) In the polynomial ring \(\mathcal{P}[t]\), we have
(b) In the polynomial ring \(\mathcal{P}[u,v]\), we have
(c) In the FPS ring \(\mathcal{P}[[t]]\), we have
(a) The elementary symmetric polynomials \(e_1, e_2, \ldots , e_N\) are algebraically independent (over \(K\)) and generate the \(K\)-algebra \(\mathcal{S}\).
In other words, each \(f \in \mathcal{S}\) can be uniquely written as a polynomial in \(e_1, e_2, \ldots , e_N\).
In yet other words, the map
is a \(K\)-algebra isomorphism.
(b) The complete homogeneous symmetric polynomials \(h_1, h_2, \ldots , h_N\) are algebraically independent (over \(K\)) and generate the \(K\)-algebra \(\mathcal{S}\).
In other words, each \(f \in \mathcal{S}\) can be uniquely written as a polynomial in \(h_1, h_2, \ldots , h_N\).
In yet other words, the map
is a \(K\)-algebra isomorphism.
(c) Now assume that \(K\) is a commutative \(\mathbb {Q}\)-algebra (e.g., a field of characteristic \(0\)). Then, the power sums \(p_1, p_2, \ldots , p_N\) are algebraically independent (over \(K\)) and generate the \(K\)-algebra \(\mathcal{S}\).
In other words, each \(f \in \mathcal{S}\) can be uniquely written as a polynomial in \(p_1, p_2, \ldots , p_N\).
In yet other words, the map
is a \(K\)-algebra isomorphism.
For each \(i \in [N-1]\), let \(s_i \in S_N\) denote the simple transposition that swaps \(i\) and \(i+1\).
Let \(f \in \mathcal{P}\). Assume that
Then, the polynomial \(f\) is symmetric.
An \(N\)-partition will mean a weakly decreasing \(N\)-tuple of nonnegative integers. In other words, an \(N\)-partition means an \(N\)-tuple \(\left( \lambda _{1},\lambda _{2},\ldots ,\lambda _{N}\right) \in \mathbb {N}^{N}\) with \(\lambda _{1}\geq \lambda _{2}\geq \cdots \geq \lambda _{N}\).
The size (or weight) of an \(N\)-partition \(\lambda = (\lambda _1, \lambda _2, \ldots , \lambda _N)\) is defined to be \(|\lambda | := \lambda _1 + \lambda _2 + \cdots + \lambda _N\).
There is a bijection
Let \(a=\left( a_{1},a_{2},\ldots ,a_{N}\right) \in \mathbb {N}^{N}\). Then:
(a) We let \(x^{a}\) denote the monomial \(x_{1}^{a_{1}}x_{2}^{a_{2}}\cdots x_{N}^{a_{N}}\).
(b) We let \(\operatorname *{sort}a\) mean the \(N\)-partition obtained from \(a\) by sorting the entries of \(a\) in weakly decreasing order.
Let \(\lambda \) be any \(N\)-partition. Then, we define a symmetric polynomial \(m_{\lambda }\in \mathcal{S}\) by
This is called the monomial symmetric polynomial corresponding to \(\lambda \).
(a) For each \(n\in \left\{ 0,1,\ldots ,N\right\} \), we have
where \(\left( 1,1,\ldots ,1,0,0,\ldots ,0\right) \) is the \(N\)-tuple that begins with \(n\) many \(1\)’s and ends with \(N-n\) many \(0\)’s.
(b) For each \(n\in \mathbb {N}\), we have
where the size \(\left\vert \lambda \right\vert \) of an \(N\)-partition \(\lambda \) is defined to be the sum of its entries (i.e., if \(\lambda =\left( \lambda _{1},\lambda _{2},\ldots ,\lambda _{N}\right) \), then \(\left\vert \lambda \right\vert :=\lambda _{1}+\lambda _{2}+\cdots +\lambda _{N}\)).
(c) Assume that \(N{\gt}0\). For each \(n\in \mathbb {N}\), we have
where \(\left( n,0,0,\ldots ,0\right) \) is the \(N\)-tuple that begins with an \(n\) and ends with \(N-1\) zeroes.
(a) The family \(\left( m_{\lambda }\right) _{\lambda \text{ is an }N\text{-partition}}\) is a basis of the \(K\)-module \(\mathcal{S}\).
(b) Each symmetric polynomial \(f\in \mathcal{S}\) satisfies
(c) Let \(n\in \mathbb {N}\). Let
(where we understand the zero polynomial \(0\in \mathcal{P}\) to be homogeneous of every degree). Then, \(\mathcal{S}_{n}\) is a \(K\)-submodule of \(\mathcal{S}\).
(d) The family \(\left( m_{\lambda }\right) _{\lambda \text{ is an }N\text{-partition of size }n}\) is a basis of the \(K\)-module \(\mathcal{S}_{n}\).
Let \(\sigma \in S_{N}\) and \(f\in \mathcal{P}\). Then,
for any \(\left( a_{1},a_{2},\ldots ,a_{N}\right) \in \mathbb {N}^{N}\).
(a) We let \(\rho \) be the \(N\)-tuple \(\left( N-1,N-2,\ldots ,N-N\right) \in \mathbb {N}^{N}\).
(b) For any \(N\)-tuple \(\alpha =\left( \alpha _{1},\alpha _{2},\ldots ,\alpha _{N}\right) \in \mathbb {N}^{N}\), we define
This is called the \(\alpha \)-alternant (of \(x_{1},x_{2},\ldots ,x_{N}\)).
Let \(\lambda \) be an \(N\)-partition.
The Young diagram of \(\lambda \) is defined as the set
We visually represent each element \(\left( i,j\right) \) of this Young diagram as a box in row \(i\) and column \(j\).
We denote the Young diagram of \(\lambda \) by \(Y\left( \lambda \right) \).
Let \(\lambda \) be an \(N\)-partition.
A Young tableau of shape \(\lambda \) means a way of filling the boxes of \(Y\left( \lambda \right) \) with elements of \(\left[ N\right] \) (one element per box). Formally speaking, it is defined as a map \(T:Y\left( \lambda \right) \rightarrow \left[ N\right] \).
Let \(\lambda \) be an \(N\)-partition.
A Young tableau \(T\) of shape \(\lambda \) is said to be semistandard if its entries
increase weakly along each row (from left to right);
increase strictly down each column (from top to bottom).
Formally speaking, this means that a Young tableau \(T:Y\left( \lambda \right) \rightarrow \left[ N\right] \) is semistandard if and only if
we have \(T\left( i,j\right) \leq T\left( i,j+1\right) \) for any \(\left( i,j\right) \in Y\left( \lambda \right) \) satisfying \(\left( i,j+1\right) \in Y\left( \lambda \right) \);
we have \(T\left( i,j\right) {\lt}T\left( i+1,j\right) \) for any \(\left( i,j\right) \in Y\left( \lambda \right) \) satisfying \(\left( i+1,j\right) \in Y\left( \lambda \right) \).
We let \(\operatorname *{SSYT}\left( \lambda \right) \) denote the set of all semistandard Young tableaux of shape \(\lambda \).
Entries increase weakly along rows
Entries increase strictly down columns
Let \(\lambda \) be an \(N\)-partition. If \(T\) is any Young tableau of shape \(\lambda \), then we define the corresponding monomial
Let \(\lambda \) be an \(N\)-partition. We define the Schur polynomial \(s_{\lambda }\in \mathcal{P}\) by
Let \(\lambda \) be an \(N\)-partition. Then:
(a) The polynomial \(s_{\lambda }\) is symmetric.
(b) We have
Here, the addition on \(\mathbb {N}^{N}\) is defined entrywise.
Let \(\lambda \) and \(\mu \) be two \(N\)-partitions.
We say that \(\mu \subseteq \lambda \) if and only if \(Y\left( \mu \right) \subseteq Y\left( \lambda \right) \). Equivalently, \(\mu \subseteq \lambda \) if and only if
Thus we have defined a partial order \(\subseteq \) on the set of all \(N\)-partitions.
Let \(\lambda \) and \(\mu \) be two \(N\)-partitions such that \(\mu \subseteq \lambda \). Then, we define the skew Young diagram \(Y\left( \lambda /\mu \right) \) to be the set difference
Let \(\lambda \) and \(\mu \) be two \(N\)-partitions such that \(\mu \subseteq \lambda \). Let \(\left( a,b\right) \) and \(\left( e,f\right) \) be two elements of \(Y\left( \lambda /\mu \right) \). Let \(\left( c,d\right) \in \mathbb {Z}^{2}\) satisfy \(a\leq c\leq e\) and \(b\leq d\leq f\). Then, \(\left( c,d\right) \in Y\left( \lambda /\mu \right) \).
Let \(\lambda \) and \(\mu \) be two \(N\)-partitions such that \(\mu \subseteq \lambda \). A Young tableau of shape \(\lambda /\mu \) means a way of filling the boxes of \(Y\left( \lambda /\mu \right) \) with elements of \(\left[ N\right] \) (one element per box). Formally speaking, it is defined as a map \(T:Y\left( \lambda /\mu \right) \rightarrow \left[ N\right] \).
Young tableaux of shape \(\lambda /\mu \) are often called skew Young tableaux.
If we don’t have \(\mu \subseteq \lambda \), then we agree that there are no Young tableaux of shape \(\lambda /\mu \).
Let \(\lambda \) and \(\mu \) be two \(N\)-partitions.
A Young tableau \(T\) of shape \(\lambda /\mu \) is said to be semistandard if its entries
increase weakly along each row (from left to right);
increase strictly down each column (from top to bottom).
Formally speaking, this means that a Young tableau \(T:Y\left( \lambda /\mu \right) \rightarrow \left[ N\right] \) is semistandard if and only if
we have \(T\left( i,j\right) \leq T\left( i,j+1\right) \) for any \(\left( i,j\right) \in Y\left( \lambda /\mu \right) \) satisfying \(\left( i,j+1\right) \in Y\left( \lambda /\mu \right) \);
we have \(T\left( i,j\right) {\lt}T\left( i+1,j\right) \) for any \(\left( i,j\right) \in Y\left( \lambda /\mu \right) \) satisfying \(\left( i+1,j\right) \in Y\left( \lambda /\mu \right) \).
We let \(\operatorname *{SSYT}\left( \lambda /\mu \right) \) denote the set of all semistandard Young tableaux of shape \(\lambda /\mu \).
Entries increase weakly along rows
Entries increase strictly down columns
Let \(\lambda \) and \(\mu \) be two \(N\)-partitions. Let \(T\) be a semistandard Young tableau of shape \(\lambda /\mu \). Then:
(a) If \(\left( i,j_{1}\right) \) and \(\left( i,j_{2}\right) \) are two elements of \(Y\left( \lambda /\mu \right) \) satisfying \(j_{1}\leq j_{2}\), then \(T\left( i,j_{1}\right) \leq T\left( i,j_{2}\right) \).
(b) If \(\left( i_{1},j\right) \) and \(\left( i_{2},j\right) \) are two elements of \(Y\left( \lambda /\mu \right) \) satisfying \(i_{1}\leq i_{2}\), then \(T\left( i_{1},j\right) \leq T\left( i_{2},j\right) \).
(c) If \(\left( i_{1},j\right) \) and \(\left( i_{2},j\right) \) are two elements of \(Y\left( \lambda /\mu \right) \) satisfying \(i_{1}{\lt}i_{2}\), then \(T\left( i_{1},j\right) {\lt}T\left( i_{2},j\right) \).
(d) If \(\left( i_{1},j_{1}\right) \) and \(\left( i_{2},j_{2}\right) \) are two elements of \(Y\left( \lambda /\mu \right) \) satisfying \(i_{1}\leq i_{2}\) and \(j_{1}\leq j_{2}\), then \(T\left( i_{1},j_{1}\right) \leq T\left( i_{2},j_{2}\right) \).
(e) If \(\left( i_{1},j_{1}\right) \) and \(\left( i_{2},j_{2}\right) \) are two elements of \(Y\left( \lambda /\mu \right) \) satisfying \(i_{1}{\lt}i_{2}\) and \(j_{1}\leq j_{2}\), then \(T\left( i_{1},j_{1}\right) {\lt}T\left( i_{2},j_{2}\right) \).
Let \(\lambda \) and \(\mu \) be two \(N\)-partitions. If \(T\) is any Young tableau of shape \(\lambda /\mu \), then we define the corresponding monomial
Let \(\lambda \) and \(\mu \) be two \(N\)-partitions. We define the skew Schur polynomial \(s_{\lambda /\mu }\in \mathcal{P}\) by
Let \(\lambda \) and \(\mu \) be any two \(N\)-partitions. Then, the polynomial \(s_{\lambda /\mu }\) is symmetric.
(a) We let \(\mathbf{0}\) denote the \(N\)-tuple \(\left( 0,0,\ldots ,0\right) \in \mathbb {N}^{N}\).
(b) Let \(\alpha =\left( \alpha _{1},\alpha _{2},\ldots ,\alpha _{N}\right) \) and \(\beta =\left( \beta _{1},\beta _{2},\ldots ,\beta _{N}\right) \) be two \(N\)-tuples in \(\mathbb {N}^{N}\). Then, we set
Note that \(\alpha +\beta \in \mathbb {N}^{N}\), whereas \(\alpha -\beta \in \mathbb {Z}^{N}\).
Let \(\lambda \) and \(\mu \) be two \(N\)-partitions. Let \(T\) be a tableau of shape \(\lambda /\mu \). We define the content of \(T\) to be the \(N\)-tuple \(\left( a_{1},a_{2},\ldots ,a_{N}\right) \), where
We denote this \(N\)-tuple by \(\operatorname *{cont}T\).
Let \(\lambda \) and \(\mu \) be two \(N\)-partitions. Let \(T\) be a tableau of shape \(\lambda /\mu \). Let \(j\) be a positive integer. Then, \(\operatorname {col}_{\geq j}T\) means the restriction of \(T\) to columns \(j,j+1,j+2,\ldots \) (that is, the result of removing the first \(j-1\) columns from \(T\)). Formally speaking, this means the restriction of the map \(T\) to the set \(\left\{ \left( u,v\right) \in Y\left( \lambda /\mu \right) \ \mid \ v\geq j\right\} \).
Let \(\lambda ,\mu ,\nu \) be three \(N\)-partitions. A semistandard tableau \(T\) of shape \(\lambda /\mu \) is said to be \(\nu \)-Yamanouchi (this is an adjective) if for each positive integer \(j\), the \(N\)-tuple \(\nu +\operatorname *{cont}\left( \operatorname {col}_{\geq j}T\right) \in \mathbb {N}^{N}\) is an \(N\)-partition (i.e., weakly decreasing).
Let \(\lambda ,\mu ,\nu \) be three \(N\)-partitions. Then,
Let \(\lambda ,\mu ,\nu \) be three \(N\)-partitions. Then,
Let \(\lambda \) be any \(N\)-partition. Let \(T\) be a semistandard tableau of shape \(\lambda \). Then, \(T\left( i,j\right) \geq i\) for each \(\left( i,j\right) \in Y\left( \lambda \right) \).
Let \(L\) be a commutative ring. Let \(a\in L\). The element \(a\) of \(L\) is said to be regular if and only if every \(x\in L\) satisfying \(ax=0\) satisfies \(x=0\).
Let \(L\) be a commutative ring. Let \(a,u,v\in L\) be such that \(a\) is regular. Assume that \(au=av\). Then, \(u=v\).
Let \(\alpha \in \mathbb {N}^{N}\).
(a) If the \(N\)-tuple \(\alpha \) has two equal entries, then \(a_{\alpha }=0\).
(b) Let \(\beta \in \mathbb {N}^{N}\) be an \(N\)-tuple obtained from \(\alpha \) by swapping two entries. Then, \(a_{\beta }=-a_{\alpha }\).
Let \(\lambda \) and \(\mu \) be two \(N\)-partitions.
(a) We write \(\lambda /\mu \) for the pair \(\left( \mu ,\lambda \right) \). Such a pair is called a skew partition.
(b) We say that \(\lambda /\mu \) is a horizontal strip if we have \(\mu \subseteq \lambda \) and the Young diagram \(Y\left( \lambda /\mu \right) \) has no two boxes lying in the same column.
(c) We say that \(\lambda /\mu \) is a vertical strip if we have \(\mu \subseteq \lambda \) and the Young diagram \(Y\left( \lambda /\mu \right) \) has no two boxes lying in the same row.
Now, let \(n\in \mathbb {N}\).
(d) We say that \(\lambda /\mu \) is a horizontal \(n\)-strip if \(\lambda /\mu \) is a horizontal strip and satisfies \(\left\vert Y\left( \lambda /\mu \right) \right\vert =n\).
(e) We say that \(\lambda /\mu \) is a vertical \(n\)-strip if \(\lambda /\mu \) is a vertical strip and satisfies \(\left\vert Y\left( \lambda /\mu \right) \right\vert =n\).
The outer partition λ
The inner partition μ
The containment condition μ ⊆ λ
Let \(\lambda =\left( \lambda _{1},\lambda _{2},\ldots ,\lambda _{N}\right) \) and \(\mu =\left( \mu _{1},\mu _{2},\ldots ,\mu _{N}\right) \) be two \(N\)-partitions.
(a) The skew partition \(\lambda /\mu \) is a horizontal strip if and only if we have
(b) The skew partition \(\lambda /\mu \) is a vertical strip if and only if we have
Let \(M\in \mathbb {N}\). Let \(\lambda =\left( \lambda _{1},\lambda _{2},\ldots ,\lambda _{M}\right) \) and \(\mu =\left( \mu _{1},\mu _{2},\ldots ,\mu _{M}\right) \) be two \(M\)-partitions (i.e., weakly decreasing \(M\)-tuples of nonnegative integers). Then,
If \(a\overset {x^n}{\equiv } b\) and \(c\overset {x^n}{\equiv } d\) with \(c\) and \(d\) invertible (i.e., \([x^0]c\) and \([x^0]d\) are units), then \(a/c \overset {x^n}{\equiv } b/d\).
Let \(\left(\mathbf{a}_{i}\right)_{i\in I}\) be a family of invertible FPSs. Let \(U\) be an \(x^n\)-approximator for \(\left(\mathbf{a}_{i}\right)_{i\in I}\). Let \(J\subseteq I\). Then \(U\cap J\) (viewed as a subset of \(J\)) is an \(x^n\)-approximator for the subfamily \(\left(\mathbf{a}_{i}\right)_{i\in J}\).
Let \(n\in \mathbb {N}\) and let \(V\) be a finite set. Let \(c,d : V \to K[[x]]\) be two families of FPSs such that \(c_v \overset {x^n}{\equiv } d_v\) for each \(v\in V\). Then
Let \(I\) be a finite set. If \(\left( f_{i}\right) _{i\in I}\in K\left[ \left[ x\right] \right] ^{I}\) is a family of FPSs, and if \(g\in K\left[ \left[ x\right] \right] \) is an FPS satisfying \(\left[ x^{0}\right] g=0\), then \(\left( \prod _{i\in I}f_{i}\right) \circ g=\prod _{i\in I}\left( f_{i}\circ g\right) \).
(a) For each even positive integer \(n\), we let \(A_{n}\) be the domino tiling of \(R_{n,3}\) consisting of the following dominos:
the horizontal dominos \(\left\{ \left( 2i-1,\ 1\right) ,\ \left( 2i,\ 1\right) \right\} \) for all \(i\in \left[ n/2\right] \), which fill the bottom row of \(R_{n,3}\), and which we call the basement dominos;
the vertical domino \(\left\{ \left( 1,2\right) ,\ \left( 1,3\right) \right\} \) in the first column, which we call the left wall;
the vertical domino \(\left\{ \left( n,2\right) ,\ \left( n,3\right) \right\} \) in the last column, which we call the right wall;
the horizontal dominos \(\left\{ \left( 2i,\ 2\right) ,\ \left( 2i+1,\ 2\right) \right\} \) for all \(i\in \left[ n/2-1\right] \), which fill the middle row of \(R_{n,3}\) (except for the first and last columns), and which we call the middle dominos;
the horizontal dominos \(\left\{ \left( 2i,\ 3\right) ,\ \left( 2i+1,\ 3\right) \right\} \) for all \(i\in \left[ n/2-1\right] \), which fill the top row of \(R_{n,3}\) (except for the first and last columns), and which we call the top dominos.
(b) For each even positive integer \(n\), we let \(B_{n}\) be the domino tiling of \(R_{n,3}\) obtained by reflecting \(A_{n}\) across the horizontal axis of symmetry of \(R_{n,3}\) (swapping row \(1\) with row \(3\) and fixing row \(2\)).
(c) We let \(C\) denote the domino tiling of \(R_{2,3}\) consisting of three horizontal dominos: \(\left\{ (1,1),(2,1)\right\} \), \(\left\{ (1,2),(2,2)\right\} \), and \(\left\{ (1,3),(2,3)\right\} \).
The faultfree domino tilings of height-\(3\) rectangles are precisely the tilings
More concretely:
(a) The faultfree domino tilings of a height-\(3\) rectangle that contain a vertical domino in the top two squares of the first column are \(A_{2},A_{4},A_{6},A_{8},\ldots \).
(b) The faultfree domino tilings of a height-\(3\) rectangle that contain a vertical domino in the bottom two squares of the first column are \(B_{2},B_{4},B_{6},B_{8},\ldots \).
(c) The only faultfree domino tiling of a height-\(3\) rectangle that contains no vertical domino in the first column is \(C\).
Let \((f_i)_{i\in \mathbb {N}}\) be a sequence of FPSs that coefficientwise stabilizes to an FPS \(f\), and let \(n\in \mathbb {N}\). Then there exists an integer \(K\in \mathbb {N}\) such that
Let \((g_i)_{i\in \mathbb {N}}\) be a sequence of FPSs that coefficientwise stabilizes to an FPS \(g\), and let \(n\in \mathbb {N}\). Then there exists an integer \(L\in \mathbb {N}\) such that
Let \(\mathbf{a} = \left(a_n\right)_{n \in \mathbb {Z}}\) be a Laurent polynomial in \(K\left[x^{\pm }\right]\). Then,
We have