Closed form expressions for the iterated floor function

✍ Scribed by K.A. Redish; W.F. Smyth

• Publisher: Elsevier Science
• Year: 1991
• Tongue: English
• Weight: 198 KB
• Volume: 91
• Category: Article
• ISSN: 0012-365X
• DOI: 10.1016/0012-365x(90)90240-i

✦ Synopsis

Redish, K.A. and W.F. Smyth, Closed from expressions for the iterated floor function, Discrete Mathematics 91 (1991) 317-321. For positive integers k, r, and n 2 k + 1, the iterated floor function f_ is defined by f,,,(k + 1) = r; f*.,(n) = [&fk,,(n -111, n > k + 1. A special case (k = r = 3) of this function occurs as an upper bound on the number of 3-subsets, excluding tetrahedra, of an n-set (Turan's problem). For certain values of k and r, this note establishes closed form expressions for fk,,, then uses them to prove some interesting properties. For positive integers k, r, and 12 2 k + 1, the iterated floor function fk,r is defined by fk,,(k + 1) = r; A&) = [SfkAn -111, n > k + 1. The special case j& occurs as an upper bound on the number of nontetrahedral 3-subsets of an n-set [l]. We state our results as a sequence of lemmas.