Count occurrences in Pascal's Triangle

Question

Pascal's triangle is a triangular diagram where the values of two numbers added together produce the one below them.

This is the start of it:

You can see that the outside is all 1s, and each number is the sum of the two above it. This continues forever.

Your challenge is to count the number of times a value \$> 1\$ appears in Pascal's triangle.

For example, with the value 6:

       1
      1 1
     1 2 1
   1  3 3  1
  1 4  6  4 1
 1 5 10  10 5 1
1 6 15 20 15 6 1

It occurs three times. It will never occur more because after this, all numbers other than 1s will be greater than it.

As pointed out by tsh, this is A003016.

Scoring

This is code-golf, shortest wins!

Testcases

2 => 1
4 => 2
6 => 3
10 => 4
28 => 4
20 => 3
120 => 6

ovs · Accepted Answer · 2021-09-25 10:09:54Z

6

Gaia, 4 bytes

Full program. Doesn't work as a function because of the way it reuses the input.

K‡_C

Try it online!

K‡ Table of binomial coefficients, ‡ casts integer arguments to the range [1 .. x].
_ Flatten the table.
C count the number of occurences of the input in this list. C doesn't care about the order of arguments as long as one is a list and the other is not.

answered Sep 25, 2021 at 10:09

ovs

58.1k3 gold badges42 silver badges154 bronze badges

Add a comment |

caird coinheringaahin g · Accepted Answer · 2021-09-25 03:17:56Z

5

Jelly, 5 bytes

c€ŻFċ

Try it online!

How it works

c€ŻFċ - Main link. Takes n on the left
  Ż   - Range from zero; [0, 1, ..., n]
 €    - Over each integer 1 ≤ i ≤ n:
c     -   Calculate iCr for each r in [0, 1, ..., n]
   F  - Flatten
    ċ - Count occurrences of n

answered Sep 25, 2021 at 3:17

caird coinheringaahin g♦

49.4k11 gold badges121 silver badges348 bronze badges

1

\$\begingroup\$ Alternative 5 bytes. Chaining rules are actively blocking from saving a byte :/ \$\endgroup\$
– Bubbler
Sep 25, 2021 at 7:45

Add a comment |

G B · Accepted Answer · 2021-09-27 18:58:52Z

5

Ruby, 54 53 bytes

->n,*a{(0..n).sum{y=0;a.map!{|x|y+y=x}<<1;a.count n}}

Try it online!

Thanks Dingus for -1 byte

edited Sep 27, 2021 at 18:58

answered Sep 27, 2021 at 14:08

G B

21.3k1 gold badge19 silver badges51 bronze badges

Add a comment |

lyxal · Accepted Answer · 2021-09-25 01:28:31Z

4

Vyxal, 7 bytes

ƛɾƈ;f?O

Try it Online!

Basically, just generate Pascal's triangle (sans the first row of just 1) and get the count. Flagless just for Redwolf.

Explained

ƛɾƈ;f?O
ƛ  ;     # for each n in the range [1, input]:
 ɾƈ      #   n c x for x in range [1, n] - ʀƈ also works if you want the full row for some reason.
    f    # flatten that
     ?O  # and get the count of the input in that

edited Sep 25, 2021 at 1:28

answered Sep 25, 2021 at 1:16

lyxal

32.3k2 gold badges56 silver badges138 bronze badges

Add a comment |

pajonk · Accepted Answer · 2021-09-25 10:03:23Z

4

R, 41 bytes

Or R>=4.1, 34 bytes by replacing the word function with \.

function(n)sum(sapply(0:n,choose,0:n)==n)

Try it online!

answered Sep 25, 2021 at 10:03

pajonk

15.1k3 gold badges21 silver badges65 bronze badges

Add a comment |

Jitse · Accepted Answer · 2021-09-27 14:30:46Z

4

Python 3, 67 bytes

f=lambda n,*r:r.count(n)+(r<(n,)and f(n,*map(sum,zip(r,(1,*r))),1))

Try it online!

answered Sep 27, 2021 at 14:30

Jitse

6,8763 gold badges18 silver badges40 bronze badges

Add a comment |

Arnauld · Accepted Answer · 2021-09-27 15:58:30Z

4

JavaScript (ES6), 61 bytes

n=>eval("for(i=t=0;i++<=n;)for(q=j=1;q*=i-j,q/=j++;)t+=q==n")

Try it online!

Or 65 bytes for a BigInt version:

n=>eval("for(i=t=0n;i++<=n;)for(q=j=1n;q*=i-j,q/=j++;)q-n?t:++t")

Try it online!

edited Sep 27, 2021 at 15:58

