Year-end appeal: Please make a donation to the OEIS Foundation to support ongoing development and maintenance of the OEIS. We are now in our 61st year, we have over 378,000 sequences, and we’ve reached 11,000 citations (which often say “discovered thanks to the OEIS”).
%I #34 Jan 29 2023 19:36:50
%S 1,3,10,33,106,333,1030,3153,9586,29013,87550,263673,793066,2383293,
%T 7158070,21490593,64504546,193579173,580868590,1742867913,5229128026,
%U 15688432653,47067395110,141206379633,423627527506,1270899359733
%N Number of 2-element intersecting families (with not necessarily distinct sets) whose union is an n-element set.
%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 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 and for which either x is a proper subset of y or y is a proper subset of x, or 3) x = y. - _Ross La Haye_, Jan 12 2008
%C From _Paul Barry_, Apr 27 2003: (Start)
%C With offset 0, this is a(n) = (3*3^n - 2*2^n + 1)/2.
%C G.f. (1-3*x+3*x^2)/((1-x)*(1-2*x)*(1-3*x)).
%C E.g.f. (3*exp(3*x) - 2*exp(2*x) + exp(x))/2.
%C Binomial transform of A083329.
%C Second binomial transform of A040001. (End)
%H G. C. Greubel, <a href="/A053156/b053156.txt">Table of n, a(n) for n = 1..1000</a>
%H V. Jovovic, G. Kilibarda, <a href="http://dx.doi.org/10.4213/dm398">On the number of Boolean functions in the Post classes F^{mu}_8</a>, in Russian, Diskretnaya Matematika, 11 (1999), no. 4, 127-138.
%H V. Jovovic, G. Kilibarda, <a href="http://dx.doi.org/10.1515/dma.1999.9.6.593">On the number of Boolean functions in the Post classes F^{mu}_8</a>, English translation, in Discrete Mathematics and Applications, 9, (1999), no. 6.
%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 (6,-11,6).
%F a(n) = (3^n - 2^n + 1)/2.
%F a(n) = StirlingS2(n+2,3) + StirlingS2(n+1,2) + 1. - _Ross La Haye_, Jan 12 2008
%F From _Colin Barker_, Jul 29 2012: (Start)
%F a(n) = 6*a(n-1) - 11*a(n-2) + 6*a(n-3) for n > 3.
%F G.f.: x*(1-3*x+3*x^2)/((1-x)*(1-2*x)*(1-3*x)). (End)
%p A053156:=n->(3^n - 2^n + 1)/2: seq(A053156(n), n=1..40); # _Wesley Ivan Hurt_, Oct 06 2017
%t LinearRecurrence[{6,-11,6}, {1, 3, 10}, 50] (* or *) Table[(3^n - 2^n + 1)/2, {n,1,50}] (* _G. C. Greubel_, Oct 06 2017 *)
%o (PARI) a(n) = (3^n-2^n+1)/2; \\ _Michel Marcus_, Nov 30 2015
%o (Magma) [(3^n-2^n+1)/2: n in [1..30]]; // _G. C. Greubel_, Oct 06 2017
%Y Cf. A000225, A000392, A028243, A000079.
%Y Cf. A036239.
%Y Column k=2 of A288638.
%Y Third column of A294201.
%K easy,nonn
%O 1,2
%A _Vladeta Jovovic_ and Goran Kilibarda, Feb 28 2000