\(\nu\)-Dyck Words#

A class of the \(\nu\)-Dyck word, see [PRV2017] for details.

AUTHORS:

  • Aram Dermenjian (2020-09-26)

This file is based off the class DyckWords written by Mike Hansen, Dan Drake, Florent Hivert, Christian Stump, Mike Zabrocki, Jean–Baptiste Priez and Travis Scrimshaw

class sage.combinat.nu_dyck_word.NuDyckWord(parent, dw, latex_options=None)#

Bases: CombinatorialElement

A \(\nu\)-Dyck word.

Given a lattice path \(\nu\) in the \(\ZZ^2\) grid starting at the origin \((0,0)\) consisting of North \(N = (0,1)\) and East \(E = (1,0)\) steps, a \(\nu\)-Dyck path is a lattice path in the \(\ZZ^2\) grid starting at the origin \((0,0)\) and ending at the same coordinate as \(\nu\) such that it is weakly above \(\nu\). A \(\nu\)-Dyck word is the representation of a \(\nu\)-Dyck path where a North step is represented by a 1 and an East step is represented by a 0.

INPUT:

  • k1 – A path for the \(\nu\)-Dyck word

  • k2 – A path for \(\nu\)

EXAMPLES:

sage: dw = NuDyckWord([1,0,1,0],[1,0,0,1]); dw
[1, 0, 1, 0]
sage: print(dw)
NENE
sage: dw.height()
2

sage: dw = NuDyckWord('1010',[1,0,0,1]); dw
[1, 0, 1, 0]

sage: dw = NuDyckWord('NENE',[1,0,0,1]); dw
[1, 0, 1, 0]

sage: NuDyckWord([1,0,1,0],[1,0,0,1]).pretty_print()
   __
 _|x
| . .

sage: from sage.combinat.nu_dyck_word import update_ndw_symbols
sage: update_ndw_symbols(0,1)
sage: dw = NuDyckWord('0101001','0110010'); dw
[0, 1, 0, 1, 0, 0, 1]
sage: dw.pp()
     __
    |x
   _| .
 _|x  .
| . . .
sage: update_ndw_symbols(1,0)
can_mutate(i)#

Return True/False based off if mutable at height \(i\).

Can only mutate if an east step is followed by a north step at height \(i\).

OUTPUT:

Whether we can mutate at height of \(i\).

EXAMPLES:

sage: NDW = NuDyckWord('10010100','00000111')
sage: NDW.can_mutate(1)
False
sage: NDW.can_mutate(3)
5
height()#

Return the height of self.

The height is the number of north steps.

EXAMPLES:

sage: NuDyckWord('1101110011010010001101111000110000',
....: '1010101010101010101010101010101010').height()
17
heights()#

Return the heights of each point on self.

We view the Dyck word as a Dyck path from \((0,0)\) to \((x,y)\) in the first quadrant by letting 1’s represent steps in the direction \((0,1)\) and 0’s represent steps in the direction \((1,0)\).

The heights is the sequence of the \(y\)-coordinates of all \(x+y\) lattice points along the path.

EXAMPLES:

sage: NuDyckWord('010','010').heights()
[0, 0, 1, 1]
sage: NuDyckWord('110100','101010').heights()
[0, 1, 2, 2, 3, 3, 3]
horizontal_distance()#

Return a list of how far each point is from \(\nu\).

EXAMPLES:

sage: NDW = NuDyckWord('10010100','00000111')
sage: NDW.horizontal_distance()
[5, 5, 4, 3, 3, 2, 2, 1, 0]
sage: NDW = NuDyckWord('10010100','00001011')
sage: NDW.horizontal_distance()
[4, 5, 4, 3, 3, 2, 2, 1, 0]
sage: NDW = NuDyckWord('10011001000','00100101001')
sage: NDW.horizontal_distance()
[2, 4, 3, 2, 3, 5, 4, 3, 3, 2, 1, 0]
latex_options()#

Return the latex options for use in the _latex_ function as a dictionary.

