A155609 - OEIS

%I #28 Sep 30 2018 17:29:56

%S 1,2,8,38,176,782,3368,14198,58976,242462,989528,4017158,16245776,

%T 65514542,263652488,1059392918,4251920576,17050729022,68332056248,

%U 273715645478,1096024843376,4387586157902,17560804984808,70274600998838

%N a(n) = 4^n - 3^n + 1.

%C Let P(A) be the power set of an n-element set A and R be a relation on P(A) such that for all x, y of P(A), xRy if x and y are intersecting. Then a(n) = |R|. - _Ross La Haye_, Mar 19 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.

%H <a href="/index/Rec#order_03">Index entries for linear recurrences with constant coefficients</a>, signature (8,-19,12).

%F G.f.: 1/(1-4*x) - 1/(1-3*x) + 1/(1-x).

%F E.g.f.: exp(4*x) - exp(3*x) + exp(x).

%F a(n) = 7*a(n-1)-12*a(n-2)+6 with a(0)=1, a(1)=2. - _Vincenzo Librandi_, Jul 21 2010

%t Table[4^n-3^n+1,{n,0,40}] (* _Vladimir Joseph Stephan Orlovsky_, Feb 15 2011 *)

%t LinearRecurrence[{8,-19,12},{1,2,8},30] (* _Harvey P. Dale_, Sep 30 2018 *)

%o (PARI) a(n)=4^n-3^n+1 \\ _Charles R Greathouse IV_, Oct 07 2015

%Y Cf. A155596, A155597, A155598, A155599, A155600, A155601, A155602, A155603, A155604, A155605, A155606, A155607, A155608.

%K nonn,easy

%O 0,2

%A _Mohammad K. Azarian_, Jan 26 2009