2

I have been working on a problem recently that hinges on a closed form solution (or one that can be modified to be continuous) for the following problem. The function takes 4 parameters $n_1,k_1,n_2,k_2$ you calculate Pascal's triangle normally until you reach row $n_1$, and for that row everything right of column $k_1$ you replace with zeroes. After that you continue the Pascal's triangle algorithm. You go down $n_2$ rows and return column $k_2$.
Here is an example with the input: $n_1=4,k_1=2,n_2=3,k_2=4$

              1
            1   1
          1   2   1
        1   3   3   1
      1   4   6   0   0
    1   5  10   6   0   0   
  1   6  15  16   6   0   0
1   7  21  31 (22)  6   0   0
output: 22

Even if you don't know how to make a closed form function, any insight into the problem is appreciated. Thanks!

Evan Bialo
  • 41

2 Answers2

2

We're trying to find the number in the $n_1+n_2$-th row and $k_1+k_2$-th column of the modified Pascal's triangle. Let's call this number $F\left(n_1, k_1, n_2, k_2\right)$ I'll do this by taking the number in the original Pascal's triangle and subtracting $f\left(n_1, k_1, n_2, k_2\right)$ from it. Our job is to find $f$. Then, $$F\left(n_1, k_1, n_2, k_2\right)={{n_1+n_2}\choose{k_2}}-f\left(n_1, k_1, n_2, k_2\right)$$

Let's start by examining the example. Here's a display of the values of $f$, i.e. the difference between the original Pascal's triangle and our modified version.

              0
            0   0
          0   0   0
        0   0   0   0
      0   0   0   4   1
    0   0   0   4   5   1   
  0   0   0   4   9   6   1
0   0   0   4  13  15   7   1

Fixing $n_1$ and $k_1$, we see that $f$ sort of acts like Pascal's triangle in that $$f\left(n_2, k_2\right)+f\left(n_2, k_2+1\right)=f\left(n_2+1, k_2+2\right)$$ Interesting. Intuitively, this makes sense. The cell $(4, 3)$ is 4 less than usual, and $(4, 4)$ is 1 less than usual. It follows that the cell $(5, 4)$ should be 5 less than usual, just because that's how Pascal's triangle works.

Let's take it one step further and "dissect" this mangled Pascal's triangle for $f$. What happens if only $(4, 3)$ is replaced with 0? What about if only $(4, 4)$ is replaced with 0?

      4   0                             0   1
    4   4   0                         0   1   1 
  4   8   4   0                     0   1   2   1
4  12  12   4   0                 0   1   3   3   1
Only replacing (4, 3)             Only replacing (4, 4)

Well, I'll be darned! It looks like each number in row $n_1$ to the right of $k_1$ creates its own mini scaled-up Pascal's triangle, and they each add together to produce the triangle $f$.

Now let's generalise. Consider what happens when we replace $t_{n_1,k_1+i}$ with a zero. Then, another $n_2$ rows down and row $k_2$, the number is reduced by $${{n_1}\choose{k_1+1}}{{n_2}\choose{k_2-k_1-1}}$$ Generally speaking, replacing a number $i$ rows to the right of $\left(n_1, k_1\right)$ results in a difference of $${{n_1}\choose{k_1+i+1}}{{n_2}\choose{k_2-k_1-i-1}}$$ So, we can construct our final function as follows: $$F\left(n_1, k_1, n_2, k_2\right)={{n_1+n_2}\choose{k_2}}-\sum\limits_{i=0}^{n_1-k_1}{{n_1}\choose{k_1+i+1}}{{n_2}\choose{k_2-k_1-i-1}}$$ I'm not sure if there's a way to reduce this any farther. It looks like it works with the provided example, although I haven't tested it against other cases yet.

doobdood
  • 689
0

Here is an approach that might be useful to consider. This is based on a matrix multiplication scheme.

Consider building the Pascal triangle as a series of matrix multiplications. For example, a 4-layer Pascal triangle would be built up as (index=0 to index=3):

$$ \begin{bmatrix} 1 \\ 3 \\ 3 \\ 1 \\ \end{bmatrix} = \begin{bmatrix} 1 & 0 & 0\\ 1 & 1 & 0\\ 0 & 1 & 1\\ 0 & 0 & 1\\ \end{bmatrix} \begin{bmatrix} 1 & 0\\ 1 & 1\\ 0 & 1\\ \end{bmatrix} \begin{bmatrix} 1 \\ 1 \\ \end{bmatrix} \begin{bmatrix} 1 \\ \end{bmatrix} $$

Now, a useful observation is the following: Say layer 1, counting from the right, was altered. The matrices to the left of layer 1 are not changed, so their product remains the same.

In fact:

$$ \begin{bmatrix} 1 & 0 & 0\\ 1 & 1 & 0\\ 0 & 1 & 1\\ 0 & 0 & 1\\ \end{bmatrix} \begin{bmatrix} 1 & 0\\ 1 & 1\\ 0 & 1\\ \end{bmatrix} = \begin{bmatrix} 1 & 0 \\ 2 & 1 \\ 1 & 2 \\ 0 & 1 \\ \end{bmatrix} $$

Further note that this partial product matrix has entries which appear to be related to a 3-layer Pascal triangle (entries 1-2-1).

It may be possible to exploit this structure in a generalized way to obtain a solution.

I hope this helps.

ad2004
  • 1,698