A325982 Triangle read by rows: T(n, k) = binomial(n - 1, k - 1) - binomial(n - k - 1, k - 1) + 1, with n >= 1 and 0 <= k < n/2.

1, 1, 1, 1, 1, 1, 1, 1, 3, 1, 1, 3, 1, 1, 3, 13, 1, 1, 3, 16, 1, 1, 3, 19, 53, 1, 1, 3, 22, 75, 1, 1, 3, 25, 101, 206, 1, 1, 3, 28, 131, 316, 1, 1, 3, 31, 165, 461, 787, 1, 1, 3, 34, 203, 646, 1267, 1, 1, 3, 37, 245, 876, 1947, 2997, 1, 1, 3, 40, 291, 1156, 2878, 4978

Offset: 1

Author

Stefano Spezia, May 29 2019

Keywords

• nonn
• tabf

Comments

Given X an n-element set and F a family of k-subsets of X. If n > 2*k and F is a nontrivial intersecting family, then the cardinality of F is almost equal to T(n, k). A family F is called trivial if all its members contain a fixed element of X (see Hilton-Milner Theorem in Links).

Examples

			The triangle T(n, k) begins
  n\k|   0   1   2    3    4
  ---+----------------------
   1 |   1
   2 |   1
   3 |   1   1
   4 |   1   1
   5 |   1   1   3
   6 |   1   1   3
   7 |   1   1   3   13
   8 |   1   1   3   16
   9 |   1   1   3   19   53
  10 |   1   1   3   22   75
  ...
		

Links

• Stefano Spezia, First 200 rows of the triangle, flattened
• Peter Frankl, A simple proof of the Hilton-Milner theorem, Moscow Journal of Combinatorics and Number Theory, Volume 8, Number 2 (2019), 97-101.
• Peter Frankl and Zoltán Füredi, Non-trivial Intersecting Families, Journal of Combinatorial Theory, Series A, Vol. 41, No. 1, January 1986.
• Peter Frankl and Andrey Kupavskii, Sharp results concerning disjoint cross-intersecting families, arXiv:1905.08123 [math.CO], 2019.
• Peter Frankl and Andrey Kupavskii, Uniform intersecting families with large covering number, arXiv:2106.05344 [math.CO], 2021. See p. 2.
• Anthony J. W. Hilton and Eric Charles Milner, Some Intersection Theorems for Systems of Finite Sets, The Quarterly Journal of Mathematics, Volume 18, Issue 1, 1967, Pages 369-384.
• Russ Woodroofe, An algebraic groups perspective on Erdős-Ko-Rado, arXiv:2007.03707 [math.CO], 2020. See p. 2.

Crossrefs

Cf. A004526, A007318, A325983 (row sums).

Programs

GAP

Flat(List([1..15], n->List([0..Int((n-1)/2)], k->Binomial(n-1, k-1)-Binomial(n-k-1, k-1)+1)));

Magma

[[Binomial(n-1, k-1)-Binomial(n-k-1, k-1)+1: k in [0..Floor((n-1)/2)]]: n in [1 .. 15]]; // triangle output

Maple

a := (n, k) -> binomial(n-1, k-1)-binomial(n-k-1, k-1)+1: seq(seq(a(n, k), k = 0 .. floor((n-1)/2)), n = 1 .. 15);

Mathematica

T[n_,k_]:=Binomial[n-1,k-1]-Binomial[n-k-1,k-1]+1; Flatten[Table[T[n,k],{n,1,15},{k,0,Floor[(n-1)/2]}]]

PARI

T(n, k) = binomial(n - 1, k - 1) - binomial(n - k - 1, k - 1) + 1;
tabf(nn) = for(i=1, nn, for(j=0, floor((i-1)/2), print1(T(i, j), ", ")); print);
tabf(15) \\ triangle output

Formula

T(n, k) = A007318(n - 1, k - 1) - A007318(n - k - 1, k - 1) + 1.