|
%I #104 Sep 08 2022 08:44:40
%S 1,9,55,285,1351,6069,26335,111645,465751,1921029,7859215,31964205,
%T 129442951,522538389,2104469695,8460859965,33972448951,136276954149,
%U 546269553775,2188563950925,8764714059751,35090233104309,140455067207455,562102681589085,2249257981411351
%N Number of monotone Boolean functions of n variables with 2 mincuts. Also number of Sperner systems with 2 blocks.
%C Half the number of 2 X (n+2) binary arrays with both a path of adjacent 1's and a path of adjacent 0's from top row to bottom row. - _R. H. Hardin_, Mar 21 2002
%C As (0,0,1,9,55,...) this is the third binomial transform of cosh(x)-1. It is the binomial transform of A000392, when this has two leading zeros. Its e.g.f. is then exp(3x)cosh(x) - exp(3x) and a(n) = (4^n - 2*3^n + 2^n)/2. - _Paul Barry_, May 13 2003
%C Let P(A) be the power set of an n-element set A. Then a(n-2) is 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 but for which x is not a subset of y and y is not a subset of x. - _Ross La Haye_, Jan 10 2008
%C a(n) also gives the third column sequence of the Sheffer triangle A143494 (2-restricted Stirling2 numbers). See the e.g.f. given below, and comments on the general case under A193685. - _Wolfdieter Lang_, Oct 08 2011
%C a(n) is also the number of even binomial coefficients in rows 0 through 2^(n+1)-1 of Pascal's triangle. - _Aaron Meyerowitz_, Oct 29 2013
%D L. Comtet, Advanced Combinatorics, Reidel, 1974, p. 292, #8, s(n,2).
%H G. C. Greubel, <a href="/A016269/b016269.txt">Table of n, a(n) for n = 0..1000</a>
%H K. S. Brown, <a href="http://www.mathpages.com/home/kmath030.htm">Dedekind's problem</a>
%H John Elias, <a href="/A016269/a016269.png">Illustration of Initial Terms: Inverse of the Sierpinski Triangle</a>
%H Vladeta Jovovic, <a href="/A047707/a047707.pdf">Illustration for A016269, A047707, A051112-A051118</a>
%H Goran Kilibarda and Vladeta Jovovic, <a href="https://cs.uwaterloo.ca/journals/JIS/VOL7/Kilibarda/kili2.html">Antichains of Multisets</a>, J. Integer Seqs., Vol. 7, 2004.
%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 N. M. Rivière, <a href="http://dx.doi.org/10.1016/S0021-9800(68)80068-7">Recursive formulas on free distributive lattices</a>, J. Combinatorial Theory 5 1968 229--234. MR0231764 (38 #92). - _N. J. A. Sloane_, May 12 2012
%H <a href="/index/Bo#Boolean">Index entries for sequences related to Boolean functions</a>
%H <a href="/index/Rec#order_03">Index entries for linear recurrences with constant coefficients</a>, signature (9,-26,24).
%F G.f.: 1/((1-2*x)*(1-3*x)*(1-4*x)).
%F a(n) = (2^n)*(2^n - 1)/2 - 3^n + 2^n.
%F a(n) = Sum_{0<=i,j,k,<=n, i+j+k=n} 2^i*3^j*4^k. - _Hieronymus Fischer_, Jun 25 2007
%F a(n) = 2^(n+1)*(1+2^(n+2))-3^(n+2). - _Hieronymus Fischer_, Jun 25 2007
%F a(n) = 3*StirlingS2(n+1,4) + StirlingS2(n+1,3). - _Ross La Haye_, Jan 10 2008
%F If we define f(m,j,x) = Sum_{k=j..m} binomial(m,k)*Stirling2(k,j)*x^(m-k) then a(n-2) = f(n,2,2), (n >= 2). - _Milan Janjic_, Apr 26 2009
%F E.g.f.: (d^2/dx^2) (exp(2*x)*((exp(x)-1)^2)/2!). See the Sheffer comment given above. - _Wolfdieter Lang_, Oct 08 2011
%F a(n) = binomial(2^n,2) - (3^n - 2^n). - _Ross La Haye_, Jan 26 2016
%F a(n) = A006516(n+1) + 3*a(n-1), n>=1, a(0)=1. - _Carlos A. Rico A._, Jun 22 2019
%p with(combinat):a:=n->stirling2(n,4)-stirling2(n-1,4): seq(a(n), n=4..24); # _Zerinvary Lajos_, Oct 05 2007
%t CoefficientList[1/((1-2x)(1-3x)(1-4x)) + O[x]^30, x] (* _Jean-François Alcover_, Nov 28 2015 *)
%t LinearRecurrence[{9, -26, 24}, {1, 9, 55}, 40] (* _Vincenzo Librandi_, Oct 06 2017 *)
%o (PARI) a(n)=(2^n)*(2^n-1)/2-3^n+2^n \\ _Charles R Greathouse IV_, Mar 22 2016
%o (Magma) [(2^n)*(2^n-1)/2-3^n+2^n: n in [2..30]]; // _Vincenzo Librandi_, Oct 06 2017
%Y Equals (1/2) A038721(n+1). First differences of A000453. Partial sums of A027650. Pairwise sums of A099110. Odd part of A019333.
%Y Cf. A000079, A000392, A001047, A006516, A032263.
%K nonn,easy
%O 0,2
%A _N. J. A. Sloane_
|
