***************************************************************************** * www.FindStat.org - The Combinatorial Statistic Finder * * * * Copyright (C) 2019 The FindStatCrew * * * * This information is distributed in the hope that it will be useful, * * but WITHOUT ANY WARRANTY; without even the implied warranty of * * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. * ***************************************************************************** ----------------------------------------------------------------------------- Statistic identifier: St001508 ----------------------------------------------------------------------------- Collection: Dyck paths ----------------------------------------------------------------------------- Description: The degree of the standard monomial associated to a Dyck path relative to the diagonal boundary. Given two lattice paths $U,L$ from $(0,0)$ to $(d,n-d)$, [1] describes a bijection between lattice paths weakly between $U$ and $L$ and subsets of $\{1,\dots,n\}$ such that the set of all such subsets gives the standard complex of the lattice path matroid $M[U,L]$. This statistic gives the cardinality of the image of this bijection when a Dyck path is considered as a path weakly above the diagonal and relative to the diagonal boundary. ----------------------------------------------------------------------------- References: [1] Engström, A., Sanyal, R., Stump, C. Standard complexes of matroids and lattice paths [[arXiv:1911.12290]] ----------------------------------------------------------------------------- Code: def standard_monomial(D, low=None, east=1): n = len(D) A = [ i+1 for i,s in enumerate(D) if s == 1-east ] low = [ i+1 for i,s in enumerate(low) if s == 1-east ] if low is None: low = [1 .. len(A)] low = [ i for i in [1 .. n] if i not in low ] vals = [] j = 0 blocker = low + [Infinity] for i in [1 .. n]: if i not in A: if i < blocker[0]: j += 1 else: blocker.pop(0) else: if j > 0: j -= 1 vals.append(i) blocker.pop(0) return tuple(vals) def statistic(D): n = len(D)//2 return len(standard_monomial(D, tuple([1,0]*n), east=1)) ----------------------------------------------------------------------------- Statistic values: [1,0] => 0 [1,0,1,0] => 0 [1,1,0,0] => 1 [1,0,1,0,1,0] => 0 [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] => 0 [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] => 2 [1,1,0,1,0,0,1,0] => 2 [1,1,0,1,0,1,0,0] => 3 [1,1,0,1,1,0,0,0] => 2 [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] => 2 [1,1,1,1,0,0,0,0] => 2 [1,0,1,0,1,0,1,0,1,0] => 0 [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] => 2 [1,0,1,1,0,1,0,0,1,0] => 2 [1,0,1,1,0,1,0,1,0,0] => 3 [1,0,1,1,0,1,1,0,0,0] => 2 [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] => 2 [1,0,1,1,1,1,0,0,0,0] => 2 [1,1,0,0,1,0,1,0,1,0] => 1 [1,1,0,0,1,0,1,1,0,0] => 2 [1,1,0,0,1,1,0,0,1,0] => 2 [1,1,0,0,1,1,0,1,0,0] => 3 [1,1,0,0,1,1,1,0,0,0] => 2 [1,1,0,1,0,0,1,0,1,0] => 2 [1,1,0,1,0,0,1,1,0,0] => 3 [1,1,0,1,0,1,0,0,1,0] => 3 [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] => 2 [1,1,0,1,1,0,0,1,0,0] => 3 [1,1,0,1,1,0,1,0,0,0] => 3 [1,1,0,1,1,1,0,0,0,0] => 3 [1,1,1,0,0,0,1,0,1,0] => 1 [1,1,1,0,0,0,1,1,0,0] => 2 [1,1,1,0,0,1,0,0,1,0] => 2 [1,1,1,0,0,1,0,1,0,0] => 3 [1,1,1,0,0,1,1,0,0,0] => 2 [1,1,1,0,1,0,0,0,1,0] => 2 [1,1,1,0,1,0,0,1,0,0] => 3 [1,1,1,0,1,0,1,0,0,0] => 3 [1,1,1,0,1,1,0,0,0,0] => 3 [1,1,1,1,0,0,0,0,1,0] => 2 [1,1,1,1,0,0,0,1,0,0] => 3 [1,1,1,1,0,0,1,0,0,0] => 3 [1,1,1,1,0,1,0,0,0,0] => 3 [1,1,1,1,1,0,0,0,0,0] => 2 [1,0,1,0,1,0,1,0,1,0,1,0] => 0 [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] => 2 [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] => 3 [1,0,1,0,1,1,0,1,1,0,0,0] => 2 [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] => 2 [1,0,1,0,1,1,1,1,0,0,0,0] => 2 [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] => 2 [1,0,1,1,0,0,1,1,0,0,1,0] => 2 [1,0,1,1,0,0,1,1,0,1,0,0] => 3 [1,0,1,1,0,0,1,1,1,0,0,0] => 2 [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] => 3 [1,0,1,1,0,1,0,1,0,0,1,0] => 3 [1,0,1,1,0,1,0,1,0,1,0,0] => 4 [1,0,1,1,0,1,0,1,1,0,0,0] => 3 [1,0,1,1,0,1,1,0,0,0,1,0] => 2 [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] => 3 [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] => 1 [1,0,1,1,1,0,0,0,1,1,0,0] => 2 [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] => 3 [1,0,1,1,1,0,0,1,1,0,0,0] => 2 [1,0,1,1,1,0,1,0,0,0,1,0] => 2 [1,0,1,1,1,0,1,0,0,1,0,0] => 3 [1,0,1,1,1,0,1,0,1,0,0,0] => 3 [1,0,1,1,1,0,1,1,0,0,0,0] => 3 [1,0,1,1,1,1,0,0,0,0,1,0] => 2 [1,0,1,1,1,1,0,0,0,1,0,0] => 3 [1,0,1,1,1,1,0,0,1,0,0,0] => 3 [1,0,1,1,1,1,0,1,0,0,0,0] => 3 [1,0,1,1,1,1,1,0,0,0,0,0] => 2 [1,1,0,0,1,0,1,0,1,0,1,0] => 1 [1,1,0,0,1,0,1,0,1,1,0,0] => 2 [1,1,0,0,1,0,1,1,0,0,1,0] => 2 [1,1,0,0,1,0,1,1,0,1,0,0] => 3 [1,1,0,0,1,0,1,1,1,0,0,0] => 2 [1,1,0,0,1,1,0,0,1,0,1,0] => 2 [1,1,0,0,1,1,0,0,1,1,0,0] => 3 [1,1,0,0,1,1,0,1,0,0,1,0] => 3 [1,1,0,0,1,1,0,1,0,1,0,0] => 4 [1,1,0,0,1,1,0,1,1,0,0,0] => 3 [1,1,0,0,1,1,1,0,0,0,1,0] => 2 [1,1,0,0,1,1,1,0,0,1,0,0] => 3 [1,1,0,0,1,1,1,0,1,0,0,0] => 3 [1,1,0,0,1,1,1,1,0,0,0,0] => 3 [1,1,0,1,0,0,1,0,1,0,1,0] => 2 [1,1,0,1,0,0,1,0,1,1,0,0] => 3 [1,1,0,1,0,0,1,1,0,0,1,0] => 3 [1,1,0,1,0,0,1,1,0,1,0,0] => 4 [1,1,0,1,0,0,1,1,1,0,0,0] => 3 [1,1,0,1,0,1,0,0,1,0,1,0] => 3 [1,1,0,1,0,1,0,0,1,1,0,0] => 4 [1,1,0,1,0,1,0,1,0,0,1,0] => 4 [1,1,0,1,0,1,0,1,0,1,0,0] => 5 [1,1,0,1,0,1,0,1,1,0,0,0] => 4 [1,1,0,1,0,1,1,0,0,0,1,0] => 3 [1,1,0,1,0,1,1,0,0,1,0,0] => 4 [1,1,0,1,0,1,1,0,1,0,0,0] => 4 [1,1,0,1,0,1,1,1,0,0,0,0] => 4 [1,1,0,1,1,0,0,0,1,0,1,0] => 2 [1,1,0,1,1,0,0,0,1,1,0,0] => 3 [1,1,0,1,1,0,0,1,0,0,1,0] => 3 [1,1,0,1,1,0,0,1,0,1,0,0] => 4 [1,1,0,1,1,0,0,1,1,0,0,0] => 3 [1,1,0,1,1,0,1,0,0,0,1,0] => 3 [1,1,0,1,1,0,1,0,0,1,0,0] => 4 [1,1,0,1,1,0,1,0,1,0,0,0] => 4 [1,1,0,1,1,0,1,1,0,0,0,0] => 4 [1,1,0,1,1,1,0,0,0,0,1,0] => 3 [1,1,0,1,1,1,0,0,0,1,0,0] => 4 [1,1,0,1,1,1,0,0,1,0,0,0] => 4 [1,1,0,1,1,1,0,1,0,0,0,0] => 4 [1,1,0,1,1,1,1,0,0,0,0,0] => 3 [1,1,1,0,0,0,1,0,1,0,1,0] => 1 [1,1,1,0,0,0,1,0,1,1,0,0] => 2 [1,1,1,0,0,0,1,1,0,0,1,0] => 2 [1,1,1,0,0,0,1,1,0,1,0,0] => 3 [1,1,1,0,0,0,1,1,1,0,0,0] => 2 [1,1,1,0,0,1,0,0,1,0,1,0] => 2 [1,1,1,0,0,1,0,0,1,1,0,0] => 3 [1,1,1,0,0,1,0,1,0,0,1,0] => 3 [1,1,1,0,0,1,0,1,0,1,0,0] => 4 [1,1,1,0,0,1,0,1,1,0,0,0] => 3 [1,1,1,0,0,1,1,0,0,0,1,0] => 2 [1,1,1,0,0,1,1,0,0,1,0,0] => 3 [1,1,1,0,0,1,1,0,1,0,0,0] => 3 [1,1,1,0,0,1,1,1,0,0,0,0] => 3 [1,1,1,0,1,0,0,0,1,0,1,0] => 2 [1,1,1,0,1,0,0,0,1,1,0,0] => 3 [1,1,1,0,1,0,0,1,0,0,1,0] => 3 [1,1,1,0,1,0,0,1,0,1,0,0] => 4 [1,1,1,0,1,0,0,1,1,0,0,0] => 3 [1,1,1,0,1,0,1,0,0,0,1,0] => 3 [1,1,1,0,1,0,1,0,0,1,0,0] => 4 [1,1,1,0,1,0,1,0,1,0,0,0] => 4 [1,1,1,0,1,0,1,1,0,0,0,0] => 4 [1,1,1,0,1,1,0,0,0,0,1,0] => 3 [1,1,1,0,1,1,0,0,0,1,0,0] => 4 [1,1,1,0,1,1,0,0,1,0,0,0] => 4 [1,1,1,0,1,1,0,1,0,0,0,0] => 4 [1,1,1,0,1,1,1,0,0,0,0,0] => 3 [1,1,1,1,0,0,0,0,1,0,1,0] => 2 [1,1,1,1,0,0,0,0,1,1,0,0] => 3 [1,1,1,1,0,0,0,1,0,0,1,0] => 3 [1,1,1,1,0,0,0,1,0,1,0,0] => 4 [1,1,1,1,0,0,0,1,1,0,0,0] => 3 [1,1,1,1,0,0,1,0,0,0,1,0] => 3 [1,1,1,1,0,0,1,0,0,1,0,0] => 4 [1,1,1,1,0,0,1,0,1,0,0,0] => 4 [1,1,1,1,0,0,1,1,0,0,0,0] => 4 [1,1,1,1,0,1,0,0,0,0,1,0] => 3 [1,1,1,1,0,1,0,0,0,1,0,0] => 4 [1,1,1,1,0,1,0,0,1,0,0,0] => 4 [1,1,1,1,0,1,0,1,0,0,0,0] => 4 [1,1,1,1,0,1,1,0,0,0,0,0] => 3 [1,1,1,1,1,0,0,0,0,0,1,0] => 2 [1,1,1,1,1,0,0,0,0,1,0,0] => 3 [1,1,1,1,1,0,0,0,1,0,0,0] => 3 [1,1,1,1,1,0,0,1,0,0,0,0] => 3 [1,1,1,1,1,0,1,0,0,0,0,0] => 3 [1,1,1,1,1,1,0,0,0,0,0,0] => 3 ----------------------------------------------------------------------------- Created: Nov 28, 2019 at 17:31 by Christian Stump ----------------------------------------------------------------------------- Last Updated: Dec 29, 2019 at 22:08 by Martin Rubey