A349849 Number of transitive relations on an n-set with exactly four ordered pairs.
0, 0, 1, 45, 549, 3755, 18120, 69006, 220710, 616554, 1545435, 3544915, 7552611, 15119325, 28699034, 52032540, 90643260, 152465316, 248625765, 394404489, 610396945, 923906655, 1370595996, 1996425530, 2859913794, 4034751150, 5612802975, 7707539151, 10457928495
Offset: 0
Examples
a(2) = binomial(2,2) = 1. The only transitive relation with four ordered pairs on the 2-set {1,2} is {(1,1),(1,2),(2,1),(2,2)}.
Links
- Index entries for linear recurrences with constant coefficients, signature (9,-36,84,-126,126,-84,36,-9,1).
Formula
a(n) = C(n,2) + 42*C(n,3) + 375*C(n,4) + 1450*C(n,5) + 2940*C(n,6) + 3360*C(n,7) + 1680*C(n,8).
a(n) = (1/24)*(n^8 - 12*n^7 + 84*n^6 - 340*n^5 + 814*n^4 - 1130*n^3 + 829*n^2 - 246*n).