From pgtsik@unipi.gr Tue Apr 18 06:04:29 2006 Return-Path: X-Spam-Checker-Version: SpamAssassin 3.1.0 (2005-09-13) on minos.uwaterloo.ca X-Spam-Level: X-Spam-Status: No, score=1.0 required=5.0 tests=AWL,DNS_FROM_RFC_ABUSE, HTML_MESSAGE autolearn=disabled version=3.1.0 Received: from ermis.unipi.gr (ermis.unipi.gr [195.251.229.9]) by graceland.math.uwaterloo.ca (8.11.7/8.11.7) with ESMTP id k3IA4Rg01033 for ; Tue, 18 Apr 2006 06:04:28 -0400 (EDT) Received: from ermis (ermis [195.251.229.9]) by ermis.unipi.gr (8.12.10+Sun/8.12.10) with ESMTP id k3I9K3Da018470 for ; Tue, 18 Apr 2006 12:20:03 +0300 (EEST) Received: from pgtsik.cs.unipi.gr ([195.251.225.112]) by ermis (MailMonitor for SMTP v1.2.2 ) ; Tue, 18 Apr 2006 12:20:02 +0300 (EEST) Message-ID: <008d01c662c9$911663b0$70e1fbc3@pgtsik> From: "P.-G. Tsikouras" To: "Jeffrey Shallit" Subject: Re: Submission to the Journal of Integer Sequences Date: Tue, 18 Apr 2006 12:17:04 +0300 MIME-Version: 1.0 Content-Type: multipart/mixed; boundary="----=_NextPart_000_0063_01C662E2.00CF14A0" X-Priority: 3 X-MSMail-Priority: Normal X-Mailer: Microsoft Outlook Express 6.00.2900.2869 X-MimeOLE: Produced By Microsoft MimeOLE V6.00.2900.2869 X-Greylist: Delayed for 00:42:06 by milter-greylist-2.0 (graceland.math.uwaterloo.ca [129.97.75.152]); Tue, 18 Apr 2006 06:04:29 -0400 (EDT) Status: RO X-Status: X-Keywords: X-UID: 2161 This is a multi-part message in MIME format. ------=_NextPart_000_0063_01C662E2.00CF14A0 Content-Type: multipart/alternative; boundary="----=_NextPart_001_0064_01C662E2.00CF14A0" ------=_NextPart_001_0064_01C662E2.00CF14A0 Content-Type: text/plain; charset="iso-8859-7" Content-Transfer-Encoding: quoted-printable Dear Professor Shallit, Attached please find the paper "On the dominance partial ordering of = Dyck paths" by A. Sapounakis, I. Tasoulas and P. Tsikouras, revised = according to the referee's suggestions. Moreover, for the improvement of the paper we have made the following = minor changes: * Emanating from a remark by the referee, we simplified the definition = of the sequences $(A_i)_{i \in [n]}$ in page 13. * We added some references ([1],[2] and [10]) and remarks (in pages 13 = and 14), in order to give the reader some additional connection to = previous work. Thank you once more for your kind attention. Yours sincerely, P. Tsikouras ------=_NextPart_001_0064_01C662E2.00CF14A0 Content-Type: text/html; charset="iso-8859-7" Content-Transfer-Encoding: quoted-printable

Dear Professor=20 Shallit,

Attached = please find=20 the paper "On the dominance partial ordering of Dyck paths" by A. = Sapounakis, I.=20 Tasoulas and P. Tsikouras, revised according to the referee's=20 suggestions.

Moreover, for the improvement of the paper we have = made the=20 following minor changes:

* Emanating from a remark by the = referee, we=20 simplified the definition of the sequences $(A_i)_{i \in [n]}$ in page=20 13.

* We added some references ([1],[2] and [10]) and remarks (in = pages=20 13 and 14), in order to give the reader some additional connection to = previous=20 work.

Thank you once more for your kind attention.

Yours=20 sincerely,

P. Tsikouras

