A005709 -id:A005709 - cp's OEIS frontend

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, 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

Offset: 1

Gerhard Kirchner, Nov 06 2019

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.

			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;
  ...

Gerhard Kirchner, First 141 rows of T(n,k): Table of n, a(n) for n = 1..10011

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

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

T(n,k) = sum(j=0, ceil(n/k), binomial(n-(k-1)*(j-1), j)); \\ Andrew Howroyd, Nov 06 2019

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<=iIn 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.

A242763 a(n) = 1 for n <= 7; a(n) = a(n-5) + a(n-7) for n>7.

Original entry on oeis.org

1, 1, 1, 1, 1, 1, 1, 2, 2, 2, 2, 2, 3, 3, 4, 4, 4, 5, 5, 7, 7, 8, 9, 9, 12, 12, 15, 16, 17, 21, 21, 27, 28, 32, 37, 38, 48, 49, 59, 65, 70, 85, 87, 107, 114, 129, 150, 157, 192, 201, 236, 264, 286, 342, 358, 428, 465, 522, 606, 644, 770, 823, 950, 1071, 1166, 1376

Offset: 1

Vicente Jesús Maniega Granado, Oct 03 2016

Generalized Fibonacci growth sequence using i = 2 as maturity period, j = 5 as conception period, and k = 2 as growth factor.

Maturity period is the number of periods that a Fibonacci tree node needs for being able to start developing branches. Conception period is the number of periods in a Fibonacci tree node needed to develop new branches since its maturity. Growth factor is the number of additional branches developed by a Fibonacci tree node, plus 1, and equals the base of the exponential series related to the given tree if maturity factor would be zero. Standard Fibonacci would use 1 as maturity period, 1 as conception period, and 2 as growth factor as the series becomes equal to 2^n with a maturity period of 0. Related to Lucas sequences.

			For n = 13 the a(13) = a(8) + a(6) = 2 + 1 = 3.

Colin Barker, Table of n, a(n) for n = 1..1000
Julia Collins, Fibonacci Tree
Fractal Foundation, Fibonacci Fractals
D. H. Lehmer, An extended theory of Lucas' functions, Annals of Mathematics, Second Series, Vol. 31, No. 3 (Jul., 1930), pp. 419-448.
Index entries for linear recurrences with constant coefficients, signature (0,0,0,0,1,0,1).

Cf. A000079 (i = 0, j = 1, k = 2), A000244 (i = 0, j = 1, k = 3), A000302 (i = 0, j = 1, k = 4), A000351 (i = 0, j = 1, k = 5), A000400 (i = 0, j = 1, k = 6), A000420 (i = 0, j = 1, k = 7), A001018 (i = 0, j = 1, k = 8), A001019 (i = 0, j = 1, k = 9), A011557 (i = 0, j = 1, k = 10), A001020 (i = 0, j = 1, k = 11), A001021 (i = 0, j = 1, k = 12), A016116 (i = 0, j = 2, k = 2), A108411 (i = 0, j = 2, k = 3), A213173 (i = 0, j = 2, k = 4), A074872 (i = 0, j = 2, k = 5), A173862 (i = 0, j = 3, k = 2), A127975 (i = 0, j = 3, k = 3), A200675 (i = 0, j = 4, k = 2), A111575 (i = 0, j = 4, k = 3), A000045 (i = 1, j = 1, k = 2), A001045 (i = 1, j = 1, k = 3), A006130 (i = 1, j = 1, k = 4), A006131 (i = 1, j = 1, k = 5), A015440 (i = 1, j = 1, k = 6), A015441 (i = 1, j = 1, k = 7), A015442 (i = 1, j = 1, k = 8), A015443 (i = 1, j = 1, k = 9), A015445 (i = 1, j = 1, k = 10), A015446 (i = 1, j = 1, k = 11), A015447 (i = 1, j = 1, k = 12), A000931 (i = 1, j = 2, k = 2), A159284 (i = 1, j = 2, k = 3), A238389 (i = 1, j = 2, k = 4), A097041 (i = 1, j = 2, k = 10), A079398 (i = 1, j = 3, k = 2), A103372 (i = 1, j = 4, k = 2), A103373 (i = 1, j = 5, k = 2), A103374 (i = 1, j = 6, k = 2), A000930 (i = 2, j = 1, k = 2), A077949 (i = 2, j = 1, k = 3), A084386 (i = 2, j = 1, k = 4), A089977 (i = 2, j = 1, k = 5), A178205 (i = 2, j = 1, k = 11), A103609 (i = 2, j = 2, k = 2), A077953 (i = 2, j = 2, k = 3), A226503 (i = 2, j = 3, k = 2), A122521 (i = 2, j = 6, k = 2), A003269 (i = 3, j = 1, k = 2), A052942 (i = 3, j = 1, k = 3), A005686 (i = 3, j = 2, k = 2), A237714 (i = 3, j = 2, k = 3), A238391 (i = 3, j = 2, k = 4), A247049 (i = 3, j = 3, k = 2), A077886 (i = 3, j = 3, k = 3), A003520 (i = 4, j = 1, k = 2), A108104 (i = 4, j = 2, k = 2), A005708 (i = 5, j = 1, k = 2), A237716 (i = 5, j = 2, k = 3), A005709 (i = 6, j = 1, k = 2), A122522 (i = 6, j = 2, k = 2), A005710 (i = 7, j = 1, k = 2), A237718 (i = 7, j = 2, k = 3), A017903 (i = 8, j = 1, k = 2).

