Pascal's Column Sums

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

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 code-golf 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]

Answer 1

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.

• Magic Octopus Urn: Fatality! I can't cut my byte-count in half; a tip of the hat to you sir.
• Luis Mendo: @carusocomputing Thanks :-) You know what they say about convolution...

Answer 2

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.

Answer 3

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.

• Neil: Can't you simplify that to @(n)sum(spdiags(flip(tril(flip(pascal(n))))))?

Answer 4

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.

Answer 5

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

Answer 6

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}]&

Answer 7

05AB1E, (削除) 34 (削除ここまで) (削除) 32 (削除ここまで) (削除) 28 (削除ここまで) (削除) 25 (削除ここまで) 24 bytes

-4 thanks to Emigna.

FN©ƒ®Ne0})1®-Å0.ø ̃ ̈ˆ} ̄øO

Try it online!

---

FN©ƒ®Ne0}) # Generate, iteratively, the current pascal row, interspersed with 0's.
 1®-Å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]

• Emigna: -Å0 instead of >-Ý0* should work and € is not needed at the end.
• Emigna: And >F can be ƒ.
• Magic Octopus Urn: Nice catches, I always forget about Å, smart! I kept "ctrl+f" for "identity list" or something like that on the info.txt heh...
• Emigna: I have only recently started to remember that they exist :)
• AdmBorkBork: Why does the transpose turn it from 13 x 5 to 5 x 11? Where'd the other two columns/rows go?

Answer 8

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!

• Jörg Hülsermann: @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
• Luis Mendo: It's nice when a correction turns out to be shorter :-)
• Titus: 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.
• Jörg Hülsermann: @Titus it was so nice too use array_column
• Titus: Some day it will save bytes.

Answer 9

Jelly, 12 bytes

Ḷμc€j0ドルṚṙ"NS

Try it online!

How it works

Ḷμc€j0ドルṚṙ"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.
 j0ドル 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.

Answer 10

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

Answer 11

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 90o 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]]

Answer 12

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.

• nimi: You can shorten the padding function# to r#n|d<-0<$[1..n]=d++r++d.
• nimi: 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 #.

Answer 13

Python 3.9+, (削除) 124 (削除ここまで) 115 chars

s=range;f=lambda k:[sum([(q:=(lambda t:(k>(u:=n+x+t)>=0)*(t<1or u/t*q(~-t))))(x)for x in s(2*k)])for n in s(1-k,k)]

My previous answer didn't seem to work. Future me using python3.9+. The solution still uses the fact that the Pascal Triangle can be defined with binomial coefficents. Expanding it and defining the negatives as 0.

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.

Answer 14

Python 3, 100 bytes

f=lambda n,r=0:r and[r]+(n and[r+n[0]+(r==n[0])]+f(n[1:],n[0]))or(n*[1]and[1]+f(f(n-1)[2::2],1))+[1]

Try it online!

This is really ugly mostly because I mashed together two separate functions. The outer one gets selected when r=0. It recursively calls itself to generate the previous row and then does the following: Discard every other entry. Add a 1 at the end and the beginning. Then have the inner function: Fill the gaps with the sums of the neighbouring entries and if the middle entry was among the discarded ones increment it by one.

Answer 15

Pari/GP, 31 bytes

n->Vec(((y=1+x^2)^n-x^n)/(y-x))

Try it online!

The sum of first \$n\$ rows is the coefficients of the polynomial \$\frac{(x^2+1)^n-x^n}{x^2+1-x}\$.

Answer 16

Wolfram Language (Mathematica), 40 bytes

(((y=x^2+1)^#-x^#)/(y-x)+O@x^(2#))[[3]]&

Try it online!