login
Triangle read by rows: T(n,k) is the number of subsets of {1,...,n} such that the difference between any two elements is k or greater, 1 <= k <= n.
2

%I #35 Mar 15 2021 02:07:18

%S 2,4,3,8,5,4,16,8,6,5,32,13,9,7,6,64,21,13,10,8,7,128,34,19,14,11,9,8,

%T 256,55,28,19,15,12,10,9,512,89,41,26,20,16,13,11,10,1024,144,60,36,

%U 26,21,17,14,12,11,2048,233,88,50,34,27,22,18,15,13,12,4096,377,129

%N Triangle read by rows: T(n,k) is the number of subsets of {1,...,n} such that the difference between any two elements is k or greater, 1 <= k <= n.

%C The restriction "the difference between any two elements is k or greater" does not apply to subsets with fewer than two elements.

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

%C T(n,k) is, for 1 <= k <= 16, a subsequence of another sequence:

%C T(n,1) = A000079(n)

%C T(n,2) = A000045(n+2)

%C T(n,3) = A000930(n+2)

%C T(n,4) = A003269(n+4)

%C T(n,5) = A003520(n+4)

%C T(n,6) = A005708(n+5)

%C T(n,7) = A005709(n+6)

%C T(n,8) = A005710(n+7)

%C T(n,9) = A005711(n+7)

%C T(n,10) = A017904(n+19)

%C T(n,11) = A017905(n+21)

%C T(n,12) = A017906(n+23)

%C T(n,13) = A017907(n+25)

%C T(n,14) = A017908(n+27)

%C T(n,15) = A017909(n+29)

%C T(n,16) = A291149(n+16)

%C Note the recurrence formula(3) below: T(n,k) = T(n-1,k) + T(n-k,k), n >= 2*k.

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

%H Gerhard Kirchner, <a href="/A329146/b329146.txt">First 141 rows of T(n,k): Table of n, a(n) for n = 1..10011</a>

%F 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

%F (1) T(n,k) = Sum_{j = 0..n} g(n,k,j)

%F (2) g(n,k,j) = binomial((n-(k-1)*(j-1),j) with the convention binomial(m,j)=0 for j > m

%F (3) T(n,k) = T(n-1,k) + T(n-k,k), n >= 2*k

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

%F Formula(1) is evident.

%F Proof of formula(2):

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

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

%F 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

%F Proof of formula(3):

%F 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:

%F T(n,k) = Sum_{j = 0..n} binomial((n-(k-1)*(j-1),j)

%F = Sum_{j = 0..n-1} binomial((n-1-(k-1)*(j-1),j)

%F + Sum_{j = 1..n} binomial((n-1-(k-1)*(j-1),j-1)

%F = T(n-1,k) + Sum_{j = 0..n-1} binomial((n-1-(k-1)*j,j)

%F = T(n-1,k) + Sum_{j = 0..n-k} binomial((n-k-(k-1)*(j-1),j)

%F = T(n-1,k) + T(n-k,k) qed

%F T(n-k,k) must be known in this recurrence, therefore n >= 2*k.

%F For k <= n < 2*k, formula(1) must be applied.

%e a(1) = T(1,1) = |{}, {1}| = 2

%e a(2) = T(2,1) = |{}, {1}, {2}, {1,2}| = 4

%e a(3) = T(2,2) = |{}, {1}, {2}| = 3

%e a(4) = T(3,1) = |{}, {1}, {2}, {3}, {1,2}, {1,3}, {2,3}, {1,2,3}| = 8

%e a(5) = T(3,2) = |{}, {1}, {2}, {3}, {1,3}| = 5

%e etc.

%e The triangle begins:

%e 2;

%e 4, 3;

%e 8, 5, 4;

%e 16, 8, 6, 5;

%e 32, 13, 9, 7, 6;

%e ...

%o (PARI) T(n,k) = sum(j=0, ceil(n/k), binomial(n-(k-1)*(j-1), j)); \\ _Andrew Howroyd_, Nov 06 2019

%Y Cf. A000079, A000045, A000930, A003269, A003520, A005708, A005709, A005710.

%Y Cf. A005711, A017904, A017905, A017906, A017907, A017908, A017909, A291149.

%K nonn,tabl

%O 1,1

%A _Gerhard Kirchner_, Nov 06 2019