"Upside-down unimodal" sequences in combinatorics

Question

Recall a sequence $a_0,\ldots,a_n$ of positive integers is unimodal if $a_0 \leq \cdots \leq a_m \geq \cdots \geq a_n$ for some $0 \leq m \leq n$. Unimodal integer sequences are abundant in combinatorics. For instance, see the classic survey "Log-concave and unimodal sequences in algebra, combinatorics, and geometry" by Stanley.

For lack of a better term, let me call a sequence $a_0,\ldots,a_n$ of positive integers upside-down unimodal if $a_0 \geq \cdots \geq a_m \leq \cdots \leq a_n$ for some $0 \leq m \leq n$.

Question: What are natural examples of upside-down unimodal sequences in combinatorics?

Here is one that I know. Let $b_{n,k}$ be the number of words $w=w_1, w_2,\ldots, w_{2n}$ with $w_i = \pm 1$ such that the greatest $m$ with $w_1 + \cdots + w_m = 0$ is $m=2k$. Then $b_{n,k} = \binom{2k}{k}\binom{2(n-k)}{n-k}$, and the sequence $b_{n,0},b_{n,1},\ldots,b_{n,n}$ is (symmetric and) upside-down unimodal (OEIS: A067804). Evidently, $b_{n,k}$ is intimately related to the famous identity $4^n =\sum_{k=0}^{n} \binom{2k}{k}\binom{2(n-k)}{n-k}$ and to the last return time for a simple random walk on $\mathbb{Z}$; see this MO answer.

EDIT: In light of the examples from Chris McDaniel, I should amend to say that I am mostly interested in sequences where $a_0 > \cdots > a_m < \cdots < a_n$ for some $0 < m < n$.

Answer 1

Log convexity (meaning $a_k^2\leq a_{k-1}a_{k+1}, \ 1\leq k\leq n-1$) seems to imply your upside down unimodal condition, and according to this paper, there are several such combinatorial sequences. An easy example of a log convex sequence is the factorial sequence $$(0!, 1!, \ldots, n!);$$ it's upside down unimodal with $m=0$ (but then again, I guess every monotone sequence trivially satisfies both right side up and upside down unimodality conditions). In fact, it seems that your sequence above $(b_{n,0},\ldots,b_{n,n})$ is log convex as well.

Added October 10, 2023: I stumbled across the following result (Theorem 9) in this old paper of Stanley on log concavity and unimodality, attributed to Rees and Sharp:

Theorem: (Rees-Sharp 1978) Let $R$ be a commutative Noetherian local ring with maximal ideal $\mathfrak{m}$ and Krull dimension $n$, and let $I,J\subset R$ be any $\mathfrak{m}$-primary ideals, and let $\ell(R/I^rJ^s)$ be length of the quotient of $R$ by powers of the product of ideals. Then for $r$ and $s$ sufficiently large, $\ell(R/I^rJ^s)$ is a polynomial in $r$ and $s$, and if the total degree $n$ part of that polynomial is $$P(r,s)=\frac{1}{n!}\sum_{k=0}^n\binom{n}{k}E_k(I,J)r^{n-k}s^k$$ then the coefficient sequence $E_0(I,J),\ldots,E_n(I,J)$ is log convex, and each $E_k(I,J)$ is a nonnegative integer (I think these are called mixed multiplicities).

Answer 2

I ran an automated filtration of OEIS for sequences which appear to have the right shape, and then filtered manually to find the combinatoric ones. Only two families of sequences survived both filtrations:

1. Floor of the expected value of number of trials until exactly two/three/four/five cells are empty in a random distribution of $n$ balls in $n$ cells: A210113, A210114, A210115, A210116
2. Number of $(n+k) \times m$ arrays of values in $[r]$ where each $t \times t$ subblock satisfies some property $P$: A204369, A204748, A224581, A251888, A252108, A252258, A252379, A253469, A253847, A254912, A254913, A255041, A255042, A258611, A258891, A258892, A258893, A258954, A258955, A258956, A259011, A259012. I don't think any of these sequences had confirmed formulae, but most of them had conjectured linear recurrences which permit the inference that they are in fact upside-down unimodal.

