29
\$\begingroup\$

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

We're going to take Pascal's Triangle and perform some sums on it (hah-ha). For a given input n, output the columnar sum of the first n rows of Pascal's Triangle. For example, for input 5, the output would be formed by

            1
          1   1
        1   2   1
      1   3   3   1
[+] 1   4   6   4   1
----------------------
    1 1 5 4 9 4 5 1 1

So the output would be [1, 1, 5, 4, 9, 4, 5, 1, 1].

Note that you don't necessarily need to generate Pascal's Triangle to calculate the summation - that's up to your implementation if it's shorter to do so or not.

Input

A single positive integer n with n >= 1 in any convenient format.

Output

The resulting array/list of the column-wise summation of the first n rows of Pascal's triangle, as outlined above. Again, in any suitable format.

Rules

  • Leading or trailing newlines or whitespace are all optional, so long as the characters themselves line up correctly.
  • Either a full program or a function are acceptable. If a function, you can return the output rather than printing it.
  • If possible, please include a link to an online testing environment so other people can try out your code!
  • Standard loopholes are forbidden.
  • This is so all usual golfing rules apply, and the shortest code (in bytes) wins.

Examples

[input]
[output]

1
[1]

2
[1, 1, 1]

3
[1, 1, 3, 1, 1]

5
[1, 1, 5, 4, 9, 4, 5, 1, 1]

11
[1, 1, 11, 10, 54, 44, 155, 111, 286, 175, 351, 175, 286, 111, 155, 44, 54, 10, 11, 1, 1]
\$\endgroup\$

13 Answers 13

7
\$\begingroup\$

MATL, 16 bytes

tZv=Gq:"t5BZ+]vs

Try it online!

Explanation

This repeatedly applies convolution to generate the rows. For example, for input n=5 we start with the first row

0 0 0 0 1 0 0 0 0

Convolving with [1 0 1] gives

0 0 0 1 0 1 0 0 0

Repeating the operation gives

0 0 1 0 2 0 1 0 0

then

0 1 0 3 0 3 0 1 0

etc. Concatenating these arrays vertically and computing the sum of each column gives the result.

t       % Input n implictly. Duplicate
Zv      % Symmetric range. Gives [1 2 3 4 5 4 3 2 1] for input 5
=       % Equal to (element-wise). Gives [0 0 0 0 1 0 0 0 0]. This is the first row
Gq:     % Push [1 2 ... n-1]
"       % For each. This executes the following code n-1 times
  t     %   Duplicate
  5B    %   Push 5 in binary, that is, [1 0 1]
  Z+    %   Convolution keeping size
]       % End
v       % Concatenate all results vertically 
s       % Sum. Display implicitly.
\$\endgroup\$
  • \$\begingroup\$ Fatality! I can't cut my byte-count in half; a tip of the hat to you sir. \$\endgroup\$ – Magic Octopus Urn Mar 16 '17 at 16:03
  • 3
    \$\begingroup\$ @carusocomputing Thanks :-) You know what they say about convolution... \$\endgroup\$ – Luis Mendo Mar 16 '17 at 16:06
5
\$\begingroup\$

CJam, 32 25 24 bytes

Thanks to Luis Mendo for saving 1 byte.

