Editing Incidence algebra (section)

=== Subset poset and exponential generating functions ===
For the Boolean poset of finite subsets <math>S\subset\{1,2,3,\ldots\}</math> ordered by inclusion <math>S\subset T</math>, the reduced incidence algebra consists of invariant functions <math>f(S,T),</math> defined to have the same value on isomorphic intervals [''S'',''T''] and [''{{prime|S}}'',''{{prime|T}}''] with |''T''&nbsp;\&nbsp;''S''| = |''{{prime|T}}''&nbsp;\&nbsp;''{{prime|S}}''|.  Again, let ''t'' denote the invariant delta function with ''t''(''S'',''T'') = 1 for |''T''&nbsp;\&nbsp;''S''| = 1 and ''t''(''S'',''T'')&nbsp;=&nbsp;0 otherwise. Its powers are:
<math display="block">t^n(S,T) =\, \sum t(T_0,T_1)\,t(T_1,T_2) \dots t(T_{n-1},T_n) 
= \left\{ \begin{array}{cl} n! & \text{if}\,\, |T\smallsetminus S| = n\\
0 & \text{otherwise,}\end{array}\right.</math> where the sum is over all chains <math>S = T_0\subset T_1\subset\cdots\subset T_n=T,</math> and the only non-zero terms occur for saturated chains with <math>|T_i\smallsetminus T_{i-1}| = 1;</math> since these correspond to permutations of ''n'', we get the unique non-zero value ''n''!. Thus, the invariant delta functions are the divided powers <math>\tfrac{t^n}{n!},</math> and we may write any invariant function as <math>\textstyle f = \sum_{n\geq0} f(\emptyset,[n])\frac{t^n}{n!},</math> where [''n''] = {1, . . . , ''n''}. This gives a natural isomorphism between the reduced incidence algebra and the ring of [[exponential generating function]]s. The zeta function is <math>\textstyle \zeta = \sum_{n\geq 0}\frac{t^n}{n!} = \exp(t),
</math> with Möbius function:
<math display="block">\mu = \frac1{\zeta} = \exp(-t) = \sum_{n\geq 0} (-1)^n \frac{t^n}{n!}.</math>
Indeed, this computation with formal power series proves that <math>\mu(S,T)=(-1)^{|T\smallsetminus S|}.</math> Many combinatorial counting sequences involving subsets or labeled objects can be interpreted in terms of the reduced incidence algebra, and [[Exponential formula|computed]] using exponential generating functions.