This site is supported by donations to The OEIS Foundation.

Łukasiewicz words

From OeisWiki
(Redirected from Łukasiewicz language)
Jump to: navigation, search

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 [1][2].

Definition

The following description follows Stanley:[3]

The letters of Łukasiewicz words come from the alphabet . The weight of a letter is defined by . A word made of letters from 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. for ) and the total sum is minus one (i.e. .) Thus .

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:[4]

Let denote the infinite alphabet and the morphism of into the additive group of rational integers defined by . The Łukasiewicz language is the set of words of such that and for any left factor of .

Preorder codewords

If instead of defining Łukasiewicz words consisting of letters taken from the alphabet , one employs nonnegative integers directly, one obtains what Vladimir Balakirsky calls preorder codewords.[5]

Also in Łukasiewicz words related OEIS sequences, the "carrier-letter" 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 A000108 Łukasiewicz words of the length where is the 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 's and 's (or respectively 's and 's) occur are called Dyck words (usually written without the trailing , and often with 's converted to '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 6917th 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: 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, ...}

Notes

  1. Biography of Jan Lukasiewicz.
  2. Jan Łukasiewicz — From Wikipedia, the free encyclopedia.
  3. R. Stanley, Hipparchus, Plutarch, Schröder and Hough, p. 4.
  4. M. Lothaire, Combinatorics on Words, Encyclopedia of Mathematics and Its Applications, vol. 17, Addison-Wesley, Reading, Massachusetts, 1983, Chapter 11, p. 219.
  5. V. B. Balakirsky A New Coding Algorithm for Trees, p. 17.