Pascal's Triangle (Sort of)

Question

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 code-golf so all usual golfing rules apply, and the shortest code (in bytes) wins.

Answer 1

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 ]
                        ^^

Answer 2

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.

Answer 3

Python 2, 86 78 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).

Answer 4

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.

Answer 5

APL (Dyalog), 26 25 bytes

1 byte saved thanks to @ngn

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

Try it online!

Answer 6

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.

Answer 7

Haskell, 143 132 125 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

Answer 8

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; }

Answer 9

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

Answer 10

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

Answer 11

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!

Answer 12

MATL, 11 bytes

:qt!XnSXzG)

1-based.

Try it online! Or verify all test cases.

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

Answer 13

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);}

Answer 14

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.

Answer 15

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 2⁵³, so at that point Dyalog has already started losing precision because of IEEE floating point

Answer 16

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>

Answer 17

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

Answer 18

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
]

Answer 19

Perl, 48 bytes

Includes +1 for p

perl -pe '$_-=$%until$_<++$%;$./=$_/--$%for 1..$_/2;$_=$.' <<< 19

Uses base 0 indexing.

Answer 20

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.

Answer 21

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

Answer 22

Jelly, 17 bytes

1+2\1,1j$$СṢ€Ẏ⁸ị

Try it online!

Answer 23

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.

Answer 24

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.

Answer 25

C (gcc), 140 123 bytes

• Saved 17 bytes thanks to ceilingcat.

F(n){n=n?n*F(~-n):1;}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 F(j)/F(k)/F(j-k);}

Try it online!

Answer 26

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.

Answer 27

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!

Answer 28

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!

Answer 29

Pari/GP, 47 bytes

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

Try it online!