Symbolic method (combinatorics): Difference between revisions

Revision as of 18:45, 1 August 2017

Revision as of 19:23, 3 August 2017

Line 4:

Bender and Goldman<ref>{{cite journal|last1=Bender|first1=E.A.|last2=Goldman|first2=J.R.|title=Enumerative uses of generating functions|journal=Indiana Univ. Math. J.|date=1971|volume=20|pages=753-764}}</ref>, Foata and Schuetzenberger<ref name="fs">{{cite journal|last1=Foata|first1=D.|last2=Schuetzenberger|first2=M.|title=Théorie géométrique des polynômes Eulériens|journal=Lectures Notes in Math.|date=1970|volume=138}}</ref>, and Joyal<ref>{{cite journal|last1=Joyal|first1=Andre|title=Une théorie combinatoire des séries formelles|journal=Adv. Math.|date=1981|volume=42|pages=1-82|ref=joy}}</ref>.

The presentation in this article borrows somewhat from Joyal's [[combinatorial species]].

== Classes of combinatorial structures ==

Line 21 ⟶ 20:

:<math> X^2/E_2 \; + \; X^3/E_3 </math>

where the term <math>X^n/G</math> is used to denote the set of orbits under ''G'' and <math>X^n = X \times \ldotscdots \times X</math>, which denotes in the obvious way the process of distributing the objects from ''X'' with repetition into the ''n'' slots. Similarly, consider the labelled problem of creating cycles of arbitrary length from a set of labelled objects ''X''. This yields the following series of actions of cyclic groups:

:<math> X/C_1 \; + \; X^2/C_2 \; + \; X^3/C_3 \; + \; X^4/C_4 \; + \cdots.</math>

Line 33 ⟶ 32:

In the following we will simplify our notation a bit and write e.g.

:<math> E_2 + E_3 \mboxtext{ and } C_1 + C_2 + C_3 + \cdots.</math>

for the classes mentioned above.

Line 156 ⟶ 155:

==Unlabelled structures==

With unlabelled structures, an [[ordinary generating function]] (OGF) is used. The OGF of a sequence <math>A_{n}A_n</math> is defined as

:<math>A(x)=\sum_{n=0}^{\infty}A_{n} A_n x^{n}</math>

===Product===

The [[Cartesian product|product]] of two combinatorial classes <math>\mathcal{A}</math> and <math>\mathcal{B}</math> is specified by defining the size of an ordered pair as the sum of the sizes of the elements in the pair. Thus we have for <math>a \in \mathcal{A}</math> and <math>b \in \mathcal{B}</math>, <math>|(a,b)| = |a| + |b|</math>. This should be a fairly intuitive definition. We now note that the number of elements in <math>\mathcal{A} \times \mathcal{B}</math> of size <var>n</var> is

:<math>\sum_{k=0}^{n}A_{k} A_k B_{n-k}.</math>

Using the definition of the OGF and some elementary algebra, we can show that

Line 186 ⟶ 185:

:<math>\begin{align}A(z) &{} = \prod_{\beta \in \mathcal{B}}(1 + z^{|\beta|}) \\

&{} = \prod_{n=1}^{\infty} (1 + z^{n})^{B_{n}B_n} \\

&{} = \exp \left ( \ln \prod_{n=1}^{\infty}(1 + z^{n})^{B_{n}B_n} \right ) \\

&{} = \exp \left ( \sum_{n = 1}^{\infty} B_{n}B_n \ln(1 + z^{n}) \right ) \\

&{} = \exp \left ( \sum_{n = 1}^{\infty} B_{n}B_n \cdot \sum_{k = 1}^{\infty} \frac{(-1)^{k-1}z^{nk}}{ k} \right ) \\

&{} = \exp \left ( \sum_{k = 1}^{\infty} \frac{(-1)^{k-1}}{ k} \cdot \sum_{n = 1}^{\infty}B_{n} B_n z^{nk} \right ) \\

&{} = \exp \left ( \sum_{k = 1}^{\infty} \frac{(-1)^{k-1} B(z^{k})}{ k} \right),

\end{align}</math>

where the expansion

:<math>\ln(1 + u) = \sum_{k = 1}^{\infty} \frac{(-1)^{k-1} u^{k}}{ k} </math>

was used to go from line 4 to line 5.

Line 208 ⟶ 207:

:<math>\begin{align} A(z) &{} = \prod_{\beta \in \mathcal{B}} (1 - z^{|\beta|})^{-1} \\

&{} = \prod_{n = 1}^{\infty} (1 - z^{n})^{-B_{n}B_n} \\

&{} = \exp \left ( \ln \prod_{n = 1}^{\infty} (1 - z^{n})^{-B_{n}B_n} \right ) \\

&{} = \exp \left ( \sum_{n=1}^{\infty}-B_{n}B_n \ln (1 - z^{n}) \right ) \\

