Shouldn't the answer be this?

[dim kraken]

The answer that Pyro gave is the sum of the first n square number = n(n+1)(2n+1)/6
but shouldn't the answer be ((2n+1) choose 3 ) * 2?

I see that the problem asks how many directed 3 cycles are in the fully connected graph with 2n+1 nodes

[tawny rivet]

1. Wait patiently for a helper to come along.
2. Once someone helps you, say thank you and close the thread with:

+close

3. Feel free to nominate the person for helper of the week in #helper-nominations
4. Do not ping the mods, unless someone is breaking the rules.
5. If you're happy with the help you got here, and the server overall, you can contribute financially as well:

[dim kraken]

Since if we have a directed 3-cycle ( a triangle with directed edges) we can find another 3-cycle triangle but with reversed directions

So for every 3 points there are 2 3-cycle out of them. And since every point is connected to each other, the answer should be 2 * how many triangles are in the completed graph with 2n+1 nodes

The answer should be 2 * ((2n+1) choose 3)

Why is my argument wrong?

[frank lintel]

we can find another 3-cycle triangle but with reversed directions
So for every 3 points there are 2 3-cycle out of them.
I don't understand this.

I think the problem consider the teams as sets of points. So, {x,y,z} = {y,z,x} = ...

[frank lintel]

when you do $\binom{2n+1}{3}$, you assume that all the triangles form a cycle, which is not true. If x beats y, y beat z, and x beat z, they don't form a cycle.

[flat spire]

k12byda5h

[dim kraken]

Well if you look at it like that they might not do

But if you choose 3 points

Then you find 2 cycles out of them X,Y,Z and X,Z,Y

I still don't see what is wrong

I am not picking edges

I am picking points

Oh wait

You are right

[frank lintel]

You could say, if X,Y,Z form a triplet, then Z,X,Y and Y,Z,X form

but not X,Z,Y

[dim kraken]

Yeah, that's why it's choose and not arrangements

But I think I see what the problem was

[frank lintel]

But this is a language problem. We need to talk to the writer what is his intention.

[dim kraken]

I was thinking that the graph is a fully connected undirected graph

Yet its not

[frank lintel]

But that is a small point in this problem. The main is to count the maximum number of directed 3-cycle.

[dim kraken]

Yeah...

[frank lintel]

The graph is complete directed graph.

[dim kraken]

Now it's actually a hard problem

[frank lintel]

I will work on that. I will have a class soon.

[dim kraken]

Good luck

[frank lintel]

I got it

Do you know double counting? @dim kraken

here are som hint: ||counting cycle of length 3 is hard. Finding a triangle that is not a cycle is easier. (by double counting)||

[dim kraken]

Eh no

Would be nice if you could ppst your answer here @frank lintel

[frank lintel]

ahhhh, if you don't know double counting, this prolem might be hard for you.

There are $2n+1$ vertices. The $i^{th}$ vertex has edges pointing outward $d_{i}$.

Note that if a triangle is not a cycle, there must be exactly one vertex having 2 out-edges.

[flat spire]

k12byda5h

[dim kraken]

Yeahh

But then what?

[frank lintel]

By double counting, we get that the number of triangles that are not cycles is $$\sum_{i} = \binom{d_i}{2}.$$ Note that $d_1+d_2+\dots+d_{2n+1} = \binom{2n+1}{2}$. Since $\binom{x}{2}$ is convex, that expression is at least $$(2n+1)\binom{n}{2}$$