|
%I #13 May 05 2020 18:11:58
%S 1,1,2,7,26,91,302,967,3026,9331,28502,86527,261626,788971,2375102,
%T 7141687,21457826,64439011,193448102,580606447,1742343626,5228079451,
%U 15686335502,47063200807,141197991026,423610750291,1270865805302,3812664524767,11438127792026
%N a(n) = (1/2)*(3^n - 2^(n+1) + 3).
%C Let P(A) be the power set of an n-element set A. Then a(n-1) = the number of pairs of elements {x,y} of P(A) for which either 0) x and y are disjoint and 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.
%C The inverse binomial transform yields A033484 with another leading 1. [From _R. J. Mathar_, Jul 06 2009]
%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. [_Ross La Haye_, Feb 22 2009]
%H <a href="/index/Rec#order_03">Index entries for linear recurrences with constant coefficients</a>, signature (6,-11,6)
%F a(n) = 3*StirlingS2(n,3) + StirlingS2(n,2) + 1.
%F a(n) = StirlingS2(n+1,3) + 1. - _Ross La Haye_, Jan 21 2008
%F a(n) = 6 a(n-1)-11 a(n-2) +6 a(n-3) (n >= 3). Also a(n) = 4 a(n-1)-3 a(n-2)+ 2^{n-2} (n >= 3). - Tian-Xiao He (the(AT)iwu.edu), Jul 02 2009
%F G.f.: -(1-4*x+6*x^2)/((x-1)*(3*x-1)*(2*x-1)). a(n+1)-a(n)=A001047(n+1). [_R. J. Mathar_, Jul 06 2009]
%e a(3) = 7 because for P(A) = {{},{1},{2},{1,2}} we have: case 0 {{1},{2}}, case 1 {{1},{1,2}}, {2},{1,2}}, case 2 {{},{}}, {{1},{1}}, {{2},{2}}, {{1,2},{1,2}}.
%p f := n -> (1/2)*(3^n - 2^(n+1) + 3);
%t Table[(3^n-2^(n+1)+3)/2,{n,0,30}] (* or *) LinearRecurrence[{6,-11,6},{1,1,2},30] (* _Harvey P. Dale_, May 05 2020 *)
%Y Cf. A000392, A028243, A000079.
%K nonn
%O 0,3
%A _Ross La Haye_, Jan 11 2008
%E Edited by _N. J. A. Sloane_, Jul 06 2009
|
