A quick proof that 321-avoiding permutations without double deficiencies are counted by the Motzkin numbers

A quick proof that 321-avoiding permutations without double deficiencies are counted by the Motzkin numbers
By Tipaluck Krityakierne, Thotsaporn "Aek" Thanatipanonda, and Doron Zeilberger
.pdf .tex

First Written: July 2, 2026.

We give a "proof from the book" of the statement in the title. It was first proved by M. Rubey and C. Stump.

Maple packages

DD321Terse.txt, a very short Maple package that ONLY implements the bijection (and checks it: try Check1(n); Check2(n);

DD321.txt, A much longer Maple package that implements the bijection but does much more

Sample Input and Output Files for DD321Terse.txt

If you want to see confirmation that the Motzkin-to No DD321 and No DD321 to Motzkin mappings are inverses of each other up to n=14,
the input file yields the input file

Sample Input and Output Files for DD321.txt

If you want to see the images of all Motzkin words of length up to 9, under the Motzkin-to-No321NoDD permutations (listed in lexicographic order)
input file yields the output file

If you want to see the images of all No321NoDD permutations of length up to 9 under the reverse mapping (listed in lexicographic order)
input file yields the output file

Tipaluck Krityakierne's Home Page
Thotsaporn "Aek" Thanatipanonda's Home Page
Doron Zeilberger's Home Page