An algebra over the operad of posets and structural binomial identities

José Antonio Arciniega-Nevárez¹ [email protected] ¹División de Ingenierías, Universidad de Guanajuato, Guanajuato, México , Marko Berghoff² [email protected] ²Mathematical Institute, University of Oxford, Oxford, UK and Eric Rubiel Dolores-Cuenca³ [email protected] ³ Department of mathematics, Yonsei University, Seoul, Korea

Abstract.

We study generating functions of strict and non-strict order polynomials of series-parallel posets, called order series. These order series are closely related to Ehrhart series and $h^{*}$ -polynomials of the associated order polytopes. We explain how they can be understood as algebras over a certain operad of posets. Our main results are based on the fact that the order series of chains form a basis in the space of order series. This allows to reduce the search space of an algorithm that finds for a given power series $f(x)$ , if possible, a poset $P$ such that $f(x)$ is the generating function of the order polynomial of $P$ . In terms of Ehrhart theory of order polytopes, the coordinates with respect to this basis describe the number of (internal) simplices in the canonical triangulation of the order polytope of $P$ . Furthermore, we derive a new proof of the reciprocity theorem of Stanley. As an application, we find new identities for binomial coefficients and for finite partitions that allow for empty sets, and we describe properties of the negative hypergeometric distribution.

Keywords— Binomial Coefficient, Ehrhart series, Generating function, Negative Hypergeometric Distribution, Order Polynomial, Order Series, Partitions, Series Parallel Poset, Vandermonde Identity

1. Introduction

For every poset ${P}$ , Stanley [24] considered the problem of counting the numbers $\Omega^{\circ}(P,n)$ and $\Omega(P,n)$ of strict and non-strict order preserving maps from $P$ to the $n$ –chain $\langle n\rangle=\{1<\ldots<n\}$ . In this paper we study the generating functions

\mathfrak{Z}\left(P\right)=\sum_{n=1}^{\infty}\Omega^{\circ}(P,n)x^{n}\quad\text{ and }\quad\mathfrak{Z}^{+}\left(P\right)=\sum_{n=1}^{\infty}\Omega(P,n)x^{n}.

We call them the strict and non-strict order series of the poset $P$ .

These series are not completely new: Let $Poly(P)$ denote the order polytope of $P$ and $E_{Poly(P)}$ its Ehrhart polynomial. Using results of Stanley [25] and Macdonald [21] we find

\displaystyle\mathfrak{Z}^{+}\left(P\right)

\displaystyle=\sum_{n=1}^{\infty}\Omega(P,n)x^{n}=x+\sum_{n=2}^{\infty}E_{Poly(P)}(n-1)x^{n}=x\frac{h^{*}(x)}{(1-x)^{|P|+1}}.

In other words, up to a degree shift we work with the Ehrhart series of $Poly(P)$ , or its $h^{*}$ -polynomial (aka $h^{*}$ -vector) if we use the basis $\{\frac{1}{(1-x)^{i+1}}\}_{0\leq i\leq|P|}$ on the Ehrhart series of $Poly(P)$ .

For a $n$ –chain we write $\mathfrak{Z}\left(\langle n\rangle\right)=\mathfrak{Z}\left(n\right)$ and $\mathfrak{Z}^{+}\left(\langle n\rangle\right)=\mathfrak{Z}^{+}\left(n\right)$ . One finds (see Section 2)

\mathfrak{Z}\left(n\right)=\frac{x^{n}}{(1-x)^{n+1}}\quad\text{and}\quad\mathfrak{Z}^{+}\left(n\right)=\frac{x}{(1-x)^{n+1}}.

Computing the order series or, equivalently, the order polynomial of a poset is difficult in general. However, for certain families of posets, for instance series-parallel posets, it can be done algorithmically in polynomial time [11]. Note that it suffices to know one of the two order series, as this determines the other by a version of combinatorial reciprocity (see [24] for order polynomials, Theorem 2.14 and Proposition 2.16 for order series, and [4] in general). In the following we focus therefore on the strict order series $\mathfrak{Z}\left(P\right)$ .

Posets have an operad structure, see [12, 16]. Here we consider an operad $\mathcal{SP}$ generated by concatenation and disjoint union of posets. Recall that series-parallel posets are built out of the singleton poset by iterating these two operations. Thus, series-parallel posets form an algebra over the operad $\mathcal{SP}$ . We show below that the same holds for their order series (see Proposition 2.3, Proposition 2.6 and Proposition 2.13). Furthermore, we demonstrate how chains are the basic building blocks not only for the set of series-parallel posets, but also for their order series (Section 2) as well as their order polytopes (Section 3.2).

The map that assigns to a poset its order series is not injective, that is, several posets can have the same order series. However, for some families of posets we can compute the preimages: Given a power series $f(x)$ we describe in Section 3.1 an algorithm to search for the posets $P$ that satisfy $f=\mathfrak{Z}\left(P\right)$ .

Our main result is based on the observation that the (strict) order series of chains form a basis $\left\{\frac{x^{i}}{(1-x)^{i+1}}\right\}_{i\in\mathbb{N}}$ for the space of (strict) order series of series-parallel posets (Proposition 2.7, see also Remark 2.17). This allows us to prove that

•

The order series of every series-parallel poset $P$ is a finite sum of order series of chains, $\mathfrak{Z}\left(P\right)=\sum c_{i}\mathfrak{Z}\left(i\right)$ . See Corollary 2.8.
•

The coefficients $c_{i}$ are non-negative integers. The indices $i$ , such that $c_{i}\neq 0$ , encode topological information of (the Hasse diagram of) $P$ . See Proposition 3.1.
•

The coefficients $c_{i}$ encode combinatorial information about the canonical triangulation of the order polytope of $P$ . See Lemma 3.6. In Section 3.2, we compare our results with Ehrhart theory.
•

The existence of the operadic action on order series implies new binomial identities. See Section 4.

In [10] Drinfeld describes a power series that corrects the notion of associativity. Motivated by the construction of Drinfeld, this paper started by the observation that order series can distinguish certain posets. For example, the two posets $\{a<b\}$ and $\{a,b\}$ differ by their order and their order series differ as well: $\frac{x^{2}}{(1-x)^{3}}\neq\frac{x}{(1-x)^{2}}+2\frac{x^{2}}{(1-x)^{3}}$ .

1.1. Related work

We give a (short) account of closely related work.

Consider the category of finite sets, and let B be the skeleton of the category whose objects are finite sets but the only morphisms are isomorphisms. The theory of B-species studies functors from B to finite sets and power series associated to them [5, 32]. A Möbius-species [22] is a functor from B to the category of finite posets. In comparison, we study an operadic homomorphism from the algebra of series-parallel posets to power series. For example, the poset $\{a<b<c,a<b^{\prime}<c\}$ has the associated power series

\frac{x^{3}}{(1-x)^{4}}+2\frac{x^{4}}{(1-x)^{5}}=x^{3}+6x^{4}+\cdots.

There is no B-species or Möbius-species with the corresponding generating function, because a species only depends on the number of elements of the input set. We believe our series are a topological version of species.

The book [23] introduces generating functions of order polynomials of posets to study partitions, Ehrhart polynomials and descent statistics. In contrast, we focus on the problem of computing the order series of a given poset. Moreover, we restrict our analysis to series-parallel posets since they have a rich algebraic structure (i.e., the operad structure referred to above, and explained below). In particular, all posets considered here are finite.

A binomial poset $P$ is a locally finite poset with an element $\hat{0}$ so that $\hat{0}\leq a$ for all $a\in P$ , contains an infinite chain, every interval $[s,t]$ is graded, and any two $n$ -intervals contain the same number of maximal chains for any $n$ (see [28]). For instance, the set $\mathbb{N}$ with the usual linear order is a binomial poset. To each binomial poset $P$ we can associate a subalgebra $R(P)$ of the incidence algebra of $P$ : It consists of all functions $f$ such that $f(x,y)$ only depends on the length of the interval $[x,y]$ . The algebra $R(P)$ is isomorphic to an algebra of generating functions with the usual product of functions. Stanley’s construction can be used to study properties of invertible elements. In comparison, we study an algebra over the set-operad of series parallel posets. This formalism does not require an underlying vector space, and it is constructed from two operations that differ from the product of functions, the Hadamard product and the ordinal sum of power series which is a deformation of the usual product of functions. The generating functions that we study are algebraic of degree 1 according to [29].

In this article, a $n$ -labeling of a poset $P$ is a map to $\langle n\rangle$ that preserves the order. This is a different notion to [18] in which a $n$ -labeling on a poset is defined as a poset $P$ and a map of sets.

In regard to labelings of Hasse diagrams, there are many different variations of labelings of (directed) graphs. See for instance [13]. However, we could not find a notion that is related to ours.

In regard to binomial identities, note that if we let $t=0$ in Proposition 4.1 we recover the Chu-Vandermonde identity. Most identities in [14] fix the top part of the combinatorial expression and vary the bottom part. For example, consider the generalized Vandermonde identity,

(1)

{q_{1}+\cdots+q_{p}\choose n}=\sum_{n_{1}+\cdots n_{p}=n}\prod_{i=1}^{p}{q_{i}\choose n_{i}}.

Fixing a partition $q_{1}+\cdots+q_{p}$ , the formula relates the binomial coefficient ${q_{1}+\cdots+q_{p}\choose n}$ with the product of binomial coefficients ${q_{i}\choose n_{i}}$ over all possible $p$ -partitions $n=\sum n_{i}$ . In comparison, in Proposition 4.2 we fix a partition $n_{1}+\cdots+n_{p}$ and relate the binomial coefficient ${q\choose n_{1}+\cdots+n_{p}}$ with the product of binomial coefficients ${q_{i}\choose n_{i}}$ where the terms $q_{i}$ depend on $q$ and the length $p$ of the partition.

While the multivariate negative hypergeometric distribution is a well known topic in probability theory, as far as we are aware, the proofs in Section 4.3 are new.

2. Order series

Let $\mathbf{Poset}$ denote the category of finite partially ordered sets whose morphisms are the strict order preserving maps. Let $\mathbf{Poset}+$ denote the category with the same objects, but whose morphisms are non-strict order preserving (i.e., they satisfy $x<y\Rightarrow f(x)\leq f(y)$ ).

Definition 2.1.

Define $\hom_{\mathbf{Poset}+}(P,n)$ as the set of (non-strict) order preserving maps from $P$ to $\langle n\rangle$ and $\hom_{\mathbf{Poset}}(P,n)$ as the set of strict order preserving maps from $P$ to $\langle n\rangle$ . Define the order polynomials $\Omega(P,n)$ and $\Omega^{\circ}(P,n)$ as the cardinality $|\hom_{\mathbf{Poset}+}(P,n)|$ and $|\hom_{\mathbf{Poset}}(P,n)|$ , respectively.

For example $\Omega^{\circ}(\langle m\rangle,n)={n\choose m}$ , while $\Omega(\langle m\rangle,n)=\left(\kern-3.00003pt\left(\genfrac{}{}{0.0pt}{}{n}{m}\right)\kern-3.00003pt\right)={n+m-1\choose m}$ .

Definition 2.2.

For a poset $Q$ we define a formal power series, called its order series, by

\mathfrak{Z}\left(Q\right)=\mathfrak{Z}\left(Q,x\right)=\sum_{n=1}^{\infty}\Omega^{\circ}(Q,n)x^{n}.

We have

(2)

\displaystyle\mathfrak{Z}\left(m\right)=\sum_{n=m}^{\infty}{n\choose m}x^{n}=\frac{x^{m}}{(1-x)^{m+1}}.

For a proof of the second equality see [31, Equation (1.5.5)], [14, Equation (1.3)] or [23, Equation (1.3)].

If $x$ is the common variable for the power series $\mathfrak{Z}\left(Q\right)$ and $\mathfrak{Z}\left(W\right)$ , we define

(3)

\mathfrak{Z}\left(Q\right)*\mathfrak{Z}\left(W\right)=\mathfrak{Z}\left(Q\right)(1-x)\mathfrak{Z}\left(W\right).

Note that here we are using the Cauchy product of power series.

We denote the Hadamard product of power series by

\sum_{n=1}^{\infty}a_{n}x^{n}\sqcup\sum_{n=1}^{\infty}b_{n}x^{n}=\sum_{n=1}^{\infty}a_{n}b_{n}x^{n}.

We interpret the Hadamard product as disjoint union of power series.

