# 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 – Leaky Nun Jul 2 '17 at 15:25
• Can our submissions use 1-based indexing instead? – user41805 Jul 2 '17 at 15:29
• @KritixiLithos Sure. It will make me sad though. – Wheat Wizard Jul 2 '17 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 – user41805 Jul 2 '17 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. – Leaky Nun Jul 2 '17 at 15:40
• I see, nice abuse of broken behavior then, +1. – Wheat Wizard Jul 2 '17 at 15:41
• @EinkornEnchanter 0^0 is 1 in most programming languages. – Arnauld Jul 2 '17 at 17:06
• @Arnauld That doesn't make it true ;) – Wheat Wizard Jul 2 '17 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). – Arnauld Jul 2 '17 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? – Arnauld Jul 2 '17 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. – Wheat Wizard Jul 2 '17 at 23:18
• Not actually shorter, but it saves the space. :) – Dennis Jul 2 '17 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.