Maximal number of regions obtained by joining n points around a circle by straight lines

Question

Let's define f(n) as the aximal number of regions obtained by joining n points around a circle by straight lines. For example, two points would split the circle into two pieces, three into four, like this:

Make sure when you are drawing the lines, you don't have an intersection of more than two lines.

Your task

Given a number n, print f(n).

Test cases:

 n | f(n)   
---+-----
 1 |   1
 2 |   2
 3 |   4
 4 |   8
 5 |  16
 6 |  31
 7 |  57
 8 |  99
 9 | 163

^{You can see more here.}

Using built-in sequence generators is not allowed.

Remember, this is code-golf, so the code with the smallest number of bytes wins.

If you guys want the formula, here it is:

Answer 1

Mathematica, 23 bytes

Tr@Binomial[#,{0,2,4}]&

Uses the formula in the question.

Answer 2

JavaScript (ES6), 29 bytes

n=>(((n-6)*n+23)*n/6-3)*n/4+1

Uses a formula given in OEIS.

Answer 3

Jelly, 6 bytes

5Ḷc@’S

Try it online! | Verify test cases

Explanation

Uses the OEIS formula ((n-1)C4 + (n-1)C3 + ... + (n-1)C0).

5Ḷc@’S    Main link.  Args: n

5         Yield 5.
 Ḷ        Lowered range: yield [0,1,2,3,4].
    ’     Yield n-1.
   @      Swap operands of the preceding dyad, 'c'.
  c       Combinations: yield [(n-1)C0, (n-1)C1, (n-1)C2, (n-1)C3, (n-1)C4].
     S    Sum: return (n-1)C0 + (n-1)C1 + (n-1)C2 + (n-1)C3 + (n-1)C4.

Answer 4

Jelly, 6 bytes

c3ḶḤ¤S

Try it online! or verify all test cases.

How it works

c3ḶḤ¤S  Main link. Argument: n

    ¤   Combine the three links to the left into a niladic chain.
 3        Yield 3.
  Ḷ       Unlength; yield [0, 1, 2].
   Ḥ      Unhalve; yield [0, 2, 4].
c       Combinations; compute [nC0, nC2, nC4].
     S  Sum; return nC0 + nc2 + nC4.

Answer 5

MATL, 7 bytes

q5:qXns

Try it online! Or verify all test cases.

Explanation

Uses the formula (from OEIS): a(n) = C(n−1, 4) + C(n−1, 3) + ... + C(n−1, 0)

q      % Implicit input. Subtract 1
5:q    % Array [0 1 2 3 4]
Xn     % Binomial coefficient, vectorized
s      % Sum

Answer 6

Java 7,50 47 bytes

int c(int n){return(n*n*(n-6)+23*n-18)*n/24+1;}

Uses the formula (from OEIS)

Answer 7

><>, 27 26+3 = 29 bytes

3 bytes added for the -v flag

::::6-**$f8+*f3+-+*f9+,1+n

Try it online!

A byte saved thanks to Martin Ender.

Answer 8

R, 25 bytes

sum(choose(scan(),0:2*2))

scan() takes the input n from stdin, which is passed to choose along with 0:2*2. This latter term is 0 to 2 (i.e. [0, 1, 2]) multiplied by 2, which is [0, 2, 4]. Since choose is vectorized, this calculates n choose 0, n choose 2, n choose 4, and returns them in a list. Finally, sum returns the sum of these numbers, surprisingly enough.

I don't think that this can be golfed further but I would be very happy to be proven wrong!

Answer 9

dc, 21

?ddd6-*23+*6/3-*4/1+p

RPN-ised version of @Neil's answer.

Test output:

$ for i in {1..9}; do dc -e "?ddd6-*23+*6/3-*4/1+p" <<< $i; done
1
2
4
8
16
31
57
99
163
$ 

Answer 10

J, 9 bytes

+4&!+2!<:

Uses the formula C(n-1, 2) + C(n, 4) + n = C(n, 0) + C(n, 2) + C(n, 4).

Usage

   f =: +4&!+2!<:
   (,.f"0) >: i. 10
 1   1
 2   2
 3   4
 4   8
 5  16
 6  31
 7  57
 8  99
 9 163
10 256
   f 20
5036

Explanation

+4&!+2!<:  Input: integer n
       <:  Decrement n
     2     The constant 2
      !    Binomial coefficient C(n-1, 2)
 4&!       Binomial coefficient C(n, 4)
    +      Add them
+          Add that to n and return

Answer 11

05AB1E, 6 bytes

2Ý·scO

Try it online!

Explanation

Straight implementation of the OEIS formula c(n,4) + c(n,2) + c(n,0)

2Ý       # range: [0,1,2]
  ·      # multiply by 2: [0,2,4]
   s     # swap list with input
    c    # combinations
     O   # sum

Answer 12

Actually, 6 bytes

D╣5@HΣ

Try it online!

Explanation:

D╣5@HΣ
D       decrement input
 ╣      push that row of Pascal's triangle
  5@H   first 5 values
     Σ  sum

Answer 13

Scala, 35 bytes

(n:Int)=>(n*n*(n-6)+23*n-18)*n/24+1

Uses the same formula as numberknot's java answer.

Answer 14

Octave, 27 bytes

@(m)binocdf(4,m-1,.5)*2^m/2

This is an anonymous function.

Try it at Ideone.

Explanation

This is based on the OEIS formula a(m) = C(m−1, 4) + C(m−1, 3) + ... + C(m−1, 0), where C are binomial coefficients. The binomial distribution function

for k = 4, n = m−1 and p = 1/2 gives 2^m−1a(m).

Answer 15

TI-89 Basic, 57 Bytes

:Def a(a)=Func
:Return nCr(n,0)+nCr(n,2)+nCr(n,4)
:End Func

Throwback to old times.