# Greetings from The On-Line Encyclopedia of Integer Sequences! http://oeis.org/

Search: id:a134165
Showing 1-1 of 1

%I A134165 #18 Feb 29 2020 11:57:20
%S A134165 1,3,8,24,86,348,1478,6324,26846,112668,467798,1925124,7867406,
%T A134165 31980588,129475718,522603924,2104600766,8461122108,33972973238,
%U A134165 136278002724,546271650926
%N A134165 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 disjoint and for which either x is a subset of y or y is a subset of x, or 1) x and y are disjoint and for which x is not a subset of y and y is not a subset of x, or 2) x and y are intersecting but for which x is not a subset of y and y is not a subset of x, or 3) x = y.
%H A134165 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 A134165 <a href="/index/Rec#order_04">Index entries for linear recurrences with constant coefficients</a>, signature (10,-35,50,-24).
%F A134165 a(n) = (1/2)(4^n - 2*3^n + 5*2^n - 2) = 3*StirlingS2(n+1,4) + StirlingS2(n+1,3) + 2*StirlingS2(n+1,2) + 1.
%F A134165 G.f.: (1-7*x+13*x^2-x^3)/((1-x)*(1-2*x)*(1-3*x)*(1-4*x)). [_Colin Barker_, Jul 30 2012]
%e A134165 a(2) = 8 because for P(A) = {{},{1},{2},{1,2}} we have for case 0 {{},{1}}, {{},{2}}, {{},{1,2}} and we have for case 1 {{1},{2}} and we have for case 3 {{},{}}, {{1},{1}}, {{2},{2}}, {{1,2},{1,2}}. There are 0 {x,y} of P(A) in this example that fall under case 2.
%t A134165 LinearRecurrence[{10,-35,50,-24},{1,3,8,24},30] (* _Harvey P. Dale_, Feb 29 2020 *)
%Y A134165 Cf. A000225, A000392, A032263, A000079.
%K A134165 nonn,easy
%O A134165 0,2
%A A134165 _Ross La Haye_, Jan 12 2008

# Content is available under The OEIS End-User License Agreement: http://oeis.org/LICENSE