A214282 Largest Euler characteristic of a downset on an n-dimensional cube.

1, 1, 1, 3, 6, 10, 15, 35, 70, 126, 210, 462, 924, 1716, 3003, 6435, 12870, 24310, 43758, 92378, 184756, 352716, 646646, 1352078, 2704156, 5200300, 9657700, 20058300, 40116600, 77558760, 145422675, 300540195, 601080390, 1166803110, 2203961430, 4537567650, 9075135300, 17672631900

Offset: 1

Author

Terence Tao, Jul 09 2012

Keywords

• nonn

Comments

An m-downset is a set of subsets of 1..m such that if S is in the set, so are all subsets of S. The Euler characteristic of a downset is the number of sets in the downset with an even cardinality, minus the number with an odd cardinality.

Examples

			G.f. = x + x^2 + x^3 + 3*x^4 + 6*x^5 + 10*x^6 + 15*x^7 + 35*x^8 + ...
		

Links

• Reinhard Zumkeller, Table of n, a(n) for n = 1..1000
• Terry Tao, Optimal bounds for an alternating sum on a downset, 2012.

Crossrefs

Cf. A214283.

Programs

Haskell

a214282 n = a007318 (n - 1) (a004524 (n - 1))
-- Reinhard Zumkeller, Jul 14 2012

Mathematica

Table[{Binomial[n - 1, n/2], Binomial[n, n/2], Binomial[n + 1, n/2 + 1], Binomial[n + 2, n/2 + 2]}, {n, 0, 28, 4}] (* Alonso del Arte, Jul 09 2012 *)

PARI

a(n)=binomial(n-1,if(n%2,(n+1)\4*2,n/2)) \\ Charles R Greathouse IV, Jul 09 2012

PARI

{a(n) = if( n<1, 0, vecmax( Vec((1 - x)^(n-1))))}; /* Michael Somos, Apr 21 2014 */

Python

from math import comb
def A214282(n): return comb(n-1, (n+1>>1)&(-1^(n&1))) # Chai Wah Wu, Jan 31 2024

Formula

a(n) = binomial(n - 1, n/2) when n is even, a(n) = binomial(n - 1, (n + 1)/2) when n is 3 mod 4, and a(n) = binomial(n - 1, (n - 1)/2) when n is 1 mod 4.

a(2n) = A001700(n-1). a(4n+1) = A001448(n). a(4n+3) = A186231(n).

a(n) = A214283(n) + A001405(n). - Reinhard Zumkeller, Jul 14 2012

a(n) = A007318(n-1, A004524(n-1)). - Reinhard Zumkeller, Jul 14 2012

a(n+1) = A000108([n/2])*A215495(n). - M. F. Hasler, Aug 25 2012

A214282(n) - A214283(n) is A056040(n) if n is even and A056040(n)/((n+1)/2) otherwise. - Peter Luschny, Jul 08 2016