%I #23 Sep 24 2024 09:20:12
%S 1,2,6,23,96,407,1716,7163,29616,121487,495276,2009603,8124936,
%T 32761367,131834436,529712843,2125993056,8525430047,34166159196,
%U 136858084883,548012945976,2193794127527,8780404589556,35137304693723,140596281975696,562526325893807,2250528914325516
%N Let P(A) be the power set of an n-element set A. Then a(n) = the number of pairs of elements {x,y} of P(A) for which either 0) x and y are intersecting but for which x is not a subset of y and y is not a subset of x, or 1) x and y are intersecting and for which either x is a proper subset of y or y is a proper subset of x, or 2) x = y.
%H Ross La Haye, <a href="https://cs.uwaterloo.ca/journals/JIS/VOL12/LaHaye/lahaye5.html">Binary Relations on the Power Set of an n-Element Set</a>, Journal of Integer Sequences, Vol. 12 (2009), Article 09.2.6.
%H <a href="/index/Rec#order_04">Index entries for linear recurrences with constant coefficients</a>, signature (10,-35,50,-24).
%F a(n) = (1/2)(4^n - 3^n + 2^n + 1) = 3*StirlingS2(n+1,4) + 2*StirlingS2(n+1,3) + StirlingS2(n+1,2) + 1.
%F a(n) = C(2^n + 1,2) - (1/2)(3^n - 1) = StirlingS2(2^n + 1,2^n) - StirlingS2(n+1,3) - StirlingS2(n+1,2). - _Ross La Haye_, Jan 21 2008
%F G.f.: (1-8*x+21*x^2-17*x^3)/((1-x)*(1-2*x)*(1-3*x)*(1-4*x)). - _Colin Barker_, Jul 30 2012
%e a(2) = 6 because for P(A) = {{},{1},{2},{1,2}} we have for case 1 {{1},{1,2}}, {{2},{1,2}} and we have for case 2 {{},{}}, {{1},{1}}, {{2},{2}}, {{1,2},{1,2}}. There are 0 {x,y} of P(A) in this example that fall under case 0.
%t LinearRecurrence[{10,-35,50,-24},{1,2,6,23},30] (* _Harvey P. Dale_, Jul 04 2023 *)
%o (PARI) Vec((1-8*x+21*x^2-17*x^3)/((1-x)*(1-2*x)*(1-3*x)*(1-4*x)) + O(x^30)) \\ _Michel Marcus_, Oct 30 2015
%Y Cf. A032263, A028243, A000079.
%K nonn,easy
%O 0,2
%A _Ross La Haye_, Jan 11 2008