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

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.

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 , so the code with the smallest number of bytes wins.

If you guys want the formula, here it is:

Mathematica, 23 bytes

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

Uses the formula in the question.

JavaScript (ES6), 29 bytes

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

Uses a formula given in OEIS.

Jelly, 6 bytes

5Ḷc@’S

Explanation

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

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.
• Welcome to PPCG and great first answer! Oct 21 '16 at 15:29

MATL, 7 bytes

q5:qXns

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

Jelly, 6 bytes

c3ḶḤ¤S

How it works

¤   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.

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)

><>, 27 26+3 = 29 bytes

3 bytes added for the -v flag

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 that to n and return

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

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

Scala, 35 bytes

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

Uses the same formula as numberknot's java answer.

Octave, 27 bytes

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

This is an anonymous function.

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 2m−1a(m).

• @Oliver That would probably end up being longer, because then it's not the distribution function. I would need the probability (mass) function and sum; something like @(m)sum(binopdf(0:2:4,m,.5)*2^m) Oct 21 '16 at 23:37

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.

• I'm not sure, but can't you remove the ) on the last nCr? Oct 24 '16 at 20:29
• @Oliver Hi "Not Sure", I am also Not Sure. (Idiocracy is a great movie). Oct 24 '16 at 20:30