Analysis of an algorithm to construct Fibonacci partitions. (English) Zbl 0562.05006

A Fibonacci partition of \(\{\) 1,2,...,n\(\}\) is a partition such that i and \(i+1\) are never in the same block, the corresponding number \(C_ n\) equals \(B_ n\) in the number of partitions of \(\{\) 1,2,...,n-1\(\}\). There exists an algorithm which constructs a unique Fibonacci partition of \(\{1,2,..,n+1\}\) from a partition of \(\{\) 1,2,...,n\(\}\). Let \(C_{n+1,k}\) be the number of companions of \((n+1)\) in the Fibonacci partitions. Exact formulas and asymptotic estimates for the average and the variance of these numbers are given.
Reviewer: M.Cheema


05A17 Combinatorial aspects of partitions of integers
05A15 Exact enumeration problems, generating functions
11P81 Elementary theory of partitions
Full Text: EuDML


[1] 1. N. G. DE BRUIJN, Asymptotic methods in Analysis, North-Holland, Amsterdam, 1958. Zbl0082.04202 · Zbl 0082.04202
[2] 2. L. COMTET, Advanced Combinatorics, Reidel, Dordrecht-Holland, 1974. Zbl0283.05001 MR460128 · Zbl 0283.05001
[3] 3. H. PRODINGER, On the Number of Fibonacci Partitions of a Set, The Fibonacci Quarterly, Vol. 19, 1981, pp. 463-466. Zbl0475.05009 MR644710 · Zbl 0475.05009
[4] 4. J. RIORDAN, Combinatorial Identifies, Wiley, New York, 1968. Zbl0194.00502 MR231725 · Zbl 0194.00502
[5] 5. G.-C. ROTA, The Number of Partitions of a Set, American Math. Monthly, Vol.71, 1964, Zbl0121.01803 MR161805 · Zbl 0121.01803
[6] reprinted in G.-C. Rota : Finite Operator Calculus, Academic Press, New York, 1975. MR379213
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.