A324172 Number of subsets of {1,...,n} that cross their complement.

0, 0, 0, 0, 2, 10, 32, 84, 198, 438, 932, 1936, 3962, 8034, 16200, 32556, 65294, 130798, 261836, 523944, 1048194, 2096730, 4193840, 8388100, 16776662, 33553830, 67108212, 134217024, 268434698, 536870098, 1073740952, 2147482716, 4294966302, 8589933534, 17179868060

Offset: 0

Author

Gus Wiseman, Feb 17 2019

Keywords

• nonn
• easy

Comments

Two sets cross each other if they are of the form {{...x...y...}, {...z...t...}} where x < z < y < t or z < x < t < y.

Also the number of verex cuts in the wheel graph on n nodes. - Eric W. Weisstein, Apr 22 2023

Examples

			The a(5) = 10 subsets are {1,3}, {1,4}, {2,4}, {2,5}, {3,5}, {1,2,4}, {1,3,4}, {1,3,5}, {2,3,5}, {2,4,5}.
		

Links

• Colin Barker, Table of n, a(n) for n = 0..1000
• Index entries for linear recurrences with constant coefficients, signature (5,-9,7,-2).
• Eric Weisstein's World of Mathematics, Vertex Cut
• Eric Weisstein's World of Mathematics, Wheel Graph

Crossrefs

Cf. A000108, A000110, A000124, A001263, A002061, A002662, A016098, A306438.

Cf. A324166, A324167, A324168, A324169, A324173.

Programs

Mathematica

croXQ[stn_]:=MatchQ[stn,{_,{_,x_,_,y_,_},_,{_,z_,_,t_,_},_}/;x
				

PARI

concat([0,0,0,0], Vec(2*x^4 / ((1 - x)^3*(1 - 2*x)) + O(x^40))) \\ Colin Barker, Feb 19 2019

Formula

a(0) = 0; a(n) = 2^n - n^2 + n - 2.

a(n) = 2*A002662(n-1) for n > 0.

G.f.: 2*x^4/((1-2*x)*(1-x)^3).

a(n) = 5*a(n-1) - 9*a(n-2) + 7*a(n-3) - 2*a(n-4) for n>4. - Colin Barker, Feb 18 2019