answered Sep 25, 2021 at 9:15

Arnauld

188k20 gold badges171 silver badges631 bronze badges

\$\begingroup\$ Latest test case f(120) returns 5, not 6. Due to floating point inaccuracy I think. \$\endgroup\$
– Kjetil S
Sep 27, 2021 at 15:30
\$\begingroup\$ @KjetilS. This is actually an integer overflow. I've added a BigInt version for larger test cases. \$\endgroup\$
– Arnauld
Sep 27, 2021 at 15:59

Add a comment |

Axuary · Accepted Answer · 2021-10-31 21:58:43Z

4

Excel (Insider Beta), 59 55 bytes

-4 using COMBIN(x+y,y) instead of COMBIN(x,y) eliminates need for IF

=SUM(MAKEARRAY(A1,A1,LAMBDA(x,y,(COMBIN(x+y,y)=A1)*1)))

LAMBDA and MAKEARRAY are not in the current release of Excel Office 365.

Excel Office 365, 67 63 bytes

=LET(x,SEQUENCE(A1),y,TRANSPOSE(x),SUM((COMBIN(x+y,y)=A1)*1)))

Link to Spreadsheet

edited Oct 31, 2021 at 21:58

answered Sep 27, 2021 at 15:57

Axuary

3,4065 silver badges11 bronze badges

Add a comment |

user · Accepted Answer · 2021-09-25 01:30:24Z

Husk, 12 bytes

ṁ#¹↑¡Sż+Θ;1→

Try it online!

The last part of this answer (Sż+Θ;1) was copied verbatim from DLosc's clever answer to Generate Pascal's triangle. Go upvote that!

ṁ#¹↑¡Sż+Θ;1→
    ¡Sż+Θ;1  Generate Pascal's triangle (an infinite list)
         ;1  Start with the list [1]
    ¡        Repeatedly
        Θ    prepend 0 to the list,
      ż+     then add that to the original list,
      ż      keeping the last element of the new, longer list
   ↑         Take the first
           → n + 1 rows
ṁ            For each,
 #           find how many occurrences of
  ¹          the input they contain,
ṁ            then sum those counts

Luis Mendo · Accepted Answer · 2021-09-25 14:21:03Z

MATL, 6 bytes _{^{(using Pascal matrix)}}

t2YL=z

Try it online! Or verify all test cases.

How it works, using input 6 as an example:

t    % Implicit input. Duplicate
     % STACK: 6, 6
2YL  % Pascal matrix of that size
     % STACK: 6, [1   1   1   1   1   1
                  1   2   3   4   5   6
                  1   3   6  10  15  21
                  1   4  10  20  35  56
                  1   5  15  35  70 126
                  1   6  21  56 126 252]
=    % Test for equality, element-wise
     % STACK: [0 0 0 0 0 0
               0 0 0 0 0 1
               0 0 1 0 0 0
               0 0 0 0 0 0
               0 0 0 0 0 0
               0 1 0 0 0 0]
z    % Number of nonzeros. Implicit display
     % STACK: 3

MATL, 8 bytes _{^{(using binomial coefficients)}}

t:t!Xn=z

Try it online! Or verify all test cases.

How it works, using input 6 as an example:

t    % Implicit input. Duplicate
     % STACK: 6, 6
:    % Range. Gives a row vector
     % STACK: 6, [1 2 3 4 5 6]
t!   % Duplicate, transpose. Gives a column vector
     % STACK: 6, [1 2 3 4 5 6], [1
                                 2
                                 3
                                 4
                                 5
                                 6]
Xn   % Binomial coefficient, element-wise with broadcast. Gives a matrix
     % 6, [1  2  3  4  5  6
           0  1  3  6 10 15
           0  0  1  4 10 20
           0  0  0  1  5 15
           0  0  0  0  1  6
           0  0  0  0  0  1]
=    % Test for equality, element-wise
     % STACK: [0 0 0 0 0 1
               0 0 0 1 0 0
               0 0 0 0 0 0
               0 0 0 0 0 0
               0 0 0 0 0 1
               0 0 0 0 0 0]
z    % Number of nonzeros. Implicit display
     % STACK: 3

att · Accepted Answer · 2021-09-26 08:14:43Z

3

Wolfram Language (Mathematica), 32 bytes

