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

Let's define f(n) as the maximal 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Ḷ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.

• Welcome to PPCG and great first answer! Oct 21, 2016 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

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.


# 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

::::6-**$f8+*f3+-+*f9+,1+n  Try it online! A byte saved thanks to Martin Ender. # 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! • I was 2 seconds from submitting the same solution, nice! Oct 21, 2016 at 11:43 # tinylisp, 73 bytes (load library) (d D(q((N)(+(/(*(s N 1)N(s N 2)(s N 3))24)(/(*(s N 1)N)2)1  Try it online! From Giuseppe. # tinylisp, 90 bytes (d C(q((N K)(i K(i N(a(C(s N 1)(s K 1))(C(s N 1)K))0)1 (d D(q((N)(a(a(C N 0)(C N 2))(C N 4  Try it online! • You're only using library for + which is rather wasteful so just use a twice: Try it online! I think neil's answer is using floordiv which is why it doesn't port quite right. Feb 4, 2022 at 15:32 • Could port the R answer as well... Feb 4, 2022 at 15:41 # 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$


# 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


# 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, 2016 at 20:29
• @Oliver Hi "Not Sure", I am also Not Sure. (Idiocracy is a great movie). Oct 24, 2016 at 20:30
• Isn't nCr(n,0) always equal to 1? Feb 4, 2022 at 15:38

# Excel, 31 bytes

=(A1^2*(A1-6)+A1*23-18)*A1/24+1


Using one of OEIS formulas

# Factor + math.combinatorics math.unicode, 29 bytes

[ "\0"[ nCk ] with map Σ ]


Try it online!

You might not be able to see them here, but there are literal 2 and literal 4 control codes embedded in the string. It's a shorter version of { 2 4 0 }. You can see them for sure on TIO.

# 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


# Vyxald, 4 bytes

3ʁdƈ


Try it Online!

Simply an implementation of the formula.

# 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, 2016 at 23:37