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

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]

Community · Accepted Answer · 2020-06-17 09:04:33Z

8

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.

edited Jun 17, 2020 at 9:04

CommunityBot

1

answered Mar 16, 2017 at 15:59

Luis Mendo

105k9 gold badges135 silver badges372 bronze badges

\$\begingroup\$ Fatality! I can't cut my byte-count in half; a tip of the hat to you sir. \$\endgroup\$
– Magic Octopus Urn
Commented Mar 16, 2017 at 16:03
3

\$\begingroup\$ @carusocomputing Thanks :-) You know what they say about convolution... \$\endgroup\$
– Luis Mendo
Commented Mar 16, 2017 at 16:06

Add a comment |

Martin Ender · Accepted Answer · 2017-03-16 17:17:12Z

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.

Community · Accepted Answer · 2020-06-17 09:04:33Z

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.

Can't you simplify that to @(n)sum(spdiags(flip(tril(flip(pascal(n))))))? — Neil, Commented Mar 16, 2017 at 17:50

Neil · Accepted Answer · 2017-03-16 19:27:58Z

5

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.

edited Mar 16, 2017 at 19:27

answered Mar 16, 2017 at 17:03

Neil

177k12 gold badges74 silver badges281 bronze badges

Add a comment |

Arnauld · Accepted Answer · 2017-03-17 06:49:40Z

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

edited Mar 17, 2017 at 6:49

answered Mar 16, 2017 at 16:16

Arnauld

198k20 gold badges179 silver badges650 bronze badges

Add a comment |

Greg Martin · Accepted Answer · 2017-03-17 17:19:08Z

5

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

edited Mar 17, 2017 at 17:19

answered Mar 16, 2017 at 16:46

Greg Martin

16.2k4 gold badges21 silver badges72 bronze badges

Add a comment |

Magic Octopus Urn · Accepted Answer · 2017-03-16 19:29:11Z

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:

Then sums each row:

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]

-Å0 instead of >-Ý0* should work and € is not needed at the end. — Emigna, Commented Mar 16, 2017 at 16:34
Nice catches, I always forget about Å, smart! I kept "ctrl+f" for "identity list" or something like that on the info.txt heh... — Magic Octopus Urn, Commented Mar 16, 2017 at 16:42
Why does the transpose turn it from 13 x 5 to 5 x 11? Where'd the other two columns/rows go? — AdmBorkBork, Commented Mar 16, 2017 at 19:36

Jörg Hülsermann · Accepted Answer · 2017-07-08 12:23:00Z

4

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!

edited Jul 8, 2017 at 12:23

answered Mar 16, 2017 at 17:01

Jörg Hülsermann

13.3k3 gold badges15 silver badges36 bronze badges

\$\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
Commented Mar 16, 2017 at 18:36
\$\begingroup\$ It's nice when a correction turns out to be shorter :-) \$\endgroup\$
– Luis Mendo
Commented 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
Commented Mar 16, 2017 at 21:14
\$\begingroup\$ @Titus it was so nice too use array_column \$\endgroup\$
– Jörg Hülsermann
Commented Mar 16, 2017 at 23:22
\$\begingroup\$ Some day it will save bytes. \$\endgroup\$
– Titus
Commented Mar 17, 2017 at 9:54

Add a comment |

Dennis · Accepted Answer · 2017-03-16 18:49:00Z

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.

Community · Accepted Answer · 2020-06-17 09:04:33Z

2

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

edited Jun 17, 2020 at 9:04

CommunityBot

1

answered Mar 16, 2017 at 15:09

Uriel

13.2k4 gold badges17 silver badges45 bronze badges

Add a comment |

Rod · Accepted Answer · 2017-03-17 14:31:00Z

2

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

edited Mar 17, 2017 at 14:31

answered Mar 16, 2017 at 17:34

Rod

18.4k4 gold badges31 silver badges89 bronze badges

Add a comment |

Nick Hansen · Accepted Answer · 2017-03-20 13:03:27Z

2

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.

edited Mar 20, 2017 at 13:03

answered Mar 16, 2017 at 17:10

Nick Hansen

714 bronze badges

\$\begingroup\$ You can shorten the padding function# to r#n|d<-0<$[1..n]=d++r++d. \$\endgroup\$
– nimi
Commented 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
Commented Mar 16, 2017 at 19:59

Add a comment |

Tilman · Accepted Answer · 2021-11-24 22:02:11Z

2

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.

edited Nov 24, 2021 at 22:02

answered Mar 18, 2017 at 1:05

Tilman

215 bronze badges

Add a comment |

loopy walt · Accepted Answer · 2021-11-25 01:31:07Z

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.

alephalpha · Accepted Answer · 2021-11-25 01:42:34Z

0

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

edited Nov 25, 2021 at 1:42

answered Nov 25, 2021 at 1:30

alephalpha

50k7 gold badges68 silver badges182 bronze badges

Add a comment |

alephalpha · Accepted Answer · 2021-11-25 06:31:49Z

0

Wolfram Language (Mathematica), 40 bytes

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

Try it online!

edited Nov 25, 2021 at 6:31

answered Nov 25, 2021 at 6:09

alephalpha

50k7 gold badges68 silver badges182 bronze badges

Add a comment |

Stack Exchange Network

Pascal's Column Sums

Input

Output

Rules

Examples

16 Answers 16

MATL, 16 bytes

Explanation

CJam, 32 25 24 bytes

Explanation

Octave, 84 67 45 bytes

Explanation

JavaScript (ES6), 83 bytes

JavaScript (ES6), 90 87 86 84 82 bytes

Test cases

Mathematica, 59 57 bytes

05AB1E, 34 32 28 25 24 bytes

PHP, 119 bytes

Jelly, 12 bytes

How it works

Python 3, 201 184 bytes

Python 2, 140 137 bytes

Haskell, 118 112 104 bytes

Python 3.9+, 124 115 chars

Python 3, 100 bytes

Pari/GP, 31 bytes

Wolfram Language (Mathematica), 40 bytes

Your Answer

Not the answer you're looking for? Browse other questions tagged
code-golf
arithmetic
number-theory
or ask your own question.

Linked

Hot Network Questions

Pascal's Column Sums

Input

Output

Rules

Examples

16 Answers 16

MATL, 16 bytes

Explanation

CJam, 32 25 24 bytes

Explanation

Octave, 84 67 45 bytes

Explanation

JavaScript (ES6), 83 bytes

JavaScript (ES6), 90 87 86 84 82 bytes

Test cases

Mathematica, 59 57 bytes

05AB1E, 34 32 28 25 24 bytes

PHP, 119 bytes

Jelly, 12 bytes

How it works

Python 3, 201 184 bytes

Python 2, 140 137 bytes

Haskell, 118 112 104 bytes

Python 3.9+, 124 115 chars

Python 3, 100 bytes

Pari/GP, 31 bytes

Wolfram Language (Mathematica), 40 bytes

Your Answer

Sign up or log in

Post as a guest

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

Linked

Related

Hot Network Questions

Not the answer you're looking for? Browse other questions tagged
code-golf
arithmetic
number-theory
or ask your own question.