login
This site is supported by donations to The OEIS Foundation.

 

Logo

Annual appeal: Please make a donation to keep the OEIS running! Over 6000 articles have referenced us, often saying "we discovered this result with the help of the OEIS".
Other ways to donate

Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
A016269 Number of monotone Boolean functions of n variables with 2 mincuts. Also number of Sperner systems with 2 blocks. 68
1, 9, 55, 285, 1351, 6069, 26335, 111645, 465751, 1921029, 7859215, 31964205, 129442951, 522538389, 2104469695, 8460859965, 33972448951, 136276954149, 546269553775, 2188563950925, 8764714059751, 35090233104309, 140455067207455, 562102681589085, 2249257981411351 (list; graph; refs; listen; history; text; internal format)
OFFSET

0,2

COMMENTS

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

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

Let P(A) be the power set of an n-element set A. Then a(n-2) = 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

a(n) gives also 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

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

REFERENCES

L. Comtet, Advanced Combinatorics, Reidel, 1974, p. 292, #8, s(n,2).

LINKS

G. C. Greubel, Table of n, a(n) for n = 0..1000

K. S. Brown, Dedekind's problem

Vladeta Jovovic, Illustration for A016269, A047707, A051112-A051118

Goran Kilibarda and Vladeta Jovovic, Antichains of Multisets, J. Integer Seqs., Vol. 7, 2004.

Ross La Haye, Binary Relations on the Power Set of an n-Element Set, Journal of Integer Sequences, Vol. 12 (2009), Article 09.2.6.

N. M. Rivière, Recursive formulas on free distributive lattices, J. Combinatorial Theory 5 1968 229--234. MR0231764 (38 #92). - N. J. A. Sloane, May 12 2012

Index entries for sequences related to Boolean functions

Index entries for linear recurrences with constant coefficients, signature (9,-26,24).

FORMULA

G.f.: 1/((1-2*x)*(1-3*x)*(1-4*x)).

a(n) = (2^n)*(2^n - 1)/2 - 3^n + 2^n.

a(n) = Sum_{0<=i,j,k,<=n, i+j+k=n} 2^i*3^j*4^k. - Hieronymus Fischer, Jun 25 2007

a(n) = 2^(n+1)*(1+2^(n+2))-3^(n+2). - Hieronymus Fischer, Jun 25 2007

a(n) = 3*StirlingS2(n+1,4) + StirlingS2(n+1,3). - Ross La Haye, Jan 10 2008

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

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

a(n) = binomial(2^n,2) - (3^n - 2^n). - Ross La Haye, Jan 26 2016

MAPLE

with(combinat):a:=n->stirling2(n, 4)-stirling2(n-1, 4): seq(a(n), n=4..24); # Zerinvary Lajos, Oct 05 2007

MATHEMATICA

CoefficientList[1/((1-2x)(1-3x)(1-4x)) + O[x]^30, x] (* Jean-François Alcover, Nov 28 2015 *)

LinearRecurrence[{9, -26, 24}, {1, 9, 55}, 40] (* Vincenzo Librandi, Oct 06 2017 *)

PROG

(PARI) a(n)=(2^n)*(2^n-1)/2-3^n+2^n \\ Charles R Greathouse IV, Mar 22 2016

(MAGMA) [(2^n)*(2^n-1)/2-3^n+2^n: n in [2..30]]; // Vincenzo Librandi, Oct 06 2017

CROSSREFS

Equals (1/2) A038721(n+1). First differences of A000453. Partial sums of A027650. Pairwise sums of A099110. Odd part of A019333.

Cf. A000392, A032263, A000079, A001047.

Sequence in context: A068970 A141530 A263478 * A005770 A030053 A072844

Adjacent sequences:  A016266 A016267 A016268 * A016270 A016271 A016272

KEYWORD

nonn,easy

AUTHOR

N. J. A. Sloane

STATUS

approved

Lookup | Welcome | Wiki | Register | Music | Plot 2 | Demos | Index | Browse | More | WebCam
Contribute new seq. or comment | Format | Style Sheet | Transforms | Superseeker | Recent | More pages
The OEIS Community | Maintained by The OEIS Foundation Inc.

License Agreements, Terms of Use, Privacy Policy .

Last modified November 22 05:36 EST 2017. Contains 295076 sequences.