5
$\begingroup$

I was experimenting and I found this pattern:

Start with an (infinite) array with top row with all ones, and leftmost two columns also all ones.

$$ \begin{matrix} 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & \cdots \\ 1 & 1 & ? & ? & ? & ? & ? & ? & \cdots \\ 1 & 1 & ? & ? & ? & ? & ? & ? & \cdots \\ 1 & 1 & ? & ? & ? & ? & ? & ? & \cdots \\ 1 & 1 & ? & ? & ? & ? & ? & ? & \cdots \\ 1 & 1 & ? & ? & ? & ? & ? & ? & \cdots \\ 1 & 1 & ? & ? & ? & ? & ? & ? & \cdots \\ 1 & 1 & ? & ? & ? & ? & ? & ? & \cdots \\ \vdots & \vdots & \vdots & \vdots & \vdots & \vdots & \vdots & \vdots & \ddots \\ \end{matrix} $$

Then, to find the columns, starting from the top row, add numbers on the diagonal to the left:

$$ \begin{matrix} 1 & \color{blue}{1} & \color{blue}{1} & 1 & 1 & 1 & 1 & 1 & \cdots \\ \color{blue}{1} & 1 & \color{blue}{1+1} & ? & ? & ? & ? & ? & \cdots \\ 1 & 1 & ? & ? & ? & ? & ? & ? & \cdots \\ 1 & 1 & ? & ? & ? & ? & ? & ? & \cdots \\ 1 & 1 & ? & ? & ? & ? & ? & ? & \cdots \\ 1 & 1 & ? & ? & ? & ? & ? & ? & \cdots \\ 1 & 1 & ? & ? & ? & ? & ? & ? & \cdots \\ 1 & 1 & ? & ? & ? & ? & ? & ? & \cdots \\ \vdots & \vdots & \vdots & \vdots & \vdots & \vdots & \vdots & \vdots & \ddots \\ \end{matrix} $$ After this step, replace the numbers below the last one like this: $$ \begin{matrix} 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & \cdots \\ 1 & 1 & 2 & ? & ? & ? & ? & ? & \cdots \\ 1 & 1 & 2 & ? & ? & ? & ? & ? & \cdots \\ 1 & 1 & 2 & ? & ? & ? & ? & ? & \cdots \\ 1 & 1 & 2 & ? & ? & ? & ? & ? & \cdots \\ 1 & 1 & 2 & ? & ? & ? & ? & ? & \cdots \\ 1 & 1 & 2 & ? & ? & ? & ? & ? & \cdots \\ 1 & 1 & 2 & ? & ? & ? & ? & ? & \cdots \\ \vdots & \vdots & \vdots & \vdots & \vdots & \vdots & \vdots & \vdots & \ddots \\ \end{matrix} $$

Repeat:

$$ \begin{matrix} 1 & 1 & \color{red}{1} & \color{red}{1} & 1 & 1 & 1 & 1 & \cdots \\ 1 & \color{red}{1} & 2 & \color{red}{1+1} & ? & ? & ? & ? & \cdots \\ \color{red}{1} & 1 & 2 & \color{red}{1+1+1} & ? & ? & ? & ? & \cdots \\ 1 & 1 & 2 & ? & ? & ? & ? & ? & \cdots \\ 1 & 1 & 2 & ? & ? & ? & ? & ? & \cdots \\ 1 & 1 & 2 & ? & ? & ? & ? & ? & \cdots \\ 1 & 1 & 2 & ? & ? & ? & ? & ? & \cdots \\ 1 & 1 & 2 & ? & ? & ? & ? & ? & \cdots \\ \vdots & \vdots & \vdots & \vdots & \vdots & \vdots & \vdots & \vdots & \ddots \\ \end{matrix} $$

Replace:

$$ \begin{matrix} 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & \cdots \\ 1 & 1 & 2 & 2 & ? & ? & ? & ? & \cdots \\ 1 & 1 & 2 & 3 & ? & ? & ? & ? & \cdots \\ 1 & 1 & 2 & 3 & ? & ? & ? & ? & \cdots \\ 1 & 1 & 2 & 3 & ? & ? & ? & ? & \cdots \\ 1 & 1 & 2 & 3 & ? & ? & ? & ? & \cdots \\ 1 & 1 & 2 & 3 & ? & ? & ? & ? & \cdots \\ 1 & 1 & 2 & 3 & ? & ? & ? & ? & \cdots \\ \vdots & \vdots & \vdots & \vdots & \vdots & \vdots & \vdots & \vdots & \ddots \\ \end{matrix} $$

Repeat:

$$ \begin{matrix} 1 & 1 & 1 & \color{blue}{1} & \color{blue}{1} & 1 & 1 & 1 & \cdots \\ 1 & 1 & \color{blue}{2} & 2 & \color{blue}{1+2} & ? & ? & ? & \cdots \\ 1 & \color{blue}{1} & 2 & 3 & \color{blue}{1+2+1} & ? & ? & ? & \cdots \\ \color{blue}{1} & 1 & 2 & 3 & \color{blue}{1+2+1+1} & ? & ? & ? & \cdots \\ 1 & 1 & 2 & 3 & ? & ? & ? & ? & \cdots \\ 1 & 1 & 2 & 3 & ? & ? & ? & ? & \cdots \\ 1 & 1 & 2 & 3 & ? & ? & ? & ? & \cdots \\ 1 & 1 & 2 & 3 & ? & ? & ? & ? & \cdots \\ \vdots & \vdots & \vdots & \vdots & \vdots & \vdots & \vdots & \vdots & \ddots \\ \end{matrix} $$

Replace:

$$ \begin{matrix} 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & \cdots \\ 1 & 1 & 2 & 2 & 3 & ? & ? & ? & \cdots \\ 1 & 1 & 2 & 3 & 4 & ? & ? & ? & \cdots \\ 1 & 1 & 2 & 3 & 5 & ? & ? & ? & \cdots \\ 1 & 1 & 2 & 3 & 5 & ? & ? & ? & \cdots \\ 1 & 1 & 2 & 3 & 5 & ? & ? & ? & \cdots \\ 1 & 1 & 2 & 3 & 5 & ? & ? & ? & \cdots \\ 1 & 1 & 2 & 3 & 5 & ? & ? & ? & \cdots \\ \vdots & \vdots & \vdots & \vdots & \vdots & \vdots & \vdots & \vdots & \ddots \\ \end{matrix} $$

I guess you get the idea now. So after filling in the array, I got:

$$ \begin{matrix} 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & \cdots \\ 1 & 1 & 2 & 2 & 3 & 3 & 4 & ? & \cdots \\ 1 & 1 & \color{red}{2} & 3 & 4 & 5 & 7 & ? & \cdots \\ 1 & 1 & 2 & \color{red}{3} & 5 & 6 & 9 & ? & \cdots \\ 1 & 1 & 2 & 3 & \color{red}{5} & 7 & 10 & ? & \cdots \\ 1 & 1 & 2 & 3 & 5 & \color{red}{7} & 11 & ? & \cdots \\ 1 & 1 & 2 & 3 & 5 & 7 & \color{red}{11} & ? & \cdots \\ 1 & 1 & 2 & 3 & 5 & 7 & 11 & \color{red}{?} & \cdots \\ \vdots & \vdots & \vdots & \vdots & \vdots & \vdots & \vdots & \vdots & \ddots \\ \end{matrix} $$

So it looks like the numbers on the diagonal might be the prime numbers. But computing the next column destroys this hope:

$$ \begin{matrix} 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & \cdots \\ 1 & 1 & 2 & 2 & 3 & 3 & 4 & 4 & \cdots \\ 1 & 1 & \color{red}{2} & 3 & 4 & 5 & 7 & 8 & \cdots \\ 1 & 1 & 2 & \color{red}{3} & 5 & 6 & 9 & 11 & \cdots \\ 1 & 1 & 2 & 3 & \color{red}{5} & 7 & 10 & 13 & \cdots \\ 1 & 1 & 2 & 3 & 5 & \color{red}{7} & 11 & 14 & \cdots \\ 1 & 1 & 2 & 3 & 5 & 7 & \color{red}{11} & 15 & \cdots \\ 1 & 1 & 2 & 3 & 5 & 7 & 11 & \color{red}{15} & \cdots \\ \vdots & \vdots & \vdots & \vdots & \vdots & \vdots & \vdots & \vdots & \ddots \\ \end{matrix} $$

Writing out this sequence:

$$2, 3, 5, 7, 11, 15, \cdots $$

So my question is, what is this sequence, that mirrored the primes but then suddenly diverged?

$\endgroup$
4
  • 1
    $\begingroup$ Try to continue a few more terms, then oeis.org $\endgroup$ Commented Jun 3, 2015 at 1:17
  • 2
    $\begingroup$ oeis suggests that $a(n)$ is the number of partitions of $n$. $\endgroup$
    – user230734
    Commented Jun 3, 2015 at 1:20
  • 1
    $\begingroup$ Thank you! I will try to see why this is. ($1, 1, 2, 3, 5, 7, 11, 15, 22, 30, 42, \cdots$) I realize that I have unwisely ignored the first two $1$'s. $\endgroup$
    – Ant
    Commented Jun 3, 2015 at 1:39
  • 2
    $\begingroup$ @JohnChessant Check out the OEIS page oeis.org/A000041 and see Gary W. Adamson's comment (it starts with "Equals an infinite convolution product..."). His comment has this same table, so maybe you could get more information by contacting him if you need. $\endgroup$
    – TomGrubb
    Commented Jun 3, 2015 at 1:55

2 Answers 2

4
$\begingroup$

The entry in the $m$th row and $(n+1)$st column equals the number of partitions of $n$ into parts not exceeding $m$. In particular, the $m$th entry on the diagonal equals the number of partitions of $m$ (as noted by BoizWeir).

If $p(k,j)$ denotes the number of partitions of $k$ into parts not exceeding $j$, then sorting the partitions of $k$ by their largest part $i$ yields $$ p(k,j) = \sum_{i=1}^{\min\{j,k\}} p(k-i,i), $$ which matches the procedure you've used to construct the array (as do the initial conditions).

$\endgroup$
1
$\begingroup$

So after looking at the OEIS page (and the comment pointed out to me by @bburGsamohT), I think I have it figured out!

The comment defines the quantities (I have changed the variable names, though):

$$a_1 = \frac{1}{1-x}$$

$$a_2 = \frac{1}{1-x^2}$$

$$a_3 = \frac{1}{1-x^3}$$

$$a_4 = \frac{1}{1-x^4}$$

etc.

The key is that we can write these as series!

$$a_1 = \frac{1}{1-x} = 1+x+x^2+x^3+x^4+\cdots$$

$$a_2 = \frac{1}{1-x^2} = 1+x^2+x^4+x^6+x^8+\cdots$$

$$a_3 = \frac{1}{1-x^3} = 1+x^3+x^6+x^9+x^{12}+\cdots$$

$$a_4 = \frac{1}{1-x^4} = 1+x^4+x^8+x^{12}+x^{16}+\cdots$$

etc.

Then the coefficient of $x^n$ in the infinite product $a_1a_2a_3a_4\cdots$ is just the number of ways we can write the number $n$ as a sum:

$$n=x_1+2x_2+3x_3+4x_4+\cdots$$

where the $x_i$ are positive integers. (This results from multiplying out the infinite product.)

The array is actually constructed in such a way that the numbers on the diagonals (or rather, as the comment points out, the rows (which stabilize to longer and longer segments of the sequence)) exactly count the number of ways to write $n$ as the sum mentioned above.

But of course the infinite product mentioned earlier is a formula for the generating function of the partition numbers! Thus, equating coefficients, we find that the sequence from the array is the sequence of partition numbers. Q.E.D.

Thanks to all of you for the help!

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .