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\$
0

16 Answers 16

8
\$\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\$
2
  • \$\begingroup\$ Fatality! I can't cut my byte-count in half; a tip of the hat to you sir. \$\endgroup\$ Mar 16, 2017 at 16:03
  • 3
    \$\begingroup\$ @carusocomputing Thanks :-) You know what they say about convolution... \$\endgroup\$
    – Luis Mendo
    Mar 16, 2017 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\$
0
5
\$\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\$
1
  • \$\begingroup\$ Can't you simplify that to @(n)sum(spdiags(flip(tril(flip(pascal(n))))))? \$\endgroup\$
    – Neil
    Mar 16, 2017 at 17:50
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\$
0
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\$
0
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\$
6
  • 1
    \$\begingroup\$ -Å0 instead of >-Ý0* should work and is not needed at the end. \$\endgroup\$
    – Emigna
    Mar 16, 2017 at 16:34
  • 1
    \$\begingroup\$ And >F can be ƒ. \$\endgroup\$
    – Emigna
    Mar 16, 2017 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\$ Mar 16, 2017 at 16:42
  • \$\begingroup\$ I have only recently started to remember that they exist :) \$\endgroup\$
    – Emigna
    Mar 16, 2017 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\$ Mar 16, 2017 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\$
5
  • \$\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\$ Mar 16, 2017 at 18:36
  • \$\begingroup\$ It's nice when a correction turns out to be shorter :-) \$\endgroup\$
    – Luis Mendo
    Mar 16, 2017 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, 2017 at 21:14
  • \$\begingroup\$ @Titus it was so nice too use array_column \$\endgroup\$ Mar 16, 2017 at 23:22
  • \$\begingroup\$ Some day it will save bytes. \$\endgroup\$
    – Titus
    Mar 17, 2017 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\$
2
  • \$\begingroup\$ You can shorten the padding function# to r#n|d<-0<$[1..n]=d++r++d. \$\endgroup\$
    – nimi
    Mar 16, 2017 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, 2017 at 19:59
2
\$\begingroup\$

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.

\$\endgroup\$
1
\$\begingroup\$

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.

\$\endgroup\$
0
\$\begingroup\$

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}\$.

\$\endgroup\$
0
\$\begingroup\$

Wolfram Language (Mathematica), 40 bytes

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

Try it online!

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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