Pascal's Rhombus

Question

Pascal's Rhombus (which is actually a triangle) is obtained by adding in the pattern:

  *
 ***
  x

instead of

* *
 x

This means that each cell is the sum of the three cells on the row directly above it and one cell on the row 2 above it. Just like Pascal's triangle the zeroth row has a single 1 on it that generates the triangle.

Here are the first couple of rows of Pascal's Rhombus

      1
    1 1 1
  1 2 4 2 1
1 3 8 9 8 3 1

Task

Given a row number (starting from the top) and an column number (starting from the first non-zero item on that row) output the value at that particular cell. Both inputs may be either 1 or 0 indexed (you may mix and match if you desire).

This is code-golf so you should aim to make the file size of your source code as a small as possible.

OEIS A059317

Answer 1

Haskell, 59 55 bytes

Pascal's Rhombus? More like Haskell's Rhombus! amiright?

4 bytes saved thanks to Ørjan Johansen

I thought I'd have a go at my own problem and practice my Haskell. Hopefully this will inspire more people to answer this.

1!1=1
n!k=sum[(n-2)!(k-2)+sum(map((n-1)!)[k-2..k])|n>1]

Try it online!

Explanation

This is a bit out of date with the latest golf

Instead of calculating

  *
 ***
  x

We calculate

*
***
  x

This slants our entire triangle to become

1
1 1 1
1 2 4 2 1
1 3 8 9 8 3 1

This lines up all of our rows making it easier to index the nth item of any column. We then define our base cases.

The zeroth row is all zeros so

0!_=0

There is a single 1 at position 1,1 so we define that

1!1=1

And we define the rest of the first row to be zeros as well

1!_=0

Then we define the general case recursively using the pattern described above:

n!k=(n-2)!(k-2)+(sum$map((n-1)!)[k-2..k])

Answer 2

Pascal, 122 bytes

Well, it's Pascal's rhombus.

_{37 bytes saved thanks to @manatwork}

function f(n,k:integer):integer;begin f:=1-Ord((k<0)or(k>n*2));if n>0then f:=f(n-1,k-2)+f(n-1,k-1)+f(n-1,k)+f(n-2,k-2)end;

Try it online!

Answer 3

PHP, 86 bytes

recursive way only the function row and column 0-Indexed

function f($r,$c){return$r|$c?$r<0?0:f($r-=1,$c)+f($r,$c-1)+f($r,$c-=2)+f($r-1,$c):1;}

Try it online!

PHP, 114 bytes

recursive way full program row and column 0-Indexed

<?=f(...$_GET);function f($r,$c){return$r|$c?$r<0|$c<0|$c>2*$r?0:f($r-=1,$c)+f($r,$c-1)+f($r,$c-=2)+f($r-1,$c):1;}

Try it online!

PHP, 129 bytes

row and column 0-Indexed

for(;$r<=$argv[1];$l=$t[+$r++])for($c=~0;$c++<$r*2;)$t[+$r][$c]=$r|$c?$t[$r-2][$c-2]+$l[$c]+$l[$c-1]+$l[$c-2]:1;echo$l[$argv[2]];

Try it online!

Answer 4

Jelly, 22 20 19 bytes

3ḶṚp@Ḣḣ4
Ḟ_ЀÇ߀ȯ¬S

Takes a 0-based index pair as command-line argument.

Try it online!

Answer 5

MATL, 22 20 19 bytes

Ti:"2Y6Y+FT_Y)]!i_)

Both inputs are 0-based.

Try it online!

Explanation

Let r and c denote the two inputs, specifying 0-based row and column respectively.

Each new row in Pascal's rhombus can be built from the matrix containing the previous two rows by convolving with the kernel [1 1 1; 0 1 0] and keeping the last two rows of the result swapped. This is done r times, starting from matrix 1.

It turns out to be shorter to use the kernel [0 1 0; 1 1 1; 0 1 0], which is a predefined literal. This produces an extra row, which will be discarded.

Consider for example r = 3, so there are 3 iterations.

1. Starting from

   1
   

   convolution with [0 1 0; 1 1 1; 0 1 0] gives

   0 1 0
   1 1 1
   0 1 0
   

   Keeping the last two rows (the whole matrix, in this case) and swapping them gives

   0 1 0
   1 1 1
   

2. Convolution of the above with [0 1 0; 1 1 1; 0 1 0] gives

   0 0 1 0 0
   0 1 1 1 0
   1 2 4 2 1
   0 1 1 1 0
   

   The matrix formed by the last two rows swapped is

   0 1 1 1 0
   1 2 4 2 1
   

   This contains the new row at the bottom, and the preceding one extended with zeros.

3. Convolving again yields

   0 0 1 1 1 0 0
   0 1 2 3 2 1 0
   1 3 8 9 8 3 1
   0 1 2 4 2 1 0
   

   Taking the last two rows swapped gives

   0 1 2 4 2 1 0
   1 3 8 9 8 3 1
   

