Multiset rewriting over Fibonacci and Tribonacci numbers

• Bridging formal logic and combinatorics.
• Formal logic techniques are applied directly to the problems in pure combinatorics.
• Church–Rosser property for both rewriting systems and their inverse counterparts.
• Bijective proofs for partition identities over k-step Fibonacci numbers.
• A new series of partition identities over k-step Fibonacci numbers.

We show how techniques from the formal logic, can be applied directly to the problems studied completely independently in the world of combinatorics, the theory of integer partitions. We characterize equinumerous partition ideals in terms of the minimal elements generating the complementary order filters. Here we apply a general rewriting methodology to the case of filters having overlapping minimal elements. In addition to a ‘bijective proof ’ for Zeckendorf-like theorems – that every positive integer is uniquely representable within the Fibonacci, Tribonacci and k-Bonacci numeration systems, we establish ‘bijective proofs’ for a new series of partition identities related to Fibonacci, Tribonacci and k-step Fibonacci numbers. The main result is proved with the help of a multiset rewriting system such that the system itself and the system consisting of its reverse rewriting rules, both have the Church–Rosser property, which provides an explicit bijection between partitions of two different types (represented by the two normal forms).