OFFSET
1,2
COMMENTS
T(n, k) is a sharp upper bound on the cardinality of a k-antichain in {0, 1}^n due to P. Erdős.
T(n, k) is also the total number of compositions with first part k, n+1 parts, and all differences between adjacent parts in {-1,1}. - John Tyler Rascoe, May 07 2023
LINKS
John Tyler Rascoe, Rows n = 1..141 of the triangle, flattened
P. Erdős, On a lemma of Littlewood and Offord, Bull. Amer. Math. Soc., 51 (1945), 898-902.
C. Pelekis and V. Vlasák, On k-antichains in the unit n-cube, arXiv:1908.04727 [math.CA], 2019.
FORMULA
EXAMPLE
n\k| 1 2 3 4 5 6
---+-----------------------------
1 | 1
2 | 2 3
3 | 3 6 7
4 | 6 10 14 15
5 | 10 20 25 30 31
6 | 20 35 50 56 62 63
...
MAPLE
a:=(n, k)->sum(binomial(n, floor((1/2)*n-(1/2)*k)+i), i = 1..k): seq(seq(a(n, k), k = 1..n), n = 1..11);
MATHEMATICA
T[n_, k_]:=Sum[Binomial[n, Floor[(n-k)/2]+i], {i, 1, k}]; Table[T[n, k], {n, 1, 11}, {k, 1, n}]
PROG
(GAP) Flat(List([1..11], n->List([1..n], k->Sum([1..k], i->Binomial(n, Int((n-k)/2)+i)))));
(PARI) T(n, k) = sum(i=1, k, binomial(n, floor((n-k)/2)+i));
CROSSREFS
KEYWORD
nonn,tabl
AUTHOR
Stefano Spezia, Aug 28 2019
STATUS
approved