&{} = \exp \left ( \sum_{k=1}^{\infty} \frac{B(z^{k})}{ k} \right ),

\end{align}

</math>

where, similar to the above set construction, we expand <math>\ln (1 - z^{n})</math>, swap the sums, and substitute for the OGF of <math>\mathcal{B}</math>.

===Other elementary constructions===

Line 230 ⟶ 229:

|-

|<math>\mathcal{A} = \mathfrak{C}\{\mathcal{B}\}</math>

|<math>A(z) = \sum_{k=1}^{\infty} \frac{\phi(k)}{ k} \ln \frac{ 1} {1 - B(z^{k})}</math> (where <math>\phi(k)</math> is the [[Euler totient function]])

|-

|<math>\mathcal{A} = \Theta\mathcal{B}</math>

Line 248 ⟶ 247:

:<math>G(z) = \frac{z}{1 - G(z)}</math>

we solve for ''G''(''z'') by multiplying <math>1 - G(z)</math> to get

<math>G(z) - G(z)^2 = z</math>

Line 277 ⟶ 276:

An object is ''weakly labelled'' if each of its atoms has a nonnegative integer label, and each of these labels is distinct. An object is (''strongly'' or ''well'') ''labelled'', if furthermore, these labels comprise the consecutive integers <math>[1 \ldots n]</math>. ''Note: some combinatorial classes are best specified as labelled structures or unlabelled structures, but some readily admit both specifications.'' A good example of labelled structures is the class of [[Graph (discrete mathematics)|labelled graph]]s.

With labelled structures, an [[exponential generating function]] (EGF) is used. The EGF of a sequence <math>A_{n}A_n</math> is defined as

:<math>A(x)=\sum_{n=0}^{\infty}A_{n} A_n \frac{x^{n}}{n!}.</math>

===Product===

Line 288 ⟶ 287:

To aid this development, let us define a function, <math>\rho</math>, that takes as its argument a (possibly weakly) labelled object <math>\alpha</math> and relabels its atoms in an order-consistent way so that <math>\rho(\alpha)</math> is well labelled. We then define the labelled product for two objects <math>\alpha</math> and <math>\beta</math> as

:<math>\alpha \star \beta = \{(\alpha',\beta'): (\alpha',\beta') \mboxtext{ is well-labelled, } \rho(\alpha') = \alpha, \rho(\beta') = \beta \}.</math>

Finally, the labelled product of two classes <math>\mathcal{A}</math> and <math>\mathcal{B}</math> is

Line 296 ⟶ 295:

The EGF can be derived by noting that for objects of size <math>k</math> and <math>n-k</math>, there are <math>{n \choose k}</math> ways to do the relabelling. Therefore, the total number of objects of size <math>n</math> is

:<math>\sum_{k=0}^{n} {n \choose k}A_{k} A_k B_{n-k}.</math>

This ''binomial convolution'' relation for the terms is equivalent to multiplying the EGFs,

Line 310 ⟶ 309:

===Set===

In labelled structures, a set of <math>k</math> elements corresponds to exactly <math>k!</math> sequences. This is different from the unlabelled case, where some of the permutations may coincide. Thus for <math>\mathcal{A} = \mathfrak{P}\{\mathcal{B}\}</math>, we have

:<math>A(z) = \sum_{k = 0}^{\infty} \frac{B(z)^k}{k!} = \exp(B(z))</math>

===Cycle===

Cycles are also easier than in the unlabelled case. A cycle of length <math>k</math> corresponds to <math>k</math> distinct sequences. Thus for <math>\mathcal{A} = \mathfrak{C}\{\mathcal{B}\}</math>, we have

:<math>A(z) = \sum_{k = 0}^{\infty} \frac{B(z)^k}{k} = \ln\left(\frac{ 1} {1-B(z)}\right).</math>

===Boxed product===

In labelled structures, the min-boxed product <math>\mathcal{A}_{\min} = \mathcal{B}^{\square}\star \mathcal{C}</math> is a variation of the original product which requires the element of <math>\mathcal{B}</math> in the product with the minimal label. Similarly, we can also define a max-boxed product, denoted by <math>\mathcal{A}_{\max} = \mathcal{B}^{\blacksquare}\star \mathcal{C}</math>, by the same manner. Then we have,

:<math>A_{\min}(z)=A_{\max}(z)=\int^{z}_{0}z_0 B'(t)C(t)\,dt.</math>

or equivalently,

:<math>A_{\min}'(t)=A_{\max}'(t)=B'(t)C(t).</math>

===Example===

Line 334 ⟶ 333:

\mathfrak{C}_{\operatorname{odd}},

\mathfrak{P}_{\operatorname{even}},

\mboxtext{ and }

\mathfrak{P}_{\operatorname{odd}}

</math>