The reason to work with power series instead of polynomials is that it highlights the structure of an underlying operad of posets (for an introduction to operads we refer to [20]). Consider the operad $\mathcal{SP}$ generated by a binary associative and commutative operation $\sqcup$ and a binary associative operation $*$ . The only unary operation is the identity. The action of $S_{n}$ is given by permutations on the inputs of the operations.

Proposition 2.3.

Order series are an algebra over the operad $\mathcal{SP}$ . The above defined operations on power series $*$ and $\sqcup$ are both associative, and $\sqcup$ is commutative.

The set of series-parallel posets $SP$ is itself an algebra over the operad $\mathcal{SP}$ . Here the action of $*$ is the ordinal sum (or concatenation) of posets, and the action of $\sqcup$ is the disjoint union of posets.

For a finit posets $Q$ and $W$ , the inclusions of $Q$ and $W$ in $Q*W$ allow us to see $Q$ and $W$ as a subposets of the concatenation. There is thus a function

(4)

G_{n}:\bigcup_{l=1}^{n-1}\hom_{\mathbf{Poset}}(Q,\langle l\rangle)\times\hom_{\mathbf{Poset}}(W,\langle n-l\rangle)\to\hom_{\mathbf{Poset}}(Q*W,\langle n\rangle).

On the term $\hom_{\mathbf{Poset}}(Q,\langle l\rangle)\times\hom_{\mathbf{Poset}}(W,\langle n-l\rangle)$ the function is given by $G_{n}(h,k)(v)=h(v)$ , if $v\in Q$ , and $G_{n}(h,k)(v)=k(v)+l$ , if $v\in W$ . This function is surjective. Furthermore, for any element $f:Q*W\rightarrow\langle n\rangle$ let $M$ be the maximum of $f|_{Q}$ and $m$ the minimum of $f|_{W}$ (actually $m=M+i$ for some integer $i\geq 0$ ). If $j\in\{0,1,\cdots,i-1\}$ , we can partition $\langle n\rangle$ in $\langle M+j\rangle$ and $\langle n-M-j\rangle$ in order to define $h_{j}=f|_{Q}:Q\to\langle M+j\rangle$ , and $k_{j}:W\to\langle n-M-j\rangle$ , given by $k_{j}(v)=f|_{W}(v)-M-j$ . See Figure 1 for an example.

Figure 1. The function from

\langle 2\rangle

\langle 4\rangle

that sends

1\mapsto 1,

and

2\mapsto 4

can be split in 3 different ways:

\{\langle 1\rangle\rightarrow\langle 1\rangle\}\times\{\langle 1\rangle\rightarrow\langle 3\rangle\},\{\langle 1\rangle\rightarrow\langle 2\rangle\}\times\{\langle 1\rangle\rightarrow\langle 2\rangle\}

and

