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

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

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.

License Agreements, Terms of Use, Privacy Policy. .

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