15
\$\begingroup\$

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:

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

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 , shortest wins!

Testcases

2 => 1
4 => 2
6 => 3
10 => 4
28 => 4
20 => 3
120 => 6
\$\endgroup\$

25 Answers 25

6
\$\begingroup\$

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.

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

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
\$\endgroup\$
1
  • 1
    \$\begingroup\$ Alternative 5 bytes. Chaining rules are actively blocking from saving a byte :/ \$\endgroup\$
    – Bubbler
    Sep 25 at 7:45
5
\$\begingroup\$

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

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

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
\$\endgroup\$
4
\$\begingroup\$

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!

\$\endgroup\$
4
\$\begingroup\$

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!

\$\endgroup\$
4
\$\begingroup\$

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!

\$\endgroup\$
2
  • \$\begingroup\$ Latest test case f(120) returns 5, not 6. Due to floating point inaccuracy I think. \$\endgroup\$
    – Kjetil S.
    Sep 27 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 at 15:59
4
\$\begingroup\$

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

\$\endgroup\$
3
\$\begingroup\$

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
\$\endgroup\$
3
\$\begingroup\$

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
\$\endgroup\$
3
\$\begingroup\$

Wolfram Language (Mathematica), 32 bytes

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

Try it online!

\$\endgroup\$
3
\$\begingroup\$

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
\$\endgroup\$
2
  • 1
    \$\begingroup\$ ≢∘⍸⊢=⍳∘.!⍳ works for 10 bytes \$\endgroup\$
    – ovs
    Sep 27 at 21:33
  • \$\begingroup\$ Didn’t cross my mind I could use , thanks! \$\endgroup\$ Sep 27 at 21:41
3
\$\begingroup\$

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
\$\endgroup\$
3
\$\begingroup\$

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
\$\endgroup\$
2
\$\begingroup\$

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
\$\endgroup\$
2
\$\begingroup\$

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!

\$\endgroup\$
2
\$\begingroup\$

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!

\$\endgroup\$
1
  • 2
    \$\begingroup\$ 69 bytes \$\endgroup\$
    – att
    Sep 27 at 21:36
2
\$\begingroup\$

05AB1E, 7 bytes

ÝDδc˜I¢

Try it online or verify all test cases.

Explanation:

ÝDδc  # Create a binomial coefficients table:
Ý     #  Push a list in the range [0, (implicit) input-integer]
 D    #  Duplicate this list
  δ   #  Apply double-vectorized with these two lists:
   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)
\$\endgroup\$
2
\$\begingroup\$

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!

\$\endgroup\$
2
\$\begingroup\$

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.

\$\endgroup\$
2
\$\begingroup\$

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.

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

Charcoal, 32 bytes

Nθ⊞υ¹≔⁰ηFθ«⊞υ⁰UMυ⁺κ§υ⊖λ≧⁺№υθη»Iη

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

Nθ

Input the target n.

⊞υ¹

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

≔⁰η

Start with 0 occurrences of n.

Fθ«

Loop n times.

⊞υ⁰

Append a 0 to the row.

UMυ⁺κ§υ⊖λ

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.

»Iη

Output the final total.

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

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.

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

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.

\$\endgroup\$
6
  • \$\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 at 6:58
  • \$\begingroup\$ Thanks for the insight! I should definitely golf my solutions more before posting. \$\endgroup\$ Oct 7 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 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\$ Oct 7 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 at 3:36
1
\$\begingroup\$

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.

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