This is a front-end for the Online Encyclopedia of Integer Sequences, made by Christian Perfect. The idea is to provide OEIS entries in non-ancient HTML, and then to think about how they're presented visually. The source code is on GitHub.
%I A329146 #38 Mar 19 2025 05:54:48
%S A329146 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 A329146 256,55,28,19,15,12,10,9,512,89,41,26,20,16,13,11,10,1024,144,60,36,
%U A329146 26,21,17,14,12,11,2048,233,88,50,34,27,22,18,15,13,12,4096,377,129
%N A329146 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 A329146 The restriction "the difference between any two elements is k or greater" does not apply to subsets with fewer than two elements.
%C A329146 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 A329146 T(n,k) is, for 1 <= k <= 16, a subsequence of another sequence:
%C A329146 T(n,1) = A000079(n)
%C A329146 T(n,2) = A000045(n+2)
%C A329146 T(n,3) = A000930(n+2)
%C A329146 T(n,4) = A003269(n+4)
%C A329146 T(n,5) = A003520(n+4)
%C A329146 T(n,6) = A005708(n+5)
%C A329146 T(n,7) = A005709(n+6)
%C A329146 T(n,8) = A005710(n+7)
%C A329146 T(n,9) = A005711(n+7)
%C A329146 T(n,10) = A017904(n+19)
%C A329146 T(n,11) = A017905(n+21)
%C A329146 T(n,12) = A017906(n+23)
%C A329146 T(n,13) = A017907(n+25)
%C A329146 T(n,14) = A017908(n+27)
%C A329146 T(n,15) = A017909(n+29)
%C A329146 T(n,16) = A291149(n+16)
%C A329146 Note the recurrence formula(3) below: T(n,k) = T(n-1,k) + T(n-k,k), n >= 2*k.
%C A329146 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 A329146 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 A329146 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 A329146 (1) T(n,k) = Sum_{j = 0..n} g(n,k,j)
%F A329146 (2) g(n,k,j) = binomial(n-(k-1)*(j-1),j) with the convention binomial(m,j)=0 for j > m
%F A329146 (3) T(n,k) = T(n-1,k) + T(n-k,k), n >= 2*k
%F A329146 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 A329146 Formula(1) is evident.
%F A329146 Proof of formula(2):
%F A329146 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 A329146 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 A329146 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 A329146 Proof of formula(3):
%F A329146 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 A329146 T(n,k) = Sum_{j = 0..n} binomial(n-(k-1)*(j-1),j)
%F A329146 = Sum_{j = 0..n-1} binomial(n-1-(k-1)*(j-1),j)
%F A329146 + Sum_{j = 1..n} binomial(n-1-(k-1)*(j-1),j-1)
%F A329146 = T(n-1,k) + Sum_{j = 0..n-1} binomial(n-1-(k-1)*j,j)
%F A329146 = T(n-1,k) + Sum_{j = 0..n-k} binomial(n-k-(k-1)*(j-1),j)
%F A329146 = T(n-1,k) + T(n-k,k) qed
%F A329146 T(n-k,k) must be known in this recurrence, therefore n >= 2*k.
%F A329146 For k <= n < 2*k, formula(1) must be applied.
%e A329146 a(1) = T(1,1) = |{}, {1}| = 2
%e A329146 a(2) = T(2,1) = |{}, {1}, {2}, {1,2}| = 4
%e A329146 a(3) = T(2,2) = |{}, {1}, {2}| = 3
%e A329146 a(4) = T(3,1) = |{}, {1}, {2}, {3}, {1,2}, {1,3}, {2,3}, {1,2,3}| = 8
%e A329146 a(5) = T(3,2) = |{}, {1}, {2}, {3}, {1,3}| = 5
%e A329146 etc.
%e A329146 The triangle begins:
%e A329146 2;
%e A329146 4, 3;
%e A329146 8, 5, 4;
%e A329146 16, 8, 6, 5;
%e A329146 32, 13, 9, 7, 6;
%e A329146 ...
%o A329146 (PARI) T(n,k) = sum(j=0, ceil(n/k), binomial(n-(k-1)*(j-1), j)); \\ _Andrew Howroyd_, Nov 06 2019
%Y A329146 Cf. A000079, A000045, A000930, A003269, A003520, A005708, A005709, A005710.
%Y A329146 Cf. A005711, A017904, A017905, A017906, A017907, A017908, A017909, A291149.
%K A329146 nonn,tabl
%O A329146 1,1
%A A329146 _Gerhard Kirchner_, Nov 06 2019