# Number of permutations with satisfactory triangles

We are given $$N$$ points($$N \leq 40$$), where no combination of three or more points is colinear. The values of $$x$$ and $$y$$ are bounded by [$$0$$,$$10^4$$]. The problem is to find the number of permutations(mod $$M$$) of the points that satisfy the following properties:

1. We draw a triangle between the first 3 points of the permutation($$p_1$$, $$p_2$$, $$p_3$$) through the use of line segments
2. For points $$4$$ to $$N$$, we draw exactly 3 line segments from $$p_i$$ to 3 points $$p_j$$ ($$j < i$$), such that none of these line segments intersect with any previous line segments drawn.

I will present 3 test cases that I have generated on my own(and tested via bruteforce).

Test case 1 :

$$N=4$$

($$0$$,$$0$$), ($$0$$,$$4$$), ($$1$$,$$1$$), ($$1$$,$$2$$)

Output = 0 since none of the permutations work.

Test case 2:

$$N=4$$

($$0$$,$$0$$), ($$0$$,$$4$$), ($$4$$,$$0$$), ($$1$$,$$1$$)

Output = 24 since all of the permutations work(4!).

Test case 3 :

$$N=5$$

($$0$$,$$0$$), ($$0$$,$$4$$), ($$4$$,$$0$$), ($$1$$,$$1$$), ($$1$$,$$2$$)

Output = 96 since all permutations work unless the first 4 points in the permutation are ($$0$$,$$0$$), ($$0$$,$$4$$), ($$1$$,$$1$$), ($$1$$,$$2$$). 5! - 4! = 96

So far I have observed that a valid permutation is one in which you can a draw valid triangle without intersecting the sides of the previous valid triangle. However, I am not sure how to build on this idea to calculate the total number of valid permutations. My solution right now is to bruteforce every permutation and manually check for intersections.

• Can you tell us the context where you encountered this task? Can you credit the original source? (i.e., link to it) – D.W. Apr 5 at 7:07