1
$\begingroup$

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.

$\endgroup$
9
  • 5
    $\begingroup$ That looks like oeis.org/A072704. $\endgroup$
    – Martin R
    Oct 19, 2021 at 10:43
  • 1
    $\begingroup$ @MattiP. 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. $\endgroup$ Oct 19, 2021 at 10:56
  • 2
    $\begingroup$ You seem to have come across the sequence at oeis.org/A072704 , as @MartinR has observed. I suspect there is no non-recursive formula because if there were one it would be likely to appear there. $\endgroup$ Oct 20, 2021 at 17:44
  • 1
    $\begingroup$ You don't sum them up! You read your numbers (the non-zero ones) one column at a time. (This isn't obvious if you haven't wasted too much time looking at OEIS.) $\endgroup$ Oct 20, 2021 at 19:47
  • 1
    $\begingroup$ @MichaelLugo holy cow, now I see it! It's exactly the same. Thanks! $\endgroup$ Oct 20, 2021 at 21:44

1 Answer 1

0
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.