The Antisigma Function

The \( \textbf{antisigma}\) function returns the sum of the proper non-divisors of \(n\). I hadn't heard of it before but came across reference to it when researching properties of the number 77. Let's designate this function as a(\(n\)) and use 15 as an example to illustrate how it works. The proper divisors of 15 are 1, 3 and 5. This means that 2, 4, 6, 7, 8, 9, 10, 11, 12, 13 and 14 are non-divisors and they total 96. Thus:$$a(15)=96$$A quicker way to calculate the sum of proper non-divisors is to use the following formula that makes use of the sum of the terms of an arithmetic sequence:$$ \begin{align} \text{a}(n) &= \frac{n(n+1)}{2} - \sigma(n) \\ \text{a}(15) &= \frac{15 \times 16}{ 2} - 24 \\ &=140-24\\&=96 \end{align} $$I had to be reminded as to the formula for the sum of the terms of an arithmetic progression with starting term \(a\) and common difference \(d\). The sum \( \text{S}_n \) of the first \(n\) terms is given by:$$ \begin{align} \text{S}_n &= \frac{n}{2}(2a+(n-1)d) \\ &= \frac{n (n+1)}{2} \text{ for }a=1 \text{ and } d=1 \end{align}$$The antisigma function differs from Euler's totient function that counts the number of integers up to a given number \(n\) that are coprime to \(n\). In the case of 15, we have:$$ \begin{align} \phi(15) &= 15 \times (1-\frac{1}{3}) \times (1-\frac{1}{5}) \\ &= 15 \times \frac{2}{3} \times \frac{4}{5} \\ &=8 \end{align}$$The eight numbers that are coprime to 15 are 1, 2, 4, 7, 8, 11, 13 and 14. 

The antisigma function relates to the non-divisors of a number and these differ from its antidivisors. The antidivisors of 15 are 2, 6 and 10. See blog More on Anti-divisors.

The OEIS includes various sequences relating to antisigma function. First and foremost there is OEIS A024816:

A024816: antisigma(\(n\)) which is the sum of the numbers less than \(n\) that do not divide \(n\).

This sequence begins:

0, 0, 2, 3, 9, 9, 20, 21, 32, 37, 54, 50, 77, 81, 96, 105, 135, 132, 170, 168, 199, 217, 252, 240, 294, 309, 338, 350, 405, 393, 464, 465, 513, 541, 582, 575, 665, 681, 724, 730, 819, 807, 902, 906, 957, 1009, 1080, 1052, 1168, 1182, 1254, 1280, 1377, 1365

Then there is OEIS A200981:

A200981: numbers \(k\) such that the sum of non-divisors of \(k\) is prime.

3, 4, 10, 21, 34, 46, 58, 70, 85, 93, 118, 129, 130, 144, 178, 201, 226, 237, 262, 298, 310, 322, 324, 325, 333, 334, 346, 382, 406, 418, 430, 466, 478, 502, 513, 514, 517, 549, 598, 622, 633, 634, 657, 658, 669, 706, 730, 742, 813, 826, 837, 838, 865, 922, 982, 985

Generating Functions

Only yesterday in a post titled Linear Recurrence Revisited did I look at this recurrence in relation to my diurnal age of 28072:$$ \begin{align} &\text{a}(n+3) = 2\text{a}(n+2) - 3\text{a}(n+1) + 2\text{a}(n)\\ & \text{a}(0) = 1, \text{a}(1) = 1, \text{a}(2) = 0 \end{align}$$Today, a day later, I find that 28073 can also be linked to a linear recurrence via OEIS A157651:$$ \begin{align} &\text{a}(n) = 3\text{a}(n-1) -3\text{a}(n-2) +\text{a}(n-3) \\ &\text{a}(0) =57, \text{a}(1) =308, \text{a}(3)=759 \end{align}$$The initial terms are:

57, 308, 759, 1410, 2261, 3312, 4563, 6014, 7665, 9516, 11567, 13818, 16269, 18920, 21771, 24822, 28073, 31524, 35175, 39026, 43077, 47328, 51779, 56430, 61281, 66332, 71583, 77034, 82685, 88536, 94587, 100838, 107289, 113940, 120791, 127842

However, this time I want to look at ordinary generating functions and exponential generating functions in relation to this linear recurrence. The following was created by Gemini.

$$
\begin{array}{@{}l}



\textbf{Derivation of the Ordinary Generating Function } G(x) \\[12pt]


\text{Let } G(x) = \displaystyle\sum_{n=0}^{\infty} a_n x^n = a_0 + a_1 x + a_2 x^2 + \dots \\[12pt]
\text{The recurrence relation is: } a_n - 3a_{n-1} + 3a_{n-2} - a_{n-3} = 0 \text{ for } n \ge 3. \\[12pt]


