- FindStat

edit this statistic or download as text // json

Identifier

St001786: Dyck paths ⟶ ℤ

Values

[1,0] => 1

[1,0,1,0] => 1

[1,1,0,0] => 1

[1,0,1,0,1,0] => 1

[1,0,1,1,0,0] => 1

[1,1,0,0,1,0] => 1

[1,1,0,1,0,0] => 2

[1,1,1,0,0,0] => 1

[1,0,1,0,1,0,1,0] => 1

[1,0,1,0,1,1,0,0] => 1

[1,0,1,1,0,0,1,0] => 1

[1,0,1,1,0,1,0,0] => 2

[1,0,1,1,1,0,0,0] => 1

[1,1,0,0,1,0,1,0] => 1

[1,1,0,0,1,1,0,0] => 1

[1,1,0,1,0,0,1,0] => 2

[1,1,0,1,0,1,0,0] => 4

[1,1,0,1,1,0,0,0] => 3

[1,1,1,0,0,0,1,0] => 1

[1,1,1,0,0,1,0,0] => 2

[1,1,1,0,1,0,0,0] => 3

[1,1,1,1,0,0,0,0] => 1

[1,0,1,0,1,0,1,0,1,0] => 1

[1,0,1,0,1,0,1,1,0,0] => 1

[1,0,1,0,1,1,0,0,1,0] => 1

[1,0,1,0,1,1,0,1,0,0] => 2

[1,0,1,0,1,1,1,0,0,0] => 1

[1,0,1,1,0,0,1,0,1,0] => 1

[1,0,1,1,0,0,1,1,0,0] => 1

[1,0,1,1,0,1,0,0,1,0] => 2

[1,0,1,1,0,1,0,1,0,0] => 4

[1,0,1,1,0,1,1,0,0,0] => 3

[1,0,1,1,1,0,0,0,1,0] => 1

[1,0,1,1,1,0,0,1,0,0] => 2

[1,0,1,1,1,0,1,0,0,0] => 3

[1,0,1,1,1,1,0,0,0,0] => 1

[1,1,0,0,1,0,1,0,1,0] => 1

[1,1,0,0,1,0,1,1,0,0] => 1

[1,1,0,0,1,1,0,0,1,0] => 1

[1,1,0,0,1,1,0,1,0,0] => 2

[1,1,0,0,1,1,1,0,0,0] => 1

[1,1,0,1,0,0,1,0,1,0] => 2

[1,1,0,1,0,0,1,1,0,0] => 2

[1,1,0,1,0,1,0,0,1,0] => 4

[1,1,0,1,0,1,0,1,0,0] => 8

[1,1,0,1,0,1,1,0,0,0] => 6

[1,1,0,1,1,0,0,0,1,0] => 3

[1,1,0,1,1,0,0,1,0,0] => 6

[1,1,0,1,1,0,1,0,0,0] => 9

[1,1,0,1,1,1,0,0,0,0] => 4

[1,1,1,0,0,0,1,0,1,0] => 1

[1,1,1,0,0,0,1,1,0,0] => 1

[1,1,1,0,0,1,0,0,1,0] => 2

[1,1,1,0,0,1,0,1,0,0] => 4

[1,1,1,0,0,1,1,0,0,0] => 3

[1,1,1,0,1,0,0,0,1,0] => 3

[1,1,1,0,1,0,0,1,0,0] => 6

[1,1,1,0,1,0,1,0,0,0] => 9

[1,1,1,0,1,1,0,0,0,0] => 6

[1,1,1,1,0,0,0,0,1,0] => 1

[1,1,1,1,0,0,0,1,0,0] => 2

[1,1,1,1,0,0,1,0,0,0] => 3

[1,1,1,1,0,1,0,0,0,0] => 4

[1,1,1,1,1,0,0,0,0,0] => 1

[1,0,1,0,1,0,1,0,1,0,1,0] => 1

[1,0,1,0,1,0,1,0,1,1,0,0] => 1

[1,0,1,0,1,0,1,1,0,0,1,0] => 1

[1,0,1,0,1,0,1,1,0,1,0,0] => 2

[1,0,1,0,1,0,1,1,1,0,0,0] => 1

[1,0,1,0,1,1,0,0,1,0,1,0] => 1

[1,0,1,0,1,1,0,0,1,1,0,0] => 1

[1,0,1,0,1,1,0,1,0,0,1,0] => 2

[1,0,1,0,1,1,0,1,0,1,0,0] => 4

[1,0,1,0,1,1,0,1,1,0,0,0] => 3

[1,0,1,0,1,1,1,0,0,0,1,0] => 1

[1,0,1,0,1,1,1,0,0,1,0,0] => 2

[1,0,1,0,1,1,1,0,1,0,0,0] => 3

[1,0,1,0,1,1,1,1,0,0,0,0] => 1

[1,0,1,1,0,0,1,0,1,0,1,0] => 1

[1,0,1,1,0,0,1,0,1,1,0,0] => 1

[1,0,1,1,0,0,1,1,0,0,1,0] => 1

[1,0,1,1,0,0,1,1,0,1,0,0] => 2

[1,0,1,1,0,0,1,1,1,0,0,0] => 1

[1,0,1,1,0,1,0,0,1,0,1,0] => 2

[1,0,1,1,0,1,0,0,1,1,0,0] => 2

[1,0,1,1,0,1,0,1,0,0,1,0] => 4

[1,0,1,1,0,1,0,1,0,1,0,0] => 8

[1,0,1,1,0,1,0,1,1,0,0,0] => 6

[1,0,1,1,0,1,1,0,0,0,1,0] => 3

[1,0,1,1,0,1,1,0,0,1,0,0] => 6

[1,0,1,1,0,1,1,0,1,0,0,0] => 9

[1,0,1,1,0,1,1,1,0,0,0,0] => 4

[1,0,1,1,1,0,0,0,1,0,1,0] => 1

[1,0,1,1,1,0,0,0,1,1,0,0] => 1

[1,0,1,1,1,0,0,1,0,0,1,0] => 2

[1,0,1,1,1,0,0,1,0,1,0,0] => 4

[1,0,1,1,1,0,0,1,1,0,0,0] => 3

[1,0,1,1,1,0,1,0,0,0,1,0] => 3

[1,0,1,1,1,0,1,0,0,1,0,0] => 6

[1,0,1,1,1,0,1,0,1,0,0,0] => 9

[1,0,1,1,1,0,1,1,0,0,0,0] => 6

>>> Load all 1760 entries. <<<

search for individual values

searching the database for the individual values of this statistic

/ search for generating function

searching the database for statistics with the same generating function

click to show known generating functions

Description

The number of total orderings of the north steps of a Dyck path such that steps after the k-th east step are not among the first k positions in the order.
Alternatively, remark that the monomials of the polynomial $\prod_{k=1}^n (z_1+\dots +z_k)$ are in bijection with Dyck paths, regarded as superdiagonal paths, with $n$ east steps: the exponent of $z_i$ is the number of north steps before the $i$-th east step, see [2]. Thus, this statistic records the coefficients of the monomials.
A formula for the coefficient of $z_1^{a_1}\dots z_n^{a_n}$ is provided in [3]:
$$ c_{(a_1,\dots,a_n)} = \prod_{k=1}^{n-1} \frac{n-k+1 - \sum_{i=k+1}^n a_i}{a_k!}. $$
This polynomial arises in a partial symmetrization process as follows, see [1]. For $w\in\frak{S}_n$, let $w\cdot F(x_1,\dots,x_n)=F(x_{w(1)},\dots,x_{w(n)})$. Furthermore, let
$$G(\mathbf{x},\mathbf{z}) = \prod_{k=1}^n\frac{x_1z_1+x_2z_2+\cdots+x_kz_k}{x_k-x_{k+1}}.$$
Then $\sum_{w\in\frak{S}_{n+1}}w\cdot G = \prod_{k=1}^n (z_1+\dots +z_k)$.

References

[1] Amdeberhan, T. Counting monomials and the Catalan numbers MathOverflow:420887
[2] The coefficients in the expansion x_1(x_1 + x_2)...(x_1 + x_2 + ... + x_n), given row by row. OEIS:A347917
[3] Fried, S. On the coefficients of the distinct monomials in the expansion of $x_1(x_1+x_2)\cdots (x_1+x_2+\cdots +x_n)$ arXiv:2111.07331

Code

def statistic(D):
    n = D.semilength()
    a = []
    i = 0
    for e in D:
        if e == 0:
            a.append(i)
            i = 0
        else:
            i += 1
    return prod((n-k-sum(a[k+1:]))/factorial(a[k]) for k in range(len(a)-1))

# alternative, direct
@cached_function
def G_sym(n):
    Z = PolynomialRing(QQ, n-1, "z").gens()
    return prod(sum(Z[:k]) for k in range(1, n))

def to_dyck(m):
    D = []
    e = m.exponents()
    assert len(e) == 1, "should be a single monomial, but is %s" % m
    for N in e[0]:
        D.extend([1]*N)
        D.append(0)
    return DyckWord(D)

def statistics(n):
    p = G_sym(n)
    s = {}
    for c, m in p:
        s[to_dyck(m)] = c
    return s

def statistic(D):
    return statistics(D.semilength()+1)[D]

# alternative, completely direct
@cached_function
def G_sym(n):
    R = PolynomialRing(QQ, n-1, "z")
    S = PolynomialRing(R, n, "x")
    X = S.gens()
    p = [x*z for z, x in zip(R.gens(), X)]
    G = prod(sum(p[:k])/(X[k-1]-X[k]) for k in range(1,n))
    G_s = 0
    for pi in Permutations(n):
        s = G.subs({X[i]: X[pi[i]-1] for i in range(n)})
        G_s += s
    return R(G_s)

def to_dyck(m):
    D = []
    e = m.exponents()
    assert len(e) == 1, "should be a single monomial, but is %s" % m
    for N in e[0]:
        D.extend([1]*N)
        D.append(0)
    return DyckWord(D)

def statistics(n):
    p = G_sym(n)
    s = {}
    for c, m in p:
        s[to_dyck(m)] = c
    return s

def statistic(D):
    return statistics(D.semilength()+1)[D]

Created

Apr 25, 2022 at 10:03 by Martin Rubey

Updated

Apr 26, 2022 at 17:11 by Martin Rubey