- FindStat

Domain*

Codomain*

Name*

Description*

See the formating rules below

Properties

Weight

Sage code*

We require working sage code for the new map. The code will be run on our machine after inspection by an admin.
You must use our standardized format
Standardized format to provide Python or Sage code for maps
# User provided code def mapping(x): # Your code return element_at_x

. You can test your code below in the sage cell.

def mapping(D):
    """
    sage: r=7; l = [(D, mapping(D)) for D in DyckWords(r)]
    sage: [D1 for D1, D2 in l if D2 and not (ldasc(D1) == D2.number_of_touch_points() and
    ....:                                    ldasc(D2) == D1.number_of_touch_points() and
    ....:                                    D1.reverse().rise_composition() == D2.reverse().rise_composition())]
    []
    """
    def ldasc(D):
        """
        Return the number of up steps after the last double rise.
    
        EXAMPLES::
    
            sage: ldasc([1,1,0,0])
            1
        
            sage: ldasc([1,1,0,1,0,0])
            2
        
            sage: ldasc([1,0,1,0,0])
            2
        """
        i = 0
        j = 0
        for j in range(1,len(D)):
            if D[-j] == 1:
                i += 1
                if D[-j-1] == 1:
                    return i
        return i+1
    
    def position_of_last_double_ascent(D):
        """
        Return the index of the last double rise within the Dyck word.
    
        EXAMPLES:
    
            sage: position_of_last_double_ascent([1,1])
            0
            sage: position_of_last_double_ascent([1,1,1])
            1
            sage: D = DyckWord([1,1,1,1,1,1,1,0,0,0,1,0,1,0,0,0,1,0,0,0])
            sage: D[position_of_last_double_ascent(D):]
            [1, 1, 0, 0, 0, 1, 0, 1, 0, 0, 0, 1, 0, 0, 0]
        """
        n = len(D)
        i = 0
        l = -1
        while i < n-1:
            if D[i] == D[i+1] == 1:
                l = i
            i += 1
        return l
    
    def no_return_to_one_return(D):
        # compute first rise after last double rise
        i = position_of_last_double_ascent(D)+2
        while D[i] == 0:
            i += 1
        p = prime_decomposition(D[:i])
        if len(p)>3 and len(p[2])==0:
            if all(len(p[j])==0 for j in range(2,len(p),2)):
                # p[2] == p[4] == ... == []
                Q = [e for P in p[1:] for e in P]
                Q, b = shrink_last_ascent(Q)
                return DyckWord([1]*b + Q + p[0] + D[i:])
            else:
                Q = [e for P in p[3:] for e in P]
                Q, b = shrink_last_ascent(Q)
                return DyckWord(p[1] + [1]*b + Q + p[0] + D[i:])
        else:
            Q = [e for P in p[1:-1] for e in P]
            return DyckWord(Q + p[0] + D[i:])
    
    def shrink_last_ascent(p):
        i1 = len(p)-1
        while p[i1] == 0:
            i1 -= 1
        i2 = i1
        while p[i2] == 1:
            i2 -= 1
        return (p[:i2+2] + [0]*(len(p)-i1-1), i1-i2-1)
    
    def one_return_to_no_return(D):
        D = DyckWord(D)
        # compute first rise after last double rise
        i = position_of_last_double_ascent(D)+1
        a = 0
        while D[i-a] == 1:
            a += 1
        # compute first fall before the rise
        d = 0
        while D[i-a-d] == 0:
            d += 1
        a -= 1
        prefix = D[:i-a-d]
        # determine length of last rise in the prefix
        if prefix[-2:] == [1, 1]:
            return [1]*a + prefix + [0]*d + D[i:]
    
        if DyckWord(prefix).number_of_touch_points() == 0:
            p = prime_decomposition(prefix)
            return [1]*a + [e for P in p[1:] for e in P] + p[0] + [0]*d + D[i:]
        else:
            p = prime_decomposition(prefix)
            return [1]*a + p[1] + [e for P in p[3:] for e in P] + p[2] + [0]*d + D[i:]
    
    
    def prime_decomposition(W):
        """Return decomposition of a word into prime Dyck paths.
    
        INPUT:
    
        - W, a not necessarily complete Dyck word
    
        OUTPUT:
    
        - a list of an odd number of DyckWords.
    
        The concatenation of the result is the original word, the words
        with even indices consist of north steps only and the words with
        odd indices are complete Dyck paths without touch points.
    
        EXAMPLES::
    
            sage: D = DyckWord([1,1,1,0,1,0,1,1,1,0,0,1,0])
            sage: prime_decomposition(D)
            [[1, 1], [1, 0], [], [1, 0], [], [1, 1, 0, 0], [], [1, 0], []]
        
            sage: all(DyckWord([e for p in prime_decomposition(D) for e in p]) == D for D in DyckWords(7, 4))
            True
    
        """
        n = len(W)
        H = DyckWord(W).heights()
        result = []
        i = 0
        h = 0
        initial = 0
        while i < n:
            j = i+1
            # find first h
            while H[j] != h:
                if j == n:
                    h += 1
                    i += 1
                    initial += 1
                    break
                j += 1
            else:
                # found h
                result.extend([[1]*initial, W[i:j]])
                i = j
                initial = 0
    
        result.append([1]*initial)
        return result
    
    def decrease_ldasc_increase_returns(D):
        """Expect that there are no trailing hills, ldasc is greater than one
        and the number of returns is not maximal.  This is the map `phi`
        in arxiv:1701.07009.
        """
        p = prime_decomposition(D)
        # since D is a Dyck path, there are no connecting up steps
        p[-2] = no_return_to_one_return(p[-2])
        return DyckWord([e for P in p for e in P])
    
    def increase_ldasc_decrease_returns(D):
        """Expect that there are no trailing hills, ldasc is not maximal and
        the number of returns is greater than one.  This is the inverse
        of the map `phi` in arxiv:1701.07009.
        """
        p = prime_decomposition(D)
        # since D is a Dyck path, there are no connecting up steps
        p[-4] = one_return_to_no_return(p[-4]+p[-2])
        p[-2] = []
        return DyckWord([e for P in p for e in P])

