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

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

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.

Formula

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

Example

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

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

Prog

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

Crossrefs

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

Sequence in context: A046929 A068695 A110787 * A202338 A139002 A251913

Adjacent sequences: A325979 A325980 A325981 * A325983 A325984 A325985

Keyword

nonn,tabf

Author

Stefano Spezia, May 29 2019

Status

approved