After the r iterations have been done, the output is contained in the last row of the final matrix. For example, for c = 2 (0-based) the result would be 8. Instead of indexing the last row and the desired column, a trick can be used which exploits the symmetry of each row: the final matrix is transposed

0 1
1 3
2 8
4 9
2 8
1 3
0 1

and its -c-th element is taken. This uses linear indexing, that is, the matrix is indexed by a single index in column-major order. Since indexing is modular, the 0-entry is the lower-right corner (value 1) and the -2-th entry is two steps above (value 8).

T       % Push true
i       % Input row number
:"      % Do the following that many times
  2Y6   %   Push predefined literal [0 1 0; 1 1 1; 0 1 0]
  Y+    %   2D convolution, increasing size
  FT_   %   Push [0 -1]
  Y)    %   Matrix with rows 0 (last) and -1 (second-last), in that order
]       % End
!       % Transpose
i       % Input: colun number
_       % Negate
)       % Entry with that index. Implicitly display

Answer 6

Pari/GP, 60 bytes

i->j->polcoeff(Vec(1/(1-x*(1+y+y^2+x*y^2))+O(x^i++))[i],j,y)

Try it online!

Answer 7

Haskell, 74 bytes

0#0=1
n#m|m<=2*n&&m>=0=sum[(n-a)#(m-b)|(a,b)<-zip[2,1,1,1]$2:[0..2]]
n#m=0

Try it online!

Call with n # m, where n is the row and m is the column.

Answer 8

Mathematica, 56 bytes

If[#<1,Boole[##==0],Sum[#0[#-i,#2-j],{i,2},{j,2i-2,2}]]&

Pure function taking two integer arguments (row first, column second) and returning an integer. Works for negative integer arguments as well, returning 0. A pretty straightforward recursive structure: If[#<1,Boole[##==0],...] defines the base-case behavior for the 0th row (and above), while Sum[#0[#-i,#2-j],{i,2},{j,2i-2,2}] implements the recursive definition.

Answer 9

Python 2, 70 66 65 bytes

f=lambda n,k:(k==0)|sum(f(n+~j/3,k-j+j/3)for j in range(4)[:3*n])

Try it online!

Answer 10

JavaScript (ES6), 68 bytes

f=(y,x)=>x<0|x>y+y?0:x>0&x<y+y?f(--y,x)+f(y,--x)+f(y,--x)+f(--y,x):1

Answer 11

Mathematica, 53 bytes

D[1/(1-x(1+y+y^2(1+x))),{x,#},{y,#2}]/#!/#2!/.x|y->0&

Using the generating function.

Answer 12

Python 3, 75 Bytes

This is a recursive lambda that takes column and row as 0-indexed integers.

p=lambda r,c:(r<0 or((c==0)|p(r-1,c-2)+p(r-1,c)+p(r-1,c-1)+p(r-2,c-2))+1)-1

Here's a (slightly) more readable version with a printing function:

p = lambda r,c:(r<0 or ((c==0) | p(r-1,c-2)+p(r-1,c)+p(r-1,c-1)+p(r-2,c-2))+1)-1

def pp(r):
    ml = len(str(p(r,r)))+1
    for i in range(0, r):
            a=" "*ml*(r-i)
            for j in range(0,i*2 + 1):
                    a+=str(p(i,j))+(" "*(ml-len(str(p(i,j)))))
            print(a)

Answer 13

Python 3, 82 84 bytes

This is a recursive implementation with 1-indexed rows and columns. (Technically needs an f= in front, someone let me know if I should change it to 84 bytes. Still new and not 100% sure of the rules.)

This uses the recursive formula found on the OEIS page, but with the k's shifted one to the left to line up properly. Coincidently, sum(f(n-1,k-i)for i in(0,1,2)) is the same size as f(n-1,k)+f(n-1,k-1)+f(n-1,k-2). The whole function is the Python and or trick, where the first condition checks if k is inside the triangle and not on the boundary, in which case the recursive formula is used. If is isn't, the part after the or is returned, which checks if k is in (1, 2*n-1), i.e. on the boundary, returning True and False. k+1in(2,2*n) is one byte shorter than k in(1,2*n-1). Wrapping that in parentheses and putting a + in front converts to integer, which is what is needed.

f=lambda n,k:2*n-1>k>1and sum(f(n-1,k-i)for i in(0,1,2))+f(n-2,k-2)or+(k+1in(2,2*n))

Try it online!

Answer 14

Java (OpenJDK 8), 87 bytes

int f(int r,int c){return c<0|2*r<c?0:0<c&c<2*r?f(--r,c)+f(r,--c)+f(r,--c)+f(--r,c):1;}

Try it online!

At first, I was happy with my 160 bytes iterative method... Hmmm... let's just forget about it, OK?

Answer 15

Husk, 38 bytes

!!¡(S+o↔↑2Fz+§,ȯΘΘ←(moΣ↑_3ḣ→)↑_2)eḋ1ḋ7

Try it online!

Displays the infinite list, but somehow indexing into the list makes it time out.