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

%I #44 Jan 31 2024 14:16:54

%S 1,1,1,3,6,10,15,35,70,126,210,462,924,1716,3003,6435,12870,24310,

%T 43758,92378,184756,352716,646646,1352078,2704156,5200300,9657700,

%U 20058300,40116600,77558760,145422675,300540195,601080390,1166803110,2203961430,4537567650,9075135300,17672631900

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

%C 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.

%H Reinhard Zumkeller, <a href="/A214282/b214282.txt">Table of n, a(n) for n = 1..1000</a>

%H Terry Tao, <a href="http://mathoverflow.net/questions/101787/optimal-bounds-for-an-alternating-sum-on-a-downset">Optimal bounds for an alternating sum on a downset</a>, 2012.

%F 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.

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

%F a(n) = A214283(n) + A001405(n). - _Reinhard Zumkeller_, Jul 14 2012

%F a(n) = A007318(n-1, A004524(n-1)). - _Reinhard Zumkeller_, Jul 14 2012

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

%F A214282(n) - A214283(n) is A056040(n) if n is even and A056040(n)/((n+1)/2) otherwise. - _Peter Luschny_, Jul 08 2016

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

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

%o (PARI) a(n)=binomial(n-1,if(n%2,(n+1)\4*2,n/2)) \\ _Charles R Greathouse IV_, Jul 09 2012

%o (PARI) {a(n) = if( n<1, 0, vecmax( Vec((1 - x)^(n-1))))}; /* _Michael Somos_, Apr 21 2014 */

%o (Haskell)

%o a214282 n = a007318 (n - 1) (a004524 (n - 1))

%o -- _Reinhard Zumkeller_, Jul 14 2012

%o (Python)

%o from math import comb

%o def A214282(n): return comb(n-1, (n+1>>1)&(-1^(n&1))) # _Chai Wah Wu_, Jan 31 2024

%Y Cf. A214283.

%K nonn

%O 1,4

%A _Terence Tao_, Jul 09 2012