A325983 -id:A325983 - cp's OEIS frontend

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

Stefano Spezia, May 29 2019

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

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

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.

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

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

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

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

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

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

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

A335322 Triangle read by rows: T(n, k) = binomial(n, floor((n+k+1)/2)) with k <= n.

Original entry on oeis.org

1, 1, 1, 3, 1, 1, 4, 4, 1, 1, 10, 5, 5, 1, 1, 15, 15, 6, 6, 1, 1, 35, 21, 21, 7, 7, 1, 1, 56, 56, 28, 28, 8, 8, 1, 1, 126, 84, 84, 36, 36, 9, 9, 1, 1, 210, 210, 120, 120, 45, 45, 10, 10, 1, 1, 462, 330, 330, 165, 165, 55, 55, 11, 11, 1, 1, 792, 792, 495, 495, 220, 220, 66, 66, 12, 12, 1, 1

Offset: 1

Stefano Spezia, May 31 2020

T(n, k) is a tight upper bound of the cardinality of an intersecting Sperner family or antichain of the set {1, 2,..., n}, where every collection of pairwise independent subsets is characterized by an intersection of cardinality at least k (see Theorem 1.3 in Wong and Tay).

Equals A061554 with the first row of the array (resp. the first column of the triangle) removed. - Georg Fischer, Jul 26 2023

			The triangle T(n, k) begins
n\k|  1   2   3   4   5   6   7   8
---+-------------------------------
1  |  1
2  |  1   1
3  |  3   1   1
4  |  4   4   1   1
5  | 10   5   5   1   1
6  | 15  15   6   6   1   1
7  | 35  21  21   7   7   1   1
8  | 56  56  28  28   8   8   1   1
...

Eric Charles Milner, A Combinatorial Theorem On Systems of Sets, Journal of the London Mathematical Society, 43, (1968), 204-206.
W. H. W. Wong and E. G. Tay, On Cross-intersecting Sperner Families, arXiv:2001.01910 [math.CO], 2020.
Index entries for sequences related to antichains.

Cf. A000372, A001405, A004526, A007318, A007695, A061554, A266696, A325982, A325983.

Cf. A037951 (k=3), A037952 (k=1), A037953 (k=5), A037954 (k=7), A037955 (k=2), A037956 (k=4), A037957 (k=6), A037958 (k=8), A045621 (row sums).

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

T(n, k) = binomial(n, (n+k+1)\2);
vector(10, n, vector(n, k, T(n, k))) \\ Michel Marcus, Jun 01 2020

T(n, k) = A007318(n, A004526(n+k+1)) with k <= n.

cp's OEIS Frontend

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.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

GAP

Magma

Maple

Mathematica

PARI

Formula