if len(D) == 0:
        return D
    elif D[-2:] == [1, 0]:
        return DyckWord(mapping(D[:-2]) + [1,0])

D = DyckWord(D)
    a = D.number_of_touch_points()
    b = ldasc(D)
    if a == b:
        return D
    elif b > a:
        for i in range(b-a):
            D = decrease_ldasc_increase_returns(D)
        return DyckWord(D)
    elif a > b:
        for i in range(a-b):
            D = increase_ldasc_decrease_returns(D)
        return DyckWord(D)

References

We suggest to provide references whenever possible.

Author*

We do not accept anonymous submissions, please provide your full name.

Email*

Sage cell

Use this to test your code!

xxxxxxxxxx
 
levels = [1, 2, 3, 4, 5, 6, 7, 8]
​
parent_initializer = DyckWords
​
elements = [x for level in levels for x in parent_initializer(level)]
​
def mapping(D):
    """
    sage: r=7; l = [(D, mapping(D)) for D in DyckWords(r)]
    sage: [D1 for D1, D2 in l if D2 and not (ldasc(D1) == D2.number_of_touch_points() and
    ....:                                    ldasc(D2) == D1.number_of_touch_points() and
    ....:                                    D1.reverse().rise_composition() == D2.reverse().rise_composition())]
    []
    """
    def ldasc(D):
        """
        Return the number of up steps after the last double rise.
    
        EXAMPLES::
    
            sage: ldasc([1,1,0,0])
            1
        
            sage: ldasc([1,1,0,1,0,0])
            2
        
            sage: ldasc([1,0,1,0,0])
            2
        """
        i = 0
        j = 0
        for j in range(1,len(D)):
            if D[-j] == 1:
                i += 1
                if D[-j-1] == 1:
                    return i
        return i+1
    
    def position_of_last_double_ascent(D):
        """
        Return the index of the last double rise within the Dyck word.
    
        EXAMPLES:
    
            sage: position_of_last_double_ascent([1,1])
            0
            sage: position_of_last_double_ascent([1,1,1])
            1
            sage: D = DyckWord([1,1,1,1,1,1,1,0,0,0,1,0,1,0,0,0,1,0,0,0])
            sage: D[position_of_last_double_ascent(D):]
            [1, 1, 0, 0, 0, 1, 0, 1, 0, 0, 0, 1, 0, 0, 0]
        """
        n = len(D)
        i = 0
        l = -1
        while i < n-1:
            if D[i] == D[i+1] == 1:
                l = i
            i += 1
        return l
    
    def no_return_to_one_return(D):
        # compute first rise after last double rise
        i = position_of_last_double_ascent(D)+2
        while D[i] == 0:
            i += 1
        p = prime_decomposition(D[:i])
        if len(p)>3 and len(p[2])==0:
            if all(len(p[j])==0 for j in range(2,len(p),2)):
                # p[2] == p[4] == ... == []
                Q = [e for P in p[1:] for e in P]
                Q, b = shrink_last_ascent(Q)
                return DyckWord([1]*b + Q + p[0] + D[i:])
            else:
                Q = [e for P in p[3:] for e in P]
                Q, b = shrink_last_ascent(Q)
                return DyckWord(p[1] + [1]*b + Q + p[0] + D[i:])
        else:
            Q = [e for P in p[1:-1] for e in P]
            return DyckWord(Q + p[0] + D[i:])
    
    def shrink_last_ascent(p):
        i1 = len(p)-1
        while p[i1] == 0:
            i1 -= 1
        i2 = i1
        while p[i2] == 1:
            i2 -= 1
        return (p[:i2+2] + [0]*(len(p)-i1-1), i1-i2-1)
    
    def one_return_to_no_return(D):
        D = DyckWord(D)
        # compute first rise after last double rise
        i = position_of_last_double_ascent(D)+1
        a = 0
        while D[i-a] == 1:
            a += 1
        # compute first fall before the rise
        d = 0
        while D[i-a-d] == 0:
            d += 1
        a -= 1
        prefix = D[:i-a-d]
        # determine length of last rise in the prefix
        if prefix[-2:] == [1, 1]:
            return [1]*a + prefix + [0]*d + D[i:]
    
        if DyckWord(prefix).number_of_touch_points() == 0:
            p = prime_decomposition(prefix)
            return [1]*a + [e for P in p[1:] for e in P] + p[0] + [0]*d + D[i:]
        else:
            p = prime_decomposition(prefix)
            return [1]*a + p[1] + [e for P in p[3:] for e in P] + p[2] + [0]*d + D[i:]
    
    
    def prime_decomposition(W):
        """Return decomposition of a word into prime Dyck paths.
    
        INPUT:
    
        - W, a not necessarily complete Dyck word
    
        OUTPUT:
    
        - a list of an odd number of DyckWords.
    
        The concatenation of the result is the original word, the words
        with even indices consist of north steps only and the words with
        odd indices are complete Dyck paths without touch points.
    
        EXAMPLES::
    
            sage: D = DyckWord([1,1,1,0,1,0,1,1,1,0,0,1,0])
            sage: prime_decomposition(D)
            [[1, 1], [1, 0], [], [1, 0], [], [1, 1, 0, 0], [], [1, 0], []]
        
            sage: all(DyckWord([e for p in prime_decomposition(D) for e in p]) == D for D in DyckWords(7, 4))
            True
    
        """
        n = len(W)
        H = DyckWord(W).heights()
        result = []
        i = 0
        h = 0
        initial = 0
        while i < n:
            j = i+1
            # find first h
            while H[j] != h:
                if j == n:
                    h += 1
                    i += 1
                    initial += 1
                    break
                j += 1
            else:
                # found h
                result.extend([[1]*initial, W[i:j]])
                i = j
                initial = 0
    
        result.append([1]*initial)
        return result
    
    def decrease_ldasc_increase_returns(D):
        """Expect that there are no trailing hills, ldasc is greater than one
        and the number of returns is not maximal.  This is the map `phi`
        in arxiv:1701.07009.
        """
        p = prime_decomposition(D)
        # since D is a Dyck path, there are no connecting up steps
        p[-2] = no_return_to_one_return(p[-2])
        return DyckWord([e for P in p for e in P])
    
    def increase_ldasc_decrease_returns(D):
        """Expect that there are no trailing hills, ldasc is not maximal and
        the number of returns is greater than one.  This is the inverse
        of the map `phi` in arxiv:1701.07009.
        """
        p = prime_decomposition(D)
        # since D is a Dyck path, there are no connecting up steps
        p[-4] = one_return_to_no_return(p[-4]+p[-2])
        p[-2] = []
        return DyckWord([e for P in p for e in P])
