OFFSET
1,1
COMMENTS
The restriction "the difference between any two elements is k or greater" does not apply to subsets with fewer than two elements.
Therefore T(n,k) = n+1 is valid not only for n=k, but also for n < k. These terms do not occur in the triangular matrix, but they help to simplify formula(3).
T(n,k) is, for 1 <= k <= 16, a subsequence of another sequence:
T(n,1) = A000079(n)
T(n,2) = A000045(n+2)
T(n,3) = A000930(n+2)
T(n,4) = A003269(n+4)
T(n,5) = A003520(n+4)
T(n,6) = A005708(n+5)
T(n,7) = A005709(n+6)
T(n,8) = A005710(n+7)
T(n,9) = A005711(n+7)
T(n,10) = A017904(n+19)
T(n,11) = A017905(n+21)
T(n,12) = A017906(n+23)
T(n,13) = A017907(n+25)
T(n,14) = A017908(n+27)
T(n,15) = A017909(n+29)
T(n,16) = A291149(n+16)
Note the recurrence formula(3) below: T(n,k) = T(n-1,k) + T(n-k,k), n >= 2*k.
As to the corresponding recurrence A..(n) = A..(n-1) + A..(n-k), see definition (1 <= k <= 9) or formula (k=13) or b-files in the remaining cases.
LINKS
Gerhard Kirchner, First 141 rows of T(n,k): Table of n, a(n) for n = 1..10011
FORMULA
Let g(n,k,j) be the number of subsets of {1,...,n} with j elements such that the difference between any two elements is k or greater. Then
(1) T(n,k) = Sum_{j = 0..n} g(n,k,j)
(2) g(n,k,j) = binomial((n-(k-1)*(j-1),j) with the convention binomial(m,j)=0 for j > m
(3) T(n,k) = T(n-1,k) + T(n-k,k), n >= 2*k
or: T(n,k) = n+1 for n <= k and T(n,k) = T(n-1,k) + T(n-k,k) for n > k (see comments).
Formula(1) is evident.
Proof of formula(2):
Let C(n,k,j) be the class of subsets of {1,...,n} with j elements such that the difference between any two elements is k or greater. Let S be one of these subsets and let us write it as a j-tuple (c(1),..,c(j)) with c(i+1)-c(i)>=k, 1<=i<j. S is the sum of a "basic" tuple (1, k+1,..,(j-1)*k+1) and a "generating" tuple (d(1),..d(j)) with d(i)=c(i)-i*k-1, where the condition 0 <= d(1) <= ... <= d(j) <= n-(j-1)*k-1 is satisfied. The number of j-tuples defined by this condition equals the number of subsets in C(n,k,j).
In particular, the number of subsets of C(m,1,j) is binomial((m,j), the basic tuple is (1,...,j) and the generating tuple is (d(1),...,d(j)) with 0 <= d(1) <= ... <= d(j) <= m-j.
With m-j = n-(j-1)*k-1, i.e., m = n-(j-1)*(k-1), the numbers of subsets in C(n,k,j) and C(m,1,j) are equal: g(n,k,j) = binomial((n-(k-1)*(j-1),j) qed
Proof of formula(3):
Using the binomial recurrence binomial((m,j) = binomial((m-1,j) + binomial((m-1,j-1) for m = n-(j-1)*(k-1), we find:
T(n,k) = Sum_{j = 0..n} binomial((n-(k-1)*(j-1),j)
= Sum_{j = 0..n-1} binomial((n-1-(k-1)*(j-1),j)
+ Sum_{j = 1..n} binomial((n-1-(k-1)*(j-1),j-1)
= T(n-1,k) + Sum_{j = 0..n-1} binomial((n-1-(k-1)*j,j)
= T(n-1,k) + Sum_{j = 0..n-k} binomial((n-k-(k-1)*(j-1),j)
= T(n-1,k) + T(n-k,k) qed
T(n-k,k) must be known in this recurrence, therefore n >= 2*k.
For k <= n < 2*k, formula(1) must be applied.
EXAMPLE
a(1) = T(1,1) = |{}, {1}| = 2
a(2) = T(2,1) = |{}, {1}, {2}, {1,2}| = 4
a(3) = T(2,2) = |{}, {1}, {2}| = 3
a(4) = T(3,1) = |{}, {1}, {2}, {3}, {1,2}, {1,3}, {2,3}, {1,2,3}| = 8
a(5) = T(3,2) = |{}, {1}, {2}, {3}, {1,3}| = 5
etc.
The triangle begins:
2;
4, 3;
8, 5, 4;
16, 8, 6, 5;
32, 13, 9, 7, 6;
...
PROG
(PARI) T(n, k) = sum(j=0, ceil(n/k), binomial(n-(k-1)*(j-1), j)); \\ Andrew Howroyd, Nov 06 2019
CROSSREFS
KEYWORD
nonn,tabl
AUTHOR
Gerhard Kirchner, Nov 06 2019
STATUS
approved