Pascal's Triangle (Sort of)

Most everyone here is familiar with Pascal's Triangle. It's formed by successive rows, where each element is the sum of its two upper-left and upper-right neighbors. Here are the first 5 rows (borrowed from Generate Pascal's triangle):

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


Collapse these rows to the left

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


Sort them in ascending order

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


Read this triangle by rows

[1, 1, 1, 1, 1, 2, 1, 1, 3, 3, 1, 1, 4, 4, 6 ...]


Given an input n, output the nth number in this series. This is OEIS 107430.

Rules

• You can choose either 0- or 1-based indexing. Please state which in your submission.
• The input and output can be assumed to fit in your language's native integer type.
• The input and output can be given by any convenient method.
• Either a full program or a function are acceptable. If a function, you can return the output rather than printing it.
• Standard loopholes are forbidden.
• This is so all usual golfing rules apply, and the shortest code (in bytes) wins.
• Very nice title! – Luis Mendo Feb 7 '18 at 14:29
• As per the OEIS link, the only change required to generate this sequence instead of a binomial coefficient is an integer division. That certainly falls under "trivial". – Peter Taylor Feb 7 '18 at 14:54
• @PeterTaylor This doesn't look like an obvious dupe to me. There are many other possible approaches which can lead to interesting golfing opportunities, especially for languages that don't have a binomial built-in. – Arnauld Feb 7 '18 at 15:09
• @PeterTaylor I'm not convinced this is a duplicate, either. So far, the MATL, JavaScript, and Pascal answers are rather different between the two challenges. However, since my vote is a hammer-open, I won't vote as yet. – AdmBorkBork Feb 7 '18 at 15:13
• Totally agree with @AdmBorkBork . So count me as reopen vote. That makes 3 now. How many votes are required for reopening? – Luis Mendo Feb 7 '18 at 15:16

JavaScript (ES6), 79 bytes

0-indexed.

f=(n,a=[L=1])=>a[n]||f(n-L,[...a.map((v,i)=>k=(x=v)+~~a[i-1-i%2]),L++&1?k:2*x])


Demo

f=(n,a=[L=1])=>a[n]||f(n-L,[...a.map((v,i)=>k=(x=v)+~~a[i-1-i%2]),L++&1?k:2*x])

console.log([...Array(79).keys()].map(n => f(n)).join(', '))

How?

f = (                       // f = recursive function taking:
n,                        //   n = target index
a = [L = 1]               //   a[] = current row, L = length of current row
) =>                        //
a[n] ||                   // if a[n] exists, stop recursion and return it
f(                        // otherwise, do a recursive call to f() with:
n - L,                  //   n minus the length of the current row
[                       //   an array consisting of:
...a.map((v, i) =>    //     replace each entry v at position i in a[] with:
k =                 //       a new entry k defined as:
(x = v) +           //       v +
~~a[i - 1 - i % 2]  //       either the last or penultimate entry
),                    //     end of map()
L++ & 1 ?             //     increment L; if L was odd:
k                   //       append the last updated entry
:                     //     else:
2 * x               //       append twice the last original entry
]                       //   end of array update
)                         // end of recursive call


This algorithm directly generates the sorted rows of Pascal's Triangle. It updates n according to the length of the previous row until a[n] exists. For instance, 6 iterations are required for n = 19:

 L | n  | a[]
---+----+------------------------
1 | 19 | [ 1 ]
2 | 18 | [ 1, 1 ]
3 | 16 | [ 1, 1, 2 ]
4 | 13 | [ 1, 1, 3, 3 ]
5 |  9 | [ 1, 1, 4, 4, 6 ]
6 |  4 | [ 1, 1, 5, 5, 10, 10 ]
^^

• Nice work. I'm not sure if I understand exactly how it works though. My attempt turned out to be much longer than yours. – kamoroso94 Feb 7 '18 at 16:24
• @kamoroso94 I've added an explanation. – Arnauld Feb 7 '18 at 16:58
• I love this! Really enjoyed figuring out what it was doing. – Shaggy Feb 7 '18 at 17:50

Octave, 46 bytes

@(n)(M=sort(spdiags(flip(pascal(n)))))(~~M)(n)


1-based.

Try it online!

Explanation

Consider n=4 as an example.

pascal(n) gives a Pascal matrix:

 1     1     1     1
1     2     3     4
1     3     6    10
1     4    10    20


The rows of the Pascal triangle are the antidiagonals of this matrix. So it is flipped vertically using flip(···)

 1     4    10    20
1     3     6    10
1     2     3     4
1     1     1     1


which transforms antidiagonals into diagonals.

spdiags(···) extracts the (nonzero) diagonals, starting from lower left, and arranges them as zero-padded columns:

 1     1     1     1     0     0     0
0     1     2     3     4     0     0
0     0     1     3     6    10     0
0     0     0     1     4    10    20


M=sort(···) sorts each column of this matrix, and assigns the result to variable M:

 0     0     0     1     0     0     0
0     0     1     1     4     0     0
0     1     1     3     4    10     0
1     1     2     3     6    10    20


Logical indexing (···)(~~M) is now used to extract the nonzeros of this matrix in column-major order (down, then across). The result is a column vector:

 1
1
1
1
···
10
10
20


Finally, the n-th entry of this vector is extracted using (···)(n), which in this case gives 1.

Python 2, 8678 72 bytes

-8 bytes thanks to Rod

g=lambda n,r=[1]:r[n:]and r[n/2]or g(n-len(r),map(sum,zip([0]+r,r+[0])))


Try it online!

Ungolfed

def g(n, row=[1]):
if n < len(row):
return row[n/2]
else:
next_row = map(sum, zip([0] + row, row + [0]))
return g(n - len(row), next_row)


Try it online!

The function recursively calculates the row of Pascal's Triangle. Given the current row as row, map(sum, zip([0] + row, row + [0])).
At each call n is reduced by the length of the current row. If the function arrives at the right row the nth lowest number of the row should be returned.
As the first half of a row is in ascending order and each row is symmetrical, the number is at index n/2 (0-indexed, integer division).

Wolfram Language (Mathematica), 55 bytes

The indexing is 1-based.

(##&@@@Sort/@Table[n~Binomial~k,{n,0,#},{k,0,n}])[[#]]&


Try it online!

Explanation

This is likely golfable, I am not a very experienced Mathematica user.

Table[n~Binomial~k,{n,0,#},{k,0,n}]


For each n ∈ [0, Input] ∩ ℤ, generate the table of binomials with each k ∈ [0, n] ∩ ℤ.

Sort/@


Sort each. Uses a shorthand to Map[function,object]function/@object.

(##&@@@...)[[#]]


Flatten the resulting list and retrieve the element whose index in the list is the input.

APL (Dyalog), 26 25 bytes

1 byte saved thanks to @ngn

{⍵⊃0~⍨∊(⍋⊃¨⊂)¨↓⍉∘.!⍨⍳1+⍵}


Try it online!

• {⍵[⍋⍵]} -> (⍋⊃¨⊂) – ngn Feb 7 '18 at 16:24

R, 58 bytes

function(n)(m=apply(outer(0:n,0:n,choose),1,sort))[m>0][n]


Try it online!

Computes n choose k for each n,k in [0,1,...,n] as a matrix, sorts the rows ascending(*), and removes the zeros, then selects the nth element.

(*) This also transforms them into columns but that's better since R stores a matrix as a vector columnwise, which allows us to index directly into it while preserving order.

Haskell, 143132125 123 bytes

((p>>=s.h)!!)
p=[1]:map(\r->zipWith(+)(0:r)(r++[0]))p
h r=splitAt(div(length r)2)r
s(a,b)=reverse b!a
(h:t)!b=h:(b!t)
x!_=x


The first line is a point-free function that takes an index (0-based) and returns the appropriate number in the sequence. Try it online!

This is my first ever Haskell program! I'm sure it can get much shorter. Tips are appreciated.

Saved 2 bytes thanks to nimi

Ungolfed

pascalRows = [1] : map (\row -> zipWith (+) (0:row) (row++[0])) pascalRows
halves row = splitAt (div (length row) 2) row
joinSorted (first, second) = interleave (reverse second) first
interleave [] _ = []
interleave longer shorter = (head longer) : (interleave shorter (tail longer))
f n = (concatMap (joinSorted.halves) pascalRows) !! n

• You still have i in function s, which was renamed to !, I guess. If you use an infix function you can drop the () around reverse b: s(a,b)=reverse b!a. – nimi Feb 7 '18 at 21:58
• @nimi Ah, thanks--I changed it on TIO but missed a spot on the code here. And thanks for the parentheses tip. – DLosc Feb 7 '18 at 22:27

Jelly, 13 bytes

0rcþZṢ€Ẏḟ0⁸ị


Try it online!

Using Uriel's Dyalog algorithm.

1-indexed.

Explanation:

0rcþZṢ€Ẏḟ0⁸ị
0r            Return inclusive range from 0 to n
         Call this dyad with this argument on both sides
þ           Outer product with this dyad
c             Binomial coefficient
Z        Zip
€      Call this link on each element
Ṣ        Sort
Ẏ     Concatenate elements
ḟ0   Remove 0s
⁸ị Take the nth element

• Could you add an explanation? I can't figure out what þ is doing here. – Shaggy Feb 7 '18 at 15:02
• @Shaggy It's outer product, I'll add an explanation. – Erik the Outgolfer Feb 7 '18 at 15:04

JavaScript (Node.js), 65 bytes

Not even an array is used. 0-indexed.

f=(n,i=0,g=x=>x?x*g(x-1):1)=>n>i?f(n-++i,i):g(i)/g(c=n>>1)/g(i-c)


Try it online!

Explanation:

f=(n,i=0,                 )=>                                     // Main Function
g=x=>x?x*g(x-1):1                                        // Helper (Factorial)
n>i?                                 // Is n > i?
f(n-++i,i):                      // If so, call function
// f(n-i-1, i+1) to skip
// . i+1 terms
g(i)/g(c=n>>1)/g(i-c) // If not, since sorting
// . the binomial coeffs
// . equals to writing
// . the first floor(i/2)
// . coefficients twice
// . each, so a shortcut


JavaScript, 57 bytes

f=(i,r=1)=>i<r?i>1?f(i-2,--r)+f(i<r?i:r-1,r):1:f(i-r,r+1)


0-indexed.

How does this come:

Step 0:

c=(i,r)=>i?r&&c(i-1,r-1)+c(i,r-1):1
f=(i,r=1)=>i<r?c(i>>1,r-1):f(i-r,r+1)


This code is easy to understand:

• function c calculate the Combination use formula: C(n,k) = C(n-1,k) + C(n-1,k-1); or 1 if k == 0 or k == n
• function f try to find out the row number and index in the row, and then call function c for getting the result.

Step 1:

c=(i,r)=>i>1?--r&&c(i-2,r)+c(i,r):1
f=(i,r=1)=>i<r?c(i,r):f(i-r,r+1)


In this step, we try to modify the call of function c to c(i,r) which makes it as same as parameter of f.

Step 2:

c=(i,r)=>i>1?--r&&c(i-2,r)+c(i<r?i:r-1,r):1
f=(i,r=1)=>i<r?c(i,r):f(i-r,r+1)


We test i<r for whether using function f or function c. That's why we musk keep i<r holds during recursion of function c.

Step 3:

f=(i,r=1)=>i<r?i>1?--r&&f(i-2,r)+f(i<r?i:r-1,r):1:f(i-r,r+1)


At this step, we merge these two function into one.

After some more golf, we finally got the answer described above.

f=(i,r=1)=>i<r?i>1?f(i-2,--r)+f(i<r?i:r-1,r):1:f(i-r,r+1)

for(i=0,x=1;x<10;x++) {
document.write('<p>')
for(j=0;j<x;j++,i++) document.write(<b>{f(i)}</b>) } p { text-align: center; } b { display: inline-block; width: 4ch; font-weight: normal; } Pascal, 373 bytes function t(n,k,r:integer):integer;begin if(n<k)then t:=r-1 else t:=t(n,k+r,r+1)end; function s(n,k:integer):integer;begin if(k=0)then s:=n else s:=s(n+k,k-1)end; function f(n,k:integer):integer;begin if((k<1)or(k>n))then f:=0 else if n=1 then f:=1 else f:=f(n-1,k-1)+f(n-1,k)end; function g(n:integer):integer;var k:integer;begin k:=t(n,0,1);g:=f(k,(n-s(0,k-1)+2)div 2)end;  g is the function. Try it online! • n=1 then can be n=1then. – Jonathan Frech Feb 7 '18 at 23:33 • SImilarly, it looks like if(k=0)then can become if k=0then. – Shaggy Feb 8 '18 at 12:43 • if some number always greater than 0, you should use word instead of integer. – tsh Feb 9 '18 at 6:59 Java 8, 187 bytes n->{int r=~-(int)Math.sqrt(8*n+1)/2+1,a[]=new int[r],k=r,x=0;for(;k-->0;a[k]=p(r,k))x+=k;java.util.Arrays.sort(a);return a[n-x];}int p(int r,int k){return--r<1|k<2|k>r?1:p(r,k-1)+p(r,k);}  Explanation: Try it online. n->{ // Method with integer as both parameter and return-type int r=~-(int)Math.sqrt(8*n+1)/2+1, // Calculate the 1-indexed row based on the input a[]=new int[r], // Create an array with items equal to the current row k=r, // Index integer x=0; // Correction integer for(;k-->0; // Loop down to 0 a[k]=p(r,k)) // Fill the array with the Pascal's Triangle numbers of the row x+=k; // Create the correction integer java.util.Arrays.sort(a); // Sort the array return a[n-x];} // Return the n-x'th (0-indexed) item in this sorted array // Separated recursive method to get the k'th value of the r'th row in the Pascal Triangle int p(int r,int k){return--r<1|k<2|k>r?1:p(r,k-1)+p(r,k);}  MATL, 11 bytes :qt!XnSXzG)  1-based. Explanation Consider input 4 as an example. ; is the row separator for matrices or column vectors. : % Implicit input: n. Push the row vector [1 2 ... n] S STACK: [1 2 3 4] q % Subtract 1, emlement-wise: gives [0 1 ... n-1] % STACK: [0 1 2 3] t! % Duplicate and transpose into a column vector % STACK: [0 1 2 3], [0; 1; 2; 3] Xn % Binomial coefficient, element-wise with broadcast. Gives an % n×n matrix where entry (i,j) is binomial(i,j), or 0 for i<j % STACK: [1 1 1 1; 0 1 2 3; 0 0 1 3; 0 0 0 1] S % Sort each column % STACK: [0 0 0 1; % 0 0 1 1; % 0 1 1 3; % 1 1 2 3] Xz % Keep only nonzeros. Gives a column vector % STACK: [1; 1; 1; 1; 1; 2; 1; 1; 3; 3] G) % Get the n-th element. Implicitly display % STACK: 1  Batch, 128 bytes @set/as=2,t=r=m=i=1 :l @if %1 geq %t% set/as+=r,t+=r+=1&goto l @for /l %%i in (%s%,2,%1)do @set/ar-=1,m=m*r/i,i+=1 @echo %m%  0-indexed. • Can you add an explanation, please? I can't quite follow the logic here. – AdmBorkBork Feb 7 '18 at 20:09 • @AdmBorkBork The first three lines calculate the row r and column %1-(s-2) of the %1th of the series. The fourth line then uses that to calculate the binomial coefficient (n k) = n!/(n-k)!k! = n(n-1)...(n+1-k)/(1)(2)...k = (n/1)((n-1)/2)...((n+1-k)/k). Where's MathJax when I need it? – Neil Feb 7 '18 at 20:25 APL (Dyalog Classic), 17 bytes ⎕⊃∊i!⍨,\⌊.5×i←⍳99  Try it online! 0-based indexing note that (49!98) > 2*53, i.e. the binomial coefficient 98 over 49 is greater than 253, so at that point Dyalog has already started losing precision because of IEEE floating point • I count 17 characters. In which encoding is that a mere 17 bytes? – Abigail Feb 8 '18 at 14:12 • @Abigail see here and here – ngn Feb 8 '18 at 15:25 05AB1E, 10 bytes 0-indexed ÝεDÝc{}˜sè  Try it online! Explanation Ý # push range [0 ... input] ε } # apply to each element DÝc # N choose [0 ... N] { # sort ˜ # flatten result to a list sè # get the element at index <input>  Jelly, 11 bytes Ḷc€Ṣ€Fḟ0ị@  Try it online! A monadic link taking the index and returning an integer - uses 1-based indexing. How? Performs the challenge pretty much just as it is written, just with more of the right of Pascal's triangle (zeros) which is then thrown away... Ḷc€Ṣ€Fḟ0ị@ - Link: integer, i e.g. 1 or 9 Ḷ - lowered range [0] [0,1,2,3,4,5,6,7,8]  - repeat left as right arg [0] [0,1,2,3,4,5,6,7,8] c€ - binomial choice for €ach [[1]] [[1,0,0,0,0,0,0,0,0],[1,1,0,0,0,0,0,0,0],[1,2,1,0,0,0,0,0,0],[1,3,3,1,0,0,0,0,0],[1,4,6,4,1,0,0,0,0],[1,5,10,10,5,1,0,0,0],[1,6,15,20,15,6,1,0,0],[1,7,21,35,35,21,7,1,0],[1,8,28,56,70,56,28,8,1]] Ṣ€ - sort €ach [[1]] [[0,0,0,0,0,0,0,0,1],[0,0,0,0,0,0,0,1,1],[0,0,0,0,0,0,1,1,2],[0,0,0,0,0,1,1,3,3],[0,0,0,0,1,1,4,4,6],[0,0,0,1,1,5,5,10,10],[0,0,1,1,6,6,15,15,20],[0,1,1,7,7,21,21,35,35],[1,1,8,8,28,28,56,56,70]] F - flatten [1] [0,0,0,0,0,0,0,0,1,0,0,0,0,0,0,0,1,1,0,0,0,0,0,0,1,1,2,0,0,0,0,0,1,1,3,3,0,0,0,0,1,1,4,4,6,0,0,0,1,1,5,5,10,10,0,0,1,1,6,6,15,15,20,0,1,1,7,7,21,21,35,35,1,1,8,8,28,28,56,56,70] ḟ0 - filter discard zeros [1] [1,1,1,1,1,2,1,1,3,3,1,1,4,4,6,1,1,5,5,111,1,6,6,15,15,21,1,7,7,21,21,35,35,1,1,8,8,28,28,56,56,70] ị@ - index into (sw@p args) 1 3 --------------^  Red, 206 bytes f: func[n][t: copy[[1]]l: 0 while[l < n][a: copy last t insert append a 0 0 b: copy[]repeat i k:(length? a)- 1[append b a/(i) + a/(i + 1)]append t reduce[b]l: l + k]foreach p t[sort p]pick split form t{ }n]  1-based Try it online! Explanation: f: func [n] [ t: copy [[1]] ; start with a list with one sublist [1] l: 0 ; there are 1 items overall while [l < n] [ ; while the number of items is less than the argument a: copy last t ; take the last sublist insert append a 0 0 ; prepend and append 0 to it b: copy [] ; prepare a list for the sums repeat i k: (length? a) - 1 [ ; loop throught the elements of the list append b a/(i) + a/(i + 1)] ; and find the sum of the adjacent items append t reduce [b] ; append the resulting list to the total list l: l + k ; update the number of the items ] foreach p t [sort p] ; sort each sublist v: pick split form t { } n ; flatten the list and take the n-th element ]  Perl, 48 bytes Includes +1 for p perl -pe '_-=$%until$_<++$%;$./=$_/--$%for 1..$_/2;$_=$.' <<< 19  Uses base 0 indexing. J, 46 41 bytes f=:](([-2!]){/:~@(i.!<:)@])[:<.2&!@,:^:_1  0-indexed Try it online! Notes: • <.2&!@,:^:_1 gives the relevant row number of Pascal's triangle by rounding down the inverse of y choose 2. • /:~@(i.!<:)@] calculates the row and sorts it. • [-2!] gives the index into the row. • Hello. Welcome to the site! This is a nice first answer :) – DJMcMayhem Feb 9 '18 at 7:05 Julia, 70 bytes f(x)=map(n->binomial(n-1,ceil(Int,x/2-(n^2-n)/4-1)),round(Int,√(x*2)))  1-based Explanation: it first find the row number, then the column number, then compute the binomial • Welcome to PPCG! – Martin Ender Feb 17 '18 at 9:19 • yeah thx happy face – Jimmy Chen Feb 17 '18 at 12:09 Jelly, 17 bytes 1+2\1,1j$\$Ð¡Ṣ€Ẏ⁸ị


Try it online!

Pyth, 15 bytes

@u+GSm.cHdhHhQY


0-indexed

Try it

Explanation

@u+GSm.cHdhHhQY
u          hQY   Reduce on [0, ..., input], starting with the empty list...
+G              ... append to the accumulator...
Sm.cHdhH      ... the sorted binomial coefficients.
@              Q  Take the 0-indexed element.


Clean, 80 bytes

import StdEnv

\n=flatten[sort[prod[j+1..i]/prod[1..i-j]\\j<-[0..i]]\\i<-[0..]]!!n


Try it online!

As a lambda function.

C (gcc), 140 bytes

F(n){n=n?n*F(~-n):1;}C(n,k){n=F(n)/F(k)/F(n-k);}f(n,j,k,c){for(c=j=0;j<n;j++)for(k=0;k<=j/2;k++)if(++c==n||j&1|k-j/2&&++c==n)return C(j,k);}


Try it online!

Ruby, 56 bytes

->n{a=0;n-=a until n<a+=1;[*2..a].combination(n/2).size}


0-based

First get the row and column in the triangle, then calculate the binomial coefficient corresponding to that position.

Try it online!

Actually, 8 bytes

Largely based on Jonathan Allan's Jelly answer. Uses 0-indexing.

;r♂╣♂SΣE


Try it online!

Ungolfing

          Implicit input n.
;         Duplicate n.
r        Lowered range. [0..n-1].
♂╣      Pascal's triangle row of every number.
♂S    Sort every row.
Σ   Sum each row into one array.
E  Get the n-th element of the array (0-indexed).
Implicit return.

• It's supposed to produce a single number; the nth in the series. This produces an array. – recursive Feb 9 '18 at 5:35
• Whoops. Fixed. Thanks @recursive – Sherlock9 Feb 9 '18 at 18:48

Coconut, 69 bytes

def g(n,r=[1])=r[n:]and r[n//2]or g(n-len(r),[*map((+),[0]+r,r+[0])])


Try it online!

Pari/GP, 47 bytes

n->concat([vecsort(Vec((1+x)^i))|i<-[0..n]])[n]


Try it online!