A381862 Number of pairs of triangles that are pairwise edge-disjoint in the complete graph K_n.

15, 100, 385, 1120, 2730, 5880, 11550, 21120, 36465, 60060, 95095, 145600, 216580, 314160, 445740, 620160, 847875, 1141140, 1514205, 1983520, 2567950, 3289000, 4171050, 5241600, 6531525, 8075340, 9911475, 12082560, 14635720, 17622880, 21101080, 25132800, 29786295

Offset: 5

Author

Julian Allagan, Mar 08 2025

Keywords

• nonn
• easy

Comments

In other words, the number of unordered pairs of triangles that share at most 1 vertex in the complete graph K_n.

Examples

			a(5) = 15 because there are 15 unordered pairs of triangles that share 1 vertex.
a(6) = 100 = 90 + 10 because there are 90 = 15*binomial(6,5) unordered pairs of triangles that share 1 vertex and 10 = 10*binomial(6,6) unordered pairs of triangles that do not share a vertex.
		

References

• Julian Allagan, Edge-Disjoint Triangle Packings in Complete Graphs: Recurrence Relations and Closed Formulas. Submitted to Journal of Integer Sequences.

Links

• Index entries for linear recurrences with constant coefficients, signature (7,-21,35,-35,21,-7,1).

Crossrefs

Cf. A381863, A054647.

Programs

Mathematica

a[n_]:=n*(n-1)*(n-2)*(n-3)*(n-4)*(n+4)/72; Array[a,33,5] (* Stefano Spezia, Mar 09 2025 *)

Python

def A381862(n): return n*(n*(n*(n*(n*(n-6)-5)+90)-176)+96)//72 # Chai Wah Wu, Mar 18 2025

Formula

a(n) = 10*binomial(n,6) + 3*n*binomial(n-1,4).

a(n) = n*(n-1)*(n-2)*(n-3)*(n-4)*(n+4)/72.

G.f.: 5*x^5*(3 - x)/(1 - x)^7. - Stefano Spezia, Mar 09 2025