The default values are set using the options.

  • color – (default: black) the line color.

  • line width – (default: 2*``tikz_scale``) value representing the line width.

  • nu_options – (default: 'rounded corners=1, color=red, line width=1') str to indicate what the tikz options should be for path of \(\nu\).

  • points_color – (default: 'black') str to indicate color points should be drawn with.

  • show_grid – (default: True) boolean value to indicate if grid should be shown.

  • show_nu – (default: True) boolean value to indicate if \(\nu\) should be shown.

  • show_points – (default: False) boolean value to indicate if points should be shown on path.

  • tikz_scale – (default: 1) scale for use with the tikz package.

EXAMPLES:

sage: NDW = NuDyckWord('010','010')
sage: NDW.latex_options()
{'color': black,
 'line width': 2,
 'nu_options': rounded corners=1, color=red, line width=1,
 'points_color': black,
 'show_grid': True,
 'show_nu': True,
 'show_points': False,
 'tikz_scale': 1}

Todo

This should probably be merged into NuDyckWord.options.

length()#

Return the length of self.

The length is the total number of steps.

EXAMPLES:

sage: NDW = NuDyckWord('10011001000','00100101001')
sage: NDW.length()
11
mutate(i)#

Return a new \(\nu\)-Dyck Word if possible.

If at height \(i\) we have an east step E meeting a north step N then we calculate all horizontal distances from this point until we find the first point that has the same horizontal distance to \(\nu\). We let

  • d is everything up until EN (not including EN)

  • f be everything between N and the point with the same horizontal distance (including N)

  • g is everything after f

See also

can_mutate()

EXAMPLES:

sage: NDW = NuDyckWord('10010100','00000111')
sage: NDW.mutate(1)
sage: NDW.mutate(3)
[1, 0, 0, 1, 1, 0, 0, 0]
path()#

Return the underlying path object.

EXAMPLES:

sage: NDW = NuDyckWord('10011001000','00100101001')
sage: NDW.path()
Path: 10011001000
plot(**kwds)#

Plot a \(\nu\)-Dyck word as a continuous path.

EXAMPLES:

sage: NDW = NuDyckWord('010','010')
sage: NDW.plot()                                                            # needs sage.plot
Graphics object consisting of 1 graphics primitive
points()#

Return an iterator for the points on the \(\nu\)-Dyck path.

EXAMPLES:

sage: list(NuDyckWord('110111001101001000110111100011000',
....: '101010101010101010101010101010101')._path.points())
[(0, 0),
 (0, 1),
 (0, 2),
 (1, 2),
 (1, 3),
 (1, 4),
 (1, 5),
 (2, 5),
 (3, 5),
 (3, 6),
 (3, 7),
 (4, 7),
 (4, 8),
 (5, 8),
 (6, 8),
 (6, 9),
 (7, 9),
 (8, 9),
 (9, 9),
 (9, 10),
 (9, 11),
 (10, 11),
 (10, 12),
 (10, 13),
 (10, 14),
 (10, 15),
 (11, 15),
 (12, 15),
 (13, 15),
 (13, 16),
 (13, 17),
 (14, 17),
 (15, 17),
 (16, 17)]
pp(style=None, labelling=None)#

Display a NuDyckWord as a lattice path in the \(\ZZ^2\) grid.

If the style is “N-E”, then a cell below the diagonal is indicated by a period, whereas a cell below the path but above the diagonal is indicated by an x. If a list of labels is included, they are displayed along the vertical edges of the Dyck path.

INPUT:

  • style – (default: None) can either be:

    • None to use the option default

    • “N-E” to show self as a path of north and east steps, or

  • labelling – (if style is “N-E”) a list of labels assigned to the up steps in self.

  • underpath – (if style is “N-E”, default: True) If True, an x to show the boxes between \(\nu\) and the \(\nu\)-Dyck Path.

EXAMPLES:

sage: for ND in NuDyckWords('101010'): ND.pretty_print()
     __
   _| .
 _| . .
| . . .
     __
 ___| .
|x  . .
| . . .
   ____
  |x  .
 _| . .
