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,4

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.

Links

Reinhard Zumkeller, Table of n, a(n) for n = 1..1000

Terry Tao, Optimal bounds for an alternating sum on a downset, 2012.

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).

From Reinhard Zumkeller, Jul 14 2012: (Start)

a(n) = A214283(n) + A001405(n).

a(n) = A007318(n-1, A004524(n-1)). (End)

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

a(n) ~ 2^(n-1/2) / sqrt(Pi*n). - Amiram Eldar, Oct 04 2025

Example

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

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 *)

Prog

(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 */
(Haskell)
a214282 n = a007318 (n - 1) (a004524 (n - 1))
-- Reinhard Zumkeller, Jul 14 2012
(Python)
from math import comb
def A214282(n): return comb(n-1, (n+1>>1)&(-1^(n&1))) # Chai Wah Wu, Jan 31 2024

Crossrefs

Cf. A000108, A001405, A001448, A001700, A004524, A007318, A056040, A214282, A214283.

Sequence in context: A346734 A366132 A230364 * A130200 A202269 A151375

Adjacent sequences: A214279 A214280 A214281 * A214283 A214284 A214285

Keyword

nonn,easy

Author

Terence Tao, Jul 09 2012

Status

approved