​
    if len(D) == 0:
        return D
    elif D[-2:] == [1, 0]:
        return DyckWord(mapping(D[:-2]) + [1,0])
​
    D = DyckWord(D)
    a = D.number_of_touch_points()
    b = ldasc(D)
    if a == b:
        return D
    elif b > a:
        for i in range(b-a):
            D = decrease_ldasc_increase_returns(D)
        return DyckWord(D)
    elif a > b:
        for i in range(a-b):
            D = increase_ldasc_decrease_returns(D)
        return DyckWord(D)
​
​
active = [mapping(x) for x in elements]
​
​
​
pending = [mapping(x) for x in elements]
​
​
​
​
if not active == pending:
​
    raise AssertionError('the new code for the map does not generate the same images as the old one')

Rules

Apply the following rules while writing your submission.

Emphasis: ''italics''; '''bold'''; '''''bold italics'''''
Bulleted lists: * Item 1
Separate line
* Subitem 1
* Item 2
Links: [[target|linktext]] target must start with http://, https:// or with www.
Links to statistics in the database: [[St000001]]
Links to arXiv papers: new: [[arxiv:1401.3690]], old: [[arXiv:math/0011099]]
Links to MathSciNet reviews: [[mathscinet:3113227]] or [[MR3113227]]
Links to zbMATH (formerly: Zentralblatt) reviews: [[zbmath:0845.11001]]
Links to OEIS sequences: [[oeis:A000108]]
Links to MathOverflow questions and answers: [[mathoverflow:132338]] or [[MO132338]]
Links to Wikipedia articles: [[wikipedia:On-Line_Encyclopedia_of_Integer_Sequences]]
Links to Mathworld articles: [[mathworld:AdjacencyMatrix]]
Digital Object Identifiers: [[doi:10.1090/noti1029]]
CiteSeerX Identifiers: [[citeseer:10.1.1.150.1445]]