- FindStat

edit this statistic or download as text // json

Identifier

St001361: Dyck paths ⟶ ℤ

Values

[1,0] => 2

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

>>> 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_{1} = q^{2}$

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

$F_{3} = q^{8} + q^{12} + q^{14} + q^{16} + q^{20}$

$F_{4} = q^{16} + q^{24} + q^{28} + q^{30} + q^{32} + 2\ q^{40} + 2\ q^{44} + q^{50} + q^{52} + q^{58} + q^{60} + q^{70}$

$F_{5} = q^{32} + q^{48} + q^{56} + q^{60} + q^{62} + q^{64} + 2\ q^{80} + 2\ q^{88} + q^{92} + q^{96} + q^{100} + 2\ q^{104} + q^{106} + q^{112} + q^{116} + q^{120} + q^{122} + 2\ q^{128} + q^{140} + q^{144} + q^{148} + q^{150} + 3\ q^{152} + q^{162} + 2\ q^{164} + q^{168} + q^{180} + q^{182} + q^{192} + q^{194} + q^{204} + q^{212} + q^{222} + q^{224} + q^{252}$

$F_{6} = q^{64} + q^{96} + q^{112} + q^{120} + q^{124} + q^{126} + q^{128} + 2\ q^{160} + 2\ q^{176} + q^{184} + q^{188} + q^{192} + q^{200} + 2\ q^{208} + q^{212} + q^{218} + 2\ q^{224} + q^{228} + 2\ q^{232} + q^{238} + q^{240} + q^{244} + q^{250} + 2\ q^{256} + q^{280} + q^{288} + q^{296} + q^{300} + 4\ q^{304} + q^{310} + q^{312} + q^{324} + 2\ q^{328} + q^{332} + 2\ q^{336} + q^{338} + q^{340} + q^{344} + q^{350} + q^{352} + q^{360} + 2\ q^{364} + q^{368} + q^{374} + 2\ q^{376} + q^{382} + q^{384} + q^{388} + q^{392} + q^{396} + q^{400} + q^{402} + q^{408} + q^{416} + q^{420} + q^{424} + q^{432} + q^{436} + q^{440} + 2\ q^{444} + 2\ q^{448} + 2\ q^{462} + q^{464} + 2\ q^{472} + q^{476} + q^{480} + q^{492} + q^{494} + 2\ q^{504} + q^{512} + 2\ q^{524} + q^{528} + q^{532} + q^{540} + q^{544} + q^{550} + q^{556} + 3\ q^{560} + q^{562} + 2\ q^{568} + q^{574} + q^{576} + q^{580} + q^{584} + q^{592} + q^{602} + q^{612} + 2\ q^{616} + q^{618} + q^{632} + 2\ q^{644} + 3\ q^{672} + q^{680} + q^{682} + q^{720} + 3\ q^{724} + q^{760} + q^{770} + 2\ q^{784} + q^{824} + 2\ q^{840} + q^{924}$

