login
A324172
Number of subsets of {1,...,n} that cross their complement.
18
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,5
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
LINKS
Eric Weisstein's World of Mathematics, Vertex Cut
Eric Weisstein's World of Mathematics, Wheel Graph
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
EXAMPLE
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}.
MATHEMATICA
croXQ[stn_]:=MatchQ[stn, {___, {___, x_, ___, y_, ___}, ___, {___, z_, ___, t_, ___}, ___}/; x<z<y<t||z<x<t<y];
Table[Length[Select[Subsets[Range[n]], croXQ[{#, Complement[Range[n], #]}]&]], {n, 0, 10}]
PROG
(PARI) concat([0, 0, 0, 0], Vec(2*x^4 / ((1 - x)^3*(1 - 2*x)) + O(x^40))) \\ Colin Barker, Feb 19 2019
KEYWORD
nonn,easy
AUTHOR
Gus Wiseman, Feb 17 2019
STATUS
approved