login
Number of 2-element intersecting families (with not necessarily distinct sets) whose union is an n-element set.
6

%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