Semi-Fibonacci Partitions
Requires a Wolfram Notebook System
Interact on desktop, mobile and cloud with the free Wolfram Player or other Wolfram Language products.
This Demonstration counts the number of partition subsum polynomials without repeated roots.
[more]
Contributed by: George Beck (July 2019)
Open content licensed under CC BY-NC-SA
Snapshots
Details
Definitions
, and if is a partition of with one odd part, say , define: .
If is a set of partitions, define , , and if contains only partitions with one odd part, .
This defines the semi-Fibonacci partitions of :
, , .
Then , , , , , ….
Lemma 1
The roots of are , .
Proof
First check the roots: . Now check the roots are distinct: Suppose , , and . Then . Since , , so . Therefore the are distinct and are the roots of . \[FilledSquare]
Lemma 2
The polynomials and have a common root iff and are both odd, in which case there are common roots. Therefore the polynomials have no common root iff is odd.
Proof
If the two polynomials have a common root, then there are integers and , , such that so . Therefore , which implies that the highest powers of 2 dividing and are equal, so that and are both odd.
If and are both odd, let and be such that and . Then so , which gives a common root of the two polynomials.
Suppose and have a common root. Let and . Then the equations and also have a common root, say . Then with , , so is also a solution of and likewise of .
For the last statement, and cannot both be even—the GCD would absorb the 2. So the polynomials have no common root iff one of or is odd and the other even, or, equivalently, is odd. \[FilledSquare]
Lemma 3
The polynomial has no repeated root iff is odd for each pair of parts , of .
Proof
Apply lemma 2 to the definition . \[FilledSquare]
Lemma 4
If , then has only even parts. If , then has exactly one odd part. In the definition , the union is disjoint.
Proof
The parts of a partition in are clearly all even.
For induction, assume each partition in has at exactly one odd part; this is true for the base case . Suppose for some . Since has at most one odd part, the same is true for . Suppose for some . Since has no odd parts, has exactly one odd part, namely 1.
The union is disjoint because the odd parts of are all 1 and the odd parts of are all greater than 1. \[FilledSquare]
Lemma 5
iff for each pair of parts and of , is odd.
Proof
This is vacuously true for the partitions with one part, . For induction, assume the statement is true up to .
If is even and , then is odd by the induction hypothesis, so the condition holds for 2.
If is odd and , either there is a such that or there is a such that . In the first case, there is only one new part, 1; because and all the other parts are even, is odd. In the second case, by lemma 4, has exactly one odd part, so is odd and the others follow by induction, since the even parts belonged to partitions in . \[FilledSquare]
Lemma 6
.
Proof
For induction, the base case is . By definition of , . By lemma 4, since the union is disjoint, . Therefore satisfies the same conditions as and they are the same sequence. \[FilledSquare]
Theorem
The number of partitions for which has no repeated root is the semi-Fibonacci sequence.
Proof
By lemma 3, has no repeated root iff is odd for each pair of parts , of . By lemma 5, the latter statement is equivalent to . By lemma 6, the number of with no repeated root is counted by . \[FilledSquare]
References
[1] N. J. A. Sloane "A000009." The On-Line Encyclopedia of Integer Sequences. https://oeis.org/A000009.
[2] N. J. A. Sloane "A126796." The On-Line Encyclopedia of Integer Sequences. https://oeis.org/A126796.
[3] N. J. A. Sloane "A030067." The On-Line Encyclopedia of Integer Sequences. https://oeis.org/A030067.
Permanent Citation