| . . .
   ____
 _|x  .
|x  . .
| . . .
 ______
|x x  .
|x  . .
| . . .
sage: nu = [1,0,1,0,1,0,1,0,1,0,1,0]
sage: ND = NuDyckWord([1,1,1,0,1,0,0,1,1,0,0,0],nu)
sage: ND.pretty_print()
       ______
      |x x  .
   ___|x  . .
 _|x x  . . .
|x x  . . . .
|x  . . . . .
| . . . . . .
sage: NuDyckWord([1,1,0,0,1,0],[1,0,1,0,1,0]).pretty_print(
....: labelling=[1,3,2])
     __
 ___| . 2
|x  . . 3
| . . . 1
sage: NuDyckWord('1101110011010010001101111000110000',
....: '1010101010101010101010101010101010').pretty_print(
....: labelling=list(range(1,18)))
                           ________
                          |x x x  . 17
                     _____|x x  . . 16
                    |x x x x  . . . 15
                    |x x x  . . . . 14
                    |x x  . . . . . 13
                   _|x  . . . . . . 12
                  |x  . . . . . . . 11
             _____| . . . . . . . . 10
         ___|x x  . . . . . . . . .  9
       _|x x x  . . . . . . . . . .  8
      |x x x  . . . . . . . . . . .  7
   ___|x x  . . . . . . . . . . . .  6
  |x x x  . . . . . . . . . . . . .  5
  |x x  . . . . . . . . . . . . . .  4
 _|x  . . . . . . . . . . . . . . .  3
|x  . . . . . . . . . . . . . . . .  2
| . . . . . . . . . . . . . . . . .  1
sage: NuDyckWord().pretty_print()
.
pretty_print(style=None, labelling=None)#

Display a NuDyckWord as a lattice path in the \(\ZZ^2\) grid.

If the style is “N-E”, then a cell below the diagonal is indicated by a period, whereas a cell below the path but above the diagonal is indicated by an x. If a list of labels is included, they are displayed along the vertical edges of the Dyck path.

INPUT:

  • style – (default: None) can either be:

    • None to use the option default

    • “N-E” to show self as a path of north and east steps, or

  • labelling – (if style is “N-E”) a list of labels assigned to the up steps in self.

  • underpath – (if style is “N-E”, default: True) If True, an x to show the boxes between \(\nu\) and the \(\nu\)-Dyck Path.

EXAMPLES:

sage: for ND in NuDyckWords('101010'): ND.pretty_print()
     __
   _| .
 _| . .
| . . .
     __
 ___| .
|x  . .
| . . .
   ____
  |x  .
 _| . .
| . . .
   ____
 _|x  .
|x  . .
| . . .
 ______
|x x  .
|x  . .
| . . .
sage: nu = [1,0,1,0,1,0,1,0,1,0,1,0]
sage: ND = NuDyckWord([1,1,1,0,1,0,0,1,1,0,0,0],nu)
sage: ND.pretty_print()
       ______
      |x x  .
   ___|x  . .
 _|x x  . . .
|x x  . . . .
|x  . . . . .
| . . . . . .
sage: NuDyckWord([1,1,0,0,1,0],[1,0,1,0,1,0]).pretty_print(
....: labelling=[1,3,2])
     __
 ___| . 2
|x  . . 3
| . . . 1
sage: NuDyckWord('1101110011010010001101111000110000',
....: '1010101010101010101010101010101010').pretty_print(
....: labelling=list(range(1,18)))
                           ________
                          |x x x  . 17
                     _____|x x  . . 16
                    |x x x x  . . . 15
                    |x x x  . . . . 14
                    |x x  . . . . . 13
                   _|x  . . . . . . 12
                  |x  . . . . . . . 11
             _____| . . . . . . . . 10
         ___|x x  . . . . . . . . .  9
       _|x x x  . . . . . . . . . .  8
      |x x x  . . . . . . . . . . .  7
   ___|x x  . . . . . . . . . . . .  6
  |x x x  . . . . . . . . . . . . .  5
  |x x  . . . . . . . . . . . . . .  4
 _|x  . . . . . . . . . . . . . . .  3
