I'd like to find the formula for this triangle number sequence.

Question

This is a numeric triangle that came up in a problem I'm trying to solve. I got this sequence using the brute force approach (Javascript):

function f(s, b){
  if(s == 0 || b == 0) return 0;
  if(s > b) return 0;
  if(s == 1 || b == 1 || b == s) return 1;

  let sum = 0;
  for(let i=0; i<Math.min(s, b); i++){
    sum += (i + 1) * f(s-i, b-s);
  }

  return sum;
}

Result for the first few numbers (10 x 10).

0 0 0 0 0 0 0 0 0 0 
0 1 1 1 1 1 1 1 1 1 
0 0 1 2 3 4 5 6 7 8 
0 0 0 1 3 5 8 12 16 21 
0 0 0 0 1 4 7 12 20 30 
0 0 0 0 0 1 5 9 16 28 
0 0 0 0 0 0 1 6 11 20 
0 0 0 0 0 0 0 1 7 13 
0 0 0 0 0 0 0 0 1 8 
0 0 0 0 0 0 0 0 0 1

I'm not very good at combinatorics (or math in general). I'd like to understand how I can change the brute force approach so that I can get the sequence without iterating all numbers from 0 to min(s, b). I've attempted building the sequence in many ways, but it's mostly by trying random multiplications and sums, so I don't think I'll end up having the correct formula soon with this approach.

Background (what I'm trying to achieve):

We are trying to build a structure that's made out of blocks. Each structure has s stacks of blocks, and the total number of blocks is b. The structure must be convex, not concave. The goal is to count how many different structures for each pair of s and b values can be built. For example, if the stack number is the same as the block number, we can only build one, because all blocks are being used for the base. If the block count is less than the stack count, we can build none. If s < b, then there are many ways to build a convex structure.

Answer 1

I was able to solve it. It requires two functions. I'm not sure about the function naming, and maybe it can be refactored into one function, but it works this way, and I was able to bring the complexity from $O(n^3)$ to $O(n^2)$, so I'm happy with it.

This is the C++ code:

ll dp(int s, int b) {
  if (s == 0 || b == 0) return 0;
  if (s > b) return 0;
  if (s == 1 || b == 1 || b == s) return 1;
  if (memo[s][b] != -1) return memo[s][b];
  ll result = dp(s, b - s) + 2 * dp(s - 1, b - 1) - dp(s - 2, b - 2);
  return memo[s][b] = result;
}

int calculate(int s, int b) {
  if (s == 1 || b == 1 || b == s) return 1;
  ll sum = 0;
  for (int i = 0; i < min(s, b); i++) {
    sum += (i + 1) * dp(s - i, b - s);
  }
  return (int)sum;
}

Then get the desired value (read the question statement to understand the problem) as calculate(3, 6) (i.e. ways to create a convex structure with 3 stacks and a total of 6 blocks).

Note: ll is typedef long long int ll;. The memo variable is for memoization.