{(_0a*1+\{_(2$+.+}*]:.+}

Try it online!

Explanation

(       e# Decrement input N.
_0a*1+  e# Create a list of N-1 zeros and a 1. This is the top row with
        e# the required indentation.
\{      e# Run this block N-1 times.
  _     e#   Duplicate the last row.
  (     e#   Pull off a leading zero, shifting the row left.
  2$+   e#   Copy the full row and prepend that zero, shifting the row right.
  .+    e#   Element-wise addition, which results in the next row.
}*
]       e# Wrap all rows in a list.
:.+     e# Add up the columns by reducing element-wise addition over the rows.
\$\endgroup\$
5
\$\begingroup\$

JavaScript (ES6), 83 bytes

f=
n=>[...Array(n+--n)].map(g=(j=n,i,a)=>j--?g(j,i-1)+g(j,i+1)+(a?g(j,i,a):0):i-n?0:1)
<input type=number min=1 oninput=o.textContent=f(+this.value)><pre id=o>

1-indexing cost me a byte. Explanation: g(j-1,i-1)+g(j-1,i+1) recursively calculates Pascal's triangle until it reaches the first row, which is the base case. To obtain column sums, I use the fact that map actually passes a third parameter, so there is an extra recursive step when this is the case.

\$\endgroup\$
5
\$\begingroup\$

JavaScript (ES6), 90 87 86 84 82 bytes

Saved 3 bytes thanks to ETHproductions

f=(n,a=[1],b=a)=>n--?f(n,[...(F=x=>a.map((n,i)=>n+~~x[i-d]))(a,d=2),0,d=1],F(b)):b

Test cases

f=(n,a=[1],b=a)=>n--?f(n,[...(F=x=>a.map((n,i)=>n+~~x[i-d]))(a,d=2),0,d=1],F(b)):b

console.log(JSON.stringify(f(1)))
console.log(JSON.stringify(f(2)))
console.log(JSON.stringify(f(3)))
console.log(JSON.stringify(f(5)))
console.log(JSON.stringify(f(11)))

\$\endgroup\$
5
\$\begingroup\$

Mathematica, 59 57 bytes

Thanks to Martin Ender for finding a two-byte savings!

Binomial[i,(j+i)/2]~Sum~{i,Abs@j,b,2}~Table~{j,-b,b=#-1}&

Pure function taking a positive integer input and returning a list of integers. Literally produces all the relevant entries of Pascal's triangle and sums them appropriately.

Previous submission (which is a bit easier to read):

Table[Sum[Binomial[i,(j+i)/2],{i,Abs@j,b,2}],{j,-b,b=#-1}]&
\$\endgroup\$
4
\$\begingroup\$

Octave, 84 67 45 bytes

22 bytes saved thanks to Neil!

@(n)sum(spdiags(flip(tril(flip(pascal(n))))))

Try it online!

Explanation

The pascal function gives a matrix that contains the values in the Pascal triangle:

>> pascal(5)
ans =
     1     1     1     1     1
     1     2     3     4     5
     1     3     6    10    15
     1     4    10    20    35
     1     5    15    35    70

To extract the desired values we flip vertically (flip), keep the lower triangular part (tril ), and flip again. This gives

ans =
   1   1   1   1   1
   1   2   3   4   0
   1   3   6   0   0
   1   4   0   0   0
   1   0   0   0   0

spdiags then extracts the diagonals as columns

ans =
   1   1   1   1   1   0   0   0   0
   0   0   4   3   2   1   0   0   0
   0   0   0   0   6   3   1   0   0
   0   0   0   0   0   0   4   1   0
   0   0   0   0   0   0   0   0   1

and sum computes the sum of each column, which gives the result.

\$\endgroup\$
  • \$\begingroup\$ Can't you simplify that to @(n)sum(spdiags(flip(tril(flip(pascal(n))))))? \$\endgroup\$ – Neil Mar 16 '17 at 17:50
  • \$\begingroup\$ @Neil Yes! Thank you!! \$\endgroup\$ – Luis Mendo Mar 16 '17 at 18:02
4
\$\begingroup\$

05AB1E, 34 32 28 25 24 bytes

-4 thanks to Emigna.

FN©ƒ®Ne0})¹®-Å0.ø˜¨ˆ}¯øO

Try it online!


FN©ƒ®Ne0})               # Generate, iteratively, the current pascal row, interspersed with 0's.
          ¹®-Å0          # Calculate the number of zeros to middle pad it.
               .ø˜¨ˆ}¯øO # Surround with the zeros, transpose and sum.

Basically all it does is generate this:

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

Transpose it:

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

Then sums each row:

0
1
1
5
4
9
4
5
1
1
0