|x  . . . . . . . . . . . . . . . .  2
| . . . . . . . . . . . . . . . . .  1
sage: NuDyckWord().pretty_print()
.
set_latex_options(D)#

Set the latex options for use in the _latex_ function.

The default values are set in the __init__ function.

  • color – (default: black) the line color.

  • line width – (default: \(2 \times\) tikz_scale) value representing the line width.

  • nu_options – (default: 'rounded corners=1, color=red, line width=1') str to indicate what the tikz options should be for path of \(\nu\).

  • points_color – (default: 'black') str to indicate color points should be drawn with.

  • show_grid – (default: True) boolean value to indicate if grid should be shown.

  • show_nu – (default: True) boolean value to indicate if \(\nu\) should be shown.

  • show_points – (default: False) boolean value to indicate if points should be shown on path.

  • tikz_scale – (default: 1) scale for use with the tikz package.

INPUT:

  • D – a dictionary with a list of latex parameters to change

EXAMPLES:

sage: NDW = NuDyckWord('010','010')
sage: NDW.set_latex_options({"tikz_scale":2})
sage: NDW.set_latex_options({"color":"blue", "show_points":True})

Todo

This should probably be merged into NuDyckWord.options.

width()#

Return the width of self.

The width is the number of east steps.

EXAMPLES:

sage: NuDyckWord('110111001101001000110111100011000',
....: '101010101010101010101010101010101').width()
16
widths()#

Return the widths of each point on self.

We view the Dyck word as a Dyck path from \((0,0)\) to \((x,y)\) in the first quadrant by letting 1’s represent steps in the direction \((0,1)\) and 0’s represent steps in the direction \((1,0)\).

The widths is the sequence of the \(x\)-coordinates of all \(x+y\) lattice points along the path.

EXAMPLES:

sage: NuDyckWord('010','010').widths()
[0, 1, 1, 2]
sage: NuDyckWord('110100','101010').widths()
[0, 0, 0, 1, 1, 2, 3]
class sage.combinat.nu_dyck_word.NuDyckWords(nu=())#

Bases: Parent

\(\nu\)-Dyck words.

Given a lattice path \(\nu\) in the \(\ZZ^2\) grid starting at the origin \((0,0)\) consisting of North \(N = (0,1)\) and East \(E = (1,0)\) steps, a \(\nu\)-Dyck path is a lattice path in the`ZZ^2` grid starting at the origin \((0,0)\) and ending at the same coordinate as \(\nu\) such that it is weakly above \(\nu\). A \(\nu\)-Dyck word is the representation of a \(\nu\)-Dyck path where a North step is represented by a 1 and an East step is represented by a 0.

INPUT:

  • nu – the base lattice path.

EXAMPLES:

sage: NDW = NuDyckWords('1010'); NDW
[1, 0, 1, 0] Dyck words
sage: [1,0,1,0] in NDW
True
sage: [1,1,0,0] in NDW
True
sage: [1,0,0,1] in NDW
False
sage: [0,1,0,1] in NDW
False
sage: NDW.cardinality()
2
Element#

alias of NuDyckWord

cardinality()#

Return the number of \(\nu\)-Dyck words.

EXAMPLES:

sage: NDW = NuDyckWords('101010'); NDW.cardinality()
5
sage: NDW = NuDyckWords('1010010'); NDW.cardinality()
7
sage: NDW = NuDyckWords('100100100'); NDW.cardinality()
12
options = Current options for NuDyckWords   - ascii_art:               pretty_output   - diagram_style:           grid   - display:                 list   - latex_color:             black   - latex_line_width_scalar: 2   - latex_nu_options:        rounded corners=1, color=red, line width=1   - latex_points_color:      black   - latex_show_grid:         True   - latex_show_nu:           True   - latex_show_points:       False   - latex_tikz_scale:        1#
sage.combinat.nu_dyck_word.path_weakly_above_other(path, other)#

