Binary Strings with No Isolated I's in Even Positions

摘要

Given a nonempty set A, a binary relation R on A makes (A, R) a partially ordered set, or poset, if R is reflexive, antisymmetric, and transitive. A subset B of A is called an order ideal of {A, R) if whenever b ∈ B and a ∈ A with aRb, then a ∈ B. For n ≥ 1, let Z_n = {x_1, x_2,...,x_n} and define the binary relation R on Z_n by the cover relations x_(2k-1) Rx_(2k), for 1 ≤ 2k -1 < 2k < n, and x_(2k+1)R_(x2k), for 2 ≤ 2k < 2k + 1 ≤ n. The resulting partial order (Z_n,R) is called the zigzag poset or fence. For n = 0, we have Z_0 = Φ and (Z0, R) = Φ. On P. 100 of the text by R. Stanley one learns that the number of order ideals for the partial order (Z_n, R) is given by the Fibonacci number F_(n+2). [The Fibonacci numbers are defined recursively by F_0 = 0, F_1 = 1, F_n = F_(n-i) + F_(n-2), n ≥ 2. Further, one finds that for n ≥ 0, F_n = (α~n - β~n)/(α - β), the Binet form for F_n, where α = the golden ratio = (1+5~(1/2))/2 and β = (1-5~(1/2))/2 In the paper by R. Grimaldi, these order ideals are examined in a variety of combinatorial situations.