Answer 3

FindStat has some, but very few, upside-down-unimodal generating functions, that are not just increasing or decreasing. For example, on Dyck paths, we find

• https://www.findstat.org/StatisticsDatabase/St000026, the position of the first return of a Dyck path.

There are some more, if you do not ignore intermediate zero coefficients, for example https://www.findstat.org/StatisticsDatabase/St000117.

Beware that all of these are candidates!

On permutations, there are

• https://www.findstat.org/StatisticsDatabase/St000487, The length of the shortest cycle of a permutation.
• https://www.findstat.org/StatisticsDatabase/St000501, The size of the first part in the decomposition of a permutation.
• https://www.findstat.org/StatisticsDatabase/St0001468, The smallest fixpoint of a permutation.

On (unlabelled, simple, possibly disconnected) graphs, we have candidates:

• https://www.findstat.org/StatisticsDatabase/St001342, The number of vertices in the center of a graph.
• https://www.findstat.org/StatisticsDatabase/St001654, The monophonic hull number of a graph.

Here is a program to do the search in SageMath (longer than necessary):

def is_increasing(gf):
    if gf in ZZ:
        return True
    return all(gf[i] <= gf[i+1] for i in range(gf.valuation(), gf.degree()))

def is_unimodal(gf, with_boundary=True):
    if gf in ZZ:
        return True
    increasing = True
    m = gf.valuation()
    n = gf.degree()
    if with_boundary:
        m -= 1
        n += 1
    for i in range(m, n):
        if not increasing and gf[i] < gf[i+1]:
            return False
        if increasing and gf[i] > gf[i+1]:
            increasing = False
    return True

def is_upside_down_unimodal(gf):
    return is_unimodal(-gf, with_boundary=False)

def search(collection, verbose=True):
    """
    sage: search("graphs", verbose=False)
    """
    L = LaurentPolynomialRing(QQ, "q", sparse=True)
    poly = lambda gf: L(L(gf).coefficients())
    for s in findstat(domain=collection):
        if s.id() in [927]: continue
        if verbose: print("checking", s)
        gfs = s.generating_functions()
        if (not all(is_increasing(poly(gf)) for gf in gfs.values())
            and not all(is_increasing(-poly(gf)) for gf in gfs.values())
            and all(is_upside_down_unimodal(poly(gf)) for gf in gfs.values())):
            print(s)

Answer 4

This answer is very half-baked, just something to possibly expand on. We can get symmetric sequences by considering antidiagonals of $AA^T$ for any matrix $A$ (e.g. nonnegative integer-valued for possible combinatorial interpretations).

One such type of matrices $A$ are Riordan arrays $A=(g,f)$, where $g=g(x)$ and $f=f(x)$ are generating functions for integer sequences, and $f(0)=0$, so that $A$ is a lower triangular matrix. In other words, the generating function of the $k$th column of $A$ (where $k\ge 0$) is $gf^k$.

In particular, we can get individual summands of the convolution of a sequence with itself by letting $f(x)=0$. Then letting $g(x)=\frac{1}{\sqrt{1-4x}}$ yields the sequences in the question.

The only monotone sequences we can have on the antidiagonals, then, are constant. This can be achieved, for example, with $A=(g(x),xg(x))$ such that $$f(x)=xg(x)=\left(\frac{x}{a+bx+ax^2}\right)^{\left\langle-1\right\rangle},$$ i.e. $f(x)$ is the generating function for generalized Motzkin paths. Here, $a,b$ can be any constants (or variables independent of $x$), but for combinatorial significance, we can let $a,b\in\mathbb{Z}$, $a>0$, $b\ge 0$. I don't know yet what condition on $g$ and $f$ is needed to ensure upside-down unimodality (or unimodality, for that matter), but maybe this is not difficult to work out.