login
The OEIS is supported by the many generous donors to the OEIS Foundation.

 

Logo
Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
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. 2
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, 256, 55, 28, 19, 15, 12, 10, 9, 512, 89, 41, 26, 20, 16, 13, 11, 10, 1024, 144, 60, 36, 26, 21, 17, 14, 12, 11, 2048, 233, 88, 50, 34, 27, 22, 18, 15, 13, 12, 4096, 377, 129 (list; table; graph; refs; listen; history; text; internal format)
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
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
Sequence in context: A057495 A321366 A180246 * A246367 A367263 A048167
KEYWORD
nonn,tabl
AUTHOR
Gerhard Kirchner, Nov 06 2019
STATUS
approved

Lookup | Welcome | Wiki | Register | Music | Plot 2 | Demos | Index | Browse | More | WebCam
Contribute new seq. or comment | Format | Style Sheet | Transforms | Superseeker | Recents
The OEIS Community | Maintained by The OEIS Foundation Inc.

License Agreements, Terms of Use, Privacy Policy. .

Last modified March 29 00:26 EDT 2024. Contains 371264 sequences. (Running on oeis4.)