A Generalization of Descent Polynomials

Updated 24 Oct 2026

Sole-author research in enumerative combinatorics. Written in 2021; published in Discrete Mathematics in 2023.

A permutation records an order. Its descent set records exactly where that order falls: the positions at which an entry is larger than the next one. Fix those positions and count all permutations that realize them. Although the permutations become longer as the alphabet grows, their number is eventually governed by a polynomial.

In this paper, I extended that counting problem to multiset permutations, where every label appears several times. The resulting family has two parameters: the number of distinct labels and their common multiplicity. I proved polynomiality in the first parameter, found the sharp point at which increasing the second stops changing the answer, and obtained an explicit formula for the stabilized polynomial. Its coefficients have a direct counting interpretation in a particular binomial basis, together with a sharp description of which shifts preserve nonnegativity.

The useful structural idea is that a prescribed descent set leaves only a bounded initial segment free. Everything after the last descent has to be sorted. That converts a count of increasingly long words into a finite collection of order patterns.

Fixing the positions of the descents

For a word $w=(w_1,\ldots,w_N)$, define

For example,

The positions are what matter, not the values of the entries at those positions. Equality is not a descent: in a word with repeated letters, $2,2$ is a weakly increasing pair.

The ordinary descent polynomial counts permutations of $\{1,\ldots,n\}$ with one specified descent set $I$. This is different from an Eulerian polynomial, which, for a fixed $n$, packages permutations according to their number of descents. Here the pattern $I$ stays fixed while $n$ varies.

My generalization replaces the set by the multiset

where the notation means $m$ copies of each label, not exponentiation. Copies of the same label are indistinguishable. If $S_n^{(m)}$ denotes its distinct permutations, the counting function is

Setting $m=1$ recovers the ordinary descent polynomial. The empty descent set always gives $\mathfrak d^m(\varnothing,n)=1$: there is exactly one weakly increasing arrangement.

A complete example

Take $n=3$, $m=2$ and $I=\{2\}$. We want arrangements of $1,1,2,2,3,3$ with a descent at position $2$ and nowhere else. There are exactly five:

This example already exposes the mechanism behind the general results. Once the first two entries are chosen, the other copies have only one allowable order. We must still check the boundary between the prefix and the suffix: a sorted suffix alone does not guarantee the required final descent.

Two parameters and two kinds of structure

Let

Let $L$ be the length of the longest consecutive run in $I$. For example, $I=\{2,3,5,7,10,11,12\}$ has $L=3$ because of the run $10,11,12$.

The main results describe different directions in this two-parameter family.

Polynomiality in the alphabet size. For every fixed positive multiplicity $m$, the function $\mathfrak d^m(I,n)$ agrees with a polynomial in $n$ for $n\ge a$.

Stabilization in the multiplicity. For $n>a$, the counts are weakly increasing as $m$ grows. They stop changing once

This threshold is sharp when $n\ge L+1$: $M$ is the smallest positive multiplicity from which the count stays constant. If $M=1$, the family is already stable at its first allowed multiplicity. The condition on $n$ matters: a run of $L$ consecutive descents needs $L+1$ distinct labels; with fewer labels, every count is zero.

The two statements should not be conflated. One says how the count changes when more labels become available. The other says that, beyond a precise point, more copies of the same labels add no new possibilities.

Seeing stabilization in a formula

For the single descent set $I=\{2\}$, the threshold is $M=2$. The two regimes have simple forms:

Here $n\ge2$. The first formula chooses two distinct prefix labels; the second allows a repeated label as well. In each case, exactly one prefix fails to produce the boundary descent.

The identical last two columns illustrate a theorem about all $m\ge2$, not a conjecture inferred from the displayed cases.

Why longer words eventually stop adding choices

After position $a=\max I$, no descent is permitted. Consequently, the suffix must be weakly increasing, and the first $a$ entries determine the entire word.

At a descent position, the entry cannot be $1$. There are $t$ such positions, so at most $a-t$ copies of $1$ can occur in the prefix. Once $m\ge a-t+1$, a copy of $1$ is guaranteed to remain for the sorted suffix. Its first entry is therefore $1$.

The last required descent now has the particularly simple condition

Also, any one label can appear at most $a-t+1$ times in an admissible prefix. To see this, cut the prefix at every weak increase, partitioning it into maximal strictly decreasing runs. Its $t-1$ internal descents leave exactly $a-t+1$ such runs, and a fixed label appears at most once in each. Thus the multiplicity bound no longer excludes any admissible prefix once $m\ge M$.

The stabilized problem is therefore a count of finite words $v=(v_1,\ldots,v_a)$ satisfying

The growing sorted suffix has disappeared from the problem. To prove sharpness, the paper constructs an admissible prefix containing exactly $M$ copies of one label. That prefix cannot exist at multiplicity $M-1$; the assumption $n\ge L+1$ supplies enough labels for its strict drops.

Write $d^\infty(I,n)$ for the resulting stable polynomial. In the polynomial range $n\ge a$, it agrees with $\mathfrak d^m(I,n)$ for every $m\ge M$. The superscript $\infty$ names this finite stabilization; it does not require infinite words or a limiting approximation.

Two proofs of polynomiality

The paper gives both an elementary counting proof and a symmetric-function proof. They explain the same phenomenon through different representations.

Count the order patterns in the prefix

Work in the polynomial range $n\ge a$. Temporarily omit the requirement that position $a$ be a descent. Let $D^m(I,n)$ count prefixes of length $a$ with descent set $I\setminus\{a\}$, using each label at most $m$ times.

