# 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
. . .


[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! Commented Feb 7, 2018 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". Commented Feb 7, 2018 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. Commented Feb 7, 2018 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. Commented Feb 7, 2018 at 15:13
• Totally agree with @AdmBorkBork . So count me as reopen vote. That makes 3 now. How many votes are required for reopening? Commented Feb 7, 2018 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. Commented Feb 7, 2018 at 16:24
• @kamoroso94 I've added an explanation. Commented Feb 7, 2018 at 16:58
• I love this! Really enjoyed figuring out what it was doing. Commented Feb 7, 2018 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
Commented Feb 7, 2018 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.

# 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; } # Haskell, 143132125123 68 bytes import Data.List ((iterate(\r->zipWith(+)(0:r)r++[0])[1]>>=sort)!!)


A point-free function that takes an index (0-based) and returns the appropriate number in the sequence.

### Explanation

First, this lambda function takes a row of Pascal's triangle and generates the next row:

\r->zipWith(+)(0:r)$r++[0] \r-> -- Lambda function with single argument r :: [Int] (0:r) -- Prepend 0 to r r++[0] -- Append 0 to r zipWith(+)$        -- Zip those two lists on addition


Then our solution is

((iterate(...)[1]>>=sort)!!)
[1]             -- Starting with [1],
iterate(...)                -- apply the above function repeatedly
(               >>=sort)     -- Sort each row and flatten
(                        !!)  -- Given an integer N, get Nth element of that list


## Old solution

This was my first ever Haskell program! Back then, I said, "I'm sure it can get much shorter," and I was right. ;) At the time, not knowing that sort was an option, I implemented a series of functions to do the sorting by splitting each row in half, reversing the second part, and interleaving.

((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


Try it online!

• 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
Commented Feb 7, 2018 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. Commented Feb 7, 2018 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. Commented Feb 7, 2018 at 15:02
• @Shaggy It's outer product, I'll add an explanation. Commented Feb 7, 2018 at 15:04

# 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

• @Abigail see here and here
– ngn
Commented Feb 8, 2018 at 15:25

# 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


# 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. Commented Feb 7, 2018 at 23:33
• SImilarly, it looks like if(k=0)then can become if k=0then. Commented Feb 8, 2018 at 12:43
• if some number always greater than 0, you should use word instead of integer.
– tsh
Commented Feb 9, 2018 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. Commented Feb 7, 2018 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
Commented Feb 7, 2018 at 20: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.

# 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! Commented Feb 17, 2018 at 9:19
• yeah thx happy face Commented Feb 17, 2018 at 12:09

# J, 43 38 bytes

](([-2!]){/:~@(i.!<:)@])[:<.2&!@,:^:_1


Try it online!

0-indexed

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 :) Commented Feb 9, 2018 at 7:05
• Your current answer is actually 39 bytes, the f=: doesn't count per standard site rules. Here's one for 26 bytes Commented Apr 22, 2020 at 2:28

# Vyxal, 9 bytes

ʀƛʀƈs;f$i  Try it Online! No efficiency at all. 0-indexed. ʀ # 0...n ƛ ; # Mapped to... ʀ # 0...n ƈ # Binomial coefficient with n, vectorised s # Sort these f # Flatten$i # Index input into this.


# Thunno 2, 8 bytes

ĖDȷc€ṠḞi


Try it online!
or see the interpreter complaining (explained below)

#### Explanation

ĖDȷc€ṠḞi  # Implicit input
Ė         # Push [0..input]
Dȷc      # Outer product over ncr with itself
# NOTE: the interpreter actually tries to calculate all the
#       values: [0C0, 0C1, 0C2, ..., (input)C(input)], but
#       fails for the ones where r > n. It silently carries
#       on, ignoring those values, so we end up with input+1
#       rows of Pascal's triangle :D. However, if you add
#       the w (warnings) flag, you'll see all the errors
#       which were caught by the interpreter (link above)
€Ṡ    # Sort each row of the triangle
Ḟ   # Flatten the list of lists
i  # Index in using the input
# Implicit output


# VyxalM, 7 bytes

ƛʀƈs;fi


Try it Online!

#### Explanation

ƛʀƈs;fi  # Implicit input
ƛ   ;    # Map over [0..input]
ʀƈ      #  nCr with each of [0..that]
s     #  Sort the resulting list
f   # Flatten the list of lists
i  # Index in using the input
# Implicit output


# 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.

# 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. Commented Feb 9, 2018 at 5:35
• Whoops. Fixed. Thanks @recursive Commented Feb 9, 2018 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!