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

 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 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= 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 Cf. A000079, A000045, A000930, A003269, A003520, A005708, A005709, A005710. Cf. A005711, A017904, A017905, A017906, A017907, A017908, A017909, A291149. Sequence in context: A057495 A321366 A180246 * A246367 A048167 A207790 Adjacent sequences:  A329143 A329144 A329145 * A329147 A329148 A329149 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.

Last modified June 29 23:00 EDT 2022. Contains 354913 sequences. (Running on oeis4.)