Test if path is weakly above other.

A path \(P\) is wealy above another path \(Q\) if \(P\) and \(Q\) are the same length and if any prefix of length \(n\) of \(Q\) contains more North steps than the prefix of length \(n\) of \(P\).

INPUT:

  • path – The path to verify is weakly above the other path.

  • other – The other path to verify is weakly below the path.

OUTPUT:

bool

EXAMPLES:

sage: from sage.combinat.nu_dyck_word import path_weakly_above_other
sage: path_weakly_above_other('1001','0110')
False
sage: path_weakly_above_other('1001','0101')
True
sage: path_weakly_above_other('1111','0101')
False
sage: path_weakly_above_other('111100','0101')
False
sage.combinat.nu_dyck_word.replace_dyck_char(x)#

A map sending an opening character ('1', 'N', and '(') to ndw_open_symbol, a closing character ('0', 'E', and ')') to ndw_close_symbol, and raising an error on any input other than one of the opening or closing characters.

This is the inverse map of replace_dyck_symbol().

INPUT:

  • x – str - A '1', '0', 'N', 'E', '(' or ')'

OUTPUT:

  • If x is an opening character, replace x with the constant ndw_open_symbol.

  • If x is a closing character, replace x with the constant ndw_close_symbol.

  • Raise a ValueError if x is neither an opening nor a closing character.

EXAMPLES:

sage: from sage.combinat.nu_dyck_word import replace_dyck_char
sage: replace_dyck_char('(')
1
sage: replace_dyck_char(')')
0
sage: replace_dyck_char(1)
Traceback (most recent call last):
...
ValueError
sage.combinat.nu_dyck_word.replace_dyck_symbol(x, open_char='N', close_char='E')#

A map sending ndw_open_symbol to open_char and ndw_close_symbol to close_char, and raising an error on any input other than ndw_open_symbol and ndw_close_symbol. The values of the constants ndw_open_symbol and ndw_close_symbol are subject to change.

This is the inverse map of replace_dyck_char().

INPUT:

  • x – either ndw_open_symbol or ndw_close_symbol.

  • open_char – str (optional) default 'N'

  • close_char – str (optional) default 'E'

OUTPUT:

  • If x is ndw_open_symbol, replace x with open_char.

  • If x is ndw_close_symbol, replace x with close_char.

  • If x is neither ndw_open_symbol nor ndw_close_symbol, a ValueError is raised.

EXAMPLES:

sage: from sage.combinat.nu_dyck_word import replace_dyck_symbol
sage: replace_dyck_symbol(1)
'N'
sage: replace_dyck_symbol(0)
'E'
sage: replace_dyck_symbol(3)
Traceback (most recent call last):
...
ValueError
sage.combinat.nu_dyck_word.to_word_path(word)#

Convert input into a word path over an appropriate alphabet.

Helper function.

INPUT:

  • word – word to convert to wordpath

OUTPUT:

  • A FiniteWordPath_north_east object.

EXAMPLES:

sage: from sage.combinat.nu_dyck_word import to_word_path
sage: wp = to_word_path('NEENENEN'); wp
Path: 10010101
sage: from sage.combinat.words.paths import FiniteWordPath_north_east
sage: isinstance(wp,FiniteWordPath_north_east)
True
sage: to_word_path('1001')
Path: 1001
sage: to_word_path([0,1,0,0,1,0])
Path: 010010
sage.combinat.nu_dyck_word.update_ndw_symbols(os, cs)#

A way to alter the open and close symbols from sage.

INPUT:

  • os – the open symbol

  • cs – the close symbol

EXAMPLES:

sage: from sage.combinat.nu_dyck_word import update_ndw_symbols
sage: update_ndw_symbols(0,1)
sage: dw = NuDyckWord('0101001','0110010'); dw
[0, 1, 0, 1, 0, 0, 1]

sage: dw = NuDyckWord('1010110','1001101'); dw
Traceback (most recent call last):
...
ValueError: invalid nu-Dyck word
sage: update_ndw_symbols(1,0)