- FindStat

edit this statistic or download as text // json

Identifier

St001808: Dyck paths ⟶ ℤ

Values

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

>>> Load all 1200 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_{2} = q + q^{2}$

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

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

$F_{5} = q + q^{2} + q^{3} + 2\ q^{4} + q^{5} + q^{6} + 2\ q^{8} + q^{9} + q^{10} + 2\ q^{12} + q^{15} + 3\ q^{16} + q^{18} + 2\ q^{20} + 2\ q^{24} + q^{27} + q^{30} + 2\ q^{32} + 2\ q^{36} + 2\ q^{40} + q^{45} + 2\ q^{48} + q^{54} + 2\ q^{60} + q^{64} + q^{72} + q^{80} + q^{90} + q^{96} + q^{120}$

$F_{6} = q + q^{2} + q^{3} + 2\ q^{4} + q^{5} + 2\ q^{6} + 2\ q^{8} + q^{9} + q^{10} + 3\ q^{12} + q^{15} + 3\ q^{16} + 2\ q^{18} + 2\ q^{20} + 4\ q^{24} + q^{25} + q^{27} + 2\ q^{30} + 3\ q^{32} + 3\ q^{36} + 2\ q^{40} + q^{45} + 5\ q^{48} + q^{50} + 2\ q^{54} + 3\ q^{60} + 3\ q^{64} + 4\ q^{72} + q^{75} + 3\ q^{80} + q^{81} + 2\ q^{90} + 5\ q^{96} + 2\ q^{100} + 3\ q^{108} + 4\ q^{120} + 2\ q^{128} + q^{135} + 4\ q^{144} + q^{150} + 2\ q^{160} + 2\ q^{162} + 3\ q^{180} + 4\ q^{192} + 2\ q^{200} + 3\ q^{216} + q^{225} + 4\ q^{240} + q^{256} + 2\ q^{270} + 3\ q^{288} + 2\ q^{300} + q^{320} + q^{324} + 3\ q^{360} + 2\ q^{384} + q^{400} + q^{432} + q^{450} + 2\ q^{480} + q^{540} + q^{576} + q^{600} + q^{720}$

$F_{7} = q + q^{2} + q^{3} + 2\ q^{4} + q^{5} + 2\ q^{6} + q^{7} + 2\ q^{8} + q^{9} + q^{10} + 3\ q^{12} + q^{14} + q^{15} + 3\ q^{16} + 2\ q^{18} + 2\ q^{20} + q^{21} + 4\ q^{24} + q^{25} + q^{27} + 2\ q^{28} + 2\ q^{30} + 3\ q^{32} + q^{35} + 4\ q^{36} + 2\ q^{40} + 2\ q^{42} + q^{45} + 5\ q^{48} + q^{50} + 2\ q^{54} + 2\ q^{56} + 3\ q^{60} + q^{63} + 4\ q^{64} + q^{70} + 5\ q^{72} + q^{75} + 3\ q^{80} + q^{81} + 3\ q^{84} + 2\ q^{90} + 6\ q^{96} + 2\ q^{100} + q^{105} + 4\ q^{108} + 3\ q^{112} + 4\ q^{120} + q^{125} + 2\ q^{126} + 3\ q^{128} + q^{135} + 2\ q^{140} + 7\ q^{144} + 2\ q^{150} + 3\ q^{160} + 2\ q^{162} + 4\ q^{168} + q^{175} + 4\ q^{180} + q^{189} + 6\ q^{192} + 2\ q^{200} + 2\ q^{210} + 5\ q^{216} + 3\ q^{224} + q^{225} + 5\ q^{240} + q^{243} + q^{250} + 3\ q^{252} + 3\ q^{256} + 2\ q^{270} + 2\ q^{280} + 7\ q^{288} + 3\ q^{300} + q^{315} + 3\ q^{320} + 4\ q^{324} + 5\ q^{336} + q^{350} + 5\ q^{360} + q^{375} + 2\ q^{378} + 5\ q^{384} + 3\ q^{400} + q^{405} + 3\ q^{420} + 6\ q^{432} + 3\ q^{448} + 2\ q^{450} + 5\ q^{480} + 2\ q^{486} + 2\ q^{500} + 4\ q^{504} + 2\ q^{512} + q^{525} + 4\ q^{540} + 3\ q^{560} + q^{567} + 7\ q^{576} + 4\ q^{600} + 2\ q^{630} + 2\ q^{640} + 4\ q^{648} + 5\ q^{672} + q^{675} + 2\ q^{700} + 6\ q^{720} + q^{750} + 3\ q^{756} + 4\ q^{768} + 2\ q^{800} + 2\ q^{810} + 4\ q^{840} + 5\ q^{864} + 2\ q^{896} + 3\ q^{900} + q^{945} + 4\ q^{960} + 2\ q^{972} + 2\ q^{1000} + 4\ q^{1008} + q^{1024} + q^{1050} + 4\ q^{1080} + 2\ q^{1120} + q^{1125} + 2\ q^{1134} + 5\ q^{1152} + 4\ q^{1200} + 3\ q^{1260} + q^{1280} + 3\ q^{1296} + 4\ q^{1344} + 2\ q^{1350} + 2\ q^{1400} + 5\ q^{1440} + 2\ q^{1500} + 3\ q^{1512} + 2\ q^{1536} + q^{1575} + q^{1600} + 2\ q^{1620} + 4\ q^{1680} + 3\ q^{1728} + q^{1792} + 3\ q^{1800} + 2\ q^{1890} + 2\ q^{1920} + q^{1944} + q^{2000} + 3\ q^{2016} + 2\ q^{2100} + 3\ q^{2160} + q^{2240} + q^{2250} + q^{2268} + 2\ q^{2304} + 2\ q^{2400} + 3\ q^{2520} + q^{2592} + 2\ q^{2688} + q^{2700} + q^{2800} + 2\ q^{2880} + q^{3000} + q^{3024} + q^{3150} + q^{3240} + 2\ q^{3360} + q^{3456} + q^{3600} + q^{3780} + q^{4032} + q^{4200} + q^{4320} + q^{5040}$

Description

The box weight or horizontal decoration of a Dyck path.
Let a Dyck path $D = (d_1,d_2,\dots,d_n)$ with steps $d_i \in \{N=(0,1),E=(1,0)\}$ be given.
For the $i$th step $d_i \in D$ we define the weight
$$ \beta(d_i) = 1, \quad \text{ if } d_i=N, $$
and
$$ \beta(d_i) = \sum_{k = 1}^{i} [\![ d_k = N]\!], \quad \text{ if } d_i=E, $$
where we use the Iverson bracket $[\![ A ]\!]$ that is equal to $1$ if $A$ is true, and $0$ otherwise.
The box weight or horizontal deocration of $D$ is defined as
$$ \prod_{i=1}^{n} \beta(d_i). $$
The name describes the fact that between each $E$ step and the line $y=-1$ exactly one unit box is marked.

References

[1] Elvey Price, A., Fang, W., Wallner, M. Compacted binary trees admit a stretched exponential arXiv:1908.11181
[2] doi:10.4230/LIPIcs.AofA.2020.11
[3] Number of deterministic completely defined initially connected acyclic automata with 2 inputs and n transient unlabeled states (and a unique absorbing state). OEIS:A082161

Code

def dyck_box_weight(x):
    xw = 1
    lvl = 1
    for step in x:
        if step == 0:
            lvl += 1
        else:
            xw *= lvl
    return xw

Created

Jun 13, 2022 at 14:21 by Michael Wallner

Updated

Jun 13, 2022 at 14:21 by Michael Wallner