\text{We multiply } G(x) \text{ by the polynomial } (1 - 3x + 3x^2 - x^3): \\[6pt]
(1 - 3x + 3x^2 - x^3)G(x) = \\[6pt]
\quad \phantom{-} (a_0 + a_1 x + a_2 x^2 + a_3 x^3 + \dots) \\
\quad - \displaystyle 3x (a_0 + a_1 x + a_2 x^2 + \dots) \\
\quad + \displaystyle 3x^2 (a_0 + a_1 x + \dots) \\
\quad - \displaystyle x^3 (a_0 + \dots) \\[18pt]


\text{Grouping coefficients by powers of } x: \\[6pt]
\text{Constant: } a_0 = 57 \\[6pt]
x^1: a_1 - 3a_0 = 308 - 3(57) = 308 - 171 = 137 \\[6pt]
x^2: a_2 - 3a_1 + 3a_0 = 759 - 3(308) + 3(57) = 759 - 924 + 171 = 6 \\[6pt]
x^n \text{ (for } n \ge 3\text{): } a_n - 3a_{n-1} + 3a_{n-2} - a_{n-3} = 0 \\[18pt]


\text{Thus:} \\[6pt]
(1 - x)^3 G(x) = 57 + 137x + 6x^2 \\[12pt]


\text{The Ordinary Generating Function is:} \\[6pt]
G(x) = \displaystyle\frac{57 + 137x + 6x^2}{(1 - x)^3} \\[24pt]




\textbf{Derivation of the Exponential Generating Function } E(x) \\[12pt]


\text{Let } E(x) = \displaystyle\sum_{n=0}^{\infty} a_n \frac{x^n}{n!}. \\[12pt]
\text{The recurrence } a_n - 3a_{n-1} + 3a_{n-2} - a_{n-3} = 0 \\ \text{ becomes the differential equation:} \\[6pt]
E'''(x) - 3E''(x) + 3E'(x) - E(x) = 0 \\[12pt]


\text{The characteristic equation is } r^3 - 3r^2 + 3r - 1 = (r-1)^3 = 0. \\[6pt]
\text{This has a triple root at } r = 1. \\[12pt]


\text{The general solution for a triple root is:} \\[6pt]
E(x) = (C_1 + C_2 x + C_3 x^2)e^x \\[12pt]


\text{We find constants } C_1, C_2, C_3 \text{ using initial conditions } a_0=57, a_1=308, a_2=759. \\[6pt]
\text{Note that } a_n \text{ is the coefficient of } \frac{x^n}{n!}. \\[6pt]
\text{Expanding } E(x) = (C_1 + C_2 x + C_3 x^2) \displaystyle \sum \frac{x^n}{n!} \\ \text{ allows us to match coefficients directly.} \\[18pt]


\text{Solving for the constants (via derivatives at } x=0 \text{):} \\[6pt]
1. \quad E(0) = a_0 \implies C_1 = 57 \\[6pt]
2. \quad E'(0) = a_1 \implies C_1 + C_2 = 308 \implies 57 + C_2 = 308 \implies C_2 = 251 \\[6pt]
3. \quad E''(0) = a_2 \implies C_1 + 2C_2 + 2C_3 = 759 \\[6pt]
\phantom{3. \quad} 57 + 2(251) + 2C_3 = 759 \\[6pt]
\phantom{3. \quad} 559 + 2C_3 = 759 \implies 2C_3 = 200 \implies C_3 = 100 \\[18pt]


\text{The Exponential Generating Function is:} \\[6pt]
E(x) = (57 + 251x + 100x^2)e^x \\[24pt]




\textbf{Expansion of the Ordinary Generating Function} \\[12pt]


\text{The correct OGF is: } G(x) = \displaystyle\frac{57 + 137x + 6x^2}{(1-x)^3} \\[12pt]


\text{We use the binomial series expansion for } (1-x)^{-3}: \\[6pt]
(1-x)^{-3} = \displaystyle\sum_{n=0}^{\infty} \binom{n+2}{2} x^n = \displaystyle\sum_{n=0}^{\infty} \frac{(n+1)(n+2)}{2} x^n \\[12pt]


\text{Multiply this series by the numerator } (57 + 137x + 6x^2): \\[6pt]
a_n = 57 \cdot \binom{n+2}{2} + 137 \cdot \binom{n+1}{2} + 6 \cdot \binom{n}{2} \\[12pt]


\text{Let's verify the first few terms again with the correct formula:} \\[12pt]


\textbf{For } n=0: \\[6pt]
a_0 = 57 \cdot \frac{(1)(2)}{2} = 57(1) = \mathbf{57} \\[12pt]


\textbf{For } n=1: \\[6pt]
\text{The term } \binom{n}{2} \text{ is 0 for } n < 2. \\[6pt]
a_1 = 57 \cdot \frac{(2)(3)}{2} + 137 \cdot \frac{(1)(2)}{2} \\[6pt]
a_1 = 57(3) + 137(1) = 171 + 137 = \mathbf{308} \\[12pt]


\textbf{For } n=2: \\[6pt]
a_2 = 57 \cdot \frac{(3)(4)}{2} + 137 \cdot \frac{(2)(3)}{2} + 6 \cdot \frac{(2)(1)}{2} \\[6pt]
a_2 = 57(6) + 137(3) + 6(1) \\[6pt]
a_2 = 342 + 411 + 6 = \mathbf{759} \\[12pt]


\textbf{For } n=3: \\[6pt]
a_3 = 57 \cdot \frac{(4)(5)}{2} + 137 \cdot \frac{(3)(4)}{2} + 6 \cdot \frac{(3)(2)}{2} \\[6pt]
a_3 = 57(10) + 137(6) + 6(3) \\[6pt]
a_3 = 570 + 822 + 18 = \mathbf{1410} \\[24pt]




\textbf{Expansion of the Exponential Generating Function} \\[12pt]


\text{We expand } e^x = \displaystyle\sum_{n=0}^{\infty} \dfrac{x^n}{n!} = 1 + x + \dfrac{x^2}{2!} + \dfrac{x^3}{3!} + \dots \\[12pt]


\text{Multiply by the polynomial } (57 + 251x + 100x^2): \\[6pt]
E(x) = 57 \displaystyle\sum \dfrac{x^n}{n!} + 251x \displaystyle\sum \dfrac{x^n}{n!} + 100x^2 \displaystyle\sum \dfrac{x^n}{n!} \\[12pt]


\text{To find } a_n, \text{ we look for the coefficient of } \frac{x^n}{n!} \text{ in the combined sum.} \\[6pt]
\text{Note that } x \cdot \dfrac{x^{n-1}}{(n-1)!} = n \dfrac{x^n}{n!} \text{ and } x^2 \cdot \dfrac{x^{n-2}}{(n-2)!} = n(n-1) \dfrac{x^n}{n!}. \\[12pt]


\text{This gives us the direct formula:} \\[6pt]
a_n = 57(1) + 251(n) + 100(n)(n-1) \\[6pt]
a_n = 100n^2 + 151n + 57 \\[12pt]


\text{Let's calculate the terms using this formula:} \\[12pt]


\textbf{For } n=0: \\[6pt]
a_0 = 0 + 0 + 57 = \mathbf{57} \\[12pt]


\textbf{For } n=1: \\[6pt]
a_1 = 100(1) + 151(1) + 57 = 251 + 57 = \mathbf{308} \\[12pt]


\textbf{For } n=2: \\[6pt]
a_2 = 100(4) + 151(2) + 57 = 400 + 302 + 57 = \mathbf{759} \\[12pt]


\textbf{For } n=3: \\[6pt]
a_3 = 100(9) + 151(3) + 57 = 900 + 453 + 57 = \mathbf{1410}
\end{array}
$$

I prefer to work with the ordinary generating function in which case the following simple code will generate the terms:

Partitions and Generating Functions

I asked Gemini to explain the statement:

“It’s long been known that you can associate

a polynomial equation to any partition.”

Here's what it came up with.

The statement refers to the relationship between an integer partition and a generating function, which is a way of encoding an infinite sequence of numbers as the coefficients of a formal power series. In this context, the "polynomial equation" is more accurately a generating function, which can be represented as a polynomial-like expression.

A partition of a positive integer \(n\) is a way of writing \(n\) as a sum of positive integers. The order of the addends (the parts of the partition) does not matter. For example, the partitions of the number 4 are:

• 4

• 3 + 1

• 2 + 2

• 2 + 1 + 1

• 1 + 1 + 1 + 1

The statement means that for any given integer, we can construct a polynomial-like expression (a generating function) that "encodes" all of its possible partitions.

How the Association Works

The connection is established through the concept of generating functions. The generating function for the number of partitions of an integer \(n\), denoted as \( p(n) \), can be expressed as an infinite product:$$P(x) = \sum_{n=0}^{\infty} p(n)x^n = \prod_{k=1}^{\infty} \frac{1}{1-x^k}$$Let's break down this formula:

• \( p(n) \) This represents the number of partitions for an integer \(n\)

• \( \displaystyle\sum_{n=0}^{\infty} p(n)x^n \) This is the power series where the coefficient of \(x^n\) is the number of partitions of \(n\).

• \(\displaystyle\prod_{k=1}^{\infty} \dfrac{1}{1-x^k}\) This is the infinite product that generates these coefficients.

Each term in the product \( \dfrac{1}{1-x^k} \) can be expanded as a geometric series:

• \(\dfrac{1}{1-x} = 1 + x + x^2 + x^3 + \dots \) This represents using the number 1 as a part in the partition

• \(\dfrac{1}{1-x^2} = 1 + x^2 + x^4 + x^6 + \dots\) This represents using the number 2 as a part

• \( \dfrac{1}{1-x^3} = 1 + x^3 + x^6 + x^9 + \dots \) This represents using the number 3 as a part

• And so on for all integers \(k\).

When you multiply these series together, the coefficient of \(x^n\) in the resulting series will be the total number of ways to form \(n\) by adding these parts.

Examples

Let's find the partitions for the number 3. The partitions are:

• 3

• 2 + 1

• 1 + 1 + 1

There are 3 partitions of 3.

Now, let's see how the generating function gives us this result. We look at the expansion of the product:$$(1 + x + x^2 + x^3 + \dots)(1 + x^2 + x^4 + \dots)(1 + x^3 + x^6 + \dots) \dots$$To get the term \(x^3\), we can combine terms from these expansions in the following ways:

• From the first factor, take \(x^3\). This corresponds to the partition 1 + 1 + 1.

• From the first factor, take \(x^1\), and from the second factor, take \(x^2\). This corresponds to the partition 1 + 2.

• From the third factor, take \(x^3\). This corresponds to the partition 3.

The coefficient of \(x^3\) is therefore 3, which matches the number of partitions.

Here is another example for the partitions of 4, which we know is 5.

To find the coefficient of \(x^4\), we would consider combinations like:

• \(x^4\) from the first factor: 1 + 1 + 1 + 1

• \(x^2\) from the first factor and \(x^2\) from the second: 1 + 1 + 2

• \(x^1\) from the first factor and \(x^3\) from the third: 1 + 3

• \(x^4\) from the second factor: 2 + 2

• \(x^4\) from the fourth factor: 4

The total number of ways to get \(x^4\) is 5, so the coefficient is 5.

In essence, the "polynomial" or generating function provides a systematic way to count the number of partitions for any integer by looking at the coefficients of the series expansion.

Fibonacci Generating Functions

The Fibonacci Sequence can be generated from the following recurrence relation:$$a(n)=a(n-1)+a(n-2) \text{ with } a(0)=1 \text{ and } a(1)=1$$The generating function for this series is given by:$$ \frac{x^2}{1-x-x^2} $$How is generating function affected if we have a recurrence relation as follows:$$a(n)=a(n-1)+a(n-8)$$I created a post about this titled Fibonacci-like Sequences quite recently on May 13th 2024. The new generating function is now:$$ \frac{x^2}{1-x-x^8} $$What if there are coefficients (let's say \( \alpha \) and \( \beta \) in front of the two terms on the LHS:$$a(n) = \alpha . a(n-1) + \beta . a(n-2)$$In this case, the generating function becomes: $$ \frac{x^2}{1-\alpha . x - \beta . x^2}$$Let's take the following example:$$a(n)=4. \, a(n-1)+10. \, a(n-2)$$The generating function becomes$$ \frac{x^2}{1-4x - 10 x^2}$$The sequence of terms becomes (permalink):

0, 1, 4, 26, 144, 836, 4784, 27496, 157824, 906256, 5203264, 29875616, 171535104, 984896576, 5654937344, 32468715136, 186424233984, 1070384087296, 6145778689024, 35286955629056

This numbers form the initial terms of OEIS A180226:

A180226

a(n) = 4*a(n-1) + 10*a(n-2), with a(1)=0 and a(2)=1.

To check what happens to the generating function when the tribonacci sequence is considered, see my post titled Beyond Fibonacci (March 10th 2019).

Centered Platonic Numbers

On the 19th November 2018, I created a post titled Platonic Numbers and at the end of that post I made reference to Centered Platonic Numbers as follows:

Additionally, there are the centered Platonic numbers defined by starting with 1 central dot (for \(n\)=0) and adding regular convex polyhedral layers around the central dot, where the \(n\)th layer, \(n\) ≥ 1, has \(n\)+1 dots per facet ridge (face edge for polyhedrons) including both end vertices. The formulae are very similar to the above and can be explored further here.

Let's look a particular type of centered Platonic number, namely the centered tetrahedral numbers, and the case where n=2. See Figure 1.

Figure 1

This second centered tetrahedral number differs from the equivalent tetrahedral number by 1. The progression of the tetrahedral numbers from n=1 to 4 is shown in Figure 2.

Figure 2

With the tetrahedral numbers, there is a layering process in place as is clearly visible in the progression shown in Figure 2. With the centered tetrahedral numbers, the tetrahedra shown in Figure 2 are being built around the central dot. Each progressive tetrahedron contains all the previous tetrahedra, Russian doll style. 

Thus the centered tetrahedral numbers can be derived by progressively summing the tetrahedral numbers:

1, 1 + 4, 1 + 4 + 10, 1 + 4 + 10 + 20 --> 1, 5, 15, 35 etc.

The formulae for the various centered Platonic numbers can be found at this site and for the centered tetrahedral numbers, the formula is:$$ \frac{ (2n+1)(n^2+n+3)}{3}$$This formula generates the following initial members of OEIS A005894:

1, 5, 15, 35, 69, 121, 195, 295, 425, 589, 791, 1035, 1325, 1665, 2059, 2511, 3025, 3605, 4255, 4979, 5781, 6665, 7635, 8695, 9849, 11101, 12455, 13915, 15485, 17169, 18971, 20895, 22945, 25125, 27439, 29891, 32485, 35225, 38115

The generating function for this series is: $$ \frac{(1+x)(1+x^2)}{(1-x)^4}$$For example, the first few terms of the resulting Taylor series are:$$1+5x+15x^2+35x^3+69x^4+121x^5+195x^6+295x^7 + ...$$

Motzkin Numbers

I recently came upon a class of numbers known as Motzkin numbers. They are defined as follows:

In mathematics, the n-th Motzkin number is the number of different ways of drawing non-intersecting chords between n points on a circle. Source.

Figures 1 and 2 are illustrations showing two of the numbers (9 and 21) using the same source:

Figure 1: there are 9 ways to draw non-intersecting chords
between 4 points on a circle (M(4)= 9)

Figure 2: there are 21 ways to draw non-intersecting chords
between 5 points on a circle (M(5) = 21)

The Motzkin numbers satisfy the following recurrence relation:$$M_n = \frac{2n+1}{n+2} M_{n-1}+\frac{3n-3}{n+2} M_{n-2}$$The Motzkin numbers can be expressed in terms of binomial coefficients and Catalan numbers:$$M_n=\sum_{k=0}^{\lfloor n/2 \rfloor} \binom{n}{2k} C_k\\ C_{n+1}=\sum_{k=0}^n \binom{n}{k} M_k$$The generating function for the Motzkin numbers is given by:$$ \frac{1-x-\sqrt{1-2x-3x^2} }{2x^2}$$I asked ChatGPT about them.

Q: Can you explain what Motzkin numbers are and give some simple examples of their usefulness.

A: Motzkin numbers, named after the mathematician Theodor Motzkin, are a sequence of numbers that count the number of ways to draw non-intersecting chords between n points on a circle. They are denoted by M(n).

The first few Motzkin numbers are:

M(0) = 1, M(1) = 1, M(2) = 2, M(3) = 4, M(4) = 9, M(5) = 21, M(6) = 51, M(7) = 127, M(8) = 323, M(9) = 835, M(10) = 2188

Motzkin numbers have a variety of applications in combinatorics, algebraic geometry, and physics. Here are some simple examples of their usefulness:

• Counting lattice paths: A lattice path is a path on a grid of integer points. The number of lattice paths from (0, 0) to (n, k) that only move up, down, or diagonally up and to the right, and never below the x-axis, is given by the Motzkin number M(k). 

• Counting RNA structures: RNA is a molecule that plays a key role in protein synthesis. The number of possible secondary structures for an RNA molecule of length n is given by the Motzkin number M(n -1). 

• Counting balanced chemical reactions: The number of balanced chemical reactions involving n molecules is given by the Motzkin number M(n -1). This can be useful in chemistry and chemical engineering. 

• Counting irreducible algebraic curves: An irreducible algebraic curve is a curve that cannot be expressed as the union of two smaller curves. The number of irreducible algebraic curves of degree n in projective space is given by the Motzkin number M(n -1). 

• Counting diagrams in knot theory: Knot theory is the study of mathematical knots. The number of diagrams that represent a knot with n crossings is given by the Motzkin number M(n -2).

These are just a few examples of the many applications of Motzkin numbers in various fields of mathematics and science.

The Motzkin numbers constitute OEIS A001006:

A001006

Motzkin numbers: number of ways of drawing any number of non-intersecting chords joining \(n\) (labeled) points on a circle.

The first few members, up to one million, are:

1, 1, 2, 4, 9, 21, 51, 127, 323, 835, 2188, 5798, 15511, 41835, 113634, 310572, 853467

The problem from the perspective of my diurnal age is that the last member occurred when I was 15511 days old and the next will occur if I were to reach 41835 days old, which is highly unlikely. I'm currently 27017 days old and a few days away from my 74th birthday. However, if reflections and rotations are allowed since, returning to Figures 1 and 2, the number 9 becomes 4 and the number 21 becomes 5. These are noticeably smaller.

These unlabeled Motzkin numbers constitute OEIS A175954:

A175954

Unlabeled (cyclic) Motzkin numbers: number of ways of drawing any number of nonintersecting chords joining n unlabeled points equally spaced on a circle, up to rotations of the circle.

The initial members, up to one million, are:

1, 1, 2, 2, 4, 5, 12, 19, 46, 95, 230, 528, 1320, 3219, 8172, 20714, 53478, 138635, 363486, 957858

However, these numbers again miss my possible forthcoming diurnal ages as there is a jump from 20714 to 53478. Ah well.

On Non-squashing Partitions

Back on the 19th June 2016, I created a blog post titled Partitions that finished with my saying that the post was "only the briefest of introductions to the topic". Since then I've not delved much deeper into partitions and today's number of 26303, representing my diurnal age, rekindled my interest. The number belongs to OEIS A089054:

A089054

Solution to the non-squashing boxes problem (version 1).

The comments say the following:

Given \(n\) boxes labeled \(1 \dots n\), such that box \(k\) weighs \(k\) grams and can support a total weight of \(k \) grams; \(a(n)\) = number of stacks of boxes that can be formed such that no box is squashed.

For 26303, the associated number of boxes is 40. However, let's start with a smaller number of boxes to illustrate what is going on. Figure 1 shows the example of four boxes:

Figure 1

For 4 boxes, there are 14 different ways of stacking boxes so that no box is squashed. See Figure 2.

Figure 2

Note that the null stack, where no boxes are used, is also counted. Up to 26303 (where we are dealing with 40 boxes), the sequence runs (beginning with \(n=0\):

1, 2, 4, 8, 14, 23, 36, 54, 78, 109, 149, 199, 262, 339, 434, 548, 686, 849, 1043, 1269, 1535, 1842, 2199, 2607, 3078, 3613, 4225, 4915, 5700, 6581, 7576, 8686, 9934, 11321, 12871, 14585, 16493, 18596, 20925, 23481, 26303, ...

The figure of 2 for \(n=1\) arises from the fact that there can be a single 1 box or the null box. There is a generating function that will yield these numbers: $$ \frac{B(x)-x}{(1-x)^2} \text{ where } B(x)=1 + \frac{x}{1-x} + \frac{\sum \limits_{k>=1} x^{3 \times 2^{k-1}}}{\prod \limits_{j=0 \dots k} (1-x^{2^j)}}$$Let's test this function out using \(k=1\):$$\begin{align} B(x)&=1+ \frac{x}{1-x}+\frac{x^3}{(1-x)(1-x^2)}\\ \\ \frac{B(x)-x}{(1-x)^2} &=\dfrac{1+ \dfrac{x}{1-x}+\dfrac{x^3}{(1-x)(1-x^2)}-x}{(1-x)^2} \end{align}$$

This does in fact produce the first term 1 because the Taylor series expansion is \(1+3x+6x^2+10x^3+\dots \) but the other coefficients are not relevant and it would be necessary to work out a new polynomial for the case of \(k=2\) and so on. A tedious procedure. Let's just assume it works.

Thus there are 26303 ways to stack 40 boxes so that there is no collapse. Examples are [39, 40], [1, 39, 40], [1, 2, 37, 40] and on and on and on. The whole business is explained in detail in this PDF file by Sloane and Sellers: 

https://arxiv.org/pdf/math/0312418.pdf 

but I haven't the mental stamina to get to the bottom of it all in this post. Suffice to say that I've reconnected with the topic of partitions. 

It should be noted that a traditional partition of 40 would be something like [1, 39] where the elements add to 40. The non-squashing partitions of 40 are different as we've seen and take forms like [39, 40], [1, 39, 40], [1, 2, 37, 40] etc. In these, the totals can be no more than 2 x 40 and so in fact range from 0 to 80. This means that for any number \(n\), the non-squashing partitions of \(n\) are particular partitions of all the numbers ranging from 0 to \(2n\).

To illustrate we can go back to the case of \(n=4\) and list the 14 non-squashing partitions of 4 as being (refer back to Figure 2): 

[4], [3, 4], [1, 3, 4], [1, 2, 4], [1, 4], [2, 4], [3], [2, 3], [1, 2, 3], [1, 3], [2], [1, 2], [1], [ ]

More on the Mathematics of Chess

Figure 1: Book Cover

On Sunday, 6 January 2019, I published a post titled The Mathematics of Chess in which I discussed the number 25480 as the number of ways to place 2 non-attacking amazons (superqueens) on an 16 x 16 board. In that post, I made reference to Vaclav Kotesovec's magnum opus Non-attacking Chess Pieces that I have in my Calibre Library. Today I am reminded of its existence yet again because my diurnal age is 25792 and this turns out to be a member of OEIS A035288: the number of ways to place a non-attacking white and black bishop on n x n chessboard. 25792 arises when n=13.

This is a variation on the problem of how to place two non-attacking bishops on an n X n board. This problem is normally colour agnostic as shown in Figure 2.

Figure 2: two non-attacking bishops on an
8 x 8 board with both of the same colour

However, in the case of OEIS A035288, the two bishops are distinguishable because one is white and the other black as shown in Figure 3.

Figure 3: two non-attacking bishops on an 8 x 8 board
but with one white and the other black

OEIS A172123 deals with the number of ways to place 2 non-attacking bishops on an n x n board, where the bishops are not distinguishable from each other. The members of OEIS A035288 are simply twice the value of those in OEIS A172123. In Vaclav's book, it is these situations (where the pieces are indistinguishable) that are investigated. Figure 4 shows the table from page 241 of the book. The value of 12896 x 2 = 25792.

Figure 4: table of values for different numbers of
non-attacking bishops on varying sized boards

The author also provides generating functions for the different number of bishops and differently sized boards. I've just shown the first five in Figure 5 (taken from page 240 of the book).

Figure 5: generating function for two to five non-attacking bishops

In the case of two indistinguishable bishops, the generating function of interest is:$$-\frac{2x^2 \, (x+1) \, (x+2)}{(x-1)^5}$$This generating function can be used to generate the members of OEIS A172123. This is shown in Figure 6 for members of the sequence up to and including 12896:

Figure 6: SageMathCell code generating members of sequence A172123

The OEIS entry also lists a simple formula for determining the members of the sequence. It is:$$a(n) = \frac{n \,(n - 1) \, (3n^2 - n + 2)}{6}$$There is also a recursion formula:$$a(n) = 5 \,a(n-1)-10\, a(n-2)+10 \, a(n-3)-5 \,a(n-4)+a(n-5)$$It was good to be reminded of Vaclav's impressive book again but I also have in my possession another book titled Across the Board: The Mathematics of Chessboard Problems by John J. Watkins.

Figure 7: Book Cover

As the author says in this introduction:

... this book is about the game board itself, the simple grid of squares that forms such a common feature of games played around the world, and, more importantly, about the mathematics that arises from such an apparently simple structure.

The book contains much of interest that hopefully I'll be able to write about in later posts. Vaclav's book is really a reference source for a huge range of non-attacking pieces on various sized boards but Watkins looks a limited number of situations in detail. Figure 8 shows the very first problem that he deals with: Guarini's Problem that dates from 1520.

Figure 8: Guarini's Problem requires the white
and black knights to exchange positions

One solution involves reducing the board to a graph so that the situation is revealed more clearly. This is shown in Figure 9.

Figure 9: Guarini's Problem as a Graph

The graph clearly shows that four steps are involved, each step involving each of the four knights to advance to the next node (either clockwise or anticlockwise). If anticlockwise, then the knight on a will move to d, the knight on c will move to b, the knight on d will move to a and the knight on b will move to c.

The Smallest Parts Partition Function

Today I turned 25773 days old and I felt it shouldn't pass without making mention of this number's connection to the Smallest Parts Partition Function. This function assigns to each natural number \(n\), another number which is the total of the smallest parts in all partitions of \(n\). Here is the mapping, from \(n=1\) up to \(n=30\):

1, 3, 5, 10, 14, 26, 35, 57, 80, 119, 161, 238, 315, 440, 589, 801, 1048, 1407, 1820, 2399, 3087, 3998, 5092, 6545, 8263, 10486, 13165, 16562, 20630, 25773, ...

Figure 1 shows the SageMath code that I wrote to generate this sequence, up to and including 25773. Here is the Permalink.

Figure 1: SageMath code to generate
Smallest Parts Partition Numbers

Here is the example given in the OEIS A092269 comments:

Partitions of 4 are [1, 1, 1, 1], [1, 1, 2], [2, 2], [1, 3], [4]. 

1 appears four times in [1, 1, 1, 1]

1 appears two times in [1, 1, 2]

2 appears two times in [2, 2]

1 appears once in [1, 3]

4 appears once in [4]

Thus a(4)=4+2+2+1+1=10

Figure 2 shows a plot of the values up to 25773:

Figure 2: plot of the Smallest Parts Partition Function

Like the partition function, there is a generating function but it's rather complicated and I won't include it here. However, it can be viewed in the OEIS comments. I just wanted to mention it because the next member of the sequence is 31897 which is a long way off. There are a number of academic papers about this function so it is a topic of serious mathematical interest.

The number of partitions from 1 to 30 are shown in the list below:

[1, 2, 3, 5, 7, 11, 15, 22, 30, 42, 56, 77, 101, 135, 176, 231, 297, 385, 490, 627, 792, 1002, 1255, 1575, 1958, 2436, 3010, 3718, 4565, 5604]

It's interesting to look at the ratio between the total value of the number of smallest parts and the number of partitions for numbers between 1 and 30. The results and a plot of these values can be found in Figure 3.

Figure 3

Polygonal Number Generating Function and Formula

Today my diurnal age is 25233, a number that happens to be a polygonal number, specifically a 32-gonal number. A WolframAlpha article states that the generating function for the n-gonal numbers is given by: $$G_n(x)= \frac{x \, [(n-3)x+1]}{(1-x)^3} $$ This means that for the 32-gonal numbers, the formula becomes: $$G_{32}(x)= \frac{x \, (33x+1)}{(1-x)^3}$$In WolframAlpha, the coefficients can then be identified using the series command:

In Sage, the Taylor series is generated using the code:

g(x)=x*(33*x+1)/(1-x)^3
g.taylor(x,0,15).coefficients()

When run, this code produces the following output:

In the case of the 36-gonal numbers, the formula for the n-th term is given by:$$a(n)=n(17n-16) $$The general formula for the n-th polygonal number is given by:$$a(n)=(P-2) \frac{n(n+1)}{2}-(P-3)n$$where \(P\) is the number of vertices of the polygon.

In the case of \(P=36 \) (our 36-gon), the formula becomes:$$34\frac{n(n+1)}{2}-33n=n(17n-16) $$Here's a video describing how the formula is derived:

Generating Functions

On March 22nd 2018, my number of the day was 25190 described as a member of OEIS A014334 whose terms arise from the exponential convolution of Fibonacci numbers with themselves. This meant the term arose from a generating function of a particular type, namely exponential. The term convolution means that the generating function is multiplied by itself to generate a new function. The first eleven terms of OEIS A014334 are 0, 0, 2, 6, 22, 70, 230, 742, 2406, 7782 and 25190. So how are these terms generated?

Firstly, we need to establish what the exponential generating function is for the Fibonacci numbers. It turns out to be: $$ \sum_{n=0}^{\infty} F_n \frac{t^n}{n!}$$ $$\text{where } F_n=\frac{\alpha^n-\beta^n}{\alpha-\beta} \text{ and } \alpha=\frac{1+\sqrt{5}}{2} \text{ and } \beta=\frac{1-\sqrt{5}}{2}$$
Now the convolution of the generating function with itself yields new terms that can be found from the original Fibonacci numbers. Let's define two exponential generating functions: $$ A(t)=\sum_{n=0}^{\infty} a_n \frac{t^n}{n!} \text{ and } B(t)=\sum_{n=0}^{\infty} b_n \frac{t^n}{n!}$$ $$ \text{then } A(t).B(t)=\sum_{n=0}^{\infty} \bigg(  \sum_{k=0}^{n} \binom{n}{k}.a_k.b_{n-k} \bigg) \frac{t^n}{n!}$$ Let's remember that \(a_n = b_n =F_n \) and so all the coefficients of this generating function can be found by setting \(n=0, 1, 2, 3, ... \). For example, when \( n=4 \) the coefficient is $$ \binom{4}{0}.F_0.F_4+\binom{4}{1}.F_1.F_3+\binom{4}{2}.F_2.F_2+\binom{4}{3}.F_3.F_1+\binom{4}{4}.F_4.F_0$$Remember that \( F_0=0, F_1=1, F_2=1, F_3=2, F_4=3 \) and so substituting these values, the coefficient becomes:$$1 \times 0 \times 3+4 \times 1 \times 2+6 \times 1 \times 1+4 \times 2 \times 1+1 \times 3 \times 0=22$$The magnitude of these coefficients rises quickly as sequence OEIS A014334 shows. So this is how the number 25190 can be calculated (by setting n=10).

REFERENCE: https://www.mathstat.dal.ca/FQ/Scanned/11-3/church.pdf