Semi-Fibonacci Partitions

Initializing live version
Download to Desktop

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]

Let be an integer partition of , so that ; assume .

For example, . (The notation means " is a partition of .") That partition can be written more compactly as .

Define the partition subsum polynomial of by . The similar-looking product generates the number of distinct partitions [1].

For example, .

The possible subsums of are over all possible choices of . Expanding gives , where is the number of ways to form the subsum .

For example, .

The term indicates that there are three ways to get the subsum 1, as there are three parts that are 1. In this polynomial, each power happens to have a nonzero coefficient, which means that the partition has a subsum for each number from 1 to ; so is called a complete partition [2]. The list of coefficients is always symmetric: if summing the subset of gives , then summing gives , so in , the coefficients of and are equal.

The semi-Fibonacci sequence [3] is defined by

,

,

.

The sequence starts: 1, 1, 2, 1, 3, 2, 5, 1, 6, 3, ….

Theorem: The number of partitions for which has no repeated root is the semi-Fibonacci sequence.

See the details for a proof.

The first tab gives the semi-Fibonacci sequence and the semi-Fibonacci partitions. The second tab shows the lattice points (as squares) that satisfy the condition stated in the tab. The third tab shows when the roots of the two equations stated in the tab overlap.

[less]

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.



Feedback (field required)
Email (field required) Name
Occupation Organization
Note: Your message & contact information may be shared with the author of any specific Demonstration for which you give feedback.
Send