I'm not a robot
New member
- Joined
- Jan 26, 2021
- Messages
- 1
Let [MATH]n\in \mathbb{Z}_{>0}[/MATH]. For every subset [MATH]S\subseteq \left[ n-1\right][/MATH] we define a poset [MATH]P_S=\left([n],\le_{P_S}\right)[/MATH] given by the covering relation [MATH]\lessdot[/MATH] which is defined as
Useful Definitions
- A function [MATH]f\colon P_S\to [m][/MATH] is called order-preserving for [MATH]P_S[/MATH], if for any [MATH]x,y\in P_S[/MATH]
- We denote with [MATH]\Omega(P_S,m)[/MATH] the order polynomial of [MATH]P_S[/MATH] for [MATH]m[/MATH], i.e.
- For any permutation [MATH]w\in\mathcal{S}_n[/MATH] we denote with [MATH]\mathsf{Des}(w)[/MATH] the descent set of [MATH]w[/MATH], i.e.
The question
We want to calculate, for any given [MATH]m\in\mathbb{Z}_{>0} [/MATH]the sum of the order polynomials on the subsets [MATH]S\subseteq[n-1][/MATH], i.e.
My progress
It seems that the requested sum is equal to
but I did not manage to show it.
It is not hard to show that the set of all the natural labelings for a given subset [MATH]S[/MATH] has the same cardinality as the set of all permutations of [MATH]$[n]$[/MATH] with descent set equal to [MATH]S[/MATH], i.e.
It is well known that
I tried to use these facts in order to calculate the requested sum but I failed...
I would love some help
[MATH]\forall i\in S \qquad i+1\lessdot i [/MATH] [MATH] \forall i\in\left[n-1\right]\setminus S\qquad
i\lessdot i+1[/MATH]
Clearly, the Hasse diagram of these kind of orderings represents a path with an ordering defined by the corresponding set. For instance if [MATH]n=3[/MATH] we have the posetsUseful Definitions
- A function [MATH]f\colon P_S\to [m][/MATH] is called order-preserving for [MATH]P_S[/MATH], if for any [MATH]x,y\in P_S[/MATH]
[MATH]x<_{P_S}y\implies f(x)\le f(y),[/MATH]
where [MATH]m\in\mathbb{Z_{>0}}[/MATH].- We denote with [MATH]\Omega(P_S,m)[/MATH] the order polynomial of [MATH]P_S[/MATH] for [MATH]m[/MATH], i.e.
[MATH]\Omega(P_S,m)=\#\left\{ f\colon P_S\to [m]\,\mid f\;\; \text{is order-preserving}\right\}[/MATH]
- We call an order-preserving bijection [MATH]\omega\colon P_S\to[n][/MATH] natural labeling of [MATH]P_S[/MATH].- For any permutation [MATH]w\in\mathcal{S}_n[/MATH] we denote with [MATH]\mathsf{Des}(w)[/MATH] the descent set of [MATH]w[/MATH], i.e.
[MATH]\mathsf{Des}(w)=\left\{ i\in\left[n\right]\mid w\left(i\right)>w\left(i+1\right)\right\} [/MATH]
The question
We want to calculate, for any given [MATH]m\in\mathbb{Z}_{>0} [/MATH]the sum of the order polynomials on the subsets [MATH]S\subseteq[n-1][/MATH], i.e.
[MATH]\sum_{S\subseteq[n-1]}\Omega\left(P_{S},m\right). [/MATH]
My progress
It seems that the requested sum is equal to
[MATH]m(1+m)^{n-1}, [/MATH]
but I did not manage to show it.
It is not hard to show that the set of all the natural labelings for a given subset [MATH]S[/MATH] has the same cardinality as the set of all permutations of [MATH]$[n]$[/MATH] with descent set equal to [MATH]S[/MATH], i.e.
[MATH]\#\left\{ \omega\colon P_{S}\to[n]\mid\omega\;\text{natural labeling}\right\} =\#\left\{ w\in\mathcal{S}_{n}\mid\mathsf{Des}\left(w\right)=S\right\} .[/MATH]
It is well known that
[MATH]\Omega\left(P_{S},m\right)=\sum_{w\in A_{S}}\binom{m+n-\mathsf{des}\left(w\right)-1}{n},[/MATH]
where[MATH] A_S[/MATH] is the set of permutations that corresponds to the natural labelings of [MATH]P_S[/MATH], i.e.[MATH]A_{S}=\left\{ w\in\mathcal{S}_{n}\mid w=\left(\omega\left(1\right),\omega\left(2\right),\dots,\omega\left(n\right)\right)\text{ for some natural labeling }\omega\text{ of }P_{S}\right\} [/MATH]
I tried to use these facts in order to calculate the requested sum but I failed...
I would love some help
Last edited: