Well, here goes... this is LONG! I'm going to also give an explanation of the derivation, since you were asking for more "insight" into the problem.
OK, so you have the recurrence I gave.
\( a_1 = r_{1, 1} \)
\( a_n = \sum_{m=1}^{n-1} r_{n, m} a_m \).
If we expand a few terms, we get
\( a_2 = r_{2, 1} r_{1, 1} \)
\( a_3 = r_{3, 1} r_{1, 1} + r_{3, 2} r_{2, 1} r_{1, 1} \)
\( a_4 = r_{4, 1} r_{1, 1} + r_{4, 2} r_{2, 1} r_{1, 1} + r_{4, 3} r_{3, 1} r_{1, 1} + r_{4, 3} r_{3, 2} r_{2, 1} r_{1, 1} \)
\( a_5 = r_{5, 1} r_{1, 1} + r_{5, 2} r_{2, 1} r_{1, 1} + r_{5, 3} r_{3, 1} r_{1, 1} + r_{5, 3} r_{3, 2} r_{2, 1} r_{1, 1} + r_{5, 4} r_{4, 1} r_{1, 1} + r_{5, 4} r_{4, 2} r_{2, 1} r_{1, 1} + r_{5, 4} r_{4, 3} r_{3, 1} r_{1, 1} + r_{5, 4} r_{4, 3} r_{3, 2} r_{2, 1} r_{1, 1} \)
...
Looking at this, we see that the number of products in each \( a_n \) is 1, 1, 2, 4, 8, ... , or \( 2^{n-2} \) for \( n > 1 \). It is possible to prove this by considering how the above process works: each sum adds together the previous terms, which are themselves sums, thus the number of products in that sum should equal the sum of the numbers of products in the previous terms. That is,
\( PN_1 = 1 \)
\( PN_n = \sum_{m=1}^{n-1} PN_m \)
Taking the forward difference \( \Delta \) of that last equation gives
\( \Delta PN_n = \sum_{m=1}^{n} PN_m - \sum_{m=1}^{n-1} PN_m = PN_n \).
This kind of difference equation has as solutions \( PN_n = r 2^n + s \). We see that for the given initial conditions, i.e. \( PN_2 = 1 \) and \( PN_3 = 2 \), \( PN_n = 2^{n-2} \) for \( n > 1 \).
Now, we move on to consider the number of factors in each product. Counting them, we see that
n = 1: 1
n = 2: 2
n = 3: 2, 3
n = 4: 2, 3, 3, 4
n = 5: 2, 3, 3, 4, 3, 4, 4, 5
...
Looking at the formula, we see the nth term should be the concatenation (due to the sum) of the previous terms with their elements each incremented by 1 (due to the multiplication of a new \( r_{n, m} \) factor.). That is,
\( PFN_n = \mathrm{incr}(PFN_1) + \mathrm{incr}(PFN_2) + ... + \mathrm{incr}(PFN_{n-1}) = \sum_{m=1}^{n-1} \mathrm{incr}(PFN_m) \).
(where the "+" are actually string concatenations. Formally, \( PFN_n \in \mathbb{N}* \).)
We can "refactor" this process by noting that the "increment" "distributes" over the concatenation, so
\( PFN_n = \sum_{m=1}^{n-1} \mathrm{incr}(PFN_m) = \mathrm{incr}\left(\sum_{m=1}^{n-1} PFN_m\right) \).
Now, we know that the previous term is also an "incremented concatenation" of the terms before it, thus if we decremented that term and then concatenated itself to that, we would have the concatenation of all terms before \( PFN_n \), and thus
\( PFN_n = \mathrm{incr}(\mathrm{decr}(PFN_{n-1}) + PFN_{n-1}) = PFN_{n-1} + \mathrm{incr}(PFN_{n-1}) \)
i.e. the sequence can be formed by taking the previous term, incrementing all its elements, and then concatenating it to the unincremented version, which is also easily observable from the pattern, but this gives a kind of "proof".
Anyway, by looking at the dictionary of integer sequences at oeis.org, I found that these strings appear within the sequence of "binary weights of n", the number of 1 bits in an integer. Looking at it, it appears element j (first is j = 1) of \( PFN_n \) is given by the number of 1 bits in \( 2^{n-1} + 2j - 1 \). This can be written explicitly. Note that \( \lfloor\frac{N}{2^k}\rfloor \) is a "lossy right shift" of \( N \) (i.e. shift right k bits, knock off everything past the binary point, like the ">>" operation in the C programming language.). Then, we can get the kth bit (0th is the LSB) of \( N \) as \( \lfloor\frac{N}{2^k}\rfloor - 2\lfloor\frac{N}{2^{k+1}}\rfloor \). The second term is a lossy right shift by k+1 bits followed by a left shift by 1 bit, which is like the right shift by k bits but with its LSB cleared. So we can add up all the bits in \( N \) (thus giving the number of 1 bits) by \( \sum_{i=0}^{\lfloor\log_2(N)\rfloor} \lfloor\frac{N}{2^i}\rfloor - 2\lfloor\frac{N}{2^{i+1}}\rfloor \). Taking \( N = 2^{n-1} + 2j - 1 \) and noting that the first and last bit are always 1 (by virtue of \( 2^{n-1} \) and note also that this is always odd as \( 2^{n-1} \) is even and \( 2j - 1 \) is odd, and even + odd = odd), we get \( {(PFN_n)}_j = 2 + \sum_{i=0}^{\lfloor\log_2(j)\rfloor} \lfloor\frac{j}{2^i}\rfloor - 2\lfloor\frac{j}{2^{i+1}}\rfloor \).
These connections to binary made me wonder about whether or not this whole thing could be interpreted in terms of binary. I noticed that the \( r_{n,m} \) are present at most only once in a product, i.e. there are no higher-degree \( r_{n,m} \) factors. And the indices, for the nth term of our original sequence, range from 1 to n. So I thought that each product could be represented as a binary nxn matrix with 1-bit elements, and we could look for patterns there. This led me to see part of, but not all of, the pattern.
However, the most fruitful way of viewing it, I found, was to arrange the terms and factors like this:
where the value of each term can be found by multiplying the columns' elements together and then adding up the results.
We can now see an interesting alternating pattern... which looks like binary counting! We see that the factors appear and disappear as the bits of \( 2^{n-1} + 2j - 1 \), which also explains the "number of 1 bits of \( 2^{n-1} + 2j - 1 \)" observation.
The left indices of the \( r_{n, m} \) in a product, then, are generated by acquiring the position of each one bit in \( 2^{n-1} + 2j - 1 \), with the LSB counted as position 1, and putting them in numerical order for convenience.
That is,
\( \mathrm{Left\ index\ of\ }k\mathrm{th\ factor\ of\ jth\ product\ in\ }n\mathrm{th\ term} = \mathrm{position\ of\ }k\mathrm{th\ 1\ bit\ in\ }2^{n-1} + 2j - 1\mathrm{,\ with\ the\ LSB\ counted\ as\ position\ 1} \).
Now for the right indices. If we look at them, they look like (here, for the 5th term)
The same "bit index" interpretation works here as well. Ignoring the last "1", these terms give the positions of 1 bits in \( 2j - 1 \). So, we have
\( \mathrm{Right\ index\ of\ }k\mathrm{th\ factor\ of\ jth\ product\ in\ }n\mathrm{th\ term} = \mathrm{if\ }k-1 > 0\mathrm{,\ position\ of\ }k-1\mathrm{th\ 1\ bit\ in\ }2j - 1\mathrm{,\ with\ the\ LSB\ counted\ as\ position\ 1,\ otherwise\ 1} \).
Then, the not-quite-symbolic but still "explicit" and "non-recursive" formula is
\( a_n = \sum_{j=1}^{2^{n-2}} \prod_{k=1}^{(\mathrm{number\ of\ 1\ bits\ in\ }2^{n-1} + 2j - 1)} r_{(\mathrm{position\ of\ }k\mathrm{th\ 1\ bit\ in\ }2^{n-1} + 2j - 1\mathrm{,\ with\ the\ LSB\ counted\ as\ position\ 1}),(\mathrm{if\ }k-1 > 0\mathrm{,\ position\ of\ }k-1\mathrm{th\ 1\ bit\ in\ }2j - 1\mathrm{,\ with\ the\ LSB\ counted\ as\ position\ 1,\ otherwise\ 1})} \).
OK, so you have the recurrence I gave.
\( a_1 = r_{1, 1} \)
\( a_n = \sum_{m=1}^{n-1} r_{n, m} a_m \).
If we expand a few terms, we get
\( a_2 = r_{2, 1} r_{1, 1} \)
\( a_3 = r_{3, 1} r_{1, 1} + r_{3, 2} r_{2, 1} r_{1, 1} \)
\( a_4 = r_{4, 1} r_{1, 1} + r_{4, 2} r_{2, 1} r_{1, 1} + r_{4, 3} r_{3, 1} r_{1, 1} + r_{4, 3} r_{3, 2} r_{2, 1} r_{1, 1} \)
\( a_5 = r_{5, 1} r_{1, 1} + r_{5, 2} r_{2, 1} r_{1, 1} + r_{5, 3} r_{3, 1} r_{1, 1} + r_{5, 3} r_{3, 2} r_{2, 1} r_{1, 1} + r_{5, 4} r_{4, 1} r_{1, 1} + r_{5, 4} r_{4, 2} r_{2, 1} r_{1, 1} + r_{5, 4} r_{4, 3} r_{3, 1} r_{1, 1} + r_{5, 4} r_{4, 3} r_{3, 2} r_{2, 1} r_{1, 1} \)
...
Looking at this, we see that the number of products in each \( a_n \) is 1, 1, 2, 4, 8, ... , or \( 2^{n-2} \) for \( n > 1 \). It is possible to prove this by considering how the above process works: each sum adds together the previous terms, which are themselves sums, thus the number of products in that sum should equal the sum of the numbers of products in the previous terms. That is,
\( PN_1 = 1 \)
\( PN_n = \sum_{m=1}^{n-1} PN_m \)
Taking the forward difference \( \Delta \) of that last equation gives
\( \Delta PN_n = \sum_{m=1}^{n} PN_m - \sum_{m=1}^{n-1} PN_m = PN_n \).
This kind of difference equation has as solutions \( PN_n = r 2^n + s \). We see that for the given initial conditions, i.e. \( PN_2 = 1 \) and \( PN_3 = 2 \), \( PN_n = 2^{n-2} \) for \( n > 1 \).
Now, we move on to consider the number of factors in each product. Counting them, we see that
n = 1: 1
n = 2: 2
n = 3: 2, 3
n = 4: 2, 3, 3, 4
n = 5: 2, 3, 3, 4, 3, 4, 4, 5
...
Looking at the formula, we see the nth term should be the concatenation (due to the sum) of the previous terms with their elements each incremented by 1 (due to the multiplication of a new \( r_{n, m} \) factor.). That is,
\( PFN_n = \mathrm{incr}(PFN_1) + \mathrm{incr}(PFN_2) + ... + \mathrm{incr}(PFN_{n-1}) = \sum_{m=1}^{n-1} \mathrm{incr}(PFN_m) \).
(where the "+" are actually string concatenations. Formally, \( PFN_n \in \mathbb{N}* \).)
We can "refactor" this process by noting that the "increment" "distributes" over the concatenation, so
\( PFN_n = \sum_{m=1}^{n-1} \mathrm{incr}(PFN_m) = \mathrm{incr}\left(\sum_{m=1}^{n-1} PFN_m\right) \).
Now, we know that the previous term is also an "incremented concatenation" of the terms before it, thus if we decremented that term and then concatenated itself to that, we would have the concatenation of all terms before \( PFN_n \), and thus
\( PFN_n = \mathrm{incr}(\mathrm{decr}(PFN_{n-1}) + PFN_{n-1}) = PFN_{n-1} + \mathrm{incr}(PFN_{n-1}) \)
i.e. the sequence can be formed by taking the previous term, incrementing all its elements, and then concatenating it to the unincremented version, which is also easily observable from the pattern, but this gives a kind of "proof".
Anyway, by looking at the dictionary of integer sequences at oeis.org, I found that these strings appear within the sequence of "binary weights of n", the number of 1 bits in an integer. Looking at it, it appears element j (first is j = 1) of \( PFN_n \) is given by the number of 1 bits in \( 2^{n-1} + 2j - 1 \). This can be written explicitly. Note that \( \lfloor\frac{N}{2^k}\rfloor \) is a "lossy right shift" of \( N \) (i.e. shift right k bits, knock off everything past the binary point, like the ">>" operation in the C programming language.). Then, we can get the kth bit (0th is the LSB) of \( N \) as \( \lfloor\frac{N}{2^k}\rfloor - 2\lfloor\frac{N}{2^{k+1}}\rfloor \). The second term is a lossy right shift by k+1 bits followed by a left shift by 1 bit, which is like the right shift by k bits but with its LSB cleared. So we can add up all the bits in \( N \) (thus giving the number of 1 bits) by \( \sum_{i=0}^{\lfloor\log_2(N)\rfloor} \lfloor\frac{N}{2^i}\rfloor - 2\lfloor\frac{N}{2^{i+1}}\rfloor \). Taking \( N = 2^{n-1} + 2j - 1 \) and noting that the first and last bit are always 1 (by virtue of \( 2^{n-1} \) and note also that this is always odd as \( 2^{n-1} \) is even and \( 2j - 1 \) is odd, and even + odd = odd), we get \( {(PFN_n)}_j = 2 + \sum_{i=0}^{\lfloor\log_2(j)\rfloor} \lfloor\frac{j}{2^i}\rfloor - 2\lfloor\frac{j}{2^{i+1}}\rfloor \).
These connections to binary made me wonder about whether or not this whole thing could be interpreted in terms of binary. I noticed that the \( r_{n,m} \) are present at most only once in a product, i.e. there are no higher-degree \( r_{n,m} \) factors. And the indices, for the nth term of our original sequence, range from 1 to n. So I thought that each product could be represented as a binary nxn matrix with 1-bit elements, and we could look for patterns there. This led me to see part of, but not all of, the pattern.
However, the most fruitful way of viewing it, I found, was to arrange the terms and factors like this:
Code:
r11
r21
r11
r31 r32
r21
r11 r11
r41 r42 r43 r43
r31 r32
r21 r21
r11 r11 r11 r11
r51 r52 r53 r53 r54 r54 r54 r54
r41 r42 r43 r43
r31 r32 r31 r32
r21 r21 r21 r21
r11 r11 r11 r11 r11 r11 r11 r11where the value of each term can be found by multiplying the columns' elements together and then adding up the results.
We can now see an interesting alternating pattern... which looks like binary counting! We see that the factors appear and disappear as the bits of \( 2^{n-1} + 2j - 1 \), which also explains the "number of 1 bits of \( 2^{n-1} + 2j - 1 \)" observation.
The left indices of the \( r_{n, m} \) in a product, then, are generated by acquiring the position of each one bit in \( 2^{n-1} + 2j - 1 \), with the LSB counted as position 1, and putting them in numerical order for convenience.
That is,
\( \mathrm{Left\ index\ of\ }k\mathrm{th\ factor\ of\ jth\ product\ in\ }n\mathrm{th\ term} = \mathrm{position\ of\ }k\mathrm{th\ 1\ bit\ in\ }2^{n-1} + 2j - 1\mathrm{,\ with\ the\ LSB\ counted\ as\ position\ 1} \).
Now for the right indices. If we look at them, they look like (here, for the 5th term)
Code:
11
211
311
3211
411
4211
4311
43211The same "bit index" interpretation works here as well. Ignoring the last "1", these terms give the positions of 1 bits in \( 2j - 1 \). So, we have
\( \mathrm{Right\ index\ of\ }k\mathrm{th\ factor\ of\ jth\ product\ in\ }n\mathrm{th\ term} = \mathrm{if\ }k-1 > 0\mathrm{,\ position\ of\ }k-1\mathrm{th\ 1\ bit\ in\ }2j - 1\mathrm{,\ with\ the\ LSB\ counted\ as\ position\ 1,\ otherwise\ 1} \).
Then, the not-quite-symbolic but still "explicit" and "non-recursive" formula is
\( a_n = \sum_{j=1}^{2^{n-2}} \prod_{k=1}^{(\mathrm{number\ of\ 1\ bits\ in\ }2^{n-1} + 2j - 1)} r_{(\mathrm{position\ of\ }k\mathrm{th\ 1\ bit\ in\ }2^{n-1} + 2j - 1\mathrm{,\ with\ the\ LSB\ counted\ as\ position\ 1}),(\mathrm{if\ }k-1 > 0\mathrm{,\ position\ of\ }k-1\mathrm{th\ 1\ bit\ in\ }2j - 1\mathrm{,\ with\ the\ LSB\ counted\ as\ position\ 1,\ otherwise\ 1})} \).
