- FindStat

edit this statistic or download as text // json

Identifier

St001800: Dyck paths ⟶ ℤ

Values

[] => 1

[1,0] => 1

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

>>> Load all 626 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

$F_{1} = q$

$F_{2} = q + q^{2}$

$F_{3} = 2\ q + 2\ q^{3} + q^{4}$

$F_{4} = 4\ q + q^{2} + 2\ q^{3} + 2\ q^{4} + 3\ q^{6} + q^{8} + q^{9}$

$F_{5} = 9\ q + 2\ q^{2} + 4\ q^{3} + 5\ q^{4} + 2\ q^{5} + 6\ q^{6} + 2\ q^{8} + 2\ q^{9} + 2\ q^{10} + 2\ q^{12} + 2\ q^{16} + 4\ q^{18}$

$F_{6} = 21\ q + 6\ q^{2} + 10\ q^{3} + 9\ q^{4} + 6\ q^{5} + 14\ q^{6} + 7\ q^{8} + 4\ q^{9} + 8\ q^{10} + 14\ q^{12} + 2\ q^{15} + 3\ q^{16} + 8\ q^{18} + q^{20} + 2\ q^{24} + q^{25} + 2\ q^{27} + 2\ q^{30} + 3\ q^{32} + 6\ q^{36} + 2\ q^{40} + q^{54}$

$F_{7} = 51\ q + 16\ q^{2} + 26\ q^{3} + 25\ q^{4} + 14\ q^{5} + 34\ q^{6} + 2\ q^{7} + 16\ q^{8} + 15\ q^{9} + 22\ q^{10} + 32\ q^{12} + 14\ q^{15} + 10\ q^{16} + 16\ q^{18} + 14\ q^{20} + 2\ q^{21} + 28\ q^{24} + q^{25} + 4\ q^{27} + 10\ q^{30} + 4\ q^{32} + 2\ q^{35} + 23\ q^{36} + 4\ q^{40} + 2\ q^{45} + 4\ q^{48} + 2\ q^{50} + 8\ q^{54} + 4\ q^{60} + 4\ q^{64} + 6\ q^{72} + 2\ q^{75} + 4\ q^{80} + q^{81} + q^{100} + 4\ q^{108} + 2\ q^{120}$

Description

The number of 3-Catalan paths having this Dyck path as first and last coordinate projections.
A 3-Catalan path is a lattice path from

$(0,0,0)$ to

$(n,n,n)$ consisting of steps

$(1,0,0)$ ,

$(0,1,0)$ , and

$(0,0,1)$ such that for each point

$(x,y,z)$ on the path we have

$x \geq y \geq z$ .
Its first and last coordinate projections, denoted by

$D_{xy}$ and

$D_{yz}$ , are the Dyck paths obtained by projecting the Catalan path onto the

$x,y$ -plane and the

$y,z$ -plane, respectively.
For a given Dyck path

$D$ this is the number of Catalan paths

$C$ such that

$D_{xy}(C) = D_{yz}(C) = D$ .
If

$D$ is of semilength

$n$ ,

$r_i(D)$ denotes the number of downsteps between the

$i$ -th and

$(i+1)$ -st upstep, and

$s_i(D)$ denotes the number of upsteps between the

$i$ -th and

$(i+1)$ -st downstep, then this number is given by

$\prod\limits_{i=1}^{n-1} \binom{r_i(D) + s_i(D)}{r_i(D)}$ .

References

[1] Archer, K., Graves, C. Pattern-restricted permutations composed of 3-cycles MathSciNet:4400005 arXiv:2104.12664 DOI:10.1016/j.disc.2022.112895
[2] Archer, K., Gravies, C. A new statistic on Dyck paths for counting 3-dimensional Catalan words arXiv:2205.09686

Code

def statistic(D):
    # D is expected to be a list of 1s (upsteps) and 0s (downsteps)
    x = 1
    n = len(D) / 2
    uppies = [j for j, n in enumerate(D) if n == 1]
    downies = [j for j, n in enumerate(D) if n == 0]
    for i in range(1,n):
        r = D[ uppies[i-1] : uppies[i] ].count(0)
        s = D[ downies[i-1] : downies[i] ].count(1)
        x *= binomial(r + s, r)
    return x

Created

Jun 02, 2022 at 16:14 by Dennis Jahn

Updated

Jun 02, 2022 at 18:06 by Dennis Jahn