Count[Binomial~Array~{#,#},#,2]&

Try it online!

answered Sep 26, 2021 at 8:14

att

19.8k2 gold badges14 silver badges56 bronze badges

Add a comment |

ZippyMagician · Accepted Answer · 2021-09-27 21:40:45Z

3

Dyalog APL, 11 10 bytes

Thanks to ovs for -1 byte

≢∘⍸⊢=⍳∘.!⍳

Try it online!

How it works:

         ⍳      Range [1, n]
      ∘.!      Outer product binomial with
     ⍳          Range [1, n]
    =          Equals
   ⊢            Right argument
 ⍸            Generate list of indices from truthy values
≢            Tally, get length

edited Sep 27, 2021 at 21:40

answered Sep 27, 2021 at 21:17

ZippyMagician

1,6317 silver badges11 bronze badges

1

\$\begingroup\$ ≢∘⍸⊢=⍳∘.!⍳ works for 10 bytes \$\endgroup\$
– ovs
Sep 27, 2021 at 21:33
\$\begingroup\$ Didn’t cross my mind I could use ⍸, thanks! \$\endgroup\$
– ZippyMagician
Sep 27, 2021 at 21:41

Add a comment |

coltim · Accepted Answer · 2021-10-02 15:03:01Z

K (ngn/k), 19 bytes

{+/,/x=x(+':|0,)\1}

Try it online!

x(+':|0,)\1 generate the first x+1 rows of Pascal's Triangle
- x(...)\1 run the code in (...) x times, seeded with 1, returning a list containing the original input and the results from each iteration
- (+':|0,) prepend a 0, then reverse the sequence. add each value to its predecessor
x= check where the original input appears in these rows
+/,/ flatten the rows into a single list, then take the sum

Traws · Accepted Answer · 2021-10-30 18:07:46Z

3

K (ngn/k), 15 bytes

{+//x=x+\\1+!x}

Try it online!

Different approach from @coltim, uses Pascal matrix.

Explanation:

{+//x=x+\\1+!x}
                / construct the pascal matrix:
      x  \      /  do x times saving intermediate results
       +\       /  cumulative sum
          1+!x  /  starting at the range [1,x]
    x=          / equals x?
 +//            / sum all elements in the binary matrix, giving the count

answered Oct 30, 2021 at 18:07

Traws

9014 silver badges8 bronze badges

Add a comment |

lyxal · Accepted Answer · 2021-09-25 03:29:57Z

2

Jelly, 7 bytes

ŻcŻ$€Fċ

Try it online!

A port of my Vyxal answer, and contains part of my Jelly answer to the "vanilla" pascal triangle generation.

(yes, this is the exact same as caird's answer but with an extra atom and quick because fgitw reasons)

Explained

ŻcŻ$€Fċ # A monadic chain with argument n. Let the current value be λ
Ż       # λ = [0, n]
    €   # over each item in λ:
 cŻ$    #   yield item choose [0, item] (vectorising)
     F  # flatten that
      ċ # and get the count of n

edited Sep 25, 2021 at 3:29

answered Sep 25, 2021 at 3:17

lyxal

32.3k2 gold badges56 silver badges138 bronze badges

Add a comment |

AZTECCO · Accepted Answer · 2021-09-25 18:28:16Z

2

Ruby, 67 bytes

->n{a=[1]
n.times{|x|a=[1]+(1..x).map{|y|a[y]+a[y-1]}+a}
a.count n}

Try it online!

answered Sep 25, 2021 at 18:28

AZTECCO

10.6k1 gold badge13 silver badges58 bronze badges

Add a comment |

Wasif · Accepted Answer · 2021-09-26 08:21:33Z

2

Python 3.8 (pre-release), 80 bytes

lambda n:sum(math.comb(x,z)==n for x in range(n+1)for z in range(x))
import math

Try it online!

edited Sep 26, 2021 at 8:21

answered Sep 26, 2021 at 7:45

Wasif

12.3k1 gold badge16 silver badges46 bronze badges

2

\$\begingroup\$ 69 bytes \$\endgroup\$
– att
Sep 27, 2021 at 21:36

Add a comment |

Kjetil S · Accepted Answer · 2021-09-27 15:42:21Z

2

Perl 5, 91 bytes

sub{($i,$c)=@_;for$r(1..$i+1){$n=1;map$c+=$i-~~($n*=$r/$_-1)?0:$_>$r/2-1?1:2,1..$r/2-.5}$c}

Try it online!

edited Sep 27, 2021 at 15:42

answered Sep 27, 2021 at 15:22

Kjetil S

5,4879 silver badges17 bronze badges

Add a comment |

Yousername · Accepted Answer · 2021-09-28 01:25:53Z

2

TI-Basic, 27 bytes

Input N
For(I,2,N
Ans+sum(N=I nCr seq(J,J,0,I
End

Output is stored in Ans.

edited Sep 28, 2021 at 1:25

answered Sep 28, 2021 at 1:11

Yousername

3,6509 silver badges24 bronze badges

Add a comment |

alephalpha · Accepted Answer · 2021-11-02 10:22:14Z

2

Pari/GP, 38 bytes

n->sum(i=0,n,#[1|j<-binomial(i),j==n])

Try it online!

When binomial takes only one argument, it returns the n'th row of the Pascal's triangle.

edited Nov 2, 2021 at 10:22

answered Sep 26, 2021 at 2:17

alephalpha

46.5k7 gold badges61 silver badges172 bronze badges

Add a comment |

Kevin Cruijssen · Accepted Answer · 2022-02-04 13:49:02Z

05AB1E, 7 5 bytes

δc˜I¢

Try it online or verify all test cases.

Explanation:

δc   # Create a binomial coefficients table:
δ    #  Apply double-vectorized:
     #  (which implicitly converts the implicit input-integer to the range
     #  [1,input] first, used twice)
 c   #   Binomial coefficient
˜I¢  # Count the amount of times the input occurs in this matrix:
˜    #  Flatten the matrix to a single list
 I¢  #  Count how many times the input is in this list
     # (after which the result is output implicitly)

Neil · Accepted Answer · 2021-10-03 09:19:07Z

Charcoal, 32 bytes

Ｎθ⊞υ¹≔⁰ηＦθ«⊞υ⁰ＵＭυ⁺κ§υ⊖λ≧⁺№υθη»Ｉη

Try it online! Link is to verbose version of code. Explanation:

Ｎθ

Input the target n.

⊞υ¹

Start with the 0th row of Pascal's triangle.

≔⁰η

Start with 0 occurrences of n.

Ｆθ«

Loop n times.

⊞υ⁰

Append a 0 to the row.

ＵＭυ⁺κ§υ⊖λ

For each element, add the original previous element to it. (Due to cyclic indexing, the 0 at the end gets added to the first element.)

≧⁺№υθη

Keep a running total of the number of occurrences of n.

»Ｉη

Output the final total.

Noodle9 · Accepted Answer · 2021-10-03 14:12:17Z

C (gcc), ^{96 \$\cdots\$ 81} 77 bytes

c;i;f(n){for(int p[n],r=c=0;p[i=r++]=r<=n;)for(;i;)c+=(p[i--]+=p[i])==n;i=c;}

Try it online!

Inputs integer \$n > 1\$ and returns the number of times \$n\$ appears in Pascal's triangle.

Saved a byte thanks to ceilingcat!!!

Commented code

c;i;                           // declare counter (c) and   
                               //   index (i).     
f(n){                          // declare function f taking an   
                               //   int parm (n).   
     for(                      // outer loop over rows of Pascal's 
                               //  triangle.     
         int p[n],             // declare int array (p) that will  
                               //  store successive rows of    
                               //  Pascal's triangle.   
         r=c=0;                // declare int row (r) and   
                               //   init r and c to 0.  
         p[                    // set the rth element in p to 1:   
                               //   the first time through this   
                               //   sets p[0] = 1, and every   
                               //   time after that sets       
                               //   p[current last position] = 1.      
           i=r++               // init i to r and post bump r.  
                ]=r<=n;)       // loop until r is greater than n.   
      for(;i;)                 // inner loop over current row's  
                               //    elements backwards but   
                               //    stops before touching p[0].  
              c+=(             // bump c...  
                  p[i--]       // update current ith element by  
                   +=p[i]      //   adding previous values:    
                               //   p[i] = p[i] + p[i-1].  
                         )==n; // ...if this new value of  
                               //    Pascal's triangle is   
                               //    equal to n.     
     i=c;                      // return counter c.      
}

Aside: This method golfed the best but also calculating rows of Pascal's triangle through repeated summation works well with \$32\$-bit integers, calculating \$\binom{n}{m}\$ as \$\frac{(n-m)!}{m!}\$ quickly overflows, even for \$64\$-bit integers. This method might also be faster, especially for \$n<=16\$ where rows of Pascal's triangle will fit on a single cache line.

Stephen Universe · Accepted Answer · 2021-10-07 08:45:47Z

1

Python 3, 117 109 94 bytes

-23 bytes thanks to Jo King

f=lambda n,k=0:(k:=k or n)-1and[math.comb(k,i)for i in range(k)].count(n)+f(n,k-1)
import math

Try it online!

Generates each line of Pascal's triangle recursively and counts times n appeared.

Sorry for causing so much trouble with this solution. Much thanks to Jo King and Bubbler for helping me out.

edited Oct 7, 2021 at 8:45

answered Oct 6, 2021 at 4:56

Stephen Universe

2511 silver badge4 bronze badges

\$\begingroup\$ Some quick golfing to get to 94 bytes. Unfortunately, there's no reason to embed a recursive function inside another one when you can just declare it outside for one less byte \$\endgroup\$
– Jo King ♦
Oct 6, 2021 at 6:58
\$\begingroup\$ Thanks for the insight! I should definitely golf my solutions more before posting. \$\endgroup\$
– Stephen Universe
Oct 7, 2021 at 2:14
\$\begingroup\$ You need to include f= in your current answer because it's a recursive function, and it is very wrong. (One of the main reasons to use TIO is to demonstrate the test cases in the footer.) \$\endgroup\$
– Bubbler
Oct 7, 2021 at 2:26
\$\begingroup\$ Thank you for pointing that out! I was testing it in the interactive terminal where f was bound to a version of the function that worked. \$\endgroup\$
– Stephen Universe
Oct 7, 2021 at 3:22
\$\begingroup\$ Some reasoning behind my 94 byte solution that you appear to have disregarded. I use k=0 to initialise since the first row of the triangle will only contain 1s. and/or will short-circuit, resulting in the corresponding truthy/falsey value (this is often more useful than if/else), e.g. k:=k or n sets k to n when k=0 and k-1 and val will either be zero or val \$\endgroup\$
– Jo King ♦
Oct 7, 2021 at 3:36

| Show 1 more comment

NikoNyrh · Accepted Answer · 2021-10-19 17:00:17Z

Clojure, 94 bytes

#((frequencies(apply concat(take(inc %)(iterate(fn[i](concat[1](map +'(rest i)i)[1]))[1]))))%)

Actually frequencies calculates the frequencies of all numbers, and it is used in a function context of that S-expression, thus returning the frequency of the queried number. One must use +' for summation to handle integer overflows properly. A loop implementation should be shorter than this iterate - take - frequencies combination. TIO.

Stack Exchange Network

Count occurrences in Pascal's Triangle

Scoring

Testcases

25 Answers 25

Gaia, 4 bytes

Jelly, 5 bytes

How it works

Ruby, 54 53 bytes

Vyxal, 7 bytes

Explained

R, 41 bytes

Python 3, 67 bytes

JavaScript (ES6), 61 bytes

Excel (Insider Beta), 59 55 bytes

Excel Office 365, 67 63 bytes

Husk, 12 bytes

MATL, 6 bytes _{^{(using Pascal matrix)}}

MATL, 8 bytes _{^{(using binomial coefficients)}}

Wolfram Language (Mathematica), 32 bytes

Dyalog APL, 11 10 bytes

K (ngn/k), 19 bytes

K (ngn/k), 15 bytes

Jelly, 7 bytes

Explained

Ruby, 67 bytes

Python 3.8 (pre-release), 80 bytes

Perl 5, 91 bytes

TI-Basic, 27 bytes

Pari/GP, 38 bytes

05AB1E, 7 5 bytes

Charcoal, 32 bytes

C (gcc), ^{96 \$\cdots\$ 81} 77 bytes

Commented code

Python 3, 117 109 94 bytes

Clojure, 94 bytes

Your Answer

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

Linked

Hot Network Questions

Count occurrences in Pascal's Triangle

Scoring

Testcases

25 Answers 25

Gaia, 4 bytes

Jelly, 5 bytes

How it works

Ruby, 54 53 bytes

Vyxal, 7 bytes

Explained

R, 41 bytes

Python 3, 67 bytes

JavaScript (ES6), 61 bytes

Excel (Insider Beta), 59 55 bytes

Excel Office 365, 67 63 bytes

Husk, 12 bytes

MATL, 6 bytes (using Pascal matrix)

MATL, 8 bytes (using binomial coefficients)

Wolfram Language (Mathematica), 32 bytes

Dyalog APL, 11 10 bytes

K (ngn/k), 19 bytes

K (ngn/k), 15 bytes

Jelly, 7 bytes

Explained

Ruby, 67 bytes

Python 3.8 (pre-release), 80 bytes

Perl 5, 91 bytes

TI-Basic, 27 bytes

Pari/GP, 38 bytes

05AB1E, 7 5 bytes

Charcoal, 32 bytes

C (gcc), 96 \$\cdots\$ 81 77 bytes

Commented code

Python 3, 117 109 94 bytes

Clojure, 94 bytes

Your Answer

Sign up or log in

Post as a guest

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

Linked

Related

Hot Network Questions

MATL, 6 bytes _{^{(using Pascal matrix)}}

MATL, 8 bytes _{^{(using binomial coefficients)}}

C (gcc), ^{96 \$\cdots\$ 81} 77 bytes

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