Łukasiewicz words

This article needs more work.

Please help by expanding it!

Łukasiewicz words were invented by or named after (expert opinion requested, see Talk page) the Polish mathematician Jan Łukasiewicz .

Definition

The following description follows Stanley:

The letters of Łukasiewicz words come from the alphabet $\scriptstyle A\,=\,\{x_{0},\,x_{1},\,x_{2},\,\ldots \}\,$. The weight $\scriptstyle \delta (x_{i})\,$ of a letter $\scriptstyle x_{i}\,$ is defined by $\scriptstyle \delta (x_{i})\,=\,i-1\,$. A word $\scriptstyle y_{1}y_{2}{\ldots }y_{m}\,$ made of letters from $\scriptstyle A\,$ is said to be a Łukasiewicz word if it fulfills the condition that for any proper prefix of the word, the sum of the weights is nonnegative (i.e. $\scriptstyle \delta (y_{1})+\ldots +\delta (y_{j})\,\geq \,0,\,$ for $\scriptstyle 1\,\leq \,j\,\leq \,m-1\,$) and the total sum is minus one (i.e. $\scriptstyle \delta (y_{1})+\ldots +\delta (y_{m})\,=\,-1\,$.) Thus $\scriptstyle y_{m}\,=\,x_{0}\,$.

To obtain a Łukasiewicz word from a rooted plane tree, one does a depth-first (preorder) search through the rooted plane tree, writing down the degree of each vertex (the number of children) at each vertex not previously visited.

Łukasiewicz language

The set of all Łukasiewicz words is called the Łukasiewicz language.

The following formal definition is from M. Lothaire:

Let $\scriptstyle A\,$ denote the infinite alphabet $\scriptstyle A\,=\,\{x_{0},\,x_{1},\,x_{2},\,\ldots \}\,$ and $\scriptstyle \delta \,$ the morphism of $\scriptstyle A^{*}\,$ into the additive group $\scriptstyle \mathbb {Z} \,$ of rational integers defined by $\scriptstyle \delta (a_{n})\,=\,n-1\,$. The Łukasiewicz language $\scriptstyle L\,$ is the set of words $\scriptstyle f\,$ of $\scriptstyle A^{*}\,$ such that $\scriptstyle \delta (f)\,=\,-1\,$ and $\scriptstyle \delta (f')\,\geq \,0\,$ for any left factor $\scriptstyle f'\,$ of $\scriptstyle f\,$.

Preorder codewords

If instead of defining Łukasiewicz words consisting of letters taken from the alphabet $\scriptstyle A\,=\,\{x_{0},\,x_{1},\,x_{2},\,\dots \}\,$, one employs nonnegative integers $\scriptstyle \{0,\,1,\,2,\,\dots \}\,$ directly, one obtains what Vladimir Balakirsky calls preorder codewords.

Also in Łukasiewicz words related OEIS sequences, the "carrier-letter" $\scriptstyle x\,$ of the index is dispensed with, and a word is written down just as a decimal number.

Connections

Being thus just another way of representing rooted plane general trees, Łukasiewicz words are one of the combinatorial interpretations of Catalan numbers:

{ {0}, {10}, {200, 110}, {3000, 2010, 2100, 1200, 1110}, ... }.

Specifically, there are $\scriptstyle C_{n}=\,$ A000108$\scriptstyle (n),\,n\,\geq \,0,\,$ Łukasiewicz words of the length $\scriptstyle n+1,\,$ where $\scriptstyle C_{n}\,$ is the $\scriptstyle n\,$^th Catalan number:

{ #{0}, #{10}, #{200, 110}, #{3000, 2010, 2100, 1200, 1110}, ... } =

{1, 1, 2, 5, 14, 42, 132, 429, 1430, 4862, 16796, 58786, 208012, 742900, 2674440, 9694845, 35357670, 129644790, 477638700, 1767263190, 6564120420, ...}

The subset of Łukasiewicz words where only $\scriptstyle x_{0}\,$'s and $\scriptstyle x_{2}\,$'s (or respectively $\scriptstyle 0\,$'s and $\scriptstyle 2\,$'s) occur are called Dyck words (usually written without the trailing $\scriptstyle 0\,$, and often with $\scriptstyle 2\,$'s converted to $\scriptstyle 1\,$'s). Specifically, the words in that subset represent such rooted plane general trees where the branching factor is always two, that is, are rooted plane binary trees.

Integer sequences associated with Łukasiewicz words

Note that the first two are well-defined only up to the 6917^th term, because of the limitations of the decimal system:

A079436 Full Lukasiewicz word for each rooted plane tree (interpretation e in Stanley's exercise 19) encoded by (in order induced by) A014486 (or A063171).

{0, 10, 200, 110, 3000, 2010, 2100, 1200, 1110, 40000, 30010, 30100, 20200, 20110, 31000, 21010, 22000, 13000, 12010, 21100, 12100, 11200, 11110, 500000, 400010, ...}

A071153 Lukasiewicz word for each rooted plane tree (interpretation e in Stanley's exercise 19) encoded by A014486 (or A063171), with the last leaf implicit, i.e. these words are given without the last trailing 0, except for the null tree which is encoded as 0.

{0, 1, 20, 11, 300, 201, 210, 120, 111, 4000, 3001, 3010, 2020, 2011, 3100, 2101, 2200, 1300, 1201, 2110, 1210, 1120, 1111, 50000, 40001, 40010, 30020, 30011, 40100, ...}

A000108 Catalan numbers: $\scriptstyle C(n)\,=\,{\frac {\binom {2n}{n}}{n+1}}\,=\,{\frac {(2n)!}{n!(n+1)!}},\,n\,\geq \,0.\,$ Also called Segner numbers.

{1, 1, 2, 5, 14, 42, 132, 429, 1430, 4862, 16796, 58786, 208012, 742900, 2674440, 9694845, 35357670, 129644790, 477638700, 1767263190, 6564120420, 24466267020, ...}