\{\langle 1\rangle\rightarrow\langle 3\rangle\}\times\{\langle 1\rangle\rightarrow\langle 1\rangle

For an integer $n>1$ define

\triangle\langle n\rangle=\bigsqcup_{i=1}^{n}(\langle i\rangle,\langle n-i\rangle).

Also define $\hom_{\mathbf{Poset}+}((X,Y),\triangle\langle n\rangle)$ as the set of pairs of non strict order preserving maps $(k:X\to\langle i\rangle,h:Y\to\langle n-i\rangle),1\leq i\leq n$ . Furthermore, a computation shows

(5)

\sum_{i=1}\Omega^{\circ}(X,i)x^{i}\sum_{j=1}\Omega^{\circ}(Y,j)x^{j}=\sum_{n=2}\Omega^{\circ}((X,Y),\triangle\langle n\rangle)x^{n}.

We will need the following auxiliary lemma.

Lemma 2.4.

Assume that there is a sequence of sets

where

•

$i:A\rightarrow B$ is injective,
•

$p:B\rightarrow C$ is surjective,
•

there is a split $s:C\to B$ , such that $p\circ s=id$ and $s(C)\cap i(A)=\varnothing$ , and
•

for every point $c\in C,s(c)\sqcup(i(A)\cap p^{-1}(c))=p^{-1}(c)$ .

Then $s(C)\sqcup i(A)=B$ .

A sequence satisfying the previous lemma is called a splitting sequence of sets.

Proposition 2.5.

Let $Q$ and $W$ be finite posets. Then

is a splitting sequence of sets.

Proof.

For $k\in\hom_{\mathbf{Poset}}(W,\langle n-1\rangle)$ define $(k+1)\in\hom_{\mathbf{Poset}}(W,\langle n\rangle)$ by $(k+1)(v)=k(v)+1$ . The shifting function

Sh\colon\bigcup_{a+b=n-1}\hom_{\mathbf{Poset}}(Q,\langle a\rangle)\times\hom_{\mathbf{Poset}}(W,\langle b\rangle)\to\bigcup_{a+(b+1)=n}\hom_{\mathbf{Poset}}(Q,\langle a\rangle)\times\hom_{\mathbf{Poset}}(W,\langle b+1\rangle),

given by sending $(h,k)$ into $(h,k+1)$ is injective. Let $G_{n}$ be the function defined in (4), and let $G_{n}^{-1}(f)$ be the preimage of $f\in\hom_{\mathbf{Poset}}(Q*W,\langle n\rangle)$ . Then

G_{n}^{-1}(f)-Sh\left(\bigcup_{a+b=n-1}\hom_{\mathbf{Poset}}(Q,\langle a\rangle)\times\hom_{\mathbf{Poset}}(W,\langle b\rangle)\right)

has only one element, namely the pair $(h,k)$ where $h=f|_{Q}:Q\rightarrow\langle m\rangle$ and $k:W\rightarrow\langle n-m+1\rangle$ is given by $k(v)=f|_{W}(v)-m+1$ (again, $m$ is the minimum of $f|_{W}$ ).

Choosing this unique point we define a section

s:\hom_{\mathbf{Poset}}(Q*W,\langle n\rangle)\to\bigcup_{c+d=n}\hom_{\mathbf{Poset}}(Q,\langle c\rangle)\times\hom_{\mathbf{Poset}}(W,\langle d\rangle),

whose image is disjoint from the image of the shifting function $Sh$ . This holds because $k(m)=1$ but no function of the form $g+1$ has $1$ in the codomain. Then the hypothesis of Lemma 2.4 holds. ∎

Suppose that there is a short splitting sequence of finite sets

(6)

with $i_{1}$ and $i_{2}$ non-negative integers and $n\in\mathbb{N}$ , then

(7)	$\displaystyle\sum_{n=2}\Omega^{\circ}(\mu(Y,W),n)x^{n}=$	$\displaystyle x^{i_{1}}\sum_{n=2}\Omega^{\circ}((Y,W),\triangle{\langle n-i_{1}\rangle})x^{n-i_{1}}-$
		$\displaystyle-x^{i_{2}}\sum_{n=2}\Omega^{\circ}((Y,W),\triangle{\langle n-i_{2}\rangle})x^{n-i_{2}}$
	$\displaystyle=$	$\displaystyle x^{i_{1}}\sum_{j=1}\Omega^{\circ}(Y,j)x^{j}\sum_{k=1}\Omega^{\circ}(W,k)x^{k}$
		$\displaystyle-x^{i_{2}}\sum_{j=1}\Omega^{\circ}(Y,j)x^{j}\sum_{k=1}\Omega^{\circ}(W,k)x^{k}.$

Proposition 2.6.

There is a homomorphism $SP\to\{\text{order series}\}$ of algebras over the operad $\mathcal{SP}$ . It maps a poset $P$ to the series $\mathfrak{Z}\left(P\right)$ and satisfies

(8)

\mathfrak{Z}\left(Q*W\right)=\mathfrak{Z}\left(Q\right)*\mathfrak{Z}\left(W\right),

(9)

\mathfrak{Z}\left(Q\sqcup W\right)=\mathfrak{Z}\left(Q\right)\sqcup\mathfrak{Z}\left(W\right).

Proof.

Equation (9) follows by counting elements in $\hom_{\mathbf{Poset}}(P\sqcup Q,n)$ . Equation (8) follows by Equation 7 with $i_{2}=1,i_{1}=0$ . ∎

Both relations are well-known at the level of order polynomials, (see for example [11]).

The following statement allows to make explicit computations.

Proposition 2.7.

For $0\leq m,k:$

\mathfrak{Z}\left(k\right)\sqcup\mathfrak{Z}\left(m\right)=\frac{x^{k}}{k!}\frac{d^{k}}{dx^{k}}\mathfrak{Z}\left(m\right)=\sum_{n=0}^{k}{m+n\choose k}{k\choose n}\mathfrak{Z}\left(m+n\right).

Proof.

First note that

(10)

\mathfrak{Z}\left(m\right)=\sum_{n}^{\infty}{n\choose m}x^{n}=\sum_{n}^{\infty}\frac{x^{m}}{m!}\frac{d^{m}}{dx^{m}}x^{n}.

From (10) we obtain

	$\displaystyle\mathfrak{Z}\left(k\right)\sqcup\mathfrak{Z}\left(m\right)$	$\displaystyle=\sum_{n}^{\infty}{n\choose k}{n\choose m}x^{n}$
		$\displaystyle=\sum_{n}^{\infty}\frac{x^{k}}{k!}\frac{d^{k}}{dx^{k}}{n\choose m}x^{n}$
		$\displaystyle=\frac{x^{k}}{k!}\frac{d^{k}}{dx^{k}}\mathfrak{Z}\left(m\right),$

and therefore

	$\displaystyle\mathfrak{Z}\left(k\right)\sqcup\mathfrak{Z}\left(m\right)$	$\displaystyle=\frac{x^{k}}{k!}\frac{d^{k}}{dx^{k}}\mathfrak{Z}\left(m\right)$
		$\displaystyle=\frac{x^{k}}{k!}\frac{d^{k}}{dx^{k}}\frac{x^{m}}{(1-x)^{m+1}}$
		$\displaystyle=\frac{x^{k}}{k!}\sum_{n=0}^{k}{k\choose n}\left(\frac{d^{k-n}}{dx^{k-n}}x^{m}\right)\left(\frac{d^{n}}{dx^{n}}(1-x)^{-m-1}\right)$
		$\displaystyle=\sum_{n=0}^{k}{k\choose n}\frac{m!}{(m+n-k)!k!}\frac{(m+n)!}{m!}x^{m+n}(1-x)^{-m-n-1}$
		$\displaystyle=\sum_{n=0}^{k}{m+n\choose k}{k\choose n}\mathfrak{Z}\left(m+n\right).$

∎

Another proof of Proposition 2.7, can be deduced from [14, (6.44)].

Corollary 2.8.

The strict order series of any series-parallel poset is a linear combination of order series of chains.

Proof.

Series-parallel posets are generated by the singleton poset under the operations $*$ and $\sqcup$ . Therefore their order series are generated by the chain $\mathfrak{Z}\left(1\right)=\frac{x}{(1-x)^{2}}$ under the operations $*$ and $\sqcup$ . These operations are linear on power series and send chains into linear combinations of chains. ∎

Example 2.9.

Let $D$ be the unary operation on posets defined by

D(P)=\langle 1\rangle*\big{(}\langle 1\rangle\sqcup P\big{)}*\langle 1\rangle.

If the input of $D$ is an $n$ -chain, we compute:

$\displaystyle\mathfrak{Z}\left(D({\langle n\rangle})\right)$	$\displaystyle=$	$\displaystyle\mathfrak{Z}\left(1\right)(\mathfrak{Z}\left(\langle 1\rangle\sqcup\langle n\rangle\right))\mathfrak{Z}\left(1\right)$
	$\displaystyle=$	$\displaystyle\frac{x}{(1-x)^{2}}(n\frac{x^{n}}{(1-x)^{n+1}}+(n+1)\frac{x^{n+1}}{(1-x)^{n+2}})\frac{x}{(1-x)^{2}}$
	$\displaystyle=$	$\displaystyle n\frac{x^{n+2}}{(1-x)^{n+3}}+(n+1)\frac{x^{n+3}}{(1-x)^{n+4}}$
	$\displaystyle=$	$\displaystyle n\mathfrak{Z}\left(n+2\right)+(n+1)\mathfrak{Z}\left(n+3\right).$

Remark 2.10.

From the explicit description as a finite sum $\mathfrak{Z}\left(P\right)=\sum a_{i}\mathfrak{Z}\left(i\right)$ the $n$ -order polynomial can be extracted as $\Omega^{\circ}(P,n)=\sum a_{i}{i\choose n}$ .

Definition 2.11.

Recall the definition of non-strict order series,

\mathfrak{Z}^{+}\left(Q\right)=\sum_{n=1}^{\infty}\Omega(Q,n)x^{n}.

Define the concatenation by

\mathfrak{Z}^{+}\left(Q\right)*^{+}\mathfrak{Z}^{+}\left(W\right)=\mathfrak{Z}^{+}\left(Q\right)\frac{1-x}{x}\mathfrak{Z}^{+}\left(W\right).

and note that the non-strict order series of a disjoint union of posets is still given by the Hadamard product of their respective non-strict order series.

Example 2.12.

We have $\mathfrak{Z}^{+}\left(i\right)=\frac{x}{(1-x)^{i+1}}=\sum{\left(\kern-3.00003pt\left(\genfrac{}{}{0.0pt}{}{n}{i}\right)\kern-3.00003pt\right)}x^{n}$ where the last equality follows from Equation (2). Now consider the poset $D(\langle n\rangle)$ for the operation $D$ defined in Example 2.9 above. Then

	$\displaystyle\mathfrak{Z}^{+}\left(D(\langle n\rangle)\right)=$	$\displaystyle\mathfrak{Z}^{+}\left(1\right)^{+}\left(\mathfrak{Z}^{+}\left(n\right)\sqcup\mathfrak{Z}^{+}\left(1\right)\right)^{+}\mathfrak{Z}^{+}\left(1\right)$
	$\displaystyle=$	$\displaystyle\frac{x}{(1-x)^{2}}\frac{d\mathfrak{Z}^{+}\left(n\right)}{dx}=\frac{nx^{2}+x}{(1-x)^{n+4}},$

which can be calculated by hand, but also follows from the result in Example 2.9 by Theorem 2.14 below.

Proposition 2.13.

Non-strict order series with $*^{+},\sqcup$ are an algebra over the operad $\mathcal{SP}$ , and there is a $\mathcal{SP}$ homomorphism $SP\rightarrow\{\text{non strict order series}\}$ , that is,

(11)

\mathfrak{Z}^{+}\left(Q*W\right)=\mathfrak{Z}^{+}\left(Q\right)*^{+}\mathfrak{Z}^{+}\left(W\right),

(12)

\mathfrak{Z}^{+}\left(Q\sqcup W\right)=\mathfrak{Z}^{+}\left(Q\right)\sqcup\mathfrak{Z}^{+}\left(W\right).

Proof.

Given a pair $(i,j)$ , if $n=i+j$ , then there is a function

\hom_{\mathbf{Poset}+}((X,Y),(\langle i\rangle,\langle j\rangle))\to\hom_{\mathbf{Poset}+}({X*Y,\langle n-1\rangle})

that takes the pair of order preserving maps $h:X\mapsto\langle i\rangle$ and $k:Y\mapsto\langle j\rangle$ and defines $F:X*Y\to\langle n-1\rangle$ by $F(v)=h(v)$ if $v\in X$ and $F(v)=k(v)+i-1$ if $v\in Y$ . The sequence

satisfies Lemma 2.4. The relation (11) then follows by Equation (7) with $i_{2}=0,i_{1}=-1$ . Equation (12) follows by the same arguments as in the $\mathbf{Poset}$ case. ∎

At the level of posets, we have a faithful functor between the categories $\mathbf{Poset}\rightarrow\mathbf{Poset}+$ that fixes the objects and for each $P,Q$ injects $\hom_{\mathbf{Poset}}(P,Q)$ into $\hom_{\mathbf{Poset}+}(P,Q)$ . At the level of order series, there is an operadic isomorphism between strict and non-strict order series.

Let $i$ denote the map $x\mapsto x^{-1}$ and define a map $\iota$ , the reciprocity morphism, as follows. If $f$ is the analytic continuation of a strict or non-strict order series of a poset $P$ , then

\iota(f):=(-1)^{|P|+1}\big{(}f\circ i\big{)}.

Theorem 2.14.

For any series-parallel poset $P$ we have

\iota(\mathfrak{Z}\left(P\right))=\mathfrak{Z}^{+}\left(P\right)\quad\text{and}\quad\iota^{2}=\mathrm{id}.

In other words, $\mathfrak{Z}\left(P\right)$ is the expansion of its analytic continuation at 0, while $\mathfrak{Z}^{+}\left(P\right)$ is the expansion at $\infty$ of the same function (up to a sign).

Proof.

By definition it follows that $\iota^{2}=\mathrm{id}$ . We will show that $\iota$ commutes with concatenation and disjoint union of chains, that is, it is a morphism between two $\mathcal{SP}$ -algebras. Since these operations generate every series-parallel poset, this proves the theorem.

Since $(1-x^{-1})=-\frac{(1-x)}{x}$ , we see that $\iota$ commutes with concatenation,

$\displaystyle\iota(\mathfrak{Z}\left(n\right)*\mathfrak{Z}\left(m\right))$	$\displaystyle=$	$\displaystyle\iota(\frac{x^{n}}{(1-x)^{n+1}}(1-x)\frac{x^{m}}{(1-x)^{m+1}})$
	$\displaystyle=$	$\displaystyle(-1)^{n+m+1}(-1)^{n+1}\frac{x}{(1-x)^{n+1}}(-1)\frac{(1-x)}{x}(-1)^{m+1}\frac{x}{(1-x)^{m+1}}$
	$\displaystyle=$	$\displaystyle\iota\mathfrak{Z}\left(n\right)*^{+}\iota\mathfrak{Z}\left(m\right).$

We claim

\iota\mathfrak{Z}^{+}\left(n\right)\sqcup\iota\mathfrak{Z}^{+}\left(m\right)=\iota\big{(}\mathfrak{Z}^{+}\left(n\right)\sqcup\mathfrak{Z}^{+}\left(m\right)\big{)}.

Since $\iota^{2}=\mathrm{id}$ this readily also implies

\iota\big{(}\mathfrak{Z}\left(n\right)\sqcup\mathfrak{Z}\left(m\right)\big{)}=\iota^{2}\left(\mathfrak{Z}^{+}\left(n\right)\sqcup\mathfrak{Z}^{+}\left(m\right)\right)=\iota\mathfrak{Z}\left(n\right)\sqcup\iota\mathfrak{Z}\left(m\right).

Abbreviate $\mathfrak{Z}^{+}\left(m\right)$ by $f$ . Using Lemma 2.15 below we calculate

	$\displaystyle\iota\mathfrak{Z}^{+}\left(n\right)\sqcup\iota(f)$	$\displaystyle=\mathfrak{Z}\left(n\right)\sqcup\iota(f)=(-1)^{m+1}\frac{x^{n}}{n!}d_{n}(f\circ i)$
		$\displaystyle=(-1)^{m+n+1}\sum_{k=1}^{n}\binom{n-1}{k-1}\frac{x^{-k}}{k!}d_{k}f({x}^{-1})=\iota\left(\mathfrak{Z}\left(n\right)\sqcup f\right).$

∎

Lemma 2.15.

Let $f$ be $n$ -times differentiable and $x\neq 0$ . Then

\frac{x^{n}}{n!}\frac{d^{n}}{dx^{n}}(f\circ i)=(-1)^{n}\sum_{k=1}^{n}\binom{n-1}{k-1}\frac{x^{-k}}{k!}\frac{d^{k}f}{dx^{k}}({x}^{-1}).

Proof.

Let us abbreviate $\frac{d^{n}}{dx^{n}}$ by $d_{n}$ . Applying the Faà di Bruno formula for the chain rule of higher derivatives we get

d_{n}(f\circ i)=\sum_{k=1}^{n}d_{k}f({x}^{-1})B_{nk}(d_{1}i,d_{2}i,\ldots,d_{n-k+1}i).

Here the (incomplete) Bell polynomials $B_{nk}$ are defined by

B_{nk}(x_{1},\ldots,x_{n-k+1})=\sum\frac{n!}{j_{1}!j_{2}!\cdots j_{n-k+1}!}\left(\frac{x_{1}}{1!}\right)^{j_{1}}\cdots\left(\frac{x_{n-k+1}}{(n-k+1)!}\right)^{j_{n-k+1}},

where the sum is taken over all sequences $j_{1},\ldots,j_{n-k+1}$ of non-negative integers such that

j_{1}+j_{2}+\cdots+j_{n-k+1}=k,\quad j_{1}+2j_{2}+3j_{3}+\cdots+(n-k+1)j_{n-k+1}=n.

Now we compute $B_{nk}(d_{1}i,d_{2}i,\ldots,d_{n-k+1}i)$ to be given by

		$\displaystyle\sum\frac{n!}{j_{1}!j_{2}!\cdots j_{n-k+1}!}\left(\frac{-x^{-2}}{1!}\right)^{j_{1}}\cdots\left(\frac{(-1)^{n-k+1}(n-k+1)!x^{-n+k-2}}{(n-k+1)!}\right)^{j_{n-k+1}}$
	$\displaystyle=$	$\displaystyle\sum\frac{n!}{j_{1}!j_{2}!\cdots j_{n-k+1}!}(-1)^{\sum_{i=1}^{n-k+1}ij_{i}}x^{-\sum_{i=1}^{n-k+1}ij_{i}}x^{-\sum_{i=1}^{n-k+1}j_{i}}$
	$\displaystyle=$	$\displaystyle\sum\frac{n!}{j_{1}!j_{2}!\cdots j_{n-k+1}!}(-1)^{n}x^{-n}x^{-k}$
	$\displaystyle=$	$\displaystyle(-1)^{n}x^{-n}x^{-k}B_{nk}(1!,\ldots,(n-k+1)!)$
	$\displaystyle=$	$\displaystyle(-1)^{n}x^{-n}x^{-k}\binom{n-1}{k-1}\frac{n!}{k!},$

where the last identity is a well-known property of the incomplete Bell polynomials [9]. ∎

Our reciprocity theorem is equivalent to Stanley’s version [24].

Proposition 2.16.

For series-parallel posets Theorem 2.14 is equivalent to the reciprocity theorem of Stanley.

Proof.

See the proof of [28, Lemma 3.15.11]. ∎

Remark 2.17.

By reciprocity we have the following relation among the coefficients of order series

\mathfrak{Z}^{+}\left(P\right)=\sum_{i=j_{0}}^{n}(-1)^{n-i}a_{i}\mathfrak{Z}^{+}\left(i\right)\quad\Longleftrightarrow\quad\mathfrak{Z}\left(P\right)=\sum_{i=j_{0}}^{n}a_{i}\mathfrak{Z}\left(i\right).

Remark 2.18.

The singularities of $\mathfrak{Z}\left(P\right)$ and $\mathfrak{Z}^{+}\left(P\right)$ at 1 are simple poles. It follows that the Moebius transformation $x\mapsto\frac{1}{1-x}$ , sending 1 to $\infty$ , turns the analytic continuations of order series into polynomials. For example, for chains we obtain

\mathfrak{Z}\left(n\right)|_{y=\frac{1}{1-x}}=\sum_{k=0}^{n}\binom{n}{k}(-1)^{k}y^{n-k+1},\quad\mathfrak{Z}^{+}\left(n\right)|_{y=\frac{1}{1-x}}=y^{n+1}-y^{n}.

Since every order series of a series-parallel poset is a linear combination of order series of chains, there are new algebraic relations between order series that are not present on the level of posets. For example, the order series of the poset $\langle s\rangle\sqcup\langle n\rangle$ becomes a linear combination of order series of chains while the poset is not a chain. The following lemma describes the interaction between concatenation and disjoint union of order series and implies a new binomial identity as explained in Proposition 4.1.

Lemma 2.19.

Let $s>0$ . The following relationship holds for power series $f$ and $g$ :

(13)

\mathfrak{Z}\left(s\right)\sqcup(f*g)=\sum_{a+c=s}(\mathfrak{Z}\left(a\right)\sqcup f)*(\mathfrak{Z}\left(c\right)\sqcup g)-\\ \left(\sum_{a+c=s-1}(\mathfrak{Z}\left(a\right)\sqcup f)*(\mathfrak{Z}\left(c\right)\sqcup g)\right)*\mathfrak{Z}\left(1\right).

Proof.

We use the notation of ${s\choose a,b,c}=\frac{s!}{a!b!c!}$ for the multinomial coefficient.

	$\displaystyle\mathfrak{Z}\left(s\right)\sqcup(f*g)$	$\displaystyle=\frac{x^{s}}{s!}\frac{d^{s}}{dx^{s}}(f(1-x)g)$
		$\displaystyle=\frac{x^{s}}{s!}\sum_{a+b+c=s}{s\choose a,b,c}\frac{d^{a}}{dx^{a}}f\frac{d^{b}}{dx^{b}}(1-x)\frac{d^{c}}{dx^{c}}g$
		$\displaystyle=\frac{x^{s}}{s!}(\sum_{a+c=s}{s\choose a,0,c}\frac{d^{a}}{dx^{a}}f(1-x)\frac{d^{c}}{dx^{c}}g$
		$\displaystyle+\sum_{a+c=s-1}{s\choose a,1,c}\frac{d^{a}}{dx^{a}}f\frac{d}{dx}(1-x)\frac{d^{c}}{dx^{c}}g)$
		$\displaystyle=\sum_{a+c=s}(\mathfrak{Z}\left(a\right)\sqcup f)*(\mathfrak{Z}\left(c\right)\sqcup g)$
		$\displaystyle-\frac{x^{s-1}}{s-1!}\sum_{a+c=s-1}{s-1\choose a,c}\frac{d^{a}}{dx^{a}}f\frac{d^{c}}{dx^{c}}g(1-x)^{2}\frac{x}{(1-x)^{2}}$
		$\displaystyle=\sum_{a+c=s}(\mathfrak{Z}\left(a\right)\sqcup f)*(\mathfrak{Z}\left(c\right)\sqcup g)$
		$\displaystyle-\left(\sum_{a+c=s-1}(\mathfrak{Z}\left(a\right)\sqcup f)(\mathfrak{Z}\left(c\right)\sqcup g)\right)\mathfrak{Z}\left(1\right).$

∎

3. Representability of posets

In this section we introduce a family of posets in which the coefficients $a_{i}$ of the order series $\mathfrak{Z}\left(P\right)=\sum a_{i}\mathfrak{Z}\left(i\right)$ encode topological information. Our results allow to reduce the search space for an algorithm that, given a power series $f(x)$ , if possible, finds a poset $P$ such that $f=\mathfrak{Z}\left(P\right)$ .

Consider the unary operation $D$ defined in Example 2.9,

D(P)=\langle 1\rangle*\big{(}\langle 1\rangle\sqcup P\big{)}*\langle 1\rangle.

This adds a new maximum $x_{1}$ and a new minimum $x_{0}$ to $P$ , and a third element $y$ with $x_{0}<y<x_{1}$ . Geometrically we are attaching a handle (with a point) to the Hasse diagram of $P$ .

Let $\mathcal{W}$ be the free operad generated by $\mu$ and $D$ . We are interested in the $\mathcal{W}$ –algebra generated by the poset with a single element where $\mu$ is concatenation and $D$ is attaching a handle. We call elements of this $\mathcal{W}$ –algebra Wixárika posets. For an example see Figure 2, which depicts the Hasse diagram of a Wixárika poset (ordered from left to right). The name is due to the resemblance of the Hasse diagrams of such posets to the intricate colorful necklaces crafted by the Wixárika community in North America.

Figure 2. Hasse diagram of a Wixarika poset.

We can describe elements in $\mathcal{W}$ by words in the letters $\mu$ and $D$ . Let $w$ be such an element. By abuse of notation, we write $w(\langle 1\rangle)$ to represent the substitution of the poset $\langle 1\rangle$ on all leaves of the tree describing the word $w$ see Figure 3.

Figure 3. Left: The identity operation, the operation

D

and the operation

\mu

. Right: A tree representing the element of

\mathcal{W}

in Figure 2.

In [11], an algorithm is described to compute the order polynomials. The same algorithm can be adapted to our setting to compute order series, and in fact, from the point of view of operads, the algorithm amounts to evaluate the operations on the tree from top to bottom. Similarly, we write $w(\mathfrak{Z}\left(1\right))$ to represent the substitution of the corresponding elements in power series. For example, the tree of Figure 3 corresponds to $w=D(\_*(\_*(\_*D(D(D(\_)*(\_*D(\_)))))))$ . Thus, following Example 2.9, we compute $w(\mathfrak{Z}\left(1\right))=882\mathfrak{Z}\left(16\right)+7995\mathfrak{Z}\left(17\right)+27232\mathfrak{Z}\left(18\right)+43792\mathfrak{Z}\left(19\right)+33552\mathfrak{Z}\left(20\right)+9880\mathfrak{Z}\left(21\right)$ .

We will say that a power series $f(x)$ is represented if there is a series-parallel poset $P$ such that $f=\mathfrak{Z}\left(P\right)$ . In order to determine which power series can be represented, we shall determine topological invariants of a poset $P$ from its associated power series $\mathfrak{Z}\left(P\right)$ , such as the Betti number of $P$ (which is short for the first Betti number of the Hasse diagram of $P$ ). With that information we describe an algorithm which determines if $f(x)$ can be represented and if so, it explicitly constructs all possible series-parallel posets $P$ so that $f=\mathfrak{Z}\left(P\right)$ . Posets that have the same order series are called Doppelgänger posets.

Proposition 3.1.

Consider $w\in\mathcal{W}$ , a word in the characters $*$ and $D$ . Let $f(x)=w(\mathfrak{Z}\left(1\right))$ and $P=w(\langle 1\rangle)$ .

(1)

The series $f(x)$ admits a unique description

$f(x)=a_{i}\mathfrak{Z}\left(i\right)+a_{i+1}\mathfrak{Z}\left(i+1\right)+\cdots+a_{k}\mathfrak{Z}\left(k\right),$

where the coefficients $a_{j}$ are non-negative integers.
(2)

The number $i$ is the number of elements in a maximal chain in $P$ .
(3)

The number $k$ is the number of elements in $P$ .
(4)

The difference $d=k-i$ is the Betti number of $P$ , equal to the number of times the character $D$ occurs in $w$ .
(5)

The difference $m=i-2d-1$ is the number of times the character $*$ occurs in $w$ .
(6)

The number $m+1$ is the number of leaves in the tree $w$ .
(7)

$\sum_{u=1}^{k}(-1)^{k-u}a_{u}=1$ .
(8)

The first coefficient $a_{i}$ admits a factorization $a_{i}=\prod_{j=1}^{d}t_{j}$ with the following property. For any $t_{j}\geq 1$ there are $r_{t_{j}},s_{t_{j}},$ and $u_{t_{j}}$ with $t_{j}<u_{t_{j}}$ , so that when we evaluate the word $w$ on $\mathfrak{Z}\left(1\right)$ then $r_{t_{j}}\mathfrak{Z}\left(t_{j}\right)+\cdots+s_{t_{j}}\mathfrak{Z}\left(u_{t_{j}}\right)$ is an input of some $D$ .

Proof.

We shall give a proof of each item.

(1)

Follows from Proposition 2.7 and Equation (3).
(2)

If $*$ appears in $w$ , it concatenates subposets of any maximal chain. If $D$ appears in $w$ , it adds a maximum and a minimum point to the maximal chain in the input poset, which is a subposet of any maximal chain.

We conclude from Proposition 2.7 and Equation (3) that when we evaluate $w$ , the lowest term counts the number of points in a maximal chain.
(3)

We prove this in Lemma 3.3 in a more general setting.
(4)

From Proposition 2.7 it follows that we can track the number of times $D$ acts by comparing the parameter of the monomial with lowest degree and the monomial of highest degree. Geometrically, $D$ modifies the Hasse diagram by increasing the number of holes.
(5)

If the word $D$ occurs $d$ times in $w$ , the only way to obtain the term $\mathfrak{Z}\left(i\right)$ is if the word $*$ occurs $i-2d-1$ times in $w$ .
(6)

Consider the representation of $w$ as a binary tree with some marked edges. If the tree has $m$ binary branches, then it has $m+1$ leaves.
(7)

Follows from Equation (3.2) and the fact that $h_{0}^{*}=1$
(8)

Follows from Proposition 2.7.

∎

3.1. The inverse problem

In this section we study the following problem. When is a power series $f(x)=\sum_{i=i_{0}}^{i_{j}}f_{i}\mathfrak{Z}\left(i\right),f_{i_{0}},f_{i_{j}}\neq 0$ , represented as $\mathfrak{Z}\left(P\right)$ for some poset $P$ ? Two posets are called Doppelgänger posets if they share the same order series, for example $\langle 1\rangle*(\langle 1\rangle\sqcup\langle 1\rangle\sqcup\langle 1\rangle)$ and $\langle 2\rangle\sqcup\langle 2\rangle$ have the same order series: $\mathfrak{Z}\left(2\right)+6\mathfrak{Z}\left(3\right)+6\mathfrak{Z}\left(4\right)$ [16].

Note that if we order the chains in the decomposition $\mathfrak{Z}\left(P\right)=a\mathfrak{Z}\left(i\right)+\cdots+b\mathfrak{Z}\left(j\right),\mathfrak{Z}\left(Q\right)=a_{2}\mathfrak{Z}\left(i_{2}\right)+\cdots+b_{2}\mathfrak{Z}\left(j_{2}\right)$ , the terms $a,i,b,j$ change under the rules:

(14)

\mathfrak{Z}\left(P\right)*\mathfrak{Z}\left(Q\right)=aa_{2}\mathfrak{Z}\left(i+i_{2}\right)+\cdots+bb_{2}\mathfrak{Z}\left(j+j_{2}\right)

and

(15)

D(\mathfrak{Z}\left(P\right))=ia\mathfrak{Z}\left(i+2\right)+\cdots+(j+1)b\mathfrak{Z}\left(j+3\right).

If we have a candidate poset $P$ , to reduce the computational time, we first compute the lowest and highest order term of the factorization $\mathfrak{Z}\left(P\right)=a\mathfrak{Z}\left(i\right)+\cdots+b\mathfrak{Z}\left(j\right),$ and compare it with $f_{i_{0}},f_{i_{j}}$ . To select candidate posets, we do not need to explore all possible words $w$ . Since $*$ is associative, we can pick $(\_*(\_*\cdots(\_*\_))\cdots\leavevmode\nobreak\ )$ as a representative of every composition of $n$ operations $*$ . We call this representative an $n$ -corolla. In other words, the $2$ –corolla is $(\_*\_)$ , the $3$ –corolla is $(\_*(\_*\_))$ , and so on. If a word $w$ is a solution to our problem, then any permutation of the inputs of the corollas will also be a solution to our problem. In our setting, some of those Doppelgängers are explained because the poset concatenation is not commutative, but the power series concatenation is commutative.

The language of operads allows us to choose representatives from equivalence classes of trees. Consider the two-colored symmetric operad 2– $\mathcal{W}$ . This operad has a binary operation $D$ , colored in red, and for every $n>1$ an $n$ –ary operation, given by an $n$ -corolla $*$ , colored in green. Red colored operations have no restrictions, but green ones can only be composed with red ones. In other words, a green corolla cannot be grafted into a green corolla.

Proposition 3.2.

Given a finite sum $f(x)=\sum_{i=i_{0}}^{i_{j}}f_{i}\mathfrak{Z}\left(i\right),f_{i_{0}},f_{i_{j}}\neq 0$ where $f_{i_{k}},{0\leq k\leq j}$ are non-negative integers, there is an algorithm to determine if $f(x)=\mathfrak{Z}\left(P\right)$ for some Wixarika poset $P$ and, in the positive case, the algorithm returns all possible posets representing $f(x)$ .

Proof.

Let $f(x)=\sum_{i=i_{0}}^{i_{j}}f_{i}\mathfrak{Z}\left(i\right),f_{i_{0}},f_{i_{j}}\neq 0$ . We first restrict the space of posets that can represent $f$ . From Proposition 3.1, we know the number of times the characters $*,D$ occurs in the candidate words as well as the possible value of $|P|$ .

Now, we verify that $f$ satisfy the restrictions from Ehrhart theory listed on [17].

The next step is to choose representatives of Doppelgängers. We restrict the number of candidate words by using the 2– $\mathcal{W}$ structure under the rule: Any $n$ -corolla counts as $n-1$ uses of $*$ .

After that, in a loop:

•

We evaluate a candidate word $\{w\}$ only on the terms $(f_{i_{0}},i_{0},f_{i_{j}},i_{j})$ of $f$ using Algorithm 1.
•

For $w$ that passed the algorithm we compute $w(\mathfrak{Z}\left(1\right))$ . This can be done evaluating from top to bottom as in [11].
•

If any poset passes this step, we use [8] to find the remaining Doppelgänger posets and we stop the algorithm. Otherwise we continue the loop until there are no more posets candidates.

Input: A candidate 2-

\mathcal{W}

tree with

i

leaves and

d

red marks. A value

(a_{i},i,a_{k},k)

;

// The four numbers stand for

a_{i}\mathfrak{Z}\left(i\right)+\cdots+a_{k}\mathfrak{Z}\left(k\right),(1,1,1,1)=\mathfrak{Z}\left(1\right)

// The

n

-corollas represent the composition of

n

copies of

*

, and the red marks represent

D

Put

(1,1,1,1)

on the leaves;

Let

B

be the set of red marks ordered by inverse Deep First Search on the tree;

for $b\in B$ do

compute the input of

b

with Equation (14) and Equation (15). Lets say

(r_{b},t_{b},s_{b},u_{b})

;

// only compute the lowest and highest term

if $t_{b}$ does not divide $a_{i}$ then

return False;

else

store

t_{b}

in Cache; // Use Cache to find the root’s value

end if

end for

if the root has a value different to $a_{i}$ then

return False

else

True.

end if

Algorithm 1 Is

w(1,1,1,1)==(a_{i},i,a_{k},k)

∎

The algorithm has as input a description of $f(x)$ as a finite combination of elements $\mathfrak{Z}\left(i\right)$ for some natural numbers $i$ . Note that every coefficient of $\sum_{i=1}^{\infty}\mathfrak{Z}\left(i\right)=x+3x^{2}+\ldots$ is finite. Because of this, we require the input to be written already as a finite sum of terms $\{x^{i}/(1-x)^{i+1}\}$ . We do not have an algorithm to discover the factorization of an arbitrary power series $f$ that is guaranteed to finish in a finite time.

For arbitrary series-parallel posets we need to adapt Proposition 3.1 and increase the search space as now we are required to work with different connected components and attached handles (as in the operation $D$ ) can consist of several elements.

Proposition 3.3.

Let $Q$ be a series-parallel poset. If $\mathfrak{Z}\left(Q\right)=\sum_{j=i}^{k}a_{j}\mathfrak{Z}\left(j\right)$ is a finite sum, then

(1)

the Betti number of $Q$ is smaller or equal to $k-i$ ,
(2)

the number $i$ is the length of any maximal chain of the largest connected component of the Hasse diagram of $Q$ ,
(3)

the number $k$ is the total number of points in the poset,
(4)

$a_{i}$ and $a_{k}$ can be factored into a product of terms obtained by the application of disjoint union on the subposets of $Q$ ,
(5)

$\sum_{u=1}^{k}(-1)^{k-u}a_{u}=1$ .

Proof.

(1)

Geometrically, when we apply $D$ to a disjoint union of posets, we increase the Betti number of the Hasse diagram. But according to Proposition (2.7), the index $k$ reflects not only the number of handles in the Hasse diagram but also the number of points on those handles and the number of connected components on the Hasse diagram. If

\sum_{j_{1}=i_{1}}^{k_{1}}a_{j_{1}}\mathfrak{Z}\left(j_{1}\right)\sqcup\sum_{j_{2}=i_{2}}^{k_{2}}a_{j_{2}}\mathfrak{Z}\left(j_{2}\right)=\sum_{j_{3}=i_{3}}^{k_{3}}a_{j_{3}}\mathfrak{Z}\left(j_{3}\right),

then we can verify that $k_{3}-i_{3}\geq(k_{1}-i_{1})+(k_{2}-i_{2})$ . Here $(k_{1}-i_{1})$ and $(k_{2}-i_{2})$ are bounds for the Betti numbers of each connected component, and $(k_{3}-i_{3})$ bounds the Betti number of the union. Hence the inequality.

(2)

We use the following observation: If $m\geq k$ , then, by the definition of $\sqcup$ (see also Proposition 2.7), we find that

$\mathfrak{Z}\left(k\right)\sqcup\mathfrak{Z}\left(m\right)={m\choose k}{k\choose 0}\mathfrak{Z}\left(m\right)+\cdots.$

The proof is similar to the proof of item (2) of Proposition 3.1.
(3)

If $m>n$ , then by Proposition 2.7 the last non-zero coefficient of $\langle m\rangle\bigsqcup\langle n\rangle$ is ${m+n\choose n}{n\choose n}\mathfrak{Z}\left(m+n\right)$ . Concatenation also preserves the number of elements. These results imply that the term $\mathfrak{Z}\left(k\right)$ is obtained by adding all elements involved in all disjoint unions as well as those elements involved in concatenation.
(4)

It follows from Proposition 2.7.
(5)

Follows from Equation (3.2) and the fact that $h_{0}^{*}=1$ .

∎

The coefficients of the power series associated to a series-parallel poset are not topological invariants. For example the posets $\langle 1\rangle*(\langle 1\rangle\sqcup\langle 1\rangle)*\langle 1\rangle$ and $\langle 2\rangle*(\langle 1\rangle\sqcup\langle 1\rangle)$ have the same number of labeling maps, but different Betti numbers.

To adapt Algorithm 1 for series-parallel posets we need to increase the search space to allow for disjoint union of posets. The algorithm depends on [8] which already works at the level of series-parallel posets.

3.2. Comparison with Ehrhart theory

Let $Poly(P)$ denote the order polytope of a poset $P$ and $E_{Poly(P)}$ its Ehrhart polynomial [3]. Recall that by

\mathfrak{Z}^{+}\left(P\right)=\sum_{n=1}^{\infty}\Omega_{P,n}x^{n}=x+\sum_{n=2}^{\infty}E_{Poly(P)}(n-1)x^{n}=x\frac{h^{*}(x)}{(1-x)^{|P|+1}}

order series are related to the Ehrhart series of $Poly(P)$ , or its $h^{*}$ -vector, by a change of basis and a shift of degree. From the point of view of Ehrhart theory there are several works characterizing $h^{*}$ -vectors [2, 17, 27] and $f^{*}$ -vectors [7] of polytopes. We instead study Ehrhart series of order polytopes. This is the reason why we work with respect to a different basis.

Remark 3.4.

Note that

Poly(P\sqcup Q)=Poly(P)\times Poly(Q),\quad Poly(P*Q)=Poly(P)\oplus Poly(Q),

where $\oplus$ denotes the free sum of polytopes: If $X\subset\mathbb{R}^{d}$ and $Y\subset\mathbb{R}^{e}$ are two polytopes of dimension $d$ and $e$ , then $X\oplus Y=\mathrm{conv}\{(0_{\mathbb{R}^{d}}\times Y)\cup(X\times 0_{\mathbb{R}^{e}})\}\subset\mathbb{R}^{d+e}$ .

This and the relation $\Omega_{P,n}=E_{Poly(P)}(n-1)$ imply the form of the respective operations on order series, Equation (11) and Equation (12). See for instance [6].

We have shown above how to express $\mathfrak{Z}^{+}\left(P\right)$ in the basis $\{\mathfrak{Z}^{+}\left(i\right)\}_{i\in\mathbb{N}}$ . In this section we relate the coordinates with respect to this basis to a certain triangulation of $Poly(P)$ .

Following Stanley [26], a lower set (order ideal) $I$ is a subset of the poset $P$ so that if $x\in I$ and $y\leq x$ then $y\in I$ . Lower sets form a poset $J(P)$ ordered by inclusion. To any chain of strict inclusions of lower sets $K:I_{1}\subset I_{2}\subset\cdots\subset I_{k}$ we assign

F_{K}=\left\{f\in\mathbb{R}^{|P|}:\begin{array}[]{l}f\hbox{ is constant on the subsets }I_{1},I_{2}\setminus I_{1},\cdots I_{k}\setminus I_{k-1},P\setminus I_{k},\\ 0=f(I_{1})\leq f(I_{2})\leq\cdots\leq f(I_{k})\leq f(P\setminus I_{k})=1.\end{array}\right\}.

The canonical triangulation of the order polytope of $P$ is given by the simplicial complex

\{F_{K}\mid K\in J(P)\}.

In other words, it is the order complex of the poset $J(P)$ (see [26]).

For an example consider the poset $\langle 2\rangle\sqcup\langle 3\rangle$ . Its order polytope is

Poly(\langle 2\rangle\sqcup\langle 3\rangle)=\{x_{1}\leq x_{2},y_{1}\leq y_{2}\leq y_{3}\}\subset[0,1]^{5}.

Using coordinates $(x_{1},x_{2},y_{1},y_{2},y_{3})$ in $\mathbb{R}^{5}$ . It contains various 5-dimensional simplices, for example $\{0\leq x_{1}\leq x_{2}\leq y_{1}\leq y_{2}\leq y_{3}\leq 1\}$ , or $\{0\leq x_{1}\leq y_{1}\leq x_{2}\leq y_{2}\leq y_{3}\leq 1\}$ . This fact can be expressed using a shuffle product (see e.g. [19]) on the order polytopes of two chains $\langle n\rangle$ and $\langle m\rangle$ . We define it as the sum of simplices that are formed by linear orders on $x_{1},x_{2},\ldots,x_{n},y_{1},y_{2},\ldots,y_{m}$ that preserve the original order on the $x$ - and the $y$ -variables. Note that this is just the usual shuffle product – we simply use words to encode linear orders, for example $xy$ means $x\leq y$ , and vice versa. It is known that the shuffle product of two words on $n$ and $m$ letters has ${n+m\choose n}$ summands. This implies that the number of maximal simplices in the canonical triangulation of $Poly(\langle n\rangle\sqcup\langle m\rangle)$ is ${n+m\choose n}$ . In the example $\langle 2\rangle\sqcup\langle 3\rangle$ we find thus 10 simplices of dimension 5 in the canonical triangulation of $Poly(\langle 2\rangle\sqcup\langle 3\rangle)$ .

The set of simplices $\{F_{K}\}_{K\in J(P)}$ is closed under taking intersections. In particular, every simplex not in the boundary of $Poly(P)$ lies in the intersection of some maximal simplices of the canonical triangulation. Suppose $P_{1},\ldots,P_{k}$ are the maximal simplices of $\{F_{K}\}_{K\in J(P)}$ . Let ${\mathbb{1}}_{X}\colon\mathbb{R}^{d}\to\mathbb{R}$ be the indicator function of polytope $X\subset\mathbb{R}^{d}$ , defined by ${\mathbb{1}}_{X}(x)=1$ if $x\in X$ and $0$ otherwise. We can determine all points on the canonical triangulation of $Poly(P)$ by considering the union of simplices of maximal dimension, but then we are overcounting. For instance, we count twice the faces obtained as intersection of two simplices. We can express this fact as

{\mathbb{1}}_{Poly(P)}=\sum_{i}{\mathbb{1}}_{P_{i}}-\sum_{i,j,i\neq j}{\mathbb{1}}_{P_{i}\cap P_{j}}+\cdots+(-1)^{k}{\mathbb{1}}_{P_{1}\cap\cdots\cap P_{k}},

which is an instance of the well-known inclusion-exclusion principle.

Figure 4. The order polytope of the poset

\langle 1\rangle\sqcup\langle 2\rangle

. The canonical triangulation consists of three 3-simplices, indicated by the dashed lines. They intersect in two internal 2-simplices, depicted in red.

Lemma 3.5.

Let $m\geq k\geq r$ , $P=\langle k\rangle\sqcup\langle m\rangle$ . Then the number of $m+r$ –dimensional simplices in the canonical triangulation of $P$ is ${m+r\choose k}{k\choose r}$ .

Proof.

Consider a $(m+r)$ –simplex $T$ in the canonical triangulation of $Poly(P)$ . We have already discussed above that in the case $r=k$ the simplex $T$ is represented by a linear order on the coordinates of $\mathbb{R}^{|P|}=\mathbb{R}^{k}\times\mathbb{R}^{m}=\text{span}_{\mathbb{R}}(x_{1},\ldots,x_{k},y_{1},\ldots,y_{m})$ that respects the individual orders $x_{1}\leq\ldots\leq x_{k}$ and $y_{1}\leq\ldots\leq y_{m}$ . If $r<k$ , then $T$ is obtained from one (or more) of these simplices by exchanging an inequality $``\leq"$ for an equality $``="$ . For instance, if $k=m=1$ , then the canonical triangulation of $Poly(P)=[0,1]^{2}$ has two 2-simplices $\{0\leq x\leq y\leq 1\}$ and $\{0\leq y\leq x\leq 1\}$ which intersect in the internal 1-simplex $\{0\leq x=y\leq 1\}$ . See also Example 3.7 below.

The general construction starts with a geometrical $m+r$ -simplex $\Delta_{m+r}=\{(z_{0},\cdots,z_{m+r-1})|$ $\sum z_{i}=1,z_{i}\geq 0\}$ . We then change coordinates $w_{1}=z_{0},w_{2}=z_{0}+z_{1},\cdots,w_{m+r}=\sum z_{i}$ , to obtain $\Delta_{m+r}=\{0\leq w_{1}\leq\cdots\leq w_{m+r}\leq 1\}$ . The final step is to embed this simplex into the canonical triangulation by assigning coordinates $x_{i},y_{j}$ to the $w_{k}$ place holders.

Choose $k$ different coordinates of $\Delta_{m+r}$ ; this can be done in ${m+r\choose k}$ ways. Out of those $k$ coordinates choose $k-r$ coordinates in ${k\choose r}$ ways. Then label the $(m+r)-k+(k-r)=m$ coordinates from $x_{1}$ to $x_{m}$ . Add a second label $y_{1},\cdots y_{k}$ to the $k$ chosen points. Those $k-r$ chosen points have now two labels $x_{i},y_{j}$ which represent the condition $x_{i}=y_{j}$ . Any other point has only a single label. The simplex $T$ is then defined by applying these labels to $\Delta_{m+r}$ . We can do this process in ${m+r\choose k}{k\choose r}$ ways, as claimed, and any simplex in the canonical triangulation is determined by such a process. ∎

Proposition 3.6 ( $\mathfrak{Z}^{+}\left(P\right)$ satisfies the inclusion-exclusion principle).

Let $n=|P|$ . Consider $\mathfrak{Z}^{+}\left(P\right)=\sum_{i=j_{0}}^{n}(-1)^{n-i}a_{i}\mathfrak{Z}^{+}\left(i\right)$ . Then every $a_{i}$ is non-negative, the order polytope of ${P}$ is the union of $a_{n}$ copies of $n-$ simplices, and the remaining coefficients $a_{i}$ of $\mathfrak{Z}^{+}\left(P\right)=\sum(-1)^{n-i}a_{i}\mathfrak{Z}^{+}\left(i\right)$ count the number of internal $i-$ faces that occur as intersections of the $n$ -simplices.

Proof.

Case $P=\langle k\rangle*\langle m\rangle$ : A $k$ –chain concatenated with a $m$ –chain is a $(m+k)$ -chain, so the coefficient of $\mathfrak{Z}^{+}\left(m+k\right)$ is 1, in accordance with the fact that $Poly(\langle m+k\rangle)$ is a $(m+k)$ –dimensional simplex.

Case $P=\langle k\rangle\sqcup\langle m\rangle$ : Assume $m\geq k$ . Lemma 3.5 together with Proposition 2.7 and Remark 2.17, implies that the inclusion-exclusion principle is valid for this case.

Now, if (the non-strict order series of) a poset $P$ satisfies the inclusion-exclusion formula, so does $P*\langle 1\rangle$ and $P\sqcup\langle 1\rangle$ . The geometric reason is that both operations add new orthogonal directions to a unit cube. The action of $*\langle 1\rangle$ is that of forming a cone while $\sqcup\langle 1\rangle$ acts as the Minkowski sum; the order polytope $Poly(P\sqcup Q)$ is constructed from the order polytopes $Poly(P)$ and $Poly(Q)$ by choosing orthogonal dimensions with coordinates $\{x_{i}\}$ and $\{y_{j}\}$ , respectively. On each we draw one order polytope, and then we consider the space $ax+yb$ , $x\in Poly(P),y\in Poly(Q)$ with $0\leq a,b\leq 1$ .

For any $s$ –simplex in $Poly(Q)$ there is a chain $S$ in $J(P)$ so that the $s$ –simplex is the order polytope of $S$ .

Then $Poly(P\sqcup Q)=\sqcup_{S\in Poly(Q)}Poly(P\sqcup S)$ . Since $*,\sqcup$ are distributive with respect to $+$ on the vector space with basis $\{\mathfrak{Z}^{+}\left(i\right)\}$ , assuming $\mathfrak{Z}\left(Q\right)=\sum a_{i}\mathfrak{Z}\left(i\right)$ , we obtain $\mathfrak{Z}\left(P\sqcup Q\right)=\sum a_{i}\mathfrak{Z}\left(P\right)\sqcup\mathfrak{Z}\left(i\right)$ . Since we proved that for chains the inclusion-exclusion formula holds, it is thus also true for series-parallel posets. ∎

Example 3.7.

Consider $P=\langle 1\rangle\sqcup\langle 2\rangle$ . Figure 4 depicts the order polytope of $P$ . The canonical triangulation has three 3-simplices, described by the linear extensions $\{x\leq y_{1}\leq y_{2}\}$ , $\{y_{1}\leq x\leq y_{2}\}$ and $\{y_{1}\leq y_{2}\leq x\}$ . If $r=0$ , then ${m+r\choose k}{k\choose r}=2$ , so there are two internal 2-simplices which arise as intersections of the latter ones. The first two produce $\{x=y_{1}\leq y_{2}\}$ , the last two produce $\{y_{1}\leq y_{2}=x\}$ . Note that there are no internal 1-simplices; every 1-simplex of the canonical triangulation lies in the boundary of $Poly(P)$ .

It is known that Ehrhart polynomials satisfy the inclusion-exclusion principle since they count lattice points on integer polytopes. In [1, Proposition 9.5] the Hopf monoid structure of posets is studied. It is proved that posets are isomorphic, as Hopf monoids, to pointed conical generalized permutahedra. In this sense, the order polynomial is the associated polynomial to a character [1, Proposition 9.4]. It follows that the order polynomial satisfies an inclusion-exclusion formula for pointed conical generalized permutahedra. In our setting, we consider the action of an operad generated by concatenation and disjoint union. In that case Proposition 3.6 shows that the inclusion-exclusion principle is preserved by the action of these two operations.

4. Combinatorics

In the first subsection we apply our results to study binomial identities. We could not find the identities in Equation (18), Proposition 4.1 and Proposition 4.2 in the book [14]. We explore some corollaries of those identities, including an identity for finite partitions of fixed length that are allowed to contain empty sets (Subsection 4.2). In Section 4.3 we introduce a combinatorial approach to study the multivariate negative hypergeometric distribution.

4.1. Identities

The existence of the operad structure on order series implies Proposition 4.1. The associativity of the concatenation on order series implies Proposition 4.2. We call these two identities structural binomial identities. We also list several direct consequences of these structural identitites that we could not find in the literature.

Proposition 4.1.

Given $p,q,s\leq p+q$ . Then for $t\leq s$ :

\displaystyle{p+q+t\choose s}{s\choose t}=\sum_{\begin{subarray}{c}a+c=s\\ n\leq a\\ r\leq c\\ n+r=t\end{subarray}}{p+n\choose a}{a\choose n}{q+r\choose c}{c\choose r}-\sum_{\begin{subarray}{c}a+c=s-1\\ n\leq a\\ r\leq c\\ n+r=t-1\end{subarray}}{p+n\choose a}{a\choose n}{q+r\choose c}{c\choose r}.

Proof.

Consider Equation (13) with $f=\mathfrak{Z}\left(q\right),g=\mathfrak{Z}\left(p\right)$ . Then

	$\displaystyle\mathfrak{Z}\left(s\right)\sqcup(\mathfrak{Z}\left(q\right)*\mathfrak{Z}\left(p\right))$	$\displaystyle=\mathfrak{Z}\left(s\right)\sqcup(\mathfrak{Z}\left(q+p\right))$
		$\displaystyle=\sum_{t=0}^{s}{p+q+t\choose s}{s\choose t}\mathfrak{Z}\left(p+q+t\right),$

and

	$\displaystyle\mathfrak{Z}\left(s\right)\sqcup(\mathfrak{Z}\left(q\right)*\mathfrak{Z}\left(p\right))=$	$\displaystyle\sum_{a+c=s}(\mathfrak{Z}\left(a\right)\sqcup\mathfrak{Z}\left(p\right))*(\mathfrak{Z}\left(c\right)\sqcup\mathfrak{Z}\left(q\right))$
		$\displaystyle-\left(\sum_{a+c=s-1}(\mathfrak{Z}\left(a\right)\sqcup\mathfrak{Z}\left(p\right))(\mathfrak{Z}\left(c\right)\sqcup\mathfrak{Z}\left(q\right))\right)\mathfrak{Z}\left(1\right)$
	$\displaystyle=$	$\displaystyle\sum_{a+c=s}\sum_{n=0}^{a}{p+n\choose a}{a\choose n}\mathfrak{Z}\left(p+n\right)*\sum_{r=0}^{c}{q+r\choose c}{c\choose r}\mathfrak{Z}\left(q+r\right)$
		$\displaystyle-\sum_{a+c=s-1}\sum_{n=0}^{a}{p+n\choose a}{a\choose n}\mathfrak{Z}\left(p+n\right)\sum_{r=0}^{c}{q+r\choose c}{c\choose r}\mathfrak{Z}\left(q+r\right)\mathfrak{Z}\left(1\right)$
	$\displaystyle=$	$\displaystyle\sum_{a+c=s}\sum_{n=0}^{a}\sum_{r=0}^{c}{p+n\choose a}{a\choose n}{q+r\choose c}{c\choose r}\mathfrak{Z}\left(p+n+q+r\right)$
		$\displaystyle-\sum_{a+c=s-1}\sum_{n=0}^{a}\sum_{r=0}^{c}{p+n\choose a}{a\choose n}{q+r\choose c}{c\choose r}\mathfrak{Z}\left(p+n+q+r+1\right).$

The result follows by comparing the coefficients. ∎

Note that the previous proposition generalizes the Chu-Vandermonde identity. To see this, evaluate on $t=0$ .

Proposition 4.2.

Let $n$ be a non-negative integer and $k\in\mathbb{N}$ . For any $k$ -partition $n=n_{1}+\cdots+n_{k}$ , with $n_{i}\geq 0$ , and for $m\geq n+k-1$ we have

{m\choose n}={k-1\choose 0}\sum_{\begin{subarray}{c}\sum m_{i}=m\\ m_{i}\geq n_{i}\end{subarray}}\prod_{i=1}^{k}{q_{i}\choose n_{i}}-{k-1\choose 1}\sum_{\begin{subarray}{c}\sum m_{i}=m-1\\ m_{i}\geq n_{i}\end{subarray}}\prod_{i=1}^{k}{q_{i}\choose n_{i}}\pm\cdots\\ +(-1)^{k-2}{k-1\choose k-2}\sum_{\begin{subarray}{c}\sum m_{i}=m-(k-2)\\ m_{i}\geq n_{i}\end{subarray}}\prod_{i=1}^{k}{q_{i}\choose n_{i}}+(-1)^{k-1}{k-1\choose k-1}\sum_{\begin{subarray}{c}\sum m_{i}=m-(k-1)\\ m_{i}\geq n_{i}\end{subarray}}\prod_{i=1}^{k}{q_{i}\choose n_{i}}.

Proof.

Decompose $\langle n\rangle$ as $\langle n_{1}\rangle*\langle n_{2}\rangle*\cdots*\langle n_{k}\rangle$ . Then the result is obtained by applying Equation (8) and computing the degree $m$ coefficient of the last row in the sequence of identities below:

	$\displaystyle\sum_{q=n}^{\infty}{q\choose n}x^{m}$	$\displaystyle=\mathfrak{Z}\left(n\right)$
		$\displaystyle=\mathfrak{Z}\left(n_{1}\right)(1-x)\mathfrak{Z}\left(n_{2}\right)(1-x)\cdots(1-x)\mathfrak{Z}\left(n_{k}\right)$
		$\displaystyle=\mathfrak{Z}\left(n_{1}\right)\mathfrak{Z}\left(n_{2}\right)\cdots\mathfrak{Z}\left(n_{k}\right)(1-x)^{k-1}$
		$\displaystyle=\sum_{q_{1}=n_{1}}^{\infty}{{q_{1}}\choose n_{1}}x^{q_{1}}\cdots\sum_{q_{k}=n_{k}}^{\infty}{{q_{k}}\choose n_{k}}x^{q_{k}}\sum_{j=0}^{k-1}(-1)^{j}{k-1\choose j}x^{j}.$

∎

Using $\mathfrak{Z}^{+}\left(n\right)$ and $*^{+}$ we obtain the equivalent identity:

Proposition 4.3.

Let $n=n_{1}+\cdots+n_{k}$ . Then for $v\geq n+k-1$

\left(\kern-3.00003pt\left(\genfrac{}{}{0.0pt}{}{v-k+1}{n}\right)\kern-3.00003pt\right)={k-1\choose 0}\sum_{\begin{subarray}{c}\sum v_{i}=v\\ v_{i}\geq 1\end{subarray}}\prod_{i=1}^{k}\left(\kern-3.00003pt\left(\genfrac{}{}{0.0pt}{}{v_{i}}{n_{i}}\right)\kern-3.00003pt\right)-{k-1\choose 1}\sum_{\begin{subarray}{c}\sum v_{i}=v-1\\ v_{i}\geq 1\end{subarray}}\prod_{i=1}^{k}\left(\kern-3.00003pt\left(\genfrac{}{}{0.0pt}{}{v_{i}}{n_{i}}\right)\kern-3.00003pt\right)+\cdots\\ +(-1)^{k-2}{k-1\choose k-2}\sum_{\begin{subarray}{c}\sum v_{i}=v-(k-2)\\ v_{i}\geq 1\end{subarray}}\prod_{i=1}^{k}\left(\kern-3.00003pt\left(\genfrac{}{}{0.0pt}{}{v_{i}}{n_{i}}\right)\kern-3.00003pt\right)+{k-1\choose k-1}\sum_{\begin{subarray}{c}\sum v_{i}=v-(k-1)\\ v_{i}\geq 1\end{subarray}}\prod_{i=1}^{k}\left(\kern-3.00003pt\left(\genfrac{}{}{0.0pt}{}{v_{i}}{n_{i}}\right)\kern-3.00003pt\right).

Following the ideas of the previous section, we define $f(x)*^{-}g(x)=f(x)\frac{1}{x}g(x)$ and generate the monoid over $\frac{x}{(1-x)^{2}}$ . In this case we study the combinatorics of the product of Ehrhart series (with respect to the basis formed by chains), see [15, Problem 6.3]. We associate the power series $\mathfrak{Z}^{-}\left(1\right)=\frac{x}{(1-x)^{2}}$ to the chain $\langle 1\rangle$ and extend by $\mathfrak{Z}^{-}\left(n\right)=\mathfrak{Z}^{-}\left(n-1\right)*^{-}\mathfrak{Z}^{-}\left(1\right)$ to get $\mathfrak{Z}^{-}\left(n\right)=\frac{x}{(1-x)^{2n}}$ . Applications of this structure to probability theory will be explained in Section 4.3.

Using the expansion of the Maclaurin series, we obtain the Vandermonde identity for negative integers:

Proposition 4.4.

Let $n=n_{1}+\cdots+n_{k}$ . Then for $v\geq k$ :

(16)

\left(\kern-3.00003pt\left(\genfrac{}{}{0.0pt}{}{v-k+1}{2n-1}\right)\kern-3.00003pt\right)=\sum_{\begin{subarray}{c}\sum v_{i}=v\\ v_{i}\geq 1\end{subarray}}\prod_{i=1}^{k}\left(\kern-3.00003pt\left(\genfrac{}{}{0.0pt}{}{v_{i}}{2n_{i}-1}\right)\kern-3.00003pt\right).

Proof.

It follows from $\mathfrak{Z}^{-}\left(n\right)=\mathfrak{Z}^{-}\left(n_{1}\right)*^{-}\mathfrak{Z}^{-}\left(n_{2}\right)\cdots\mathfrak{Z}^{-}\left(n_{k}\right)$ . ∎

From Equation (16) and $n=1+\cdots+1$ we obtain for $v\geq n$

(17)

{v+n-1\choose 2n-1}=\sum_{\begin{subarray}{c}\sum v_{i}=v\\ v_{i}\geq 1\end{subarray}}\prod_{i=1}^{n}{v_{i}}.

This gives a formula to compute certain binomial coefficients without using any division.

Proposition 4.5.

Given $q\in\mathbb{N}$ , then for $n\leq\frac{m+1}{2}$ we have

(18)

{q\choose 2n-1}=\sum_{\begin{subarray}{c}\sum v_{i}=q-(n-1)\\ v_{i}\geq 1\end{subarray}}\prod_{i=1}^{n}{v_{i}}.

Proof.

It follows from Equation (17). ∎

The latter identity requires that the lower entry in the binomial coefficient must be odd. Consider instead $n=1+\cdots+1$ . Then using Proposition 4.2, for $m\geq 2n-1$ ,

(19)

{m\choose n}={n-1\choose 0}\sum_{\begin{subarray}{c}\sum m_{i}=m\\ m_{i}\geq 1\end{subarray}}\prod_{i=1}^{n}m_{i}-{n-1\choose 1}\sum_{\begin{subarray}{c}\sum m_{i}=m-1\\ m_{i}\geq 1\end{subarray}}\prod_{i=1}^{n}m_{i}\pm\cdots\\ +(-1)^{n-2}{n-1\choose n-2}\sum_{\begin{subarray}{c}\sum m_{i}=m-(n-2)\\ m_{i}\geq 1\end{subarray}}\prod_{i=1}^{n}{q_{i}}+(-1)^{n-1}{n-1\choose n-1}\sum_{\begin{subarray}{c}\sum m_{i}=m-(n-1)\\ m_{i}\geq 1\end{subarray}}\prod_{i=1}^{n}{q_{i}}.

If we use $n^{2}=n+\cdots+n$ , then using Proposition 4.2, for $m\geq n^{2}+n-1$ ,

{m\choose n^{2}}={n-1\choose 0}\sum_{\begin{subarray}{c}\sum m_{i}=m\\ m_{i}\geq n\end{subarray}}\prod_{i=1}^{n}{q_{i}\choose n}-{n-1\choose 1}\sum_{\begin{subarray}{c}\sum m_{i}=m-1\\ m_{i}\geq n\end{subarray}}\prod_{i=1}^{n}{q_{i}\choose n}\pm\cdots

(20)

+(-1)^{n-2}{n-1\choose n-2}\sum_{\begin{subarray}{c}\sum m_{i}=m-(n-2)\\ m_{i}\geq n\end{subarray}}\prod_{i=1}^{n}{q_{i}\choose n}+(-1)^{n-1}{n-1\choose n-1}\sum_{\begin{subarray}{c}\sum m_{i}=m-(n-1)\\ m_{i}\geq n\end{subarray}}\prod_{i=1}^{n}{q_{i}\choose n}.

Similar identities allow us to compute ${m\choose n^{k}}$ in terms of ${m\choose n^{r}}$ for $r<k$ .

On Equation (17), for every partition $\sum v_{i}=v$ , if $v_{i}$ appears $s_{i}$ times then the term $\prod_{i}v_{i}$ will appear as many times as the multinomial coefficient ${n\choose s_{1},\cdots,s_{j}}$ . We compute

(21)

{v+n-1\choose 2n-1}=\sum_{\begin{subarray}{c}\sum v_{i}=v\\ \#v_{i}=s_{i}\end{subarray}}{n\choose s_{1},\cdots,s_{j}}\prod_{i=1}^{n}{v_{i}},

where the sum is over different $n$ -partitions of $v$ , and each term $v_{i}$ appears $s_{i}$ times.

Finally, we apply Proposition 4.3 to the case $2n-k=\sum^{k}_{i=1}2n_{i}-1,v\geq 2n-1$ .

\left(\kern-3.00003pt\left(\genfrac{}{}{0.0pt}{}{v-k+1}{2n-k}\right)\kern-3.00003pt\right)={k-1\choose 0}\sum_{\begin{subarray}{c}\sum v_{i}=v\\ v_{i}\geq 1\end{subarray}}\prod_{i=1}^{k}\left(\kern-3.00003pt\left(\genfrac{}{}{0.0pt}{}{v_{i}}{2n_{i}-1}\right)\kern-3.00003pt\right)-{k-1\choose 1}\sum_{\begin{subarray}{c}\sum v_{i}=v-1\\ v_{i}\geq 1\end{subarray}}\prod_{i=1}^{k}\left(\kern-3.00003pt\left(\genfrac{}{}{0.0pt}{}{v_{i}}{2n_{i}-1}\right)\kern-3.00003pt\right)\pm\\ \cdots+(-1)^{k-2}{k-1\choose k-2}\sum_{\begin{subarray}{c}\sum v_{i}=v-(k-2)\\ v_{i}\geq 1\end{subarray}}\prod_{i=1}^{k}\left(\kern-3.00003pt\left(\genfrac{}{}{0.0pt}{}{v_{i}}{2n_{i}-1}\right)\kern-3.00003pt\right)+{k-1\choose k-1}\sum_{\begin{subarray}{c}\sum v_{i}=v-(k-1)\\ v_{i}\geq 1\end{subarray}}\prod_{i=1}^{k}\left(\kern-3.00003pt\left(\genfrac{}{}{0.0pt}{}{v_{i}}{2n_{i}-1}\right)\kern-3.00003pt\right).

We then substitute Equation (16) to obtain, for $v\geq 2n-1+k-1$ ,

\left(\kern-3.00003pt\left(\genfrac{}{}{0.0pt}{}{v-k+1}{2n-k}\right)\kern-3.00003pt\right)={k-1\choose 0}\left(\kern-3.00003pt\left(\genfrac{}{}{0.0pt}{}{v-k+1}{2n-1}\right)\kern-3.00003pt\right)-{k-1\choose 1}\left(\kern-3.00003pt\left(\genfrac{}{}{0.0pt}{}{v-k}{2n-1}\right)\kern-3.00003pt\right)\pm\cdots\\ +(-1)^{k-2}{k-1\choose k-2}\left(\kern-3.00003pt\left(\genfrac{}{}{0.0pt}{}{v-2k+3}{2n-1}\right)\kern-3.00003pt\right)+(-1)^{k-1}{k-1\choose k-1}\left(\kern-3.00003pt\left(\genfrac{}{}{0.0pt}{}{v-2k+2}{2n-1}\right)\kern-3.00003pt\right),

{v-2k+2n\choose 2n-k}={k-1\choose 0}{v-k-1+2n\choose 2n-1}-{k-1\choose 1}{v-k-2+2n\choose 2n-1}\pm\cdots\\ +(-1)^{k-2}{k-1\choose k-2}{v-2k+1+2n\choose 2n-1}+(-1)^{k-1}{k-1\choose k-1}{v-2k+2n\choose 2n-1}.

Our identities come from objects in which a notion of series-parallel order is defined. It is expected that new series-parallel algebras will imply new properties of binomial coefficients.

4.2. Finite partitions that allow empty sets

Define $\tilde{n}(m,k)=\sum_{\sum_{i=1}^{k}m_{i}=m}1$ . In words, $\tilde{n}(m,k)$ is the number of partitions of $m$ points into $k$ sets that can be empty. Let $n=0$ , $k\in\mathbb{N}$ , $m\geq k-1$ . From Proposition 4.2 we obtain the identity

(22)

1={k-1\choose 0}\tilde{n}(m,k)-{k-1\choose 1}\tilde{n}(m-1,k)+\cdots\\ +(-1)^{k-2}{k-1\choose k-2}\tilde{n}(m-(k-2),k)+(-1)^{k-1}{k-1\choose k-1}\tilde{n}(m-(k-1),k).

The Stirling number of the second kind ${m\brace k}$ is defined as the number of partitions of a set with $m$ elements into $k$ non-empty subsets. It follows that

\tilde{n}(m,k)={k\choose 0}{m\brace k}+{k\choose 1}{m\brace k-1}+\cdots+{k\choose k-1}{m\brace 1}.

4.3. Probability

Consider $N$ classes of objects. Take $V$ objects with repetition. Divide the $N$ classes into groups, the first with $n_{1}$ classes, the next with $n_{2}$ classes, and so on. We assume $N=n_{1}+\cdots+n_{k}$ . Let $V=v_{1}+\cdots+v_{k}$ . What is the probability that $v_{1}$ objects belong to the group of $n_{1}$ fixed classes, and $v_{2}$ objects belong to the group of $n_{2}$ fixed classes, and so on? The answer comes from the multivariate negative hypergeometric distribution,

P(X=(v_{1},\cdots,v_{k}))=\frac{\left(\kern-3.00003pt\left(\genfrac{}{}{0.0pt}{}{n_{1}}{v_{1}}\right)\kern-3.00003pt\right)\dots\left(\kern-3.00003pt\left(\genfrac{}{}{0.0pt}{}{n_{k}}{v_{k}}\right)\kern-3.00003pt\right)}{\left(\kern-3.00003pt\left(\genfrac{}{}{0.0pt}{}{N}{V}\right)\kern-3.00003pt\right)}.

As an application of our methods we provide a direct proof that $P$ is a distribution.

Proposition 4.6.

The function $P$ is a distribution.

Proof.

From $\frac{x}{(1-x)^{N}}=\frac{x}{(1-x)^{n_{1}}}\frac{1}{x}\cdots\frac{1}{x}\frac{x}{(1-x)^{n_{k}}}$ and Proposition 4.4 we obtain

\left(\kern-3.00003pt\left(\genfrac{}{}{0.0pt}{}{V-(k-1)}{N-1}\right)\kern-3.00003pt\right)=\sum_{\begin{subarray}{c}\sum v_{i}=V\\ v_{i}\geq 1\end{subarray}}\prod_{i=1}^{k}\left(\kern-3.00003pt\left(\genfrac{}{}{0.0pt}{}{v_{i}}{n_{i}-1}\right)\kern-3.00003pt\right).

Equivalently,

\left(\kern-3.00003pt\left(\genfrac{}{}{0.0pt}{}{N}{V-k}\right)\kern-3.00003pt\right)=\sum_{\begin{subarray}{c}\sum v_{i}=V\\ v_{i}\geq 1\end{subarray}}\prod_{i=1}^{k}\left(\kern-3.00003pt\left(\genfrac{}{}{0.0pt}{}{n_{i}}{v_{i}-1}\right)\kern-3.00003pt\right),

and by changing variables we have

\left(\kern-3.00003pt\left(\genfrac{}{}{0.0pt}{}{N}{W}\right)\kern-3.00003pt\right)=\sum_{\begin{subarray}{c}\sum w_{i}=W\\ w_{i}\geq 0\end{subarray}}\prod_{i=1}^{k}\left(\kern-3.00003pt\left(\genfrac{}{}{0.0pt}{}{n_{i}}{w_{i}}\right)\kern-3.00003pt\right)\ \text{ and }\ 1=\sum_{\begin{subarray}{c}\sum w_{i}=W\\ w_{i}\geq 0\end{subarray}}\frac{\prod_{i=1}^{k}\left(\kern-3.00003pt\left(\genfrac{}{}{0.0pt}{}{n_{i}}{w_{i}}\right)\kern-3.00003pt\right)}{\left(\kern-3.00003pt\left(\genfrac{}{}{0.0pt}{}{N}{W}\right)\kern-3.00003pt\right)}.

∎

We also provide a method to compute the expectation value of the negative hypergeometric distribution:

$\displaystyle\sum_{W=1}x^{W}\sum_{w=1}^{W}w\left(\kern-3.00003pt\left(\genfrac{}{}{0.0pt}{}{n}{w}\right)\kern-3.00003pt\right)\left(\kern-3.00003pt\left(\genfrac{}{}{0.0pt}{}{N-n}{W-w}\right)\kern-3.00003pt\right)$	$\displaystyle=$	$\displaystyle\left(\sum_{i=1}i\left(\kern-3.00003pt\left(\genfrac{}{}{0.0pt}{}{n}{i}\right)\kern-3.00003pt\right)x^{i}\right)\left(\sum_{j=1}\left(\kern-3.00003pt\left(\genfrac{}{}{0.0pt}{}{N-n}{j}\right)\kern-3.00003pt\right)x^{j}\right)$
	$\displaystyle=$	$\displaystyle\left(x\frac{d}{dx}\left(\frac{1}{(1-x)^{n}}\right)\right)\frac{1}{(1-x)^{N-n}}$
	$\displaystyle=$	$\displaystyle\frac{nx}{(1-x)^{N+1}}$
	$\displaystyle=$	$\displaystyle\sum_{W=1}n\left(\kern-3.00003pt\left(\genfrac{}{}{0.0pt}{}{N+1}{W-1}\right)\kern-3.00003pt\right)x^{W}.$

It follows that

\mathbb{E}(P)=\sum_{w=0}^{W}\frac{w\left(\kern-3.00003pt\left(\genfrac{}{}{0.0pt}{}{n}{2}\right)\kern-3.00003pt\right)\left(\kern-3.00003pt\left(\genfrac{}{}{0.0pt}{}{N-n}{W-w}\right)\kern-3.00003pt\right)}{\left(\kern-3.00003pt\left(\genfrac{}{}{0.0pt}{}{N}{W}\right)\kern-3.00003pt\right)}=\frac{n\left(\kern-3.00003pt\left(\genfrac{}{}{0.0pt}{}{N+1}{W-1}\right)\kern-3.00003pt\right)}{\left(\kern-3.00003pt\left(\genfrac{}{}{0.0pt}{}{N}{W}\right)\kern-3.00003pt\right)}.

5. Open problems

We conclude with a list of open problems.

•

Do the polynomials in Remark 2.18 have a combinatorial interpretation?
•

Is there a combinatorial proof of Proposition 4.1?
•

Is there a proof of Proposition 4.2 by computing the Euler characteristic or using the inclusion-exclusion principle?
•

What is the topological story behind the $*^{-}$ structure linked to the negative hypergeometric distribution?
•

What are the generators of the operad of finite posets?

Acknowledgements

We thank Elton P. Hsu for carefully reading the section on probability. We thank Max Hopkings, Isaias Marin Gaviria, and Mario Sanchez for several discussions. We thank John Baez for online discussions about binomial identities and Theo Johnson-Freyd for discussions about the units of the operad of series-parallel posets. Furthermore, we thank Raman Sanyal for suggesting the reference [4], and the anonymous referee(s) for many helpful comments and for pointing us to the papers [11], [24] and [30]. The second author was funded through the Royal Society grant URF $\setminus$ R1 $\setminus$ 20147. The third author was funded by the National Research Foundation of Korea (NRF) grant funded by the Korea government (MSIT) (No. 2020R1C1C1A0100826). This project started while the third author worked at NewSci Labs and he thanks them for their hospitality.

References

[1] Federico Ardila and Mario Sanchez. Valuations and the Hopf monoid of generalized permutahedra. 2010.
[2] M. Beck, J. A. De Loera, M. Develin, J. Pfeifle, and R. P. Stanley. Coefficients and roots of Ehrhart polynomials. In Integer points in Polyhedra-Geometry, Number Theory, Algebra, Optimization, volume 374, pages 15–36. Contemp. Math, 2005.
[3] Matthias Beck and Sinai Robins. Computing the Continuous Discretely. Integer-Point Enumeration in Polyhedra. Springer, New York, 2nd edition, 2007.
[4] Matthias Beck and Raman Sanyal. Combinatorial reciprocity theorems: An invitation to enumerative Geometric Combinatorics, volume 195. American Mathematical Society, Providence, Rhode Island, first edition, 2018.
[5] François Bergeron, Gilbert Labelle, and Pierre Leroux. Combinatorial species and tree-like structures. Encyclopedia of Mathematics and its applications. Cambridge University Press, 1997.
[6] Benjamin Braun. An Ehrhart series formula for reflexive polytopes. Electron. J. Comb., 13, 2006.
[7] F. Breuer. Ehrhart f⁢-coefficients of polytopal complexes are non-negative integers. Electron. J. Combin., 19(4):16, 2012.
[8] Thomas Browning, Max Hopkins, and Zander Kelley. Doppelgangers: The Ur-operation and posets of bounded height, 2018.
[9] Louis Comtet. Advanced Combinatorics: The art of finite and infinite expansions; Rev. version. Reidel, Dordrecht, 1974. Trans. of : Analyse combinatoire. Paris : Presses Univ. de France, 1970.
[10] V.G. Drinfeld. On quasitriangular quasi-Hopf algebras and on a group that is closely connected with $\text{Gal}(\overline{\mathbb{Q}}/\mathbb{Q}$ ). Algebra i Analiz, page 149–181, 1990.
[11] U. Faigle and R. Schrader. On the computational complexity of the order polynomial. Discrete Appl. Math., 15:261–269, 1986.
[12] Frédéric Fauvet, Loïc Foissy, and Dominique Manchon. Operads of finite posets. Electronic Journal of Combinatorics, 25, 04 2016.
[13] Joseph Gallian. A dynamic survey of graph labeling. Electron J Combin DS6, 19:553, 11 2000.
[14] H.W. Gould. Combinatorial identities: A standardized set of tables listing 500 binomial coefficient summations. Gould, 1972.
[15] Christian Haase, Benjamin Nill, and Andreas Paffenholz. Lectures notes on lattice polytopes, 2012.
[16] Zachary Hamaker, Rebecca Patrias, Oliver Pechenik, and Nathan Williams. Doppelgängers: Bijections of plane partitions. International Mathematics Research Notices, 2020(2):487–540, 03 2018.
[17] Akihiro Higashitani. Classification of Ehrhart polynomials of integral simplices. 24th International Conference on Formal Power Series and Algebraic Combinatorics (FPSAC 2012) , Nagoya, Japan, pages 587–594, 2012.
[18] Erkko Lehtonen. Labeled posets are universal. European Journal of Combinatorics, 29(2):493–506, 2008.
[19] Zhonghua Li and Chen Qin. Shuffle product formulas of multiple zeta values. Journal of Number Theory, 171:79–111, 2017.
[20] Bruno Loday, Jean-Louis an Vallette. Algebraic Operads. Springer-Verlag Berlin Heidelberg, 1st edition, 2012.
[21] Ian G. MacDonald. Polynomials associated with finite cell-complexes. Journal of the London Mathematical Society, s2-4(1):181–192, 1971.
[22] M Mendez and J Yang. Möbius species. Advances in Mathematics, 85(1):83–128, 1991.
[23] T. Kyle Petersen. Eulerian Numbers. Birkhäuser advanced texts basler Lehrbücher series. Birkhäuser, New York, NY, 1 edition, 2015.
[24] Richard P. Stanley. A chromatic-like polynomial for ordered sets. In Proc. Second Chapel Hill Conf. on Combinatorial Mathematics and its Applications, pages 421–427, May 1970.
[25] Richard P. Stanley. Decompositions of rational convex polytopes. Annals of Discrete Mathematics, 6:333–342, 1980.
[26] Richard P. Stanley. Two poset polytopes. Discrete & Computational Geometry, 1(1):9–23, 1986.
[27] Richard P. Stanley. A monotonicity property of h-vectors and h*-vectors. European Journal of Combinatorics, 14(3):251–258, 1993.
[28] Richard P. Stanley. Enumerative Combinatorics: Volume I. Cambridge Studies in Advanced Mathematics. Cambridge University Press, 1997.
[29] Richard P. Stanley. Enumerative Combinatorics: Volume II. Cambridge Studies in Advanced Mathematics. Cambridge University Press, 2001.
[30] D. G. Wagner. Enumeration of functions from posets to chains. European Journal of Combinatorics, 13(4):313–324, 1992.
[31] Herbert S. Wilf. Generatingfunctionology. A K Peters Ltd., Wellesley, MA, third edition, 2006.
[32] Tomoyuki Yoshida. Categorical aspects of generating functions (I): Exponential formulas and Krull–Schmidt categories. Journal of Algebra, 240(1):40–82, 2001.

An algebra over the operad of posets and structural binomial identities

Abstract.

1. Introduction

1.1. Related work

2. Order series

Definition 2.1.

Definition 2.2.

Proposition 2.3.

Lemma 2.4.

Proposition 2.5.

Proof.

Proposition 2.6.

Proof.

Proposition 2.7.

Proof.

Corollary 2.8.

Proof.

Example 2.9.

Remark 2.10.

Definition 2.11.

Example 2.12.

Proposition 2.13.

Proof.

Theorem 2.14.

Proof.

Lemma 2.15.

Proof.

Proposition 2.16.

Proof.

Remark 2.17.

Remark 2.18.

Lemma 2.19.

Proof.

3. Representability of posets

Proposition 3.1.

Proof.

3.1. The inverse problem

Proposition 3.2.

Proof.

Proposition 3.3.

Proof.

3.2. Comparison with Ehrhart theory

Remark 3.4.

Lemma 3.5.

Proof.

Proposition 3.6 (ℨ+​(P)\mathfrak{Z}^{+}\left(P\right) satisfies the inclusion-exclusion principle).

Proof.

Example 3.7.

4. Combinatorics

4.1. Identities

Proposition 4.1.

Proof.

Proposition 4.2.

Proof.

Proposition 4.3.

Proposition 4.4.

Proof.

Proposition 4.5.

Proof.

4.2. Finite partitions that allow empty sets

4.3. Probability

Proposition 4.6.

Proof.

5. Open problems

Acknowledgements

References

Proposition 3.6 ( $\mathfrak{Z}^{+}\left(P\right)$ satisfies the inclusion-exclusion principle).