login
The OEIS is supported by the many generous donors to the OEIS Foundation.

 

Logo
Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
A134168 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 intersecting but for which x is not a subset of y and y is not a subset of x, or 2) 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 3) x = y. 1

%I #22 May 30 2016 04:39:35

%S 1,3,9,30,111,438,1779,7290,29871,121998,496299,2011650,8129031,

%T 32769558,131850819,529745610,2126058591,8525561118,34166421339,

%U 136858609170,548013994551,2193796224678,8780408783859,35137313082330,140596298752911,562526359448238,2250528981434379,9003386657325090

%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 disjoint and for which either x is a subset of y or y is a subset of x, or 1) x and y are intersecting but for which x is not a subset of y and y is not a subset of x, or 2) 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 3) x = y.

%H G. C. Greubel, <a href="/A134168/b134168.txt">Table of n, a(n) for n = 0..1000</a>

%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 + 3*2^n - 1).

%F a(n) = 3*StirlingS2(n+1,4) +2*StirlingS2(n+1,3) +2*StirlingS2(n+1,2) +1.

%F G.f.: -(5*x^3 - 14*x^2 + 7*x - 1)/((x-1)*(2*x-1)*(3*x-1)*(4*x-1)). - _Colin Barker_, Jul 30 2012

%e a(2) = 9 because for P(A) = {{},{1},{2},{1,2}} we have for case 0 {{},{1}}, {{},{2}}, {{},{1,2}} and we have for case 2 {{1},{1,2}}, {{2},{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 1.

%t LinearRecurrence[{10, -35, 50, -24}, {1, 3, 9, 30}, 50] (* or *) Table[(1/2)*(4^n - 3^n + 3*2^n - 1), {n,0,50}] (* _G. C. Greubel_, May 30 2016 *)

%Y Cf. A000225, A032263, A028243, A000079.

%K nonn,easy

%O 0,2

%A _Ross La Haye_, Jan 12 2008

Lookup | Welcome | Wiki | Register | Music | Plot 2 | Demos | Index | Browse | More | WebCam
Contribute new seq. or comment | Format | Style Sheet | Transforms | Superseeker | Recents
The OEIS Community | Maintained by The OEIS Foundation Inc.

License Agreements, Terms of Use, Privacy Policy. .

Last modified March 29 05:43 EDT 2024. Contains 371264 sequences. (Running on oeis4.)