[n le 7 select 1 else Self(n-5)+Self(n-7): n in [1..70]]; // Vincenzo Librandi, Nov 30 2016

LinearRecurrence[{0, 0, 0, 0, 1, 0, 1}, {1, 1, 1, 1, 1, 1, 1}, 70] (*  or *)
CoefficientList[ Series[(1+x+x^2+x^3+x^4)/(1-x^5-x^7), {x, 0, 70}], x] (* Robert G. Wilson v, Nov 25 2016 *)
nxt[{a_,b_,c_,d_,e_,f_,g_}]:={b,c,d,e,f,g,a+c}; NestList[nxt,{1,1,1,1,1,1,1},70][[;;,1]] (* Harvey P. Dale, Oct 22 2024 *)

Vec(x*(1+x+x^2+x^3+x^4)/((1-x+x^2)*(1+x-x^3-x^4-x^5)) + O(x^100)) \\ Colin Barker, Oct 27 2016

@CachedFunction # a = A242763
def a(n): return 1 if n<8 else a(n-5) +a(n-7)
[a(n) for n in range(1,76)] # G. C. Greubel, Oct 23 2024

Generic a(n) = 1 for n <= i+j; a(n) = a(n-j) + (k-1)*a(n-(i+j)) for n>i+j where i = maturity period, j = conception period, k = growth factor.
G.f.: x*(1+x+x^2+x^3+x^4) / ((1-x+x^2)*(1+x-x^3-x^4-x^5)). - Colin Barker, Oct 09 2016
Generic g.f.: x*(Sum_{l=0..j-1} x^l) / (1-x^j-(k-1)*x^(i+j)), with i > 0, j > 0 and k > 1.

A247489 Square array read by antidiagonals: A(k, n) = hypergeometric(P, Q, -k^k/(k-1)^(k-1)) rounded to the nearest integer, P = [(j-n)/k, j=0..k-1] and Q = [(j-n)/(k-1), j=0..k-2], k>=1, n>=0.

Original entry on oeis.org

1, 0, 2, 0, 1, 4, 0, 1, 2, 8, 0, 1, 1, 3, 16, 0, 1, 1, 2, 5, 32, 0, 1, 1, 1, 3, 8, 64, 0, 0, 1, 1, 2, 4, 13, 128, 0, 0, 1, 1, 1, 3, 6, 21, 256, 0, 0, 1, 1, 1, 2, 4, 9, 34, 512, 0, 0, 1, 1, 1, 1, 3, 5, 13, 55, 1024, 0, 0, 1, 1, 1, 1, 2, 4, 7, 19, 89, 2048

Offset: 0

Peter Luschny, Sep 19 2014