If a leading and trailing 0 are not acceptable, ®>-Å isntead of ®-Å fixes it for a +1 byte penalty.


Result for 50:

[0, 1, 1, 50, 49, 1224, 1175, 19551, 18376, 229125, 210749, 2100384, 1889635, 15679951, 13790316, 97994765, 84204449, 523088334, 438883885, 2421229251, 1982345366, 9833394285, 7851048919, 35371393434, 27520344515, 113548602181, 86028257666, 327340174085, 241311916419, 851817398634, 610505482215, 2009517658701, 1399012176486, 4313184213360, 2914172036874, 8448367214664, 5534195177790, 15139356846901, 9605161669111, 24871748205410, 15266586536299, 37524050574849, 22257464038550, 52060859526501, 29803395487951, 66492351226050, 36688955738099, 78239857877649, 41550902139550, 84859704298201, 43308802158651, 84859704298201, 41550902139550, 78239857877649, 36688955738099, 66492351226050, 29803395487951, 52060859526501, 22257464038550, 37524050574849, 15266586536299, 24871748205410, 9605161669111, 15139356846901, 5534195177790, 8448367214664, 2914172036874, 4313184213360, 1399012176486, 2009517658701, 610505482215, 851817398634, 241311916419, 327340174085, 86028257666, 113548602181, 27520344515, 35371393434, 7851048919, 9833394285, 1982345366, 2421229251, 438883885, 523088334, 84204449, 97994765, 13790316, 15679951, 1889635, 2100384, 210749, 229125, 18376, 19551, 1175, 1224, 49, 50, 1, 1, 0]
\$\endgroup\$
  • 1
    \$\begingroup\$ -Å0 instead of >-Ý0* should work and is not needed at the end. \$\endgroup\$ – Emigna Mar 16 '17 at 16:34
  • 1
    \$\begingroup\$ And >F can be ƒ. \$\endgroup\$ – Emigna Mar 16 '17 at 16:39
  • \$\begingroup\$ Nice catches, I always forget about Å, smart! I kept "ctrl+f" for "identity list" or something like that on the info.txt heh... \$\endgroup\$ – Magic Octopus Urn Mar 16 '17 at 16:42
  • \$\begingroup\$ I have only recently started to remember that they exist :) \$\endgroup\$ – Emigna Mar 16 '17 at 16:45
  • 1
    \$\begingroup\$ Why does the transpose turn it from 13 x 5 to 5 x 11? Where'd the other two columns/rows go? \$\endgroup\$ – AdmBorkBork Mar 16 '17 at 19:36
4
\$\begingroup\$

PHP, 119 bytes

columns numbers from 1-input to input -1

for(;$r<$argn;$l=$t[+$r++])for($c=-$r;$c<=$r;$c+=2)$s[$c]+=$t[+$r][$c]=$r|$c?$l[$c+1]+$l[$c-1]:1;ksort($s);print_r($s);

Try it online!

\$\endgroup\$
  • \$\begingroup\$ @LuisMendo Thank You I have found the error and it saves 3 Bytes. Now it works with PHP Versions greater 5.5 . array_column is a new function in this version \$\endgroup\$ – Jörg Hülsermann Mar 16 '17 at 18:36
  • \$\begingroup\$ It's nice when a correction turns out to be shorter :-) \$\endgroup\$ – Luis Mendo Mar 16 '17 at 19:24
  • \$\begingroup\$ Here are another 24 to 30 bytes: Save 13 bytes by swapping row and column count and dropping array_column(). $x=2*$j++-$i saves 7 bytes. Looping $j down instead of up can save 1 (for($j=$i+1;$j--;)). And 3 more bytes can be golfed from the output. \$\endgroup\$ – Titus Mar 16 '17 at 21:14
  • \$\begingroup\$ @Titus it was so nice too use array_column \$\endgroup\$ – Jörg Hülsermann Mar 16 '17 at 23:22
  • \$\begingroup\$ Some day it will save bytes. \$\endgroup\$ – Titus Mar 17 '17 at 9:54
