# Lets make a triangle

Most people are familiar with Pascal's triangle.

    1
1 1
1 2 1
1 3 3 1
1 4 6 4 1


Pascal's triangle is an automaton where the value of a cell is the sum of the cells to the upper left and upper right. Now we are going to define a similar triangle. Instead of just taking the cells to the upper left and the upper right we are going to take all the cells along two infinite lines extending to the upper left and upper right. Just like Pascal's triangle we start with a single 1 padded infinitely by zeros and build downwards from there.

For example to calculate the cell denoted with an x

   1
1 1
2 2 2
4 5 5 4
x


We would sum the following cells

   .
. .
2 . 2
. 5 5 .
x


Making our new cell 14.

Given a row number (n), and distance from the left (r) calculate and output the rth non-zero entry from the left on the nth row. (the equivalent on Pascal's triangle is nCr). You may assume that r is less than n.

This is , the goal is to minimize the number of bytes in your solution.

# Test cases

0,0 -> 1
1,0 -> 1
2,0 -> 2
4,2 -> 14
6,3 -> 106


Here's the first couple rows in triangle form:

                  1
1   1
2   2   2
4   5   5   4
8  12  14  12   8
16  28  37  37  28  16
32  64  94  106 94  64  32
64  144 232 289 289 232 144 64
128 320 560 760 838 760 560 320 128

• OEIS A035002 Jul 2, 2017 at 15:25
• Can our submissions use 1-based indexing instead? Jul 2, 2017 at 15:29
• @KritixiLithos Sure. It will make me sad though. Jul 2, 2017 at 15:30

# Jelly, 18 17 bytes

SṚ0;+Sṭ
1WWÇ⁸¡ṪṙḢ


Uses 0-based indexing.

Try it online!

### How it works

1WWÇ⁸¡ṪṙḢ  Main link. Arguments: n, r

1          Set the return value to 1.
W         Wrap; yield [1].
W        Wrap; yield [[1]].
This is the triangle with one row.
Ç⁸¡     Call the helper link n times.
Each iteration adds one row to the triangle.
Ṫ    Tail; take the last array, i.e., the row n of the triangle.
ṙ   Rotate row n r units to the left.
Ḣ  Head; take the first element, i.e., entry r of row n.

SṚ0;+Sṭ    Helper link. Argument: T (triangle)

S          Take the column-wise sums, i.e., sum the ascending diagonals of the
centered triangle, left to right.
Ṛ         Reverse the array of sums. The result is equal to the sums of the
descending diagonals of the centered triangle, also left to right.
0;       Prepend a 0. This is required because the first element of the next row
doesn't have a descending diagonal.
S     Take the column-wise sum of T.
+      Add the ascending to the descending diagonals.


# Python 3, 72 bytes

1 byte thanks to Kritixi Lithos.

f=lambda n,r:n>=r>=0and(0**n or sum(f(i,r)+f(i,r+i-n)for i in range(n)))


Try it online!

• You can rearrange to get this: n>=r>=0and and save a byte Jul 2, 2017 at 15:36
• @EinkornEnchanter if n is 0, then it gives 1; otherwise, it gives 0. It is like n and ... or 1, but shorter. Jul 2, 2017 at 15:40
• I see, nice abuse of broken behavior then, +1. Jul 2, 2017 at 15:41
• @EinkornEnchanter 0^0 is 1 in most programming languages. Jul 2, 2017 at 17:06
• @Arnauld That doesn't make it true ;) Jul 2, 2017 at 17:08

# ES6, 80 78 bytes

p=(n,r,c=0)=>n?(o=>{while(n&&r<n)c+=p(--n,r);while(o*r)c+=p(--o,--r)})(n)||c:1


In action!

Two bytes thanks to Arnauld.

• You can save 2 bytes by using while(n&&r<n) and while(o*r). Jul 2, 2017 at 17:25
• This answer is perfectly valid. So, whoever downvoted it should definitely provide an explanation... Or can it be one of these weird automatic downvotes from Community? Jul 2, 2017 at 17:35

# PHP, 94 bytes

recursive way 0-indexed

function f($r,$c){for($s=$r|$c?$r<0?0:!$t=1:1;$t&&$r;)$s+=f($r-=1,$c)+f($r,$c-++$i);return$s;}


Try it online!

# PHP, 125 bytes

0-indexed

for(;$r<=$argv[1];$r++)for($z++,$c=~0;++$c<$z;$v+=$l)$x[$c]+=$t[+$r][$c]=$l=($v=&$y[$r-$c])+$x[$c]?:1;echo$t[$r-1][$argv[2]];


Try it online!

## PHP>=7.1, 159 bytes

0-indexed for rows over 50

for([,$m,$n]=$argv;$r<=$m;$r++)for($z++,$c=0;$c<$z;$v=bcadd($v,$l),$x[$c]=bcadd($x[$c],$l),$c++)$t[+$r][$c]=$l=bcadd(($v=&$y[$r-$c]),$x[$c])?:1;echo$t[$m][$n];


# Python 3, 61 bytes

f=lambda n,r:sum(f(k,r)+f(k,r+k-n)for k in range(n))or~n<-r<1


This returns True for base case (0, 0), which is allowed by default.

Try it online!

• ~n<-r<1 is quite clever, I spent a good 10 minutes trying to golf n>=r>=0. Jul 2, 2017 at 23:18
• Not actually shorter, but it saves the space. :) Jul 2, 2017 at 23:42

# Husk, 16 bytes

!!¡ȯSż+oΘ↔mΣT;;1


Try it online!

Same idea as Dennis' answer, but simpler indexing method.

# Pascal, 145 bytes

function f(n,k:integer):integer;var i,r:integer;begin r:=1-Ord((k<0)or(k>n));if n>0 then r:=0;for i:=1 to n do r:=r+f(n-i,k-i)+f(n-i,k);f:=r;end;


Try it online!

Uses the T(n, r) = T(n-1, r-1) + T(n-1, r) recursion.