This site is supported by donations to The OEIS Foundation.

Totally balanced sequences

From OeisWiki
(Redirected from Totally balanced binary sequences)
Jump to: navigation, search


This article is under construction.

Please do not rely on any information it contains.


A totally balanced sequence (or totally balanced binary sequence) is a binary string with of bits, of which bits are 0s and bits are 1s, and reading from left to right (from the most significant bit to least significant bit), the number of 0's never exceeds the number of 1's.

The above definition differs from the one given by Kreher and Stinson in[1] only in that the order of 0s and 1s is reversed, thus allowing the unambiguous reading of each totally balanced sequence as a unique binary number (with no leading zeros). Ordering such binary numbers by their magnitude, gives us two sequences, A063171 (with representation kept in binary) and A014486 (with representation converted to decimal).

Totally balanced sequences are really just one manifestation of Dyck words. Replacing each 1 in binary representation with ( and each 0 with ) we get well-formed (balanced) parenthesizations. Furthermore, they can be easily converted to many other combinatorial interpretations of Catalan numbers.


Notes

  1. D. Kreher and D. Stinson Combinatorial Algorithms, Generation, Enumeration and Search (CAGES), CRC Press, 1998, p. 95