------=_NextPart_001_0064_01C662E2.00CF14A0-- ------=_NextPart_000_0063_01C662E2.00CF14A0 Content-Type: application/postscript; name="fig0.eps" Content-Transfer-Encoding: quoted-printable Content-Disposition: attachment; filename="fig0.eps" %!PS-Adobe-2.0 EPSF-2.0 %%Title: fig0.eps %%Creator: fig2dev Version 3.2 Patchlevel 3d %%CreationDate: Sun Jun 19 17:15:27 2005 %%For: user@omega (lamer,,,) %%BoundingBox: 0 0 385 130 %%Magnification: 1.0000 %%EndComments /$F2psDict 200 dict def $F2psDict begin $F2psDict /mtrx matrix put /col-1 {0 setgray} bind def /col0 {0.000 0.000 0.000 srgb} bind def /col1 {0.000 0.000 1.000 srgb} bind def /col2 {0.000 1.000 0.000 srgb} bind def /col3 {0.000 1.000 1.000 srgb} bind def /col4 {1.000 0.000 0.000 srgb} bind def /col5 {1.000 0.000 1.000 srgb} bind def /col6 {1.000 1.000 0.000 srgb} bind def /col7 {1.000 1.000 1.000 srgb} bind def /col8 {0.000 0.000 0.560 srgb} bind def /col9 {0.000 0.000 0.690 srgb} bind def /col10 {0.000 0.000 0.820 srgb} bind def /col11 {0.530 0.810 1.000 srgb} bind def /col12 {0.000 0.560 0.000 srgb} bind def /col13 {0.000 0.690 0.000 srgb} bind def /col14 {0.000 0.820 0.000 srgb} bind def /col15 {0.000 0.560 0.560 srgb} bind def /col16 {0.000 0.690 0.690 srgb} bind def /col17 {0.000 0.820 0.820 srgb} bind def /col18 {0.560 0.000 0.000 srgb} bind def /col19 {0.690 0.000 0.000 srgb} bind def /col20 {0.820 0.000 0.000 srgb} bind def /col21 {0.560 0.000 0.560 srgb} bind def /col22 {0.690 0.000 0.690 srgb} bind def /col23 {0.820 0.000 0.820 srgb} bind def /col24 {0.500 0.190 0.000 srgb} bind def /col25 {0.630 0.250 0.000 srgb} bind def /col26 {0.750 0.380 0.000 srgb} bind def /col27 {1.000 0.500 0.500 srgb} bind def /col28 {1.000 0.630 0.630 srgb} bind def /col29 {1.000 0.750 0.750 srgb} bind def /col30 {1.000 0.880 0.880 srgb} bind def /col31 {1.000 0.840 0.000 srgb} bind def end save newpath 0 130 moveto 0 0 lineto 385 0 lineto 385 130 lineto closepath = clip newpath -54.0 234.0 translate 1 -1 scale /cp {closepath} bind def /ef {eofill} bind def /gr {grestore} bind def /gs {gsave} bind def /sa {save} bind def /rs {restore} bind def /l {lineto} bind def /m {moveto} bind def /rm {rmoveto} bind def /n {newpath} bind def /s {stroke} bind def /sh {show} bind def /slc {setlinecap} bind def /slj {setlinejoin} bind def /slw {setlinewidth} bind def /srgb {setrgbcolor} bind def /rot {rotate} bind def /sc {scale} bind def /sd {setdash} bind def /ff {findfont} bind def /sf {setfont} bind def /scf {scalefont} bind def /sw {stringwidth} bind def /tr {translate} bind def /tnt {dup dup currentrgbcolor 4 -2 roll dup 1 exch sub 3 -1 roll mul add 4 -2 roll dup 1 exch sub 3 -1 roll mul add 4 -2 roll dup 1 exch sub 3 -1 roll mul add srgb} bind def /shd {dup dup currentrgbcolor 4 -2 roll mul 4 -2 roll mul 4 -2 roll mul srgb} bind def /$F2psBegin {$F2psDict begin /$F2psEnteredState save def} def /$F2psEnd {$F2psEnteredState restore end} def $F2psBegin 10 setmiterlimit 0 slj 0 slc 0.06000 0.06000 sc % % Fig objects follow % % Polyline 30.000 slw n 1200 3600 m 1800 3000 l gs col0 s gr=20 % Polyline n 1800 3000 m 2400 3600 l gs col0 s gr=20 % Polyline n 2400 3600 m 4200 1800 l gs col0 s gr=20 % Polyline n 4200 1800 m 4800 2400 l gs col0 s gr=20 % Polyline n 4800 2400 m 5100 2100 l gs col0 s gr=20 % Polyline n 5100 2100 m 6000 3000 l gs col0 s gr=20 % Polyline n 6000 3000 m 6300 2700 l gs col0 s gr=20 % Polyline n 6300 2700 m 7200 3600 l gs col0 s gr=20 % Polyline n 1200 3600 m 7200 3600 l gs col0 s gr=20 % Polyline 7.500 slw n 1200 3300 m 7200 3300 l gs col0 s gr=20 % Polyline n 1200 3000 m 7200 3000 l gs col0 s gr=20 % Polyline n 1200 2700 m 7200 2700 l gs col0 s gr=20 % Polyline n 1200 2400 m 7200 2400 l gs col0 s gr=20 % Polyline n 1200 2100 m 7200 2100 l gs col0 s gr=20 % Polyline n 1200 1800 m 7200 1800 l gs col0 s gr=20 % Polyline n 1200 3600 m 1200 1800 l gs col0 s gr=20 % Polyline n 1500 3600 m 1500 1800 l gs col0 s gr=20 % Polyline n 1800 3600 m 1800 1800 l gs col0 s gr=20 % Polyline n 2100 3600 m 2100 1800 l gs col0 s gr=20 % Polyline n 2400 3600 m 2400 1800 l gs col0 s gr=20 % Polyline n 2700 3600 m 2700 3300 l 2700 3000 l 2700 2700 l 2700 2400 l 2700 2100 = l 2700 1800 l gs col0 s gr=20 % Polyline n 3000 3600 m 3000 1800 l gs col0 s gr=20 % Polyline n 3300 3600 m 3300 1800 l gs col0 s gr=20 % Polyline n 3600 3600 m 3600 3300 l 3600 3000 l 3600 2700 l 3600 2400 l 3600 2100 = l 3600 1800 l gs col0 s gr=20 % Polyline n 3900 3600 m 3900 3300 l 3900 3000 l 3900 2700 l 3900 2400 l 3900 2100 = l 3900 1800 l gs col0 s gr=20 % Polyline n 4200 3600 m 4200 3300 l 4200 3000 l 4200 2700 l 4200 2400 l 4200 2100 = l 4200 1800 l gs col0 s gr=20 % Polyline n 4500 3600 m 4500 3300 l 4500 3000 l 4500 2700 l 4500 2400 l 4500 2100 = l 4500 1800 l gs col0 s gr=20 % Polyline n 4800 3600 m 4800 3300 l 4800 3000 l 4800 2700 l 4800 2400 l 4800 2100 = l 4800 1800 l gs col0 s gr=20 % Polyline n 5100 3600 m 5100 3300 l 5100 3000 l 5100 2700 l 5100 2400 l 5100 2100 = l 5100 1800 l gs col0 s gr=20 % Polyline n 5400 3600 m 5400 3300 l 5400 3000 l 5400 2700 l 5400 2400 l 5400 2100 = l 5400 1800 l gs col0 s gr=20 % Polyline n 5700 3600 m 5700 3300 l 5700 3000 l 5700 2700 l 5700 2400 l 5700 2100 = l 5700 1800 l gs col0 s gr=20 % Polyline n 6000 3600 m 6000 1800 l gs col0 s gr=20 % Polyline n 6300 3600 m 6300 3300 l 6300 3000 l 6300 2700 l 6300 2400 l 6300 2100 = l 6300 1800 l gs col0 s gr=20 % Polyline n 6600 3600 m 6600 3300 l 6600 3000 l 6600 2700 l 6600 2400 l 6600 2100 = l 6600 1800 l gs col0 s gr=20 % Polyline n 6900 3600 m 6900 3300 l 6900 3000 l 6900 2700 l 6900 2400 l 6900 2100 = l 6900 1800 l gs col0 s gr=20 % Polyline n 7200 3600 m 7200 1800 l gs col0 s gr=20 /Times-Roman ff 180.00 scf sf 1425 3900 m gs 1 -1 sc (1) col0 sh gr /Times-Roman ff 180.00 scf sf 1725 3900 m gs 1 -1 sc (2) col0 sh gr /Times-Roman ff 180.00 scf sf 2025 3900 m gs 1 -1 sc (3) col0 sh gr /Times-Roman ff 180.00 scf sf 2325 3900 m gs 1 -1 sc (4) col0 sh gr /Times-Roman ff 180.00 scf sf 2625 3900 m gs 1 -1 sc (5) col0 sh gr /Times-Roman ff 180.00 scf sf 2925 3900 m gs 1 -1 sc (6) col0 sh gr /Times-Roman ff 180.00 scf sf 3225 3900 m gs 1 -1 sc (7) col0 sh gr /Times-Roman ff 180.00 scf sf 3525 3900 m gs 1 -1 sc (8) col0 sh gr /Times-Roman ff 180.00 scf sf 3825 3900 m gs 1 -1 sc (9) col0 sh gr /Times-Roman ff 180.00 scf sf 4125 3900 m gs 1 -1 sc (10) col0 sh gr /Times-Roman ff 180.00 scf sf 4425 3900 m gs 1 -1 sc (11) col0 sh gr /Times-Roman ff 180.00 scf sf 4725 3900 m gs 1 -1 sc (12) col0 sh gr /Times-Roman ff 180.00 scf sf 5025 3900 m gs 1 -1 sc (13) col0 sh gr /Times-Roman ff 180.00 scf sf 5325 3900 m gs 1 -1 sc (14) col0 sh gr /Times-Roman ff 180.00 scf sf 5625 3900 m gs 1 -1 sc (15) col0 sh gr /Times-Roman ff 180.00 scf sf 5925 3900 m gs 1 -1 sc (16) col0 sh gr /Times-Roman ff 180.00 scf sf 6225 3900 m gs 1 -1 sc (17) col0 sh gr /Times-Roman ff 180.00 scf sf 6525 3900 m gs 1 -1 sc (18) col0 sh gr /Times-Roman ff 180.00 scf sf 6825 3900 m gs 1 -1 sc (19) col0 sh gr /Times-Roman ff 180.00 scf sf 7125 3900 m gs 1 -1 sc (20) col0 sh gr /Times-Roman ff 180.00 scf sf 900 3375 m gs 1 -1 sc (1) col0 sh gr /Times-Roman ff 180.00 scf sf 900 3075 m gs 1 -1 sc (2) col0 sh gr /Times-Roman ff 180.00 scf sf 900 2775 m gs 1 -1 sc (3) col0 sh gr /Times-Roman ff 180.00 scf sf 900 2475 m gs 1 -1 sc (4) col0 sh gr /Times-Roman ff 180.00 scf sf 900 2175 m gs 1 -1 sc (5) col0 sh gr /Times-Roman ff 180.00 scf sf 900 1875 m gs 1 -1 sc (6) col0 sh gr /Times-Roman ff 180.00 scf sf 1125 3900 m gs 1 -1 sc (0) col0 sh gr $F2psEnd rs ------=_NextPart_000_0063_01C662E2.00CF14A0 Content-Type: application/postscript; name="fig1.eps" Content-Transfer-Encoding: quoted-printable Content-Disposition: attachment; filename="fig1.eps" %!PS-Adobe-2.0 EPSF-2.0 %%Title: fig1b.eps %%Creator: fig2dev Version 3.2 Patchlevel 3d %%CreationDate: Sat Jun 25 11:43:52 2005 %%For: user@omega (lamer,,,) %%BoundingBox: 0 0 183 335 %%Magnification: 1.0000 %%EndComments /$F2psDict 200 dict def $F2psDict begin $F2psDict /mtrx matrix put /col-1 {0 setgray} bind def /col0 {0.000 0.000 0.000 srgb} bind def /col1 {0.000 0.000 1.000 srgb} bind def /col2 {0.000 1.000 0.000 srgb} bind def /col3 {0.000 1.000 1.000 srgb} bind def /col4 {1.000 0.000 0.000 srgb} bind def /col5 {1.000 0.000 1.000 srgb} bind def /col6 {1.000 1.000 0.000 srgb} bind def /col7 {1.000 1.000 1.000 srgb} bind def /col8 {0.000 0.000 0.560 srgb} bind def /col9 {0.000 0.000 0.690 srgb} bind def /col10 {0.000 0.000 0.820 srgb} bind def /col11 {0.530 0.810 1.000 srgb} bind def /col12 {0.000 0.560 0.000 srgb} bind def /col13 {0.000 0.690 0.000 srgb} bind def /col14 {0.000 0.820 0.000 srgb} bind def /col15 {0.000 0.560 0.560 srgb} bind def /col16 {0.000 0.690 0.690 srgb} bind def /col17 {0.000 0.820 0.820 srgb} bind def /col18 {0.560 0.000 0.000 srgb} bind def /col19 {0.690 0.000 0.000 srgb} bind def /col20 {0.820 0.000 0.000 srgb} bind def /col21 {0.560 0.000 0.560 srgb} bind def /col22 {0.690 0.000 0.690 srgb} bind def /col23 {0.820 0.000 0.820 srgb} bind def /col24 {0.500 0.190 0.000 srgb} bind def /col25 {0.630 0.250 0.000 srgb} bind def /col26 {0.750 0.380 0.000 srgb} bind def /col27 {1.000 0.500 0.500 srgb} bind def /col28 {1.000 0.630 0.630 srgb} bind def /col29 {1.000 0.750 0.750 srgb} bind def /col30 {1.000 0.880 0.880 srgb} bind def /col31 {1.000 0.840 0.000 srgb} bind def end save newpath 0 335 moveto 0 0 lineto 183 0 lineto 183 335 lineto closepath = clip newpath -126.0 340.4 translate 1 -1 scale /cp {closepath} bind def /ef {eofill} bind def /gr {grestore} bind def /gs {gsave} bind def /sa {save} bind def /rs {restore} bind def /l {lineto} bind def /m {moveto} bind def /rm {rmoveto} bind def /n {newpath} bind def /s {stroke} bind def /sh {show} bind def /slc {setlinecap} bind def /slj {setlinejoin} bind def /slw {setlinewidth} bind def /srgb {setrgbcolor} bind def /rot {rotate} bind def /sc {scale} bind def /sd {setdash} bind def /ff {findfont} bind def /sf {setfont} bind def /scf {scalefont} bind def /sw {stringwidth} bind def /tr {translate} bind def /tnt {dup dup currentrgbcolor 4 -2 roll dup 1 exch sub 3 -1 roll mul add 4 -2 roll dup 1 exch sub 3 -1 roll mul add 4 -2 roll dup 1 exch sub 3 -1 roll mul add srgb} bind def /shd {dup dup currentrgbcolor 4 -2 roll mul 4 -2 roll mul 4 -2 roll mul srgb} bind def /$F2psBegin {$F2psDict begin /$F2psEnteredState save def} def /$F2psEnd {$F2psEnteredState restore end} def $F2psBegin 10 setmiterlimit 0 slj 0 slc 0.06000 0.06000 sc % % Fig objects follow % % Polyline 30.000 slw n 3600 5400 m 2400 4800 l gs col0 s gr=20 % Polyline n 3600 5400 m 3600 4800 l gs col0 s gr=20 % Polyline n 3600 5400 m 4800 4800 l gs col0 s gr=20 % Polyline n 3600 4500 m 2400 3900 l gs col0 s gr=20 % Polyline n 3600 4500 m 4800 3900 l gs col0 s gr=20 % Polyline n 2400 4500 m 2400 3900 l gs col0 s gr=20 % Polyline n 2400 4500 m 3600 3900 l gs col0 s gr=20 % Polyline n 4800 4500 m 3600 3900 l gs col0 s gr=20 % Polyline n 4800 4500 m 4800 3900 l gs col0 s gr=20 % Polyline n 2400 3600 m 2400 3000 l gs col0 s gr=20 % Polyline n 2400 3600 m 3600 3000 l gs col0 s gr=20 % Polyline n 3600 3600 m 3600 3000 l gs col0 s gr=20 % Polyline n 3600 3000 m 4800 3600 l gs col0 s gr=20 % Polyline n 4800 3600 m 4800 3000 l gs col0 s gr=20 % Polyline n 2400 2700 m 2400 2100 l gs col0 s gr=20 % Polyline n 4800 2700 m 4800 2100 l gs col0 s gr=20 % Polyline n 3600 2700 m 2400 2100 l gs col0 s gr=20 % Polyline n 3600 2700 m 4800 2100 l gs col0 s gr=20 % Polyline n 2400 1800 m 3600 1200 l gs col0 s gr=20 % Polyline n 4800 1800 m 3600 1200 l gs col0 s gr=20 % Polyline n 3600 900 m 3600 300 l gs col0 s gr=20 /Times-Roman ff 180.00 scf sf 3300 225 m gs 1 -1 sc (4, 0, 0, 0) col0 sh gr /Times-Roman ff 180.00 scf sf 3300 1125 m gs 1 -1 sc (3, 1, 0, 0) col0 sh gr /Times-Roman ff 180.00 scf sf 2100 2025 m gs 1 -1 sc (3, 0, 1, 0) col0 sh gr /Times-Roman ff 180.00 scf sf 2100 2925 m gs 1 -1 sc (3, 0, 0, 1) col0 sh gr /Times-Roman ff 180.00 scf sf 2100 3825 m gs 1 -1 sc (2, 1, 0, 1) col0 sh gr /Times-Roman ff 180.00 scf sf 2100 4725 m gs 1 -1 sc (2, 0, 1, 1) col0 sh gr /Times-Roman ff 180.00 scf sf 3300 4725 m gs 1 -1 sc (1, 2, 0, 1) col0 sh gr /Times-Roman ff 180.00 scf sf 3300 3825 m gs 1 -1 sc (2, 0, 2, 0) col0 sh gr /Times-Roman ff 180.00 scf sf 3300 2925 m gs 1 -1 sc (2, 1, 1, 0) col0 sh gr /Times-Roman ff 180.00 scf sf 4500 2025 m gs 1 -1 sc (2, 2, 0, 0) col0 sh gr /Times-Roman ff 180.00 scf sf 4500 2925 m gs 1 -1 sc (1, 3, 0, 0) col0 sh gr /Times-Roman ff 180.00 scf sf 4500 3825 m gs 1 -1 sc (1, 2, 1, 0) col0 sh gr /Times-Roman ff 180.00 scf sf 4500 4725 m gs 1 -1 sc (1, 1, 2, 0) col0 sh gr /Times-Roman ff 180.00 scf sf 3300 5625 m gs 1 -1 sc (1, 1, 1, 1) col0 sh gr $F2psEnd rs ------=_NextPart_000_0063_01C662E2.00CF14A0 Content-Type: application/octet-stream; name="On_the_dominance_partial_ordering_of_Dyck_paths.tex" Content-Transfer-Encoding: quoted-printable Content-Disposition: attachment; filename="On_the_dominance_partial_ordering_of_Dyck_paths.tex" %A LaTex file for a 17 page document. \documentclass[12pt,reqno]{article} \usepackage{fullpage} \usepackage{amsmath, amssymb, amsfonts} \usepackage{graphicx, epsf} \usepackage[usenames]{color} \definecolor{webgreen}{rgb}{0,.5,0} \definecolor{webbrown}{rgb}{.6,0,0} \usepackage[colorlinks=3Dtrue, linkcolor=3Dwebgreen, filecolor=3Dwebbrown, citecolor=3Dwebgreen]{hyperref} \newtheorem{tm}{Theorem}[section] \newtheorem{prop}[tm]{Proposition} \newtheorem{cor}[tm]{Corollary} \newtheorem{lemma}[tm]{Lemma} \setlength{\textwidth}{6.5in} \setlength{\oddsidemargin}{.1in} \setlength{\evensidemargin}{.1in} \setlength{\topmargin}{-.5in} \setlength{\textheight}{8.9in} \newcommand{\seqnum}[1]{\href{http://www.research.att.com/cgi-bin/access.= cgi/as/~njas/sequences/eisA.cgi?Anum=3D#1}{\underline{#1}}} \begin{document} %\begin{center} %\epsfxsize=3D4in %\leavevmode\epsffile{logo129.eps} %\end{center} \begin{center} \vskip 1cm{\LARGE\bf On the dominance partial ordering \vskip .1in of Dyck paths} \vskip 1cm \large A. Sapounakis, I. Tasoulas and P. Tsikouras \\ Department of Informatics\\ University of Piraeus\\ 18534 Piraeus \\ GREECE\\ \{\htmladdnormallink{\texttt{arissap}}{arissap@unipi.gr}, \htmladdnormallink{\texttt{jtas}}{jtas@unipi.gr}, = \htmladdnormallink{\texttt{pgtsik}}{pgtsik@unipi.gr}\}\texttt{@unipi.gr} \end{center} \vskip .2 in \begin{abstract} The lattice of Dyck paths with the dominance partial order is studied. = The notions of filling and degree of a Dyck path are introduced, studied and = used for the evaluation of the M\"obius function and its powers. The relation between the symmetric group endowed with the weak Bruhat order and the set of Dyck paths is studied. \end{abstract} \section{Introduction}\label{section1} A wide range of articles dealing with lattices of combinatorial objects appear frequently in the literature, e.g., lattices of integer partitions, \cite{Brylawski, Stanley1}, permutations \cite{GuilbaudRosenstiehl, Tamari} and noncrossing partitions \cite{EdelmanSimion, SimionUllman}. In this paper, the lattice of Dyck paths with the dominance partial = order and some of its relations to other combinatorial structures are studied. In section \ref{section2}, some basic definitions and notations = referring to the set $\mathcal{D}_n$ of Dyck paths of semilength $n$, are given. In section \ref{section3}, the rank of a Dyck path is studied and the rank-generating function is exhibited. In section \ref{section4}, the notions of filling and degree of a Dyck path are introduced and studied. Various enumeration results are presented. These notions are used in section \ref{section5} for the evaluation of the M\"obius function and its powers. In this context, a new appearance of the Fibonacci numbers (\seqnum{A000045} of \cite{Sloane}) occurs. Finally, in section \ref{section6} the relation between the symmetric group $S_n$ endowed with the weak Bruhat order and $\mathcal{D}_n$ is studied. More precisely, a partition of $S_n$ into $C_n$ (\mbox{Catalan,} (\seqnum{A000108}) of \cite{Sloane}) classes is constructed, satisfying an ordering condition, and the cardinal numbers of its members are evaluated. \section{Preliminaries}\label{section2} A \textit{Dyck path} of semilength $n$ is a path in the first quadrant, = which begins at the origin, ends at $(2n,0)$, and consists of steps $(1,1)$ = and $(1,-1)$, called \textit{rise} and \textit{fall} respectively. It is clear that each Dyck path is coded by a word $u \in \{a, = \bar{a}\}^*$, called \textit{Dyck word}, so that every rise (resp. fall) corresponds = to the letter $a$ (resp. $\bar{a}$); see Fig. \ref{fig1}. \begin{figure}[ht] \centerline{\includegraphics[width=3D4in]{fig0.eps}} \centerline{$a$ $a$ $\bar{a}$ $\bar{a}$ $a$ $a$ $a$ $a$ $a$ $a$ = $\bar{a}$ $\bar{a}$ $a$ $\bar{a}$ $\bar{a}$ $\bar{a}$ $a$ $\bar{a}$ $\bar{a}$ = $\bar{a}$} \caption{A Dyck path and its corresponding word}\label{fig1} \end{figure} Throughout this paper we will denote with $D$ the set of all Dyck paths (or equivalently Dyck words). Furthermore, the subset of $D$ that contains the paths $u$ of semilength $l(u) =3D n$ is denoted by $D_n$. We denote with $\epsilon$ the empty path. Every $u \in D \setminus = \{\epsilon\}$ can be uniquely decomposed in the form $u =3D a w \bar{a} v$, $w, v \in = D$, which is called the \textit{first return decomposition} of $u$. Every Dyck path $u$ that meets the $x$-axis only at its endpoints (i.e., $u =3D a w \bar{a}$, with $w \in D$) is called \textit{prime}. Every Dyck path can be uniquely decomposed into prime paths \cite{PS}. It is well known that Dyck paths are enumerated by the Catalan numbers, = with generating function $C(x)$, which satisfies the relation $xC^2(x) =3D = C(x) - 1$. \medskip For a parameter $q$ defined on $D$, we will denote with $F_q$ the generating function of $D$ according to the parameters $l$, $q$, i.e., \[ F_q (x,y) =3D \sum\limits_{u \in D} x^{l(u)} y^{q(u)}. \] A point of a Dyck path is called \textit{peak} (resp. \textit{valley}) = if it is preceded by a rise (resp. fall) and followed by a fall (resp. rise). = A point of a Dyck path is called \textit{double rise} (resp. \textit{double = fall}) if it is preceded and followed by a rise (resp. fall). A convenient way to represent a Dyck word is by using dominating = sequences. A sequence $d =3D (d_i)_{i \in [n]}$ of non-negative integers is called \textit{dominating} if it satisfies the following two conditions : \\ i) $\sum\limits_{i=3D1}^{n} d_i =3D n$, \\ ii) = $\sum\limits_{i=3D1}^{\nu} d_i \ge \nu$, for every $\nu \in [n]$. It is well known that every non-empty Dyck word $u$ is uniquely represented by a dominating sequence $d(u) =3D (d_i)_{i \in l(u)}$ where $d_1$ is the number of $a$'s before the $1^{\rm st}$ occurrence of $\bar{a}$ in $u$, and $d_i$ is the number of $a$'s between the $(i-1)^{\rm th}$ and the $i^{\rm th}$ occurrence of $\bar{a}$ in $u$, where $i \in [2, l(u)]$. For example, the word $u =3D a a \bar{a} \bar{a} a \bar{a} a a \bar{a} a \bar{a} \bar{a}$ is represented by the sequence $d(u) =3D 2, 0, 1, 2, 1, 0$. \medskip A sequence $d =3D (d_i)_{i \in [n]}$ \textit{dominates} another sequence $d' =3D (d'_i)_{i \in [n]}$ iff $\sum\limits_{i =3D 1}^{\nu} d_i \ge \sum\limits_{i=3D1}^{\nu} d'_i$ for every $\nu \in [n]$. In this case we = say that $d'$ is \textit{dominated} by $d$. Notice that every dominating = sequence dominates the constant sequence with elements equal to 1. \medskip The \textit{dominance partial order ``$\preceq$''} on $D$ is defined as = follows: \smallskip \centerline{$u \preceq w$ iff $l(u) =3D l(w)$ and the sequence $d(u)$ is = dominated by the sequence $d(w)$,} \smallskip \noindent i.e., the path $w$ lies above (in the broad sense) the path $u$. If $u \preceq w$ and $u \ne w$, we will write $u \prec w$. In the sequel, we will denote $(D, \preceq)$ (resp. $(D_n, \preceq)$) = with $\mathcal{D}$ (resp. $\mathcal{D}_n$). Narayana and Fulton \cite{NarayanaFulton}, using an equivalent language, = proved that the set of Grand-Dyck paths of fixed length $n$ (i.e., paths defined similarly to Dyck paths but allowed to go below the $x$-axis, e.g., see \cite{Pergola}) endowed with the dominance order is a distributive lattice. Kreweras \cite{Kreweras2, Kreweras1} has done further work in this context. Ferrari and Pinzani \cite{FerrariPinzani} have recently presented a more general approach to this subject. It is easy to see that $\mathcal{D}_n$ is a sublattice of the lattice of all Grand-Dyck paths of semilength $n$, such that if $d(w) =3D (d'_i)_{i \in [n]}$, $d(v) =3D (d''_i)_{i \in [n]}$ we have: \noindent $d(w \vee v) =3D (d_i)_{i \in [n]}$, where \centerline{ $d_1 =3D \max \{d'_1, d''_1 \}$ and $d_i =3D \max \{ = \sum\limits_{j=3D1}^{i} d'_j, \sum\limits_{j=3D1}^{i} d''_j \} - \max \{ \sum\limits_{j=3D1}^{i-1} d'_j, \sum\limits_{j=3D1}^{i-1} = d''_j\}$ for every $i \in [2,n]$\phantom{.}} \noindent and $d(w \wedge v) =3D (d_i)_{i \in [n]}$, where \centerline{$d_1 =3D \min \{d'_1, d''_1 \}$ and $d_i =3D \min \{ = \sum\limits_{j=3D1}^{i} d'_j, \sum\limits_{j=3D1}^{i} d''_j \} - \min \{ \sum\limits_{j=3D1}^{i-1} d'_j, \sum\limits_{j=3D1}^{i-1} d''_j = \}$ for every $i \in [2,n]$.} \bigskip We note that the least (resp. greatest) element of $\mathcal{D}_n$ is $0_n =3D (a\bar{a})^n$ (resp. $1_n =3D a^n \bar{a}^n$). Finally, for = every $n \ge 2$, $1_n$ covers one and only one element of $\mathcal{D}_n$, = namely $a^{n-1} \bar{a} a \bar{a}^{n-1}$. The Hasse diagram of $\mathcal{D}_4$ coded by dominating sequences is = given in Fig. \ref{fig2}. \begin{figure}[ht] \centerline{\includegraphics[height=3D3in]{fig1.eps}} \caption{The Hasse diagram of $\mathcal{D}_4$}\label{fig2} \end{figure} All unexplained notations and definitions for posets and Dyck paths can = be found in \cite{Stanley1} and \cite{Deutsch}, respectively. \section{Chains and Ranks}\label{section3} In this section we first evaluate the length of maximal chains in = intervals of $\mathcal{D}_n$. For this, notice first that for $u, w \in = \mathcal{D}_n$ with $d(u) =3D (d_i)_{i \in [n]}$ and $d(w) =3D (d'_i)_{i \in [n]}$, $w$ = covers $u$ iff there exists $j \in [n-1]$ such that $d'_i =3D d_i$ for every $i = \ne j,j+1$ and $d'_j =3D d_j+1$, $d'_{j+1} =3D d_{j+1}-1$. >From the above observation, we deduce that every path $w$ which covers the path $u$ is obtained by turning a valley $(x,y)$ of $u$ into the = peak $(x,y+2)$. \begin{prop}\label{prop1} Let $u,w \in \mathcal{D}_n$ with $u \preceq w$ and $d(u) =3D (d_i)_{i = \in [n]}$, $d(w) =3D (d'_i)_{i \in [n]}$. Then, the length of every maximal chain = $\mathcal{C}$ of $[u,w]$ is equal to \[\sum\limits_{i=3D1}^{n} i (d_i - d'_i).\] \end{prop} \noindent \textit{Proof}. We will use induction with respect to the = length $k$ of $\mathcal{C}$. If $k=3D1$ then $w$ covers $u$; so there exists $j \in = [n-1]$ with $d_i =3D d'_i$ for every $i \in [n] \setminus \{j, j+1\}$ and $d'_j = =3D d_j + 1$, $d'_{j+1} =3D d_{j+1} - 1$.=20 Hence \begin{align*}\sum\limits_{i =3D 1}^{n} i (d_i - d'_i) & =3D j (d_j - d'_j) + (j + 1) (d_{j+1} - d'_{j+1}) \\ & =3D j (-1) + (j + 1) 1 =3D 1. \end{align*} Since in this case the only maximal chain of $[u,w]$ is $\{u,w\}$ and = has length 1, the result holds when $k=3D1$. Suppose now that the result holds for every maximal chain of $[u,w]$ of length $k$, for every $u, w \in \mathcal{D}_n$ with $u \prec w$. We will prove that the result also holds for any maximal chain $\mathcal{C}$ of $[u,w]$ of length $k+1$. If $v$ is the predecessor of $w$, then $C \setminus \{w\}$ is a maximal chain of $[u, v]$ of length $k$; so by the induction hypothesis we have \[k =3D \sum\limits_{i=3D1}^n i (d_i - d''_i)\] \noindent where $d(v) =3D (d''_i)_{i \in [n]}$. Since $\sum\limits_{i=3D1}^n i (d''_i - d'_i) =3D 1$, we obtain that $\sum\limits_{i=3D1}^n i (d_i - d'_i) =3D k+1$. \hfill{$\Box$} \smallskip If we apply the previous proposition for $u =3D 0_n$ and $w =3D 1_n$ we = obtain that every maximal chain in $\mathcal{D}_n$ has length equal to ${n = (n-1)/2}$. Thus, the lattice $\mathcal{D}_n$ is graded of rank ${n \choose 2}$. In the sequel, we investigate the parameter ``rank'' of $\mathcal{D}$ = defined as follows : $\rho(\epsilon) =3D 0$ and for $u \ne \epsilon$, $\rho(u)$ is = the rank of $u$ in $\mathcal{D}_{l(u)}$. By Proposition \ref{prop1}, it follows easily that if $u \ne \epsilon$ = with $d(u) =3D (d_i)_{i \in l(u)}$, then \begin{equation}\label{eq0} \rho(u) =3D {l(u) (l(u) +1)}/{2} - \sum\limits_{i=3D1}^{l(u)} i d_i. \end{equation} Ferrari and Pinzani \cite{FerrariPinzani} give an equivalent expression = of the above relation through the notion of the area of a Dyck path.=20 Using relation \eqref{eq0} (or alternatively its equivalent relation in \cite{FerrariPinzani}), we can deduce that the parameter ``rank'' = satisfies the following properties: \\=20 \rm{i}) $\rho(wv) =3D \rho(w) + \rho(v)$, \\ \rm{ii}) $\rho(aw\bar{a}) =3D \rho(w) + l(w)$, \\ for every $w, v \in \mathcal{D}$. \medskip Taking into account the above properties and the fact that every Dyck = path is either empty or of the form $a w \bar{a} v$, where $w, v \in D$, we can easily deduce the following = relation. \begin{equation}\label{relation2} F_{\rho} (x, y) =3D 1 + x F_{\rho} = (xy, y) F_{\rho} (x,y). \end{equation} Furthermore, if $f_n (y) =3D \sum\limits_{k=3D0}^{n \choose 2} a_{n,k} = y^k$, where $a_{n,k}$ denotes the number of elements of $\mathcal{D}_n$ of = rank $k$, then by relation~\eqref{relation2} we have \begin{align*} & \sum\limits_{n=3D0}^{\infty} f_n (y) x^n =3D 1 + x\left ( = \sum\limits_{n=3D0}^{\infty} f_n (y) y^n x^n \right ) \left (\sum\limits_{n=3D0}^{\infty} f_n (y) = x^n \right ) \end{align*} \noindent or, equivalently, \begin{align*} & \sum\limits_{n=3D0}^{\infty} f_{n+1}(y) x^n =3D = \sum\limits_{n=3D0}^{\infty} \left (\sum\limits_{\nu=3D0}^{n} f_{\nu} (y) f_{n - \nu}(y) y^{\nu} = \right ) x^n. \end{align*} Hence we obtain the following result. \begin{prop} The rank-generating function of $\mathcal{D}_n$ is given by the = following recursive formula \[f_{n+1} (y) =3D \sum\limits_{\nu=3D0}^n f_{\nu}(y) f_{n - \nu} (y) = y^{\nu},\] \noindent where $f_0 (y) =3D 1$. \end{prop} \section{Fillings and Degrees}\label{section4} In this section we first introduce and study the notion of the filling = of a Dyck path. The \textit{filling} $\widetilde{u}$ of $u \in \mathcal{D} \setminus \{ = \epsilon \}$ is defined to be the Dyck path obtained by turning each valley = $(x,y)$ of $u$ into the peak $(x,y+2)$. The filling of the empty path is assumed = to be the empty path. For example, if $u =3D a a \bar{a} \bar{a} a a \bar{a} a \bar{a} = \bar{a}$ then $\widetilde{u} =3D a a \bar{a} a \bar{a} a a \bar{a} \bar{a} \bar{a}$. The main properties of the filling are given in the following = proposition, which is easy to prove. \begin{prop} For a non-empty Dyck path $u$ we have : \\ \rm{i}) $l(\widetilde{u}) =3D l(u)$, $u \preceq \widetilde{u}$ and $u =3D \widetilde{u}$ if $u =3D 1_{l(u)}$. \\ \rm{ii}) The length $l(u,\widetilde{u})$ of the interval $[u, = \widetilde{u}]$ is equal to the number $\rm{val}(u)$ of all valleys of $u$.\\ \rm{iii}) The cardinal number of the interval $[u,\widetilde{u}]$ is = equal to $2^{\rm{val}(u)}$. \\ \rm{iv}) If $u \preceq v$, then $\widetilde{u} \preceq \widetilde{v}$. \end{prop} We note that since the parameter $\rm{val}$ defined by the number of = valleys follows the Narayana distribution \cite{Deutsch}, we deduce that the = number $a_{n,k}$ of all $u \in \mathcal{D}_n$ such that the interval $[u, = \widetilde{u}]$ contains exactly $k$ elements is equal to \[a_{n,k} =3D \begin{cases} \frac{1}{n}{n \choose \lambda}{n \choose \lambda - 1}, & \textrm{if $k =3D 2^{\lambda}$, $\lambda \in \mathbb{N}^*$}; \\ 0, & \textrm{if $k \ne 2^{\lambda}$, $\lambda \in \mathbb{N}^*$}. \end{cases}\] \medskip Next, we consider the Dyck paths which are fillings of Dyck paths. For = this, we need the following characterization. \begin{prop} A Dyck path $u$ is a filling of a Dyck path iff $u$ is prime and avoids $\bar{a}\bar{a} a a$. \end{prop} \noindent \textit{Proof}. If $u =3D \widetilde{v}$ for some $v \in = \mathcal{D}$, then clearly $u$ has no valleys on level zero and so $u$ is prime. = Furthermore, if $u$ contains a $\bar{a} \bar{a} a a$, then there exists a valley $(x,y)$ = of $u$ such that the points $(x-1,y+1)$ and $(x+1,y+1)$ are a double fall and a = double rise of $u$, respectively. It follows that the points $(x,y)$, = $(x-1,y+1)$ and $(x+1,y+1)$ remain unchanged during the generation of $u$ from $v$, so = that $(x,y)$ is also a valley of $v$. This contradicts the definition of the = filling, since $(x,y+2)$ is not a peak of $u$. Conversely, assume that $u$ is prime and avoids $\bar{a} \bar{a} aa$.=20 Let $v$ be the path that we obtain from $u$ by turning each peak $(x,y)$ = of $u$ into the valley $(x,y-2)$. Clearly, since $u$ is prime it has no low = peaks, hence $v$ never crosses the $x$-axis and so $v \in \mathcal{D}$. In = order to show that $\widetilde{v} =3D u$, it is enough to show that every valley = of $v$ is generated by a peak of $u$ according to the above procedure. Indeed, if = this is not true and $(x,y)$ is a valley of $v$ that is not generated in such = a way, then $(x,y)$ must be a valley of $u$, too. Since $u$ avoids $\bar{a} \bar{a} a a$, it follows that at least one of = the points $(x-1,y+1)$ and $(x+1,y+1)$ is a peak of $u$ and hence a valley = of $v$, which contradicts the fact that $(x,y)$ is a valley of $v$. = \hfill{$\Box$} \medskip We remark that the Dyck path $v$ constructed by turning each peak of a = Dyck path $u$ into a valley as in the converse of the above proof, is the = least Dyck path with the property $\widetilde{v} =3D u$. In this case, we say that = $v$ is the \textit{antifilling} of $u$. In the following, we study the set $\mathcal{\widetilde{D}}$ of all Dyck = paths that are fillings of Dyck paths. \begin{prop} The generating function $F$ of $\mathcal{\widetilde{D}}$ according to=20 semilength satisfies the equation \begin{equation}\label{eq1} F(x) =3D 1 + x F^2(x) - x^2 = F(x).\end{equation} \noindent Furthermore, the number $a_n$ of all Dyck paths of semilength = $n$ that are fillings of Dyck paths is given by the formula \begin{equation}\label{equation4} a_n =3D \sum\limits_{k=3D[n/2]}^n = \frac{(-1)^{n-k}}{k} {k \choose n-k}{3k-n \choose k-1}, \textit{ for } n \ge 2 \end{equation} \noindent whereas $a_0 =3D a_1 =3D 1$. \end{prop} \noindent \textit{Proof}. Let $\mathcal{A}$ be the set of all Dyck paths = that avoid $\bar{a} \bar{a} a a$ and $A(x)$ its generating function according = to semilength. Clearly, by the previous proposition, every non-empty element of $\mathcal{\widetilde{D}}$ can be written uniquely in the form $a w = \bar{a}$ where $w \in \mathcal{A}$, so that $F(x) =3D 1 + xA(x)$. Furthermore, we can easily check that every non-empty element $u \in = \mathcal{A}$ can be written uniquely in one of the following forms: $u =3D a \bar{a} = v$, $u =3D a w \bar{a}$ or $u =3D a w \bar{a} a \bar{a} v$ where $w, v \in = \mathcal{A}$ and $w \ne \epsilon$. Thus, we have: \begin{align*} A(x) & =3D 1 + x A(x) + x (A(x)-1) + x^2 (A(x) -1)A(x). \end{align*} So \[x^2 A^2(x) - (x-1)^2 A(x) + 1 - x =3D 0\] \noindent and hence \[ xF^2(x) - (1+x^2) F(x) + 1 =3D 0 \] \noindent which gives formula \eqref{eq1}. For the proof of formula \eqref{equation4} we consider the generating function $F(x,y)$ satisfying the equation \begin{equation}\label{equation5} F(x,y) =3D 1 + y (x F^2(x,y) - x^2 = F(x,y)). \end{equation} If we set $P(\lambda) =3D x \lambda^2 - x^2 \lambda$, then $F(x,y) =3D 1 = + y P(F(x,y))$; so applying the Lagrange inversion formula with respect to the variable = $y$, in the form given by Deutsch \cite{Deutsch}, we obtain that \begin{equation}\label{equation6} [y^k] F =3D \frac{1}{k} = [\lambda^{k-1}](P(1+\lambda))^k \end{equation} \noindent for every $k \in \mathbb{N}^*$. Furthermore, we have \begin{align*} (P(1+\lambda))^k & =3D x^k \sum\limits_{\nu=3D0}^k = \sum\limits_{\rho=3D0}^k {k \choose \nu}{k \choose \rho} \lambda^{\nu} = (\lambda -x)^{\rho} \\ & =3D \sum\limits_{\nu=3D0}^k \sum\limits_{\rho=3D0}^k = \sum\limits_{i=3D0}^{\rho} (-1)^{\rho-i} {k \choose \nu} {k \choose \rho} {\rho \choose i} \lambda^{\nu +i} x^{k + \rho - i}. \end{align*} Then, for $i =3D k - \nu -1$, from relation \eqref{equation6} we obtain = that \[ [y^k] F =3D \frac{1}{k} \sum\limits_{\rho =3D 0}^k = \sum\limits_{\nu=3D0}^{k-1} (-1)^{\rho-k+\nu+1} {k \choose \nu}{k = \choose \rho} {\rho \choose k - \nu -1} x^{\rho + \nu +1}. \] Thus, \begin{align*} F(x,y) & =3D 1 + \sum\limits_{k=3D1}^{\infty} \sum\limits_{\rho=3D0}^{k} = \sum\limits_{\nu =3D0}^{k-1} (-1)^{\rho-k+\nu+1} \frac{1}{k} {k \choose \nu} {k \choose \rho} {\rho \choose k - \nu -1} = x^{\rho+\nu +1} y^k \\ & =3D 1 + xy + \sum\limits_{n=3D2}^{\infty} \sum\limits_{k =3D [n = / 2]}^n \sum\limits_{\nu =3D0}^{k-1} (-1)^{n-k} \frac{1}{k} {k \choose \nu} {k \choose n - \nu - 1}{n - \nu - 1 \choose k - = \nu -1} x^n y^k \\ & =3D 1 + xy + \sum\limits_{n=3D2}^{\infty} \sum\limits_{k =3D [n = / 2]}^n (-1)^{n-k} \frac{1}{k} {k \choose n -k}{3k -n \choose k-1} x^n y^k. \end{align*} Thus, since by relations \eqref{eq1} and \eqref{equation5} we have $F(x) = =3D F(x,1)$, it follows that \[ a_0 =3D a_1 =3D 1 \textrm{ and } a_n =3D \sum\limits_{k =3D [n/2]}^n = (-1)^{n-k} \frac{1}{k} {k \choose n -k}{3k - n \choose k-1}, \textrm{ for $n \ge 2$. } \] $\enspace$\\[-48pt] \hfill{$\Box$} \bigskip By formula \eqref{equation4} by obtain the sequence 1,1,1,2,5,13,35,97,275,\ldots, which also counts the number of Dyck = paths that avoid $a a \bar{a} \bar{a}$ (\seqnum{A086581} of \cite{Sloane}). This can also be seen by proving that the set of all antifillings = coincides with the set of all Dyck paths that avoid $a a \bar{a} \bar{a}$. \medskip The rest of this section deals with the notion of the degree of a Dyck = path. For this, we define the $i^{\rm th}$ filling $u^{(i)}$ of a non-empty = Dyck path $u$ recursively, as follows: \centerline{$u^{(0)} =3D u$ and $u^{(i)} =3D \widetilde{u^{(i-1)}}$, for = $i \ge 1$.} We define the \textit{degree} $\delta(u)$ of $u \in \mathcal{D} = \setminus \{ \epsilon \}$ to be the least non-negative integer such that $u^{(\delta(u))} =3D 1_{l(u)}$. The degree of the empty path is assumed to be equal to zero. For example, if $u =3D a a \bar{a} \bar{a} a a \bar{a} a \bar{a} = \bar{a}$ then $\delta(u) =3D 4$. \medskip The main properties of the degree are given in the following result. \begin{prop}\label{prop4.5} For every non-empty Dyck path $u$ we have: \\ \rm{i}) $\delta(\widetilde{u}) =3D \delta(u) - 1$, for every $u \ne = 1_{l(u)}$. \\ \rm{ii}) $\delta(au\bar{a}) =3D \delta(u)$. \\ \rm{iii}) $0 \le \delta(u) \le l(u) - 1$, and $\delta(u) =3D l(u) -1$ = iff $u$ is non-prime. \\ \rm{iv}) If $u \prec v$, then $\delta(v) \le \delta(u)$. \end{prop} \noindent \textit{Proof}. i) is obvious, whereas ii) is based on the equality $(a w \bar{a})^{(i)} =3D a w^{(i)} \bar{a}$, for every $i \in \mathbb{N}$. For the proof of iii) we first show by induction with respect to the = semilength of $u$ that if $u$ is non-prime then $\delta(u) =3D l(u) -1$. Indeed, if $l(u) =3D2$, then $u =3D a \bar{a} a \bar{a}$ and $\delta(u) = =3D 1 =3D l(u) - 1$. Assume that the result holds for every non-prime Dyck path with = semilength equal to $n-1$, where $n \ge 3$, and let $u$ be a non-prime path of semilength = $n$. Then, using the prime decomposition of $u$, there exists a finite = sequence $(w_i)_{i \in [k]}$, $k \ge 2$, of Dyck words such that \centerline{$u =3D a w_1 \bar{a} a w_2 \bar{a} a \cdots \bar{a} a = w_{k-1} \bar{a} a w_k \bar{a}$.} It follows easily that \centerline{$\widetilde{u} =3D a \widetilde{w}_i a \bar{a} \widetilde{w}_2 a \bar{a} \cdots a \bar{a} \widetilde{w}_{k-1} a \bar{a} \widetilde{w}_k \bar{a}$.} If we set \centerline{$z =3D \widetilde{w}_i a \bar{a} \widetilde{w}_2 a \bar{a} = \cdots a \bar{a} \widetilde{w}_{k-1} a \bar{a} \widetilde{w}_k$,} \noindent then $z \in \mathcal{D}$, $l(z) =3D n-1$, $\widetilde{u} =3D a z \bar{a}$ and z is non-prime. = Thus, by the induction hypothesis we have $\delta(z) =3D l(z) - 1$ and so \centerline{$\delta(u) =3D \delta(\widetilde{u}) + 1 =3D \delta(z) + 1 = =3D l(z) =3D l(u) -1$.} Next, we note that $0 \le \delta(u)$ and $\delta(u) =3D 0$ iff $u =3D 1_{l(u)}$. Furthermore, if $u \ne 1_{l(u)}$, there exists $\nu \in \mathbb{N}$ such that $u =3D a^{\nu} w \bar{a}^{\nu}$, where w is a non-prime Dyck path. Then, by ii) we deduce that \centerline{$\delta(u) =3D \delta(w) =3D l(w) - 1 \le l(u) - 1$.} It remains to check that $\delta(u) < l(u) -1$ for every prime Dyck path = $u$. Indeed, $u =3D aw\bar{a}$ with $w \in \mathcal{D}$, so that $\delta(u) =3D \delta(w) \le l(w) - 1 =3D l(u) - 2$. Finally, we show iv) using induction with respect to the semilength of = $u$. It is clear that the result is true when $l(u) =3D 1$. Assuming that the = result holds for Dyck paths of semilength $n-1$, where $n \ge 2$, we will show = that if $u, v \in \mathcal{D}_n$ with $u \prec v$ then $\delta(v) \le = \delta(u)$. Clearly, by iii), it is enough to restrict ourselves to the case where $u$ is a prime word. Thus, if $u =3D a u' \bar{a}$ where $u' \in = \mathcal{D}_{n-1}$, it follows easily that $v =3D a v' \bar{a}$, where $v' \in = \mathcal{D}_{n-1}$ and $u' \prec v'$. From the induction hypothesis it follows that = $\delta(v) =3D \delta(v') \le \delta(u') =3D \delta(u)$. \hfill{$\Box$} \bigskip We conclude this section with the following result. \begin{prop} The number of all $u \in \mathcal{D}_{n}$, $n \ge 2$, with degree equal = to $k$, where \mbox{$k \in [n - 1]$}, is equal to $C_{k+1} - C_k$. \end{prop} \noindent \textit{Proof}. Clearly, since every non-empty Dyck path $u$ = can be written uniquely in either of the forms $u =3D a w \bar{a}$ or $u =3D a w \bar{a} v$, where $w, v \in \mathcal{D}$ and $v \ne = \epsilon$, applying Proposition \ref{prop4.5} we obtain that \begin{align*} F_{\delta}(x,y) & =3D 1 + x F_{\delta}(x,y) + x C(xy) (C(xy) - 1). \end{align*} It follows that \begin{align*} F_{\delta}(x,y) & =3D \frac{1 + y^{-1} \sum\limits_{n=3D1}^{\infty} C_n (xy)^n - = x \sum\limits_{n=3D0}^{\infty} C_n (xy)^n}{1 - x} \\ & =3D \frac{1 + \sum\limits_{n=3D1}^{\infty} \left (C_n - C_{n-1} = \right ) y^{n-1} x^n}{1 - x} \\ & =3D \left (\sum\limits_{n=3D0}^{\infty} g_n (y) x^n \right ) = \left (\sum\limits_{n=3D0}^{\infty} x^n\right), \end{align*} \noindent where \[g_n(y) =3D \begin{cases} \left(C_{n} - C_{n-1} \right ) y^{n-1}, & \textrm{if $n \ge = 1$}; \\ 1, & \textrm{if $n =3D 0$.} \end{cases}\] Therefore, we have \begin{align*} F_{\delta}(x,y) & =3D \sum\limits_{n=3D0}^{\infty} = \sum\limits_{k=3D0}^n g_k(y) x^n \\ & =3D \sum\limits_{n=3D0}^{\infty} x^n + \sum\limits_{n=3D2}^{\infty} \sum\limits_{k=3D1}^{n-1} (C_{k+1} - C_k) y^k x^n, \end{align*} \noindent which gives the required result. \hfill{$\Box$} \section{The M\"obius function}\label{section5} In this section we study the M\"obius function of $\mathcal{D}$ and its powers. We recall \cite{Stanley1} that the M\"obius function $\mu$ of a = poset $(P, \preceq)$ is defined by \[\mu(x,y) =3D - \sum\limits_{x \preceq z \prec y} \mu(x,z) \textrm{ for = $x \prec y$ and $\mu(x,x) =3D 1$}.\] Furthermore, the $k$-th power of $\mu$, for $k \ge 2$, is defined by \[\mu^k(x,y) =3D \sum\limits_{x=3Dx_0 \preceq x_1 \preceq \cdots \preceq x_k =3Dy} \mu(x_0,x_1) \mu(x_1,x_2) \cdots \mu(x_{k-1},x_k).\] It is known \cite{BarnabeiPezzoli} that if $(P, \preceq)$ is a locally = finite distributive lattice, then its M\"obius function is given by the formula \[ \mu(x,y) =3D \begin{cases} (-1)^{\nu}, & \textrm{if $y$ is a join of = $\nu$ elements covering $x$}; \\ 0, & \textrm{if $y$ is not a join of elements = covering $x$.} \end{cases} \] For the lattice of Dyck paths, we have that $v \in (u, \widetilde{u}]$ = with $l(u,v) =3D \nu$ iff $v$ is obtained by turning $\nu$ of the valleys of = $u$ into peaks or, equivalently, iff $v$ is a join of $\nu$ elements of $D$ = covering $u$. Thus, from the above formula we obtain the following result.=20 \begin{prop}\label{prop5.1} The M\"obius function of $\mathcal{D}$ is given by the formula \[\mu(u,v) =3D \begin{cases} (-1)^{l(u,v)}, & \textrm{if $u \preceq v \preceq = \widetilde{u}$}; \\ 0, & \textrm{otherwise} \end{cases}\] \noindent for every $u, v \in \mathcal{D}$, where $l(u,v)$ denotes the length of the interval $[u,v]$. \end{prop} In the sequel we study the powers of the M\"obius function of = $\mathcal{D}_n$. For this, we need the following result, which is an easy consequence of Proposition \ref{prop5.1}. \begin{cor}\label{lemma5.2} For every multichain $u_0 \preceq u_1 \preceq \cdots \preceq u_k$ in $\mathcal{D}_n$ with \centerline{$\mu(u_0, u_1) \mu(u_1, u_2) \cdots \mu(u_{k-1},u_k) \ne 0$} \noindent we have $u_i \preceq \widetilde{u_{i-1}}$ and $u_i \preceq u_0^i$ for every $i \in [k]$. \end{cor} Clearly, if $u \in \mathcal{D}_n$ and $k < \delta(u)$, for every = multichain $u =3D u_0 \preceq u_1 \preceq \cdots \preceq u_k =3D 1_n$ we have that $u^{(k)} \prec u_k$ so that, by the above Corollary, we deduce that \centerline{$\mu(u_0, u_1) \mu(u_1, u_2) \cdots \mu(u_{k-1},u_k) =3D = 0$.} This shows that $\mu^{k}(u,1_n) =3D 0$ for every $k < \delta(u)$. \medskip In the following result we consider the case where $k =3D \delta(u)$. \begin{prop} Let $u \in \mathcal{D}_n$ and $j, \nu \in \mathbb{N}^*$ such that $u^{(j)} =3D 0_{l(u)}^{\nu}$. Then, we have that \[\mu^{\delta(u)}(u,1_{n}) =3D (-1)^{l(u^{(j)}, 1_{n})} \mu^j(u, = u^{(j)}).\] \end{prop} \noindent \textit{Proof}. Let $u =3D u_0 \preceq u_1 \preceq \cdots \preceq u_{\delta(u)} =3D = 1_{n}$ be a multichain of $\mathcal{D}_n$ with \centerline{$\mu(u_0, u_1) \mu(u_1, u_2) \cdots \mu(u_{\delta(u)-1}, = u_{\delta(u)}) \ne 0$;} \noindent then, by Corollary \ref{lemma5.2} it follows that $u_i \preceq \widetilde{u_{i-1}}$ and $u_i \preceq = u^{(i)}$ for every $i \in [\delta(u)]$. We show that $u_i =3D u^{(i)}$ for every $i = \ge j$. Indeed, if this is not true, let $\xi$ be the greatest element of $[j, = \delta(u)]$ such that $u_{\xi} \prec u^{(\xi)}$. Clearly, since $u_{\delta(u)} =3D 1_{l(u)} =3D u^{(\delta(u))}$, we have = that $\xi < \delta(u)$. Since $u^{(\xi+1)} =3D u_{\xi+1} \preceq \widetilde{u_{\xi}} \preceq = u^{(\xi+1)}$, we obtain that $u^{(\xi+1)} =3D \widetilde{u_{\xi}}$. Furthermore, since $u^{(\xi)} =3D 0_{n}^{(\nu+\xi-j)}$, $u^{(\xi+1)} =3D 0_{n}^{(\nu+\xi-j+1)}$ and the antifilling of $0^{(k+1)}_n$ is = $0^{(k)}_n$ for every $k \in [n-2]$, we obtain that $u^{(\xi)}$ is the antifilling of $u^{(\xi+1)}$, though $\widetilde{u_{\xi}} =3D u^{(\xi+1)}$ and $u_{\xi} \prec u^{(\xi)}$, = which is a contradiction. Thus, $u_i =3D u^{(i)}$ for every $i \ge j$. It follows that \bigskip \centerline{$ \mu^{\delta(u)}(u,1_{n}) =3D \sum \mu(u_0, u_1) \mu(u_1, u_2) \cdots \mu(u_{j-1},\! u^{(j)}) \mu(u^{(j)},\! u^{(j+1)}) \mu(u^{(j+1)},\! = u^{(j+2)}) \cdots \mu(u^{(\delta(u)-1)},\! u^{(\delta(u))}) $} \bigskip \noindent where the sum is taken over all multichains $u =3D u_0 \preceq = u_1 \preceq \cdots u_j =3D u^{(j)}$ of $\mathcal{D}_n$. Since, by Proposition \ref{prop5.1}, we have \begin{align*} & \mu(u^{(j)}, u^{(j+1)}) \mu(u^{(j+1)}, u^{(j+2)}) \cdots = \mu(u^{(\delta(u)-1)}, u^{(\delta(u))}) \\ & \qquad \qquad \qquad =3D (-1)^{l(u^{(j)}, u^{(j+1)})} = (-1)^{l(u^{(j+1)}, u^{(j+2)})} \cdots (-1)^{l(u^{(\delta(u)-1)}, u^{(\delta(u))})} \\ & \qquad \qquad \qquad =3D (-1)^{l(u^{(j)}, 1_{n})}, \end{align*} \noindent we deduce that \[\mu^{\delta(u)}(u,1_{n}) =3D (-1)^{l(u^{(j)}, 1_{n})} \mu^j(u, = u^{(j)}).\] $\enspace$\\[-48pt] \hfill{$\Box$} \medskip \bigskip \noindent \textbf{Remark} Let $\mathcal{N}$ be the set of all non-empty Dyck paths $u$ such that $\widetilde{u} =3D0^{\nu}_{l(u)}$ for some $\nu \in \mathbb{N}^*$. Then, taking $j =3D1$ in the previous proposition, we obtain that \begin{align*} \mu^{\delta(u)}(u,1_{l(u)}) & =3D (-1)^{l(\widetilde{u}, 1_{l(u)})} \mu(u, \widetilde{u}) = \\ & =3D (-1)^{l(\widetilde{u}, 1_{l(u)})} (-1)^{l(u, = \widetilde{u})} \\ & =3D (-1)^{l(u, 1_{l(u)})} \end{align*} \noindent for every $u \in \mathcal{N}$. In particular if $u =3D0_n$ for some $n \in \mathbb{N}^*$, we have that $\delta(u) =3D n-1$ and \[\mu^{n-1} (0_n, 1_n) =3D (-1)^{n \choose 2}.\] Thus, by Lemma 4.1 in \cite{Edelman} we deduce that the zeta polynomial = of $\mathcal{D}_n$ satisfies the following formula \[Z(\mathcal{D}_n, -k) =3D \begin{cases} (-1)^{{n \choose 2}}, & = \textrm{if $k =3D n -1$}; \\ 0, & \textrm{if $1 \le k < n -1$.} \end{cases} \] \bigskip We close this section by enumerating the sets $\mathcal{N} \cap = \mathcal{D}_n$. For this, we consider the set \[\mathcal{N}_{\nu,n} =3D \{ u \in \mathcal{D}_n : \widetilde{u} =3D = 0_n^{\nu} \}\] \noindent where $\nu \in \mathbb{N}^*$ and $\nu \le n -1$. Clearly, for every $p \in \mathbb{N}^*$, by considering the bijection $u \to a^p u \bar{a}^p$ we can deduce that \begin{equation}\label{eq2}|\mathcal{N}_{\nu,n}| =3D = |\mathcal{N}_{\nu+p,n+p}|\end{equation} \noindent for every $p \in \mathbb{N}^*$. Furthermore, we have the following result. \begin{prop} For every $\nu \in \mathbb{N}^*$, the sequence $(\mathcal{N}_{\nu,n})$, $n \ge \nu +1$ satisfies the following relation \[|\mathcal{N}_{\nu,n}| =3D F_{n-\nu+2},\] \noindent where $(F_n)$ denotes the Fibonacci sequence. \end{prop} \noindent \textit{Proof}. In view of relation \eqref{eq2} it is enough = to show that \[|\mathcal{N}_{1,n}| =3D F_{n+1}\] \noindent for every $n \ge 2$. Clearly, since $|\mathcal{N}_{1,2}| =3D 2$ and $|\mathcal{N}_{1,3}| =3D = 3$, it is enough to show that \[|\mathcal{N}_{1,n}| =3D |\mathcal{N}_{1,n-1}| + = |\mathcal{N}_{1,n-2}|\] \noindent for every $n \ge 4$. Every element of $\mathcal{N}_{1,n}$ is obtained by turning some peaks = of $\widetilde{0}_n$ into valleys. However, in this procedure for the = generation of the elements of $\mathcal{N}_{1,n}$ we must turn at least one of each = pair of consecutive peaks into valleys. Thus, if $A_1$ (resp. $A_2$) is the set that consists of all elements of $\mathcal{N}_{1,n}$ that pass from the point $(2,0)$ (resp. $(2,2)$), = then $\{A_1, A_2\}$ is a partition of $\mathcal{N}_{1,n}$. Clearly, $A_1 =3D \mathcal{N}_{1,n-1}$ and since the elements of $A_2$ = must pass from the point $(4,0)$, we have $A_2 =3D \mathcal{N}_{1,n-2}$, which = gives the required result. \hfill{$\Box$} \medskip We note that using the previous proposition, we obtain by a simple = summation that $|\mathcal{N} \cap \mathcal{D}_n| =3D F_{n+3} - 3$, = (\seqnum{A006327} of \cite{Sloane}).=20 \section{Dyck paths and permutations}\label{section6} We recall that a simple reduction of a permutation $\pi =3D \pi(1)\pi(2)\cdots\pi(n)$ is a permutation obtained from $\pi$ = by interchanging some $\pi(i)$ with $\pi(i+1)$, provided that $\pi(i) > = \pi(i+1)$. The weak Bruhat order $\ltimes$ is defined on the symmetric group $S_n$ = as follows: \centerline{$\sigma \ltimes \pi$ iff $\sigma$ can be obtained from $\pi$ = by a sequence of simple reductions.} The poset $(S_n, \ltimes)$ is a well known distributive lattice, graded = of rank ${n \choose 2}$ and has many interesting properties \cite{EdelmanGreene,Stanley3}. In the = following, we examine the connection between the lattices $(S_n, \ltimes)$ and $(D_n, \preceq)$. For this, we first define the set $\mathcal{L}_n$ of all finite = sequences $(A_i)_{i \in [n]}$ of pairwise disjoint subsets of $[n]$ such that $[\nu] \subseteq = \bigcup\limits_{i=3D1}^{\nu} A_i$ for every $\nu \in [n]$ and $\bigcup\limits_{i=3D1}^n A_i =3D [n]$. For example, $\mathcal{L}_3 =3D \{ \left(\{1\},\{2\},\{3\}\right), = \left(\{1\},\{2,3\},\emptyset \right), \left(\{1,2\},\emptyset,\{3\}\right)$, $\enspace \qquad \qquad \qquad \qquad \!\!\!\quad = \left(\{1,2\},\{3\},\emptyset\right), \left(\{1,3\}, \{2\}, = \emptyset\right)$, $\left(\{1,2,3\}, \emptyset, \emptyset\right)\}$. We will show that the sets $S_n$ and $\mathcal{L}_n$ can be identified. Indeed, for $\sigma \in S_n$ and $i \in [n]$ we define $A_i^{\sigma}$ to = be the set of all elements $j \in [n]$ for which there exist exactly $i-1$ elements of $\sigma$, which are less than $j$ and lie on the left of $j$ = in $\sigma$. We can easily check that the sequence $(A_i^{\sigma})_{i \in [n]}$ = belongs to $\mathcal{L}_n$. Conversely, if $(A_i)_{i \in [n]} \in \mathcal{L}_n$ then there exists = unique $\sigma \in S_n$ such that $A_i^{\sigma} =3D A_i$ for every $i \in [n]$. For the construction of $\sigma$ we define recursively a finite sequence $(\sigma_j)_{j \in [n]}$, such that $\sigma_j \in S_j$ and for $j > 1$ = with $j \in A_i$ where $i \in [n]$, $\sigma_j$ is generated from = $\sigma_{j-1}$ by inserting $j$ before the $i^{\rm th}$ element of $\sigma_{j-1}$ if $i < = j$, or by placing $j$ at the end of $\sigma_{j-1}$ if $i =3D j$. Then, for $\sigma = =3D \sigma_n$ we have $A_i^{\sigma} =3D A_i$ for each $i \in [n]$. \medskip >From the above discussion we have the following result. \begin{prop}\label{prop6.1} The mapping $\sigma \to (A_i^{\sigma})_{i \in [n]}$ is a bijection = between the sets $S_n$ and $\mathcal{L}_n$. \end{prop} \noindent \textbf{Remark}. Using the above bijection we can characterize = the set of=20 all permutations of $S_n(312)$ (i.e. the ones avoiding the pattern 312) = as follows:=20 $\sigma \in S_n(132)$ iff for every $j, k \in [n]$ with $j \in = A_i^{\sigma}$, $k \in A_l^{\sigma}$ and $i < l$ we have that $j < k$. =20 Indeed, assume that $\sigma \in S_n(312)$ and $j, k \in [n]$ with $j \in A_i^{\sigma}$, $k \in A_l^{\sigma}$, $i < l$ and $j > k$. Since $i < l$, = we have that $j$ lies on the left of $k$ and there exists some element $m$ which is less that $k$ and lies between them in $\sigma$. Then, the = triplet=20 $jmk$ is an appearance of the pattern $312$ in $\sigma$, which is a = contradiction. Conversely, assume that the sequence $(A_i^{\sigma})_{i \in [n]}$ = satisfies the above condition though $\sigma$ contains the pattern $312$. Let $jmk$ be the = first appearance of the pattern $312$ in $\sigma$, with $j \in A_i^{\sigma}$ = and $k \in A_l^{\sigma}$. It follows that each element lying on the left of $j$ = in $\sigma$ that is less than $j$ is also less than $k$. Thus, $i < l$ = although $j > k$,=20 which is a contradiction. \smallskip >From the above remark it follows that if $\sigma \in S_n(312)$, then=20 every non-empty $A_i^{\sigma}$ consists of consecutive integers. \bigskip Next, we consider the family of sets $(\Gamma_u)_{u \in \mathcal{D}_n}$, = where \[ \Gamma_u =3D \{ \sigma \in S_n : d(u) =3D (|A_i^{\sigma}|)_{i \in = [n]} \}.\] \begin{prop}\label{prop6.2} The family $(\Gamma_u)_{u \in \mathcal{D}_n}$ is a partition of $S_n$ = such that if $\sigma \in \Gamma_u$, $\pi \in \Gamma_w$ and $\pi$ covers $\sigma$, = then $w$ covers $u$. \end{prop} \noindent \textit{Proof}. We first show that $\Gamma_u \ne \emptyset$, for every $u \in = \mathcal{D}_n$. Indeed, if $d(u) =3D (d_i)_{i \in [n]}$, set $A_1 =3D [d_1]$ and for $i = > 1$, $A_i =3D \emptyset$ iff $d_i =3D 0$ and $A_i =3D [\sum\limits_{j=3D1}^{i-1} d_j + 1, \sum\limits_{j=3D1}^i d_j]$ = iff $d_i \ne 0$. It follows that the sequence $(A_i)_{i \in [n]}$ belongs to = $\mathcal{L}_n$ and $|A_i| =3D d_i$ for every $i \in [n]$, so that by Proposition = \ref{prop6.1} there exists $\sigma \in S_n$ such that $d(u) =3D (|A_i^{\sigma}|)_{i = \in [n]}$ and $\sigma \in \Gamma_u$. Next, if $\sigma \in S_n$, since the sequence $(A_i^{\sigma})_{i \in = [n]}$ belongs to $\mathcal{L}_n$, it follows that $(|A_i^{\sigma}|)_{i \in = [n]}$ is a dominating sequence, so that there exists unique $u \in \mathcal{D}_n$ = such that $d(u) =3D (|A_i^{\sigma}|)_{i \in [n]}$ and hence $\sigma \in \Gamma_u$. This shows that $\bigcup\limits_{u \in \mathcal{D}_n} \Gamma_u =3D S_n$, = and since the sets $\Gamma_{u}$ are pairwise disjoint, the family $(\Gamma_u)_{u \in \mathcal{D}_n}$ is a partition of $S_n$. Finally, since $\pi$ covers $\sigma$, there exists unique $k \in [n-1]$ = such that=20 \centerline{$\sigma(j) =3D \pi(j)$ for every $j \in [n] \setminus = \{k,k+1\}$ and=20 $\sigma(k) =3D \pi(k+1) < \pi(k) =3D \sigma(k+1)$.}=20 Then, if $\pi(k) \in A_{\nu}^{\pi}$ we have that=20 \centerline{$\pi(k) \in A_{\nu+1}^{\sigma}$, $A_i^{\pi} =3D = A_i^{\sigma}$ for every $i \in [n] \setminus \{\nu,\nu+1\}$, $A_{\nu}^{\pi} =3D A_{\nu}^{\sigma} \cup = \{\pi(k)\}$,=20 $A_{\nu+1}^{\pi} =3D A_{\nu+1}^{\sigma} \setminus \{\pi(k)\}$.} Thus, since $d(u) =3D (|A_i^{\sigma}|)_{i \in [n]}$, $d(w) =3D (|A_i^{\pi}|)_{i \in [n]}$, $|A_i^{\pi}| =3D |A_i^{\sigma}|$ = for every $i \in [n] \!\setminus\! \{\nu, \nu+1\}$, $|A_{\nu}^{\pi}| =3D = |A_{\nu}^{\sigma}| + 1$, and $|A_{\nu+1}^{\pi}| =3D |A_{\nu+1}^{\sigma}| -1$, we deduce that=20 $w$ covers $u$. \hfill{$\Box$} \medskip \noindent \textbf{Remarks} \\ {\bf 1.} By Proposition \ref{prop6.2} it follows easily that if $\sigma \in \Gamma_u$ and $\pi \in \Gamma_w$ with $\sigma = \ltimes \pi$, then $u \preceq w$. \\ {\bf 2.} Since $\Gamma_{0_n} =3D \{\hat{0}_n\}$ and $\Gamma_{1_n} =3D = \{\hat{1}_n\}$ where $\hat{0}_n$ and $\hat{1}_n$ are the least and greatest element of $S_n$ respectively, by Proposition \ref{prop6.2} it follows that for $u \in \mathcal{D}_n$ we have \centerline{$\rho(\sigma) =3D \rho(u)$ for every $\sigma \in \Gamma_u$,} \noindent where $\rho$ denotes the rank function. \\ {\bf 3.} Following the first part of proof of Proposition \ref{prop6.2} = we realize that the sequence $(A_i^{\sigma})_{i \in [n]}$ constructed for every $u \in = \mathcal{D}_n$ satisfies the conditions of the previous remark and hence $\sigma \in S_n(312)$. Since = the number of permutations of $S_n(312)$ is equal to $C_n$, we deduce that each $\Gamma_u$ contains exactly one element of $S_n(312)$. Thus, we can define a bijection $f$ from $S_n(312)$ to $D_n$, such that = $f(\sigma) =3D u$ iff $\sigma \in \Gamma_u$.=20 This bijection has been also presented in different ways in \cite{BK}, = \cite{BBFP} and \cite{Fulmek}. \medskip In the following, we will evaluate the cardinal number of $\Gamma_u$ for = a Dyck path $u \in \mathcal{D}_n$ with $n \ge 2$. For this we need to consider = the Dyck path $u' \in \mathcal{D}_{n-1}$=20 obtained from the path $u =3D a^{\nu} \bar{a} \tau \in \mathcal{D}_n$ if = we delete its first peak,=20 i.e., the path $u' =3D a^{\nu-1} \tau$.=20 \begin{lemma}\label{lemma6.3} For every $u \in \mathcal{D}_n$ with $d(u) =3D (d_i)_{i \in [n]}$ and $d(u') =3D (d_i')_{i \in [n-1]}$, we have \[ d'_1 =3D d_1 + d_2 -1, d'_i =3D d_{i+1} \textrm{ for every } i \in = [2,n-1] \] \noindent and \begin{equation}\label{eq3} |\Gamma_u| =3D {d_1 + d_2 -1 \choose d_2} |\Gamma_{u'}|. \end{equation} \end{lemma} \noindent \textit{Proof}. Clearly, the proof of the first part of this = lemma is evident. So we restrict ourselves to the proof of relation \eqref{eq3}. For $\sigma' \in \Gamma_{u'}$ and a subset $B \subseteq A_1^{\sigma'}$ = with $|B| =3Dd_2$, we consider the finite sequence $(A_i)_{i \in [n]}$ = defined as follows : $A_1 =3D \{1\} \cup \{x : x-1 \in A_1^{\sigma'} \setminus B\}$, $A_2 =3D \{x : x -1 \in B\}$ and $A_i =3D \{x : x -1 \in = A_{i-1}^{\sigma'}\}$ for $i \ge 3$. Then, since $(A_i^{\sigma})_{i \in [n-1]} \in \mathcal{L}_{n-1}$, by the previous construction it follows that $(A_i)_{i \in [n]} \in = \mathcal{L}_n$, so that by Proposition \ref{prop6.1} there exists unique $\sigma \in = S_n$ such that=20 $A_1^{\sigma} =3D \{1\} \cup \{x : x -1 \in A_1^{\sigma'} \setminus B = \}$, $A_2^{\sigma} =3D \{x : x - 1 \in B\}$ and $A_i^{\sigma} =3D \{x : x -1 \in A_{i-1}^{\sigma'}\}$. So $|A_1^{\sigma}| =3D 1 + (|A_1^{\sigma'}| \setminus |B|) =3D d_1$, $|A_2^{\sigma}| =3D |B| =3D d_2$ and $|A_i^{\sigma}| =3D |A_{i-1}^{\sigma'}| =3D d'_{i-1} =3D d_i$ for every = $i \ge 3$. Thus, $d(u) =3D (|A_i^{\sigma}|)_{i \in [n]}$ and $\sigma \in \Gamma_u$. Moreover, we will show that every $\sigma \in \Gamma_u$ is generated by a unique pair $(\sigma', B)$ as above. Indeed, given $\sigma \in \Gamma_u$ we consider the sequence $(A'_i)_{i = \in [n-1]}$=20 of sets in $[n-1]$ defined by=20 \[ A_1' =3D \{ x : x + 1 \in A_1^{\sigma} \cup A_2^{\sigma} \}, \enspace = A_i' =3D \{ x : x+1 \in A_{i+1}^{\sigma} \}, \] \noindent as well as the set=20 \[ B =3D \{ x : x + 1 \in A_2^{\sigma} \} \subseteq A_1'. \] Then, $(A_i') \in \mathcal{L}_{n-1}$ and so by Proposition \ref{prop6.1} = there exists a unique $\sigma' \in S_{n-1}$ such that $A_i' =3D A_i^{\sigma'}$ for every $i \in [n-1]$. It follows that = $\sigma' \in \Gamma_{u'}$ and hence $(\sigma',B)$ is the required pair. Thus, since $|A_1^{\sigma'}| =3D d_1 + d_2 - 1$ and $|B| =3D d_2$, we = deduce that each permutation \mbox{$\sigma' \in \Gamma_{u'}$} generates exactly ${d_1 + d_2 - 1 \choose d_2}$ permutations $\sigma \in \Gamma_u$ = according to the above procedure. This shows that \[ |\Gamma_u| =3D {d_1 + d_2 -1 \choose d_2} |\Gamma_{u'}|. \] $\enspace$\\[-48pt] \hfill{$\Box$} \begin{prop} If $u \in \mathcal{D}_n$ with $d(u) =3D (d_i)_{i \in [n]}$, we have that \[ |\Gamma_u| =3D \prod\limits_{j=3D1}^{n-1} \frac{\sum\limits_{i=3D1}^j = d_i - j + 1}{d_j !}. \] \end{prop} \noindent \textit{Proof}. We consider the finite sequence $(u_j)_{j \in [n]}$ of Dyck paths, where $u_1 =3D u$ and for $j > 1$ the Dyck path $u_j$ is obtained from = $u_{j-1}$ by deleting its first peak. Clearly, $u_j \in \mathcal{D}_{n-j+1}$ for every $j \in [n]$; if $d(u_j) =3D (d_i^{j})_{i \in [n-j+1]}$, by Lemma \ref{lemma6.3} we have = that \[ d_1^j =3D d_1^{j-1} + d_2^{j-1} - 1, d_i^j =3D d_{i+1}^{j-1} \] \noindent and \begin{equation}\label{eq4} |\Gamma_{u_{j-1}}| =3D {d_1^{j-1} + d_2^{j-1} - 1 \choose d_2^{j-1}} | = \Gamma_{u_j}| \end{equation} \noindent for every $j \in [2,n]$. It is easy to check that $d_2^{j-1} =3D d_j$ and $d_1^{j-1} + d_2^{j-1} - 1 =3D \sum\limits_{i=3D1}^j d_i - j +1$, for = every $j \in [2,n]$. Furthermore, using the previous equalities and applying formula = \eqref{eq4} for every $j \in [2,n]$, we obtain that \begin{align*}|\Gamma_u| & =3D \prod\limits_{j=3D2}^n {\sum\limits_{i=3D1}^{j} d_i - j + 1 = \choose d_j} |\Gamma_{u_n}| \\ & =3D \prod\limits_{j=3D1}^{n-1} \frac{\sum\limits_{i=3D1}^{j} d_i - = j + 1}{d_j!}. \end{align*} $\enspace$\\[-48pt] \hfill{$\Box$} \medskip \bigskip We note that since the family $(\Gamma_u)_{u \in \mathcal{D}_n}$ is a partition of $S_n$, by the previous proposition we obtain an identity for the factorial number, i.e., \[ \sum\limits_{d} \prod\limits_{j=3D1}^{n-1} = \frac{\sum\limits_{i=3D1}^{j} d_i - j + 1}{d_j!} =3D n!\] \noindent where the sum is taken over all dominating sequences $d =3D = (d_i)_{i \in [n]}$. \begin{thebibliography}{99} \bibitem{BK} J. Bandlow and K. Killpatrick, An Area-to-Inv Bijection Between Dyck = paths and 312-avoiding Permutation, \textit{Electronic J. Combin.}, {\bf 8} (2001), Article = R40. \bibitem{BBFP} E. Barcucci, A. Bernini, L. Ferrari and M. Poneti, A Distributive = Lattice Structure Connecting Dyck paths, Noncrossing Partitions and 312-avoiding Permutations, = \textit{Order}, {\bf 22} (2005), 311--328. \bibitem{BarnabeiPezzoli} M. Barnabei and E. Pezzoli, Gian-Carlo Rota on Combinatorics, in J.P.S. Kung, ed., \textit{M\"obius functions}, Birkhauser, 1995, pp. 83--104. \bibitem{Brylawski} T. Brylawski, The lattice of integer partitions, \textit{Discrete Math.} \textbf{6} (1973), 210--219. \bibitem{Deutsch} E. Deutsch, Dyck path enumeration, \textit{Discrete Math.} \textbf{204} = (1999), 167--202. \bibitem{Edelman} P. H. Edelman, Zeta polynomials and the M\"obius function, = \textit{European J. Combin.} \textbf{1} (1980), 335--340. \bibitem{EdelmanGreene} P. Edelman and C. Greene, Balanced tableaux, \textit{Adv. in. Math.} = \textbf{63} (1987), 42--99. \bibitem{EdelmanSimion} P. H. Edelman and R. Simion, Chains in the lattice of noncrossing = partitions, \textit{Discrete Math.} \textbf{126} (1994), 107--119. \bibitem{FerrariPinzani} L. Ferrari and R. Pinzani, Lattices of lattice paths, \textit{J. = Statist. Plann. Inference} \textbf{135} (2005), 77--92. \bibitem{Fulmek} M. Fulmek, Enumeration of permutations containing a prescribed number of = occurrences of=20 a pattern of length three, \textit{Adv. Appl. Math.}, {\bf 30} (2003), = 607--632. \bibitem{GuilbaudRosenstiehl} G. Guilbaud and P. Rosenstiehl, Analyse alg\'ebrique d'un scrutin, \textit{Math. Sci. Hum.} \textbf{4} (1963), 9--33. \bibitem{NarayanaFulton} T. V. Narayana and G. E. Fulton, A note on the compositions of an = integer, \textit{Canad. Math. Bull.} \textbf{1} (1958), 169--173. \bibitem{Kreweras2} G. Kreweras, Sur une classe de probl\`emes de d\'enombrement li\'es au treillis des partitions d'entiers, \textit{Cahiers du = B.U.R.O.} \textbf{6} (1965), 5--105. \bibitem{Kreweras1} G. Kreweras and H. Niederhausen, Solution of an enumerative problem = connected with lattice paths, \textit{European J. Combin.} \textbf{2} (1981), = 55--60. \bibitem{PS} A. Panayotopoulos and A. Sapounakis, On the prime decomposition of Dyck = words, \textit{J. Combin. Math. Combin. Comput.} \textbf{40} (2002), 33--39. \bibitem{Pergola} E. Pergola, Two bijections for the area of Dyck paths, \textit{Discrete = Math.} \textbf{241} (2001), 435--447. \bibitem{SimionUllman} R. Simion and D. Ullman, On the structure of the lattice of noncrossing partitions, \textit{Discrete Math.} \textbf{98} (1991), 193--206. \bibitem{Sloane} N. J. A. Sloane, The On-Line Encyclopedia of Integer Sequences (2005), published electronically at \htmladdnormallink{http://www.research.att.com/${\tilde{\enspace}}$njas/s= equences/}{http://www.research.att.com/~njas/sequences/}. \bibitem{Stanley3} R. Stanley, On the number of reduced decompositions of elements of = Coxeter groups, \textit{European J. Combin.} \textbf{5} (1984), 359--372. \bibitem{Stanley1} R. Stanley, \textit{Enumerative Combinatorics}, Vol. 1, Cambridge = University Press, 1997. \bibitem{Tamari} D. Tamari, The algebra of bracketings and their enumeration, = \textit{Nieuw. Arch. Wisk.} \textbf{10} (1962), 131--146. \end{thebibliography} \bigskip \hrule \bigskip \noindent 2000 {\it Mathematics Subject Classification}: Primary 06A07; Secondary 06D99. \noindent \emph{Keywords: Dyck paths, lattices, dominating sequences.} \bigskip \hrule \bigskip \noindent (Concerned with sequences \seqnum{A000045}, \seqnum{A000108}, \seqnum{A086581}, \seqnum{A006327}.) \bigskip \hrule \bigskip \end{document} ------=_NextPart_000_0063_01C662E2.00CF14A0--