$F_{7} = q^{128} + q^{192} + q^{224} + q^{240} + q^{248} + q^{252} + q^{254} + q^{256} + 2\ q^{320} + 2\ q^{352} + q^{368} + q^{376} + q^{380} + q^{384} + q^{400} + 2\ q^{416} + q^{424} + q^{436} + q^{442} + 2\ q^{448} + q^{456} + 2\ q^{464} + q^{472} + q^{476} + 2\ q^{480} + q^{486} + q^{488} + q^{492} + q^{500} + q^{506} + 3\ q^{512} + q^{560} + q^{576} + q^{592} + q^{600} + 4\ q^{608} + q^{620} + q^{624} + q^{630} + q^{632} + q^{648} + 2\ q^{656} + q^{664} + 2\ q^{672} + q^{676} + q^{680} + q^{688} + q^{690} + q^{692} + q^{700} + 2\ q^{704} + q^{708} + q^{718} + q^{720} + 2\ q^{728} + q^{730} + q^{736} + q^{748} + 2\ q^{752} + q^{758} + q^{764} + q^{768} + q^{776} + q^{782} + q^{784} + 2\ q^{792} + 2\ q^{800} + q^{804} + 2\ q^{812} + q^{816} + q^{818} + q^{824} + q^{832} + q^{840} + q^{842} + 2\ q^{848} + q^{852} + q^{856} + 2\ q^{864} + q^{868} + 3\ q^{872} + q^{880} + q^{882} + q^{884} + 2\ q^{888} + q^{892} + 2\ q^{896} + q^{908} + q^{912} + 2\ q^{924} + 2\ q^{928} + q^{936} + q^{942} + 2\ q^{944} + q^{950} + q^{952} + q^{960} + q^{968} + q^{984} + q^{988} + q^{992} + q^{1004} + q^{1006} + 2\ q^{1008} + 2\ q^{1024} + q^{1040} + 2\ q^{1048} + q^{1056} + q^{1064} + q^{1080} + 2\ q^{1088} + q^{1092} + q^{1100} + q^{1112} + 4\ q^{1120} + q^{1124} + q^{1126} + 2\ q^{1128} + 2\ q^{1136} + q^{1144} + q^{1148} + 3\ q^{1152} + q^{1160} + q^{1162} + q^{1164} + 2\ q^{1168} + q^{1172} + q^{1182} + 3\ q^{1184} + 2\ q^{1192} + q^{1194} + q^{1204} + q^{1206} + q^{1224} + q^{1228} + 4\ q^{1232} + q^{1236} + 2\ q^{1248} + q^{1250} + q^{1256} + 4\ q^{1264} + q^{1268} + q^{1274} + q^{1278} + 4\ q^{1288} + q^{1292} + q^{1296} + 2\ q^{1304} + q^{1312} + q^{1316} + q^{1328} + q^{1332} + 4\ q^{1344} + q^{1348} + q^{1352} + q^{1360} + q^{1364} + q^{1372} + 3\ q^{1376} + q^{1378} + 2\ q^{1380} + q^{1384} + q^{1392} + q^{1400} + q^{1402} + q^{1412} + q^{1414} + 2\ q^{1424} + q^{1428} + q^{1432} + 2\ q^{1440} + 2\ q^{1442} + 2\ q^{1444} + 3\ q^{1448} + q^{1454} + q^{1464} + 2\ q^{1472} + q^{1476} + q^{1488} + q^{1492} + 2\ q^{1500} + q^{1504} + q^{1514} + 2\ q^{1520} + q^{1528} + q^{1540} + q^{1542} + 4\ q^{1568} + q^{1584} + q^{1586} + q^{1592} + q^{1604} + 2\ q^{1608} + q^{1616} + 2\ q^{1628} + 2\ q^{1632} + q^{1640} + q^{1648} + q^{1656} + 2\ q^{1664} + q^{1672} + q^{1674} + q^{1678} + 3\ q^{1680} + q^{1684} + q^{1692} + q^{1696} + 3\ q^{1712} + q^{1720} + q^{1728} + 2\ q^{1736} + 2\ q^{1744} + q^{1748} + 2\ q^{1752} + q^{1766} + q^{1768} + q^{1772} + q^{1776} + q^{1788} + 2\ q^{1796} + 3\ q^{1800} + 2\ q^{1808} + q^{1818} + q^{1832} + q^{1838} + q^{1840} + 2\ q^{1848} + q^{1858} + q^{1878} + q^{1880} + q^{1892} + q^{1896} + 2\ q^{1904} + q^{1908} + q^{1920} + 2\ q^{1928} + 2\ q^{1932} + q^{1948} + 2\ q^{1968} + q^{1976} + q^{1980} + 2\ q^{1984} + 2\ q^{1988} + q^{1992} + q^{2002} + q^{2012} + q^{2014} + q^{2016} + q^{2020} + 2\ q^{2048} + q^{2052} + q^{2060} + q^{2070} + q^{2072} + q^{2080} + q^{2082} + q^{2092} + 2\ q^{2104} + q^{2108} + 2\ q^{2116} + q^{2118} + q^{2120} + q^{2124} + q^{2128} + q^{2148} + q^{2156} + q^{2166} + 2\ q^{2172} + q^{2178} + 3\ q^{2184} + q^{2198} + q^{2208} + q^{2214} + q^{2216} + q^{2224} + q^{2228} + q^{2256} + q^{2272} + q^{2288} + q^{2298} + 2\ q^{2304} + 3\ q^{2328} + q^{2340} + q^{2352} + q^{2356} + 2\ q^{2368} + q^{2428} + q^{2436} + q^{2440} + q^{2442} + q^{2452} + q^{2464} + q^{2472} + q^{2496} + q^{2508} + q^{2528} + q^{2540} + q^{2560} + q^{2562} + q^{2578} + 2\ q^{2592} + q^{2596} + q^{2632} + q^{2640} + q^{2718} + q^{2720} + q^{2724} + q^{2728} + q^{2736} + q^{2740} + q^{2764} + q^{2832} + q^{2868} + q^{2890} + q^{2902} + q^{2928} + q^{2944} + q^{2984} + q^{3000} + q^{3082} + q^{3152} + q^{3168} + q^{3180} + q^{3432}$

Description

The number of lattice paths of the same length that stay weakly above a Dyck path.
In particular, the statistic value is $2^n$ for the Dyck path consisting of $n$ north steps followed by $n$ east steps and the central binomial coefficient $\binom{2n}{n}$ for the Dyck path consisting of $n$ alternating north and east steps.
The number of such paths is always even: the final step of a Dyck path $D$ must be a down step. Thus, the final step of a path above $D$ can be arbitrarily chosen.

Code

@cached_function
def all_paths_above(L, i=0):
    if i < 0:
        return []
    elif len(L) == 0:
        return [tuple()]

    else:
        steps = []
        if L[0] == 1:
            steps.append((1,i))
            steps.append((0,i-1))
        if L[0] == 0:
            steps.append((1,i+1))
            steps.append((0,i))
        return [ tuple([a]) + path for a,i in steps for path in all_paths_above(L[1:],i)]

def statistic(D):
    return len(all_paths_above(tuple(D)))

Created

Mar 04, 2019 at 14:56 by Christian Stump

Updated

Mar 10, 2019 at 08:02 by Martin Rubey