3
\$\begingroup\$

Jelly, 12 bytes

Ḷµc€j€0Ṛṙ"NS

Try it online!

How it works

Ḷµc€j€0Ṛṙ"NS  Main link. Argument: k

Ḷ             Unlength; yield A := [0, ..., k-1].
 µ            New chain. Argument: A
  c€          Combinations each; compute nCr for each n and r in A, grouping by n.
    j€0       Join each resulting array [nC0, ..., nC(k-1)], separating by zeroes,
              yielding, [nC0, 0, ..., 0, nC(k-1)].
              Note that nCr = 0 whenever r > n.
       Ṛ      Reverse the resulting 2D array.
          N   Negate A, yielding [0, ..., -(k-1)].
        ṙ"    Zipwith rotate; for each array in the result to the left and the
              corresponding integer non-positive integer to the right, rotate
              the array that many units to the left.
           S  Take the columnwise sum.
\$\endgroup\$
2
\$\begingroup\$

Python 3, 201 184 bytes

def f(n):x,z,m=[1],[0],n-1;l=[z*m+x+z*m];exec("x=[*map(sum,zip(z+x,x+z))];l.append(z*(n-len(x))+[b for a in zip(x,z*len(x))for b in a][:-1]+z*(n-len(x)));"*m);return[*map(sum,zip(*l))]
\$\endgroup\$
2
\$\begingroup\$

Python 2, 140 137 bytes

n=input()
x=[]
a=[0]*n+[1]+n*[0]
z=n%2
exec'x+=[a];a=[(i%2^z)*sum(a[i-1:i+2])for i in range(2*n+1)];z^=1;'*n
print map(sum,zip(*x))[1:-1]

Try it online! or Try it online!

For n=3
Starts with a list with n zeros surround an one - [[0, 0, 0, 1, 0, 0, 0]]
Generate the full pyramid

[[0, 0, 0, 1, 0, 0, 0],
 [0, 0, 1, 0, 1, 0, 0],
 [0, 1, 0, 2, 0, 1, 0]]

Rotate 90º and sum each row, discarding the first and the last one (only zeros)

[[0, 0, 0],
 [0, 0, 1],
 [0, 1, 0],
 [1, 0, 2],
 [0, 1, 0],
 [0, 0, 1],
 [0, 0, 0]]
\$\endgroup\$
2
\$\begingroup\$

Haskell, 118 112 104 bytes

6 14 bytes saved thanks to @nimi

z=zipWith(+)
p n|n<2=[1]|m<-p(n-1)=z(0:0:m)(m++[0,0])            -- Generate the nth triangle row.
f n=foldl1 z[d++p x++d|x<-[1..n],d<-[0<$[1..n-x]]]  -- Pad each row with 0s and then sum all the rows.
\$\endgroup\$
  • \$\begingroup\$ You can shorten the padding function# to r#n|d<-0<$[1..n]=d++r++d. \$\endgroup\$ – nimi Mar 16 '17 at 17:36
  • \$\begingroup\$ Oh, now you can inline #, because it's not recursive anymore: define f as f n=foldl1 z[d++p x++d|x<-[1..n],d<-[0<$[1..n-x]]] and dump #. \$\endgroup\$ – nimi Mar 16 '17 at 19:59
1
\$\begingroup\$

Python 3, 124 chars

f=lambda n:[sum(map(lambda n,k:k<1or (2*k+n)*f(2*k+n-1,k-1)/k,[abs(x)]*n,range(n))[:(n+1-abs(x))/2]) for x in range(-n+1,n)]

This uses the fact that the Pascal Triangle can be defined with binomial coefficents. I tried removing the abs(x) and the range(-n+1,n) by making it range(n) and then using lambda l:l[-1:0:-1]+l but it was longer.

Also this is my first time golfing so I hope you forgive any faux-pas.

The binomial is not mine and was taken from here.

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.