A prefix uses some number $r\le a$ of distinct labels. Record their multiplicities in increasing label order:

Let $C(A,I)$ be the number of such prefixes after their labels are normalized to $1,\ldots,r$. Choosing the actual labels contributes $\binom nr$, independently of their order pattern. Hence

where $\operatorname{Comp}(a,m)$ is the finite set of compositions of $a$ with parts at most $m$, and $\ell(A)$ is the number of parts. Every summand is a polynomial in $n$, and all remaining data depend only on $I$ and $m$.

Completing the sorted suffix produces either the desired last descent or no descent at that boundary. Thus

Induction on the size of the descent set proves polynomiality. The proof turns a global arrangement problem into the choice of labels for finitely many normalized patterns.

Encode the words as ribbon tableaux

There is also a geometric representation. Break a word at its descents. Each weakly increasing run becomes a row of a ribbon-shaped tableau; strict drops become the strict inequalities in the overlapping columns. A ribbon is a connected skew Young diagram containing no $2\times2$ square.

For the appropriate shape $\lambda/\mu$, the count becomes a coefficient of a skew Schur function:

The Jacobi–Trudi identity expresses this Schur function as a determinant of complete homogeneous symmetric functions. The determinant’s dimension is fixed by $I$. As $n$ grows, only the ribbon’s long final row grows; each determinant term has one large factor $h_{nm-u}$ and finitely many factors of fixed total degree $u$.

Extracting the equal-multiplicity coefficient again reduces to choosing labels for a fixed pattern. Each term is eventually polynomial in $n$, so their finite signed sum is too. This proof connects the counting family to symmetric functions, rather than treating the polynomiality as an isolated numerical property.

An explicit formula for the stable polynomial

In the stable regime, no multiplicity constraint remains in the prefix. Its weakly increasing runs can be counted by stars and bars, and inclusion–exclusion enforces a strict drop at each prescribed internal boundary.

Define the gaps between the descent positions by

For a composition $A=(a_1,\ldots,a_s)$ of $t$, group consecutive gaps into $s$ blocks; let $\sigma_j$ be the sum of the gaps in the $j$th block. For example, $A=(2,1)$ groups $(\beta_1,\beta_2,\beta_3)$ into $(\beta_1+\beta_2,\beta_3)$.

Put

This is the number of weakly increasing words of length $r$ on $n$ labels. The paper’s formula can then be written compactly as

Merging adjacent runs removes a required descent, producing the inclusion–exclusion sign. The final subtraction removes the all-$1$ final block, the only weakly increasing block that would end at $1$ rather than above it.

For $I=\{1,3\}$, the gap sequence is $(1,2)$. There are only two compositions of $2$, so

This is a degree-$3$ polynomial arising from words whose lengths keep growing. The last descent position, rather than the eventual word length, governs that degree.

Coefficients that count normalized patterns

A polynomial can have positive or negative coefficients depending on its basis. For the stabilized family, the basis

has a particularly natural meaning. Write

The coefficient $b_i(I)$ counts normalized prefixes $v$ of length $a$ such that:

• $\operatorname{Des}(v)=I\setminus\{a\}$;
• all entries lie in $\{1,\ldots,i+1\}$;
• each of $2,\ldots,i+1$ occurs at least once;
• the final entry is greater than $1$.

The label $1$ is optional. The other $i$ labels are mandatory, and choosing their actual values from $\{2,\ldots,n\}$ contributes the factor $\binom{n-1}{i}$. The count therefore separates into a choice of labels and a normalized pattern.

The coefficient theorem is more precise than nonnegativity:

and every other coefficient is zero. In particular, $d^\infty(I,n)$ has degree exactly $a$.

For $I=\{2\}$, the two patterns counted by $b_1$ are $(1,2)$ and $(2,2)$; the one pattern counted by $b_2$ is $(2,3)$. Thus

In the unshifted basis, the same polynomial is

The negative constant is not a defect in the count. It shows that the choice of basis can reveal or obscure its direct combinatorial structure.

The shift boundary is sharp

The paper classifies every integer shift. In the expansion in $\bigl(\binom{n+k}{i}\bigr)_{i\ge0}$, all coefficients are integers, and:

• if $k\le-1$, every coefficient is nonnegative;
• if $k\ge0$, at least one coefficient is negative.

For the unshifted basis, write its coefficients as $c_i(I)$. There is an exact initial segment:

Pascal’s identity transfers nonnegativity toward smaller shifts. Together with the alternating initial coefficients at shift $0$, this identifies $\binom{n-1}{i}$ as the boundary within this family of shifted binomial bases: it retains a direct nonnegative counting interpretation, while every shift to its right introduces a negative coefficient.

Paper and publication

I carried out most of this work at the Research Science Institute in summer 2021, mentored by Pakawut Jiradilok, who proposed the topic and guided the research. The paper is sole-authored.

Angel Raychev. “A generalization of descent polynomials.” Discrete Mathematics 346(1), Article 113105, 2023. DOI: 10.1016/j.disc.2022.113105.

The downloadable paper is the original September 2021 arXiv preprint, not the publisher’s typeset version. It contains the full proofs, seven figures, and references to the descent-polynomial and symmetric-function literature.

The central outcome is a structured family of counting polynomials: an elementary prefix decomposition explains polynomiality, ribbon tableaux place it in the language of symmetric functions, and stabilization exposes coefficients that themselves count finite order patterns.