Conjecture: hypergeometric(P, Q, -k^k/(k-1)^(k-1)) = sum_{j=0.. floor(n/k)} binomial(n-(k-1)*j, j) for n>=(k-1)^2, P and Q as above. (This means for n>=(k-1)^2 the representation is exact without rounding.)

			First few rows of the square array:
[k\n]                                             if conjecture true
[1], 1, 2, 4, 8, 16, 32, 64, 128, 256, 512, ...     A000079  n>=0
[2], 0, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, ...     'A000045' n>=1
[3], 0, 1, 1, 2, 3, 4, 6, 9, 13, 19, 28, 41, ...    A000930  n>=4
[4], 0, 1, 1, 1, 2, 3, 4, 5, 7, 10, 14, 19, ...     A003269  n>=9
[5], 0, 1, 1, 1, 1, 2, 3, 4, 5, 6, 9, 11, 15, ...   A003520  n>=16
[6], 0, 1, 1, 1, 1, 1, 2, 3, 3, 4, 6, 7, 10, ...    A005708  n>=25
[7], 0, 0, 1, 1, 1, 1, 1, 2, 3, 3, 4, 5, 7, 8, ...  A005709  n>=36
[8], 0, 0, 1, 1, 1, 1, 2, 1, 2, 3, 3, 4, 5, 6, ...  A005710  n>=49
'A000045' means that the Fibonacci numbers as referenced here start 1, 1, 2, 3, ... for n>=0.

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

A247489 := proc(k, n)
seq((j-n)/k, j=0..k-1); seq((j-n)/(k-1), j=0..k-2);
hypergeom([%%], [%], -k^k/(k-1)^(k-1));
round(evalf(%,100)) end: # Adjust precision if necessary!
for k from 1 to 9 do print(seq(A247489(k, n), n=0..16)) od;

def A247489(k, n):
    P = [(j-n)/k for j in range(k)]
    Q = [(j-n)/(k-1) for j in range(k-1)]
    H = hypergeometric(P, Q, -k^k/(k-1)^(k-1))
    return round(H.n(100)) # Adjust precision if necessary!

A292027 a(n) = a(n-7) + a(n-11), starting a(0)=a(1)=...= a(10) = 1.

Original entry on oeis.org

1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 2, 2, 2, 2, 2, 2, 2, 3, 3, 3, 3, 4, 4, 4, 5, 5, 5, 5, 7, 7, 7, 8, 9, 9, 9, 12, 12, 12, 13, 16, 16, 16, 20, 21, 21, 22, 28, 28, 28, 33, 37, 37, 38, 48, 49, 49, 55, 65, 65, 66, 81, 86, 86, 93, 113, 114, 115, 136, 151, 151, 159, 194, 200, 201, 229, 264, 265, 274

Offset: 0

Jason Bruce, Sep 07 2017

Kenneth H. Rosen, Discrete Mathematics and its Applications, McGraw-Hill, 2012, 501-503.

Index entries for linear recurrences with constant coefficients, signature (0,0,0,0,0,0,1,0,0,0,1).

Cf. A000930, A003269, A003520, A005708, A005709.

