A322291 Triangle T read by rows: T(n, k) = Sum_{i=1..k} binomial(n, floor((n-k)/2)+i).

1, 2, 3, 3, 6, 7, 6, 10, 14, 15, 10, 20, 25, 30, 31, 20, 35, 50, 56, 62, 63, 35, 70, 91, 112, 119, 126, 127, 70, 126, 182, 210, 238, 246, 254, 255, 126, 252, 336, 420, 456, 492, 501, 510, 511, 252, 462, 672, 792, 912, 957, 1002, 1012, 1022, 1023, 462, 924, 1254, 1584, 1749, 1914, 1969, 2024, 2035, 2046, 2047

Offset: 1

Author

Stefano Spezia, Aug 28 2019

Keywords

• nonn
• tabl

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

Examples

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

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.

Crossrefs

Cf. A000225 (diagonal), A189390 (row sums).

Cf. A000247, A000918, A001405, A006126, A007318, A052515, A052516, A263857, A272352, A306550.

Programs

GAP

Flat(List([1..11], n->List([1..n], k->Sum([1..k], i->Binomial(n, Int((n-k)/2)+i)))));

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}]

PARI

T(n, k) = sum(i=1, k, binomial(n, floor((n-k)/2)+i));

Formula

T(n, n) = A000225(n).

T(n, n-1) = A000918(n).

T(n, n-2) = A000247(n).

T(n, n-3) = A052515(n).

T(n, n-4) = A272352(n+1).

T(n, n-5) = A052516(n).