cp's OEIS Frontend

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

%I A324172 #22 Feb 16 2025 08:33:57
%S A324172 0,0,0,0,2,10,32,84,198,438,932,1936,3962,8034,16200,32556,65294,
%T A324172 130798,261836,523944,1048194,2096730,4193840,8388100,16776662,
%U A324172 33553830,67108212,134217024,268434698,536870098,1073740952,2147482716,4294966302,8589933534,17179868060
%N A324172 Number of subsets of {1,...,n} that cross their complement.
%C A324172 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.
%C A324172 Also the number of verex cuts in the wheel graph on n nodes. - _Eric W. Weisstein_, Apr 22 2023
%H A324172 Colin Barker, <a href="/A324172/b324172.txt">Table of n, a(n) for n = 0..1000</a>
%H A324172 <a href="/index/Rec#order_04">Index entries for linear recurrences with constant coefficients</a>, signature (5,-9,7,-2).
%H A324172 Eric Weisstein's World of Mathematics, <a href="https://mathworld.wolfram.com/VertexCut.html">Vertex Cut</a>
%H A324172 Eric Weisstein's World of Mathematics, <a href="https://mathworld.wolfram.com/WheelGraph.html">Wheel Graph</a>
%F A324172 a(0) = 0; a(n) = 2^n - n^2 + n - 2.
%F A324172 a(n) = 2*A002662(n-1) for n > 0.
%F A324172 G.f.: 2*x^4/((1-2*x)*(1-x)^3).
%F A324172 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
%e A324172 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}.
%t A324172 croXQ[stn_]:=MatchQ[stn,{___,{___,x_,___,y_,___},___,{___,z_,___,t_,___},___}/;x<z<y<t||z<x<t<y];
%t A324172 Table[Length[Select[Subsets[Range[n]],croXQ[{#,Complement[Range[n],#]}]&]],{n,0,10}]
%o A324172 (PARI) concat([0,0,0,0], Vec(2*x^4 / ((1 - x)^3*(1 - 2*x)) + O(x^40))) \\ _Colin Barker_, Feb 19 2019
%Y A324172 Cf. A000108, A000110, A000124, A001263, A002061, A002662, A016098, A306438.
%Y A324172 Cf. A324166, A324167, A324168, A324169, A324173.
%K A324172 nonn,easy
%O A324172 0,5
%A A324172 _Gus Wiseman_, Feb 17 2019