import java.util.Arrays;
public class IntegerSequences
{
    public static void main(String[] args)
    {
        int j = 7;
        int k = 11;
        // Set N to the number of terms you would like to generate.
        int N = 200;
        long[] G = new long[N];
        for(int i=0; i

LinearRecurrence[{0,0,0,0,0,0,1,0,0,0,1},{1,1,1,1,1,1,1,1,1,1,1},80] (* Harvey P. Dale, Oct 09 2018 *)

G.f.: (x^6 + x^5 + x^4 + x^3 + x^2 + x + 1)/(1 - x^7 - x^11). - R. J. Mathar and N. J. A. Sloane, Nov 10 2017

A306489 Square array A(n,k), n >= 0, k >= 1, read by antidiagonals, where column k is the expansion of 1/(1 - Sum_{d|k} x^d).

Original entry on oeis.org

1, 1, 1, 1, 1, 1, 1, 1, 2, 1, 1, 1, 1, 3, 1, 1, 1, 2, 2, 5, 1, 1, 1, 1, 3, 3, 8, 1, 1, 1, 2, 1, 6, 4, 13, 1, 1, 1, 1, 4, 1, 10, 6, 21, 1, 1, 1, 2, 1, 7, 2, 18, 9, 34, 1, 1, 1, 1, 3, 1, 13, 3, 31, 13, 55, 1, 1, 1, 2, 2, 6, 1, 25, 4, 55, 19, 89, 1, 1, 1, 1, 3, 3, 10, 1, 46, 5, 96, 28, 144, 1

Offset: 0

Ilya Gutkovskiy, Feb 19 2019

A(n,k) is the number of compositions (ordered partitions) of n into divisors of k.

			Square array begins:
  1,  1,  1,   1,  1,   1,  ...
  1,  1,  1,   1,  1,   1,  ...
  1,  2,  1,   2,  1,   2,  ...
  1,  3,  2,   3,  1,   4,  ...
  1,  5,  3,   6,  1,   7,  ...
  1,  8,  4,  10,  2,  13,  ...

Columns k=1..7 give A000012, A000045 (for n > 0), A000930, A060945, A003520, A079958, A005709.

Cf. A100346, A214575.

Table[Function[k, SeriesCoefficient[1/(1 - Sum[x^d, {d, Divisors[k]}]), {x, 0, n}]][i - n + 1], {i, 0, 12}, {n, 0, i}] // Flatten

G.f. of column k: 1/(1 - Sum_{d|k} x^d).

A376695 a(n) = Sum_{k=0..floor(n/2)} binomial(n-2*k,floor(k/3)).

Original entry on oeis.org

1, 1, 2, 2, 3, 3, 3, 4, 5, 7, 9, 12, 15, 18, 22, 27, 34, 43, 55, 70, 88, 110, 137, 171, 214, 269, 339, 427, 537, 674, 845, 1059, 1328, 1667, 2094, 2631, 3305, 4150, 5209, 6537, 8204, 10298, 12929, 16234, 20384, 25593, 32130, 40334, 50632, 63561, 79795, 100179, 125772, 157902, 198236

Offset: 0

Seiichi Manyama, Oct 01 2024

nonn

Index entries for linear recurrences with constant coefficients, signature (1,0,0,0,0,0,1).

Cf. A000930, A098523.

Cf. A005709.

a(n) = sum(k=0, n\2, binomial(n-2*k, k\3));

my(N=60, x='x+O('x^N)); Vec((1+x^2+x^4)/(1-x*(1+x^6)))

G.f.: (1-x^6)/((1-x^2) * (1-x*(1+x^6))) = (1+x^2+x^4)/(1-x*(1+x^6)).
a(n) = a(n-1) + a(n-7).
a(n) = A005709(n) + A005709(n-2) + A005709(n-4).

Previous Showing 31-36 of 36 results.

cp's OEIS Frontend

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.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

PARI

Formula

A242763 a(n) = 1 for n <= 7; a(n) = a(n-5) + a(n-7) for n>7.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Magma

Mathematica

PARI

SageMath

Formula

A247489 Square array read by antidiagonals: A(k, n) = hypergeometric(P, Q, -k^k/(k-1)^(k-1)) rounded to the nearest integer, P = [(j-n)/k, j=0..k-1] and Q = [(j-n)/(k-1), j=0..k-2], k>=1, n>=0.

Views

Author

Keywords

Comments

Examples

Crossrefs

Programs

Maple

Sage

A292027 a(n) = a(n-7) + a(n-11), starting a(0)=a(1)=...= a(10) = 1.

Views

Author

Keywords

References

Links

Crossrefs

Programs

Java

Mathematica

Formula

A306489 Square array A(n,k), n >= 0, k >= 1, read by antidiagonals, where column k is the expansion of 1/(1 - Sum_{d|k} x^d).

Views

Author

Keywords

Comments

Examples

Crossrefs

Programs

Mathematica

Formula

A376695 a(n) = Sum_{k=0..floor(n/2)} binomial(n-2*k,floor(k/3)).

Views

Author

Keywords

Links

Crossrefs

Programs

PARI

PARI

Formula