A006500 -id:A006500 - cp's OEIS frontend

A376033 Number A(n,k) of binary words of length n avoiding distance (i+1) between "1" digits if the i-th bit is set in the binary representation of k; square array A(n,k), n>=0, k>=0, read by antidiagonals.

1, 1, 2, 1, 2, 4, 1, 2, 3, 8, 1, 2, 4, 5, 16, 1, 2, 3, 6, 8, 32, 1, 2, 4, 4, 9, 13, 64, 1, 2, 3, 8, 6, 15, 21, 128, 1, 2, 4, 5, 12, 9, 25, 34, 256, 1, 2, 3, 6, 7, 18, 13, 40, 55, 512, 1, 2, 4, 4, 8, 11, 27, 19, 64, 89, 1024, 1, 2, 3, 8, 5, 11, 16, 45, 28, 104, 144, 2048

Offset: 0

Alois P. Heinz, Sep 09 2024

Also the number of subsets of [n] avoiding distance (i+1) between elements if the i-th bit is set in the binary representation of k. A(6,3) = 13: {}, {1}, {2}, {3}, {4}, {5}, {6}, {1,4}, {1,5}, {1,6}, {2,5}, {2,6}, {3,6}.
Each column sequence satisfies a linear recurrence with constant coefficients.
The sequence of row n is periodic with period A011782(n) = ceiling(2^(n-1)).

			A(6,6) = 17: 000000, 000001, 000010, 000011, 000100, 000110, 001000, 001100, 010000, 010001, 011000, 100000, 100001, 100010, 100011, 110000, 110001 because 6 = 110_2 and no two "1" digits have distance 2 or 3.
A(6,7) = 10: 000000, 000001, 000010, 000100, 001000, 010000, 010001, 100000, 100001, 100010.
A(7,7) = 14: 0000000, 0000001, 0000010, 0000100, 0001000, 0010000, 0010001, 0100000, 0100001, 0100010, 1000000, 1000001, 1000010, 1000100.
Square array A(n,k) begins:
     1,  1,   1,  1,   1,  1,  1,  1,   1,  1, ...
     2,  2,   2,  2,   2,  2,  2,  2,   2,  2, ...
     4,  3,   4,  3,   4,  3,  4,  3,   4,  3, ...
     8,  5,   6,  4,   8,  5,  6,  4,   8,  5, ...
    16,  8,   9,  6,  12,  7,  8,  5,  16,  8, ...
    32, 13,  15,  9,  18, 11, 11,  7,  24, 11, ...
    64, 21,  25, 13,  27, 16, 17, 10,  36, 17, ...
   128, 34,  40, 19,  45, 25, 27, 14,  54, 25, ...
   256, 55,  64, 28,  75, 37, 41, 19,  81, 37, ...
   512, 89, 104, 41, 125, 57, 60, 26, 135, 57, ...

Alois P. Heinz, Antidiagonals n = 0..200, flattened

Columns k=0-20 give: A000079, A000045(n+2), A006498(n+2), A000930(n+2), A006500, A130137, A079972(n+3), A003269(n+4), A031923(n+1), A263710(n+1), A224809(n+4), A317669(n+4), A351873, A351874, A121832(n+4), A003520(n+4), A208742, A374737, A375977, A375980, A375978.
Rows n=0-2 give: A000012, A007395(k+1), A010702(k+1).
Main diagonal gives A376091.
A(n,2^k-1) gives A141539.
A(2^n-1,2^n-1) gives A376697.
A(n,2^k) gives A209435.
Cf. A011782, A062383, A098011, A376921.

h:= proc(n) option remember; `if`(n=0, 1, 2^(1+ilog2(n))) end:
b:= proc(n, k, t) option remember; `if`(n=0, 1, add(`if`(j=1 and
      Bits[And](t, k)>0, 0, b(n-1, k, irem(2*t+j, h(k)))), j=0..1))
    end:
A:= (n, k)-> b(n, k, 0):
seq(seq(A(n, d-n), n=0..d), d=0..12);

step(v,b)={vector(#v, i, my(j=(i-1)>>1); if(bittest(i-1,0), if(bitand(b,j)==0, v[1+j], 0), v[1+j] + v[1+#v/2+j]));}
col(n,k)={my(v=vector(2^(1+logint(k,2))), r=vector(1+n)); v[1]=r[1]=1; for(i=1, n, v=step(v,k); r[1+i]=vecsum(v)); r}
A(n,k)=if(k==0, 2^n, col(n,k)[n+1]) \\ Andrew Howroyd, Oct 03 2024

A(n,k) = A(n,k+ceiling(2^(n-1))).
A(n,ceiling(2^(n-1))-1) = n+1.
A(n,ceiling(2^(n-2))) = ceiling(3*2^(n-2)) = A098011(n+2).

A031923 Let r and s be consecutive Fibonacci numbers. Sequence is r^4, r^3 s, r^2 s^2, and r s^3.

Original entry on oeis.org

1, 2, 4, 8, 16, 24, 36, 54, 81, 135, 225, 375, 625, 1000, 1600, 2560, 4096, 6656, 10816, 17576, 28561, 46137, 74529, 120393, 194481, 314874, 509796, 825384, 1336336, 2161720, 3496900, 5656750, 9150625, 14807375, 23961025, 38773295, 62742241, 101515536

Offset: 1

Jeff Burch

Two consecutive Fibonacci numbers are coprime. This sequence satisfies a 14th-order linear difference equation. Note that it is the fourth sequence in the sequences that begin with the Fibonacci numbers, A006498, and A006500. Subsequent sequences will have orders 22, 32, and 44. - T. D. Noe, Mar 05 2012

Also the number of subsets of the set {1,2,...,n-1} which do not contain two elements whose difference is 4. - David Nacin, Mar 07 2012

			Since F_5 = 5 and F_6 = 8 are consecutive Fibonacci numbers, 8^4 = 4096, 8^3*5 = 2560, 8^2*5^2 = 1600, 8*5^3 = 1000, and 5^4 = 625 are in the sequence.
The number 3^3*8 = 216 is not in the sequence since 3 and 8 are not consecutive.
If n = 6 then this gives the number of subsets of {1,...,5} not containing both 1 and 5. There are 2^3 subsets containing 1 and 5, giving us 2^5 - 2^3 = 24. Thus a(5) = 24. - _David Nacin_, Mar 07 2012

Vincenzo Librandi, Table of n, a(n) for n = 1..1000
Michael A. Allen, On a Two-Parameter Family of Generalizations of Pascal's Triangle, arXiv:2209.01377 [math.CO], 2022.
Michael A. Allen, Connections between Combinations Without Specified Separations and Strongly Restricted Permutations, Compositions, and Bit Strings, arXiv:2409.00624 [math.CO], 2024. See p. 16.
M. El-Mikkawy and T. Sogabe, A new family of k-Fibonacci numbers, Appl. Math. Comput. 215 (2010) 4456-4461 doi:10.1016/j.amc.2009.12.069, Table 1 k=4.
M. Tetiva, Subsets that make no difference d, Mathematics Magazine 84 (2011), no. 4, 300-301.
Index entries for linear recurrences with constant coefficients, signature (1,1,0,-2,2,2,0,2,-2,-2,0,1,-1,-1).

Cf. A000045, A006498, A006500.

A031923 := proc(n)
    local n0,i,r,s,m ;
    n0 := n-1 ;
    i := floor(n0/4) ;
    r := combinat[fibonacci](i+2) ;
    s := combinat[fibonacci](i+3) ;
    m := modp(n0,4) ;
    r^(4-m)*s^m ;
end proc:
seq(A031923(n),n=1..50) ; # R. J. Mathar, Jan 23 2022

f = Fibonacci[Range[12]]; m = Most[f]; r = Rest[f]; Union[m^4, m^3 r, m^2 r^2, m r^3] (* T. D. Noe, Mar 05 2012 *)
LinearRecurrence[{1, 1, 0, -2, 2, 2, 0, 2, -2, -2, 0, 1, -1, -1}, {1, 2, 4, 8, 16, 24, 36, 54, 81, 135, 225, 375, 625, 1000}, 40] (* T. D. Noe, Mar 05 2012 *)
Table[Fibonacci[Floor[n/4] + 3]^Mod[n, 4]*Fibonacci[Floor[n/4] + 2]^(4 - Mod[n, 4]), {n, 0, 40}] (* David Nacin, Mar 07 2012 *)
cfn[{a_,b_}]:={a^4,a^3 b,a^2 b^2,a b^3}; Flatten[cfn/@Partition[ Fibonacci[ Range[20]],2,1]]//Union (* Harvey P. Dale, Feb 03 2019 *)

for(m=2,10,r=fibonacci(m);s=fibonacci(m+1);print(r^4," ",r^3*s," ",r^2*s^2," ",r*s^3)) \\ Michael B. Porter, Mar 04 2012

def a(n, adict={0:0, 1:0, 2:0, 3:0, 4:0, 5:4, 6:15, 7:37, 8:87, 9:200}):
    if n in adict:
        return adict[n]
    adict[n]=3*a(n-1)-2*a(n-2)+2*a(n-3)-4*a(n-4)+2*a(n-5)-2*a(n-6)-4*a(n-7)-a(n-8)+a(n-9)+2*a(n-10)
    return adict[n] # David Nacin, Mar 07 2012

a(n) = F(floor((n-1)/4) + 3)^(n-1 mod 4)*F(floor((n-1)/4) + 2)^(4 - (n-1 mod 4)) where F(n) is the n-th Fibonacci number. - David Nacin, Mar 07 2012
a(n) = a(n-1) + a(n-2) - 2*a(n-4) + 2*a(n-5) + 2*a(n-6) + 2*a(n-8) - 2*a(n-9) - 2*a(n-10) + a(n-12) - a(n-13) - a(n-14). - David Nacin, Mar 07 2012
G.f.: x*(2 + 2*x + 2*x^2 + 4*x^3 + 4*x^4 - 2*x^6 - 1*x^7 - 4*x^8 - 3*x^9 - x^10 - x^11 - 2*x^12 - x^13)/((1 - x)*(1 + x)*(1 + x^2)*(1 - x - x^2)*(1 + 3*x^4 + x^8)). - David Nacin, Mar 08 2012
a(4*k-3) = F(k+1)^4, a(4*k-2) = F(k+1)^3*F(k+2), a(4*k-1) = F(k+1)^2*F(k+2)^2, a(4*k) = F(k+1)*F(k+2)^3, k >= 1, where F = A000045. - Jianing Song, Feb 06 2019
a(4n+1)= A056571(n+2). a(4n+3)=A197424(n). - R. J. Mathar, Jan 23 2022

a(19) changed from 10416 to 10816 by David Nacin, Mar 04 2012

A350110 Triangle read by rows, T(n,k) = T(n-1,k) + T(n-1,k-1) - T(n-2,k-1) + T(n-3,k-1) + T(n-3,k-2) + T(n-3,k-3) - T(n-4,k-3) - T(n-4,k-4) + delta(n,0)delta(k,0) - delta(n,1)delta(k,1), T(n

Original entry on oeis.org

1, 1, 0, 1, 0, 0, 1, 1, 1, 1, 1, 2, 3, 2, 0, 1, 3, 5, 4, 0, 0, 1, 4, 8, 8, 4, 2, 1, 1, 5, 12, 16, 13, 9, 3, 0, 1, 6, 17, 28, 30, 22, 9, 0, 0, 1, 7, 23, 45, 58, 51, 27, 9, 3, 1, 1, 8, 30, 68, 103, 108, 78, 40, 18, 4, 0, 1, 9, 38, 98, 171, 211, 187, 123, 58, 16, 0, 0

Offset: 0

Michael A. Allen, Dec 21 2021

This is the m=3 member in the sequence of triangles A007318, A059259, A350110, A350111, A350112 which give the number of tilings of an (n+k) X 1 board using k (1,m-1)-fences and n-k unit square tiles. A (1,g)-fence is composed of two unit square tiles separated by a gap of width g.
It is also the m=3, t=2 member of a two-parameter family of triangles such that T(n,k) is the number of tilings of an (n+(t-1)*k) X 1 board using k (1,m-1;t)-combs and n-k unit square tiles. A (1,g;t)-comb is composed of a line of t unit square tiles separated from each other by gaps of width g. - Michael A. Allen, Dec 27 2021
T(3*j+r-k,k) is the coefficient of x^k in (f(j,x))^(3-r)*(f(j+1,x))^r for r=0,1,2 where f(n,x) is one form of a Fibonacci polynomial defined by f(n+1,x)=f(n,x)+x*f(n-1,x) where f(0,x)=1 and f(n<0,x)=0.
T(n+3-k,k) is the number of subsets of {1,2,...,n} of size k such that no two elements in a subset differ by 3.
Sum of (n+3)-th antidiagonal (counting initial 1 as the 0th) is A006500(n).

			Triangle begins:
   1;
   1,   0;
   1,   0,   0;
   1,   1,   1,   1;
   1,   2,   3,   2,   0;
   1,   3,   5,   4,   0,   0;
   1,   4,   8,   8,   4,   2,   1;
   1,   5,  12,  16,  13,   9,   3,   0;
   1,   6,  17,  28,  30,  22,   9,   0,   0;
   1,   7,  23,  45,  58,  51,  27,   9,   3,   1;
   1,   8,  30,  68, 103, 108,  78,  40,  18,   4,   0;
   1,   9,  38,  98, 171, 211, 187, 123,  58,  16,   0,   0;
   1,  10,  47, 136, 269, 382, 399, 310, 176,  64,  16,   4,   1;

Michael A. Allen, On a Two-Parameter Family of Generalizations of Pascal's Triangle, arXiv:2209.01377 [math.CO], 2022.
Michael A. Allen, On A Two-Parameter Family of Generalizations of Pascal's Triangle, J. Int. Seq. 25 (2022) Article 22.9.8.
Michael A. Allen and Kenneth Edwards, On Two Families of Generalizations of Pascal's Triangle, J. Int. Seq. 25 (2022) Article 22.7.1.

Other members of the two-parameter family of triangles: A007318 (m=1,t=2), A059259 (m=2,t=2), A350111 (m=4,t=2), A350112 (m=5,t=2), A354665 (m=2,t=3), A354666 (m=2,t=4), A354667 (m=2,t=5), A354668 (m=3,t=3).

Other triangles related to tiling using fences: A123521, A157897, A335964.

Mathematica
```
T[n_, k_]:=If[k<0 || n
				
```

T(n,0) = 1.
T(n,n) = delta(n mod 3,0).
T(n,1) = n-2 for n>1.
T(3*j-r,3*j-p) = 0 for j>0, p=1,2, and r=1,...,p.
T(3*(j-1)+p,3*(j-1)) = T(3*j,3*j-p) = j^p for j>0 and p=0,1,2,3.
T(3*j+1,3*j-1) = 3*j(j+1)/2 for j>0.
T(3*j+2,3*j-2) = 3*(C(j+2,4) + C(j+1,2)^2) for j>1.
G.f. of row sums: (1-x)/((1-2*x)*(1+x^2-x^3)).
G.f. of antidiagonal sums: (1-x^2)/((1-x-x^2)*(1+x^3-x^6)).
T(n,k) = T(n-1,k) + T(n-1,k-1) for n>=2*k+1 if k>=0.

A208742 Number of subsets of the set {1,2,...,n} which do not contain two elements whose difference is 5.

Original entry on oeis.org

1, 2, 4, 8, 16, 32, 48, 72, 108, 162, 243, 405, 675, 1125, 1875, 3125, 5000, 8000, 12800, 20480, 32768, 53248, 86528, 140608, 228488, 371293, 599781, 968877, 1565109, 2528253, 4084101, 6612354, 10705716, 17333064, 28063056, 45435424, 73498480, 118894600

Offset: 0

David Nacin, Mar 01 2012

			If n=6 then we must count all subsets not containing both 1 and 6.  There are 2^4 subsets containing 1 and 6, giving us 2^6 - 2^4 = 48.  Thus a(6) = 48.

M. El-Mikkawy, T. Sogabe, A new family of k-Fibonacci numbers, Appl. Math. Comput. 215 (2010) 4456-4461 doi:10.1016/j.amc.2009.12.069, Table 1 k=5.

Vincenzo Librandi, Table of n, a(n) for n = 0..1000
M. Tetiva, Subsets that make no difference d, Mathematics Magazine 84 (2011), no. 4, 300-301.
Index entries for linear recurrences with constant coefficients, signature (1, 1, 0, 0, -3, 3, 3, 0, 0, 6, -6, -6, 0, 0, 3, -3, -3, 0, 0, -1, 1, 1).

Cf. A006498, A006500, A208741, A208743.

Table[Fibonacci[Floor[n/5] + 3]^Mod[n, 5] * Fibonacci[Floor[n/5] + 2]^(5 - Mod[n, 5]), {n, 1, 40}]
LinearRecurrence[{1, 1, 0, 0, -3, 3, 3, 0, 0, 6, -6, -6, 0, 0, 3, -3, -3, 0, 0, -1, 1, 1}, {2, 4, 8, 16, 32, 48, 72, 108, 162, 243, 405, 675, 1125, 1875, 3125, 5000, 8000, 12800, 20480, 32768, 53248, 86528, 140608, 228488, 371293, 599781, 968877}, 80]

a(n)=fibonacci(n\5+3)^(n%5)*fibonacci(n\5+2)^(5-n%5) \\ Charles R Greathouse IV, Mar 05 2012

a(n) = F(floor(n/5) + 3)^(n mod 5)*F(floor(n/5) + 2)^(5 - (n mod 5)) where F(n) is the n-th Fibonacci number.
a(n) = a(n-1) + a(n-2) - 3*a(n-5) + 3*a(n-6) + 3*a(n-7) + 6*a(n-10) - 6*a(n-11) - 6*a(n-12) + 3*a(n-15) - 3*a(n-16) - 3*a(n-17) - a(n-20) + a(n-21) + a(n-22).
G.f.: 1-x*(x^21 +2*x^20 +x^19 +x^18 +x^17 -2*x^16 -6*x^15 -4*x^14 -3*x^13 -3*x^12 -9*x^11 -12*x^10 -3*x^9 -6*x^8 -6*x^7 -2*x^6 +6*x^5 +8*x^4 +4*x^3 +2*x^2 +2*x +2) / ((x^2 +x -1) * (x^10 -4*x^5 -1) * (x^10 +x^5 -1)). - Colin Barker, Jun 02 2013

a(0)=1 prepended by Alois P. Heinz, Sep 17 2024

A209434 Table T(n,m), read by antidiagonals, is the number of subsets of {1,...,n} which do not contain two elements whose difference is m+1.

Original entry on oeis.org

1, 2, 1, 3, 2, 1, 5, 4, 2, 1, 8, 6, 4, 2, 1, 13, 9, 8, 4, 2, 1, 21, 15, 12, 8, 4, 2, 1, 34, 25, 18, 16, 8, 4, 2, 1, 55, 40, 27, 24, 16, 8, 4, 2, 1, 89, 64, 45, 36, 32, 16, 8, 4, 2, 1, 144, 104, 75, 54, 48, 32, 16, 8, 4, 2, 1, 233, 169, 125, 81, 72, 64, 32

Offset: 0

David Nacin, Mar 09 2012

1st column is the Fibonacci sequence.

			Table begins:
1,   1,   1,   1,   1,   1,   1,   1,   1,   1,    1,    ...
2,   2,   2,   2,   2,   2,   2,   2,   2,   2,    2,    ...
3,   4,   4,   4,   4,   4,   4,   4,   4,   4,    4,    ...
5,   6,   8,   8,   8,   8,   8,   8,   8,   8,    8,    ...
8,   9,   12,  16,  16,  16,  16,  16,  16,  16,   16,   ...
13,  15,  18,  24,  32,  32,  32,  32,  32,  32,   32,   ...
21,  25,  27,  36,  48,  64,  64,  64,  64,  64,   64,   ...
34,  40,  45,  54,  72,  96,  128, 128, 128, 128,  128,  ...
55,  64,  75,  81,  108, 144, 192, 256, 256, 256,  256,  ...
89,  104, 125, 135, 162, 216, 288, 384, 512, 512,  512,  ...
144, 169, 200, 225, 243, 324, 432, 576, 768, 1024, 1024, ...
............................................................

M. El-Mikkawy, T. Sogabe, A new family of k-Fibonacci numbers, Appl. Math. Comput. 215 (2010) 4456-4461 doi:10.1016/j.amc.2009.12.069, Table 1.

G. C. Greubel, Table of n, a(n) for the first 100 antidiagonals, flattened
Katharine A. Ahrens, Combinatorial Applications of the k-Fibonacci Numbers: A Cryptographically Motivated Analysis, Ph. D. thesis, North Carolina State University (2020).
M. Tetiva, Subsets that make no difference d, Mathematics Magazine 84 (2011), no. 4, 300-301.

Cf. A209435, A209436, A209437. Columns: A006498, A006500, A031923, A208742, A208743, A009641

a[n_, m_] := Product[Fibonacci[Floor[(n + i)/(m + 1) + 2]], {i, 0, m}]; Flatten[Table[a[j - i, i], {j, 0, 30}, {i, 0, j}]]

T(n,m) = Product_{i=0 to m} F(floor[(n + i)/(m + 1) + 2]) where F(n) is the n-th Fibonacci number.

A376743 Number of permutations (p(1),p(2),...,p(n)) of (1,2,...,n) such that p(i)-i is in {-2,-1,4} for all i=1,...,n.

Original entry on oeis.org

1, 0, 0, 0, 0, 1, 1, 1, 1, 1, 1, 5, 5, 6, 8, 11, 15, 25, 35, 46, 61, 85, 125, 175, 245, 341, 470, 650, 925, 1300, 1810, 2521, 3520, 4915, 6880, 9640, 13476, 18801, 26251, 36721, 51346, 71776, 100335, 140210, 195886, 273813, 382821, 535105, 747850, 1045220

Offset: 0

Michael A. Allen, Oct 03 2024

Other sequences related to strongly restricted permutations pi(i) of i in {1,..,n} along with the sets of allowed p(i)-i (containing at least 3 elements): A000045 {-1,0,1}, A189593 {-1,0,2,3,4,5,6}, A189600 {-1,0,2,3,4,5,6,7}, A006498 {-2,0,2}, A080013 {-2,1,2}, A080014 {-2,0,1,2}, A033305 {-2,-1,1,2}, A002524 {-2,-1,0,1,2}, A080000 {-2,0,3}, A080001 {-2,1,3}, A080004 {-2,0,1,3}, A080002 {-2,2,3}, A080005 {-2,0,2,3}, A080008 {-2,1,2,3}, A080011 {-2,0,1,2,3}, A079999 {-2,-1,3}, A080003 {-2,-1,0,3}, A080006 {-2,-1,1,3}, A080009 {-2,-1,0,1,3}, A080007 {-2,-1,2,3}, A080010 {-2,-1,0,2,3}, A080012 {-2,-1,1,2,3}, A072827 {-2,-1,0,1,2,3}, A224809 {-2,0,4}, A189585 {-2,0,1,3,4}, A189581 {-2,-1,0,3,4}, A072850 {-2,-1,0,1,2,3,4}, A189587 {-2,0,1,3,4,5}, A189588 {-2,-1,0,3,4,5}, A189594 {-2,0,1,3,4,5,6}, A189595 {-2,-1,0,3,4,5,6}, A189601 {-2,0,1,3,4,5,6,7}, A189602 {-2,-1,0,3,4,5,6,7}, A224811 {-2,0,8}, A224812 {-2,0,10}, A224813 {-2,0,12}, A006500 {-3,0,3}, A079981 {-3,1,3}, A079983 {-3,0,1,3}, A079982 {-3,2,3}, A079984 {-3,0,2,3}, A079988 {-3,1,2,3}, A079989 {-3,0,1,2,3}, A079986 {-3,-1,1,3}, A079992 {-3,-1,0,1,3}, A079987 {-3,-1,2,3}, A079990 {-3,-1,0,2,3}, A079993 {-3,-1,1,2,3}, A079985 {-3,-2,2,3}, A079991 {-3,-2,0,2,3}, A079996 {-3,-2,0,1,2,3}, A079994 {-3,-2,1,2,3}, A079997 {-3,-2, -1,1,2,3}, A002526 {-3,-2,-1,0,1,2,3}, A189586 {-3,0,1,2,4}, A189583 {-3,-1,0,2,4}, A189582 {-3,-2,0,1,4}, A189584 {-3,-2,-1,0,4}, A189589 {-3,0,1,2,4,5}, A189590 {-3,-1,0,2,4,5}, A189591 {-3,-2,1,4,5}, A189592 {-3,-2,-1,0,4,5}, A224810 {-3,0,6}, A189596 {-3,0,1,2,4,5,6}, A189597 {-3,-1,0,2,4,5,6}, A189598 {-3,-2,0,1,4,5,6}, A189599 {-3,-2,-1,0,4,5,6}, A224814 {-3,0,9}, A031923 {-4,0,4}, A072856 {-4,-3, -2,-1,0,1,2,3,4}, A224815 {-4,0,8}, A154654 {-5,-4,-3,-2,-1,0,1,2,3,4,5}, A154655 {-6,-5,-4,-3, -2,-1,0,1,2,3,4,5,6}.

[Keyword "less", because this comment should be moved to the Index to the OEIS, it is not appropriate here. - N. J. A. Sloane, Oct 25 2024]

D. H. Lehmer, Permutations with strongly restricted displacements. Combinatorial theory and its applications, II (Proc. Colloq., Balatonfured, 1969), North-Holland, Amsterdam, 1970, pp. 755-770.

Michael A. Allen and Kenneth Edwards, Connections between two classes of generalized Fibonacci numbers squared and permanents of (0,1) Toeplitz matrices, Lin. Multilin. Alg. 72:13 (2024) 2091-2103.
Vladimir Baltic, On the number of certain types of strongly restricted permutations, Applicable Analysis and Discrete Mathematics, 4(1) (2010), 119-135.
Kenneth Edwards and Michael A. Allen, Strongly restricted permutations and tiling with fences, Discrete Applied Mathematics, 187 (2015), 82-90.
Index entries for linear recurrences with constant coefficients, signature (0,0,1,1,1,2,1,0,-2,-2,0,-1,0,0,1).

See comments for other sequences related to strongly restricted permutations.

CoefficientList[Series[(1 - x^3 - x^4 - x^6 + x^9)/(1 - x^3 - x^4 - x^5 - 2*x^6 - x^7 + 2*x^9 + 2*x^10 + x^12 - x^15),{x,0,49}],x]
LinearRecurrence[{0, 0, 1, 1, 1, 2, 1, 0, -2, -2, 0, -1, 0, 0, 1}, {1, 0, 0, 0, 0, 1, 1, 1, 1, 1, 1, 5, 5, 6, 8}, 50]

a(n) = a(n-3) + a(n-4) + a(n-5) + 2*a(n-6) + a(n-7) - 2*a(n-9) - 2*a(n-10) - a(n-12) + a(n-15).

G.f.: (1 - x^3 - x^4 - x^6 + x^9)/(1 - x^3 - x^4 - x^5 - 2*x^6 - x^7 + 2*x^9 + 2*x^10 + x^12 - x^15).

A208743 Number of subsets of the set {1,2,...,n} which do not contain two elements whose difference is 6.

Original entry on oeis.org

2, 4, 8, 16, 32, 64, 96, 144, 216, 324, 486, 729, 1215, 2025, 3375, 5625, 9375, 15625, 25000, 40000, 64000, 102400, 163840, 262144, 425984, 692224, 1124864, 1827904, 2970344, 4826809, 7797153, 12595401, 20346417, 32867289, 53093313, 85766121, 138859434

Offset: 1

David Nacin, Mar 01 2012

			If n=7 then we must count all subsets not containing both 1 and 7.  There are 2^5 subsets containing 1 and 7, giving us 2^7 - 2^5 = 48.  Thus a(7) = 96.

M. El-Mikkawy, T. Sogabe, A new family of k-Fibonacci numbers, Appl. Math. Comput. 215 (2010) 4456-4461 doi:10.1016/j.amc.2009.12.069, Table 1 k=6.

Vincenzo Librandi, Table of n, a(n) for n = 1..1000
Katharine A. Ahrens, Combinatorial Applications of the k-Fibonacci Numbers: A Cryptographically Motivated Analysis, Ph. D. thesis, North Carolina State University (2020).
M. Tetiva, Subsets that make no difference d, Mathematics Magazine 84 (2011), no. 4, 300-301.
Index entries for linear recurrences with constant coefficients, signature (1, 1, 0, 0, 0, -5, 5, 5, 0, 0, 0, 15, -15, -15, 0, 0, 0, 15, -15, -15, 0, 0, 0, -5, 5, 5, 0, 0, 0, -1, 1, 1).

Cf. A006498, A006500, A208741, A208742.

Table[Fibonacci[Floor[n/6] + 3]^Mod[n, 6] * Fibonacci[Floor[n/6] + 2]^(6 - Mod[n, 6]), {n, 1, 80}]
LinearRecurrence[{1, 1, 0, 0, 0, -5, 5, 5, 0, 0, 0, 15, -15, -15, 0, 0, 0, 15, -15, -15, 0, 0, 0, -5, 5, 5, 0, 0, 0, -1, 1, 1}, {2, 4, 8, 16, 32, 64, 96, 144, 216, 324, 486, 729, 1215, 2025, 3375, 5625, 9375, 15625, 25000, 40000, 64000, 102400, 163840, 262144, 425984, 692224, 1124864, 1827904, 2970344, 4826809, 7797153, 12595401}, 80]

Vec(x*(2 + 2*x + 2*x^2 + 4*x^3 + 8*x^4 + 16*x^5 + 10*x^6 - 6*x^7 - 14*x^8 - 16*x^9 - 14*x^10 - x^11 - 30*x^12 - 29*x^13 - 15*x^14 - 15*x^15 - 15*x^16 - 20*x^17 - 30*x^18 - 10*x^19 + 5*x^20 + 5*x^21 + 5*x^22 + 4*x^23 + 10*x^24 + 6*x^25 + x^26 + x^27 + x^28 + x^29 + 2*x^30 + x^31) / ((1 + x^2)*(1 - x - x^2)*(1 - x^2 + x^4)*(1 + x^3 - x^6)*(1 - x^3 - x^6)*(1 + 7*x^6 + x^12)) + O(x^30)) \\ Colin Barker, Feb 23 2017

a(n) = F(floor(n/6) + 3)^(n mod 6)*F(floor(n/6) + 2)^(6 - (n mod 6)) where F(n) is the n-th Fibonacci number.
a(n) = a(n-1) + a(n-2) - 5*a(n-6) + 5*a(n-7) + 5*a(n-8) + 15*a(n-12) - 15*a(n-13) - 15*a(n-14) + 15*a(n-18) - 15*a(n-19) - 15*a(n-20) - 5*a(n-24) + 5*a(n-25) + 5*a(n-26) - a(n-30) + a(n-31) + a(n-32).
G.f.: x*(2 + 2*x + 2*x^2 + 4*x^3 + 8*x^4 + 16*x^5 + 10*x^6 - 6*x^7 - 14*x^8 - 16*x^9 - 14*x^10 - x^11 - 30*x^12 - 29*x^13 - 15*x^14 - 15*x^15 - 15*x^16 - 20*x^17 - 30*x^18 - 10*x^19 + 5*x^20 + 5*x^21 + 5*x^22 + 4*x^23 + 10*x^24 + 6*x^25 + x^26 + x^27 + x^28 + x^29 + 2*x^30 + x^31) / ((1 + x^2)*(1 - x - x^2)*(1 - x^2 + x^4)*(1 + x^3 - x^6)*(1 - x^3 - x^6)*(1 + 7*x^6 + x^12)). - Colin Barker, Feb 23 2017

A209399 Number of subsets of {1,...,n} containing two elements whose difference is 3.

Original entry on oeis.org

0, 0, 0, 0, 4, 14, 37, 83, 181, 387, 824, 1728, 3584, 7360, 15032, 30571, 61987, 125339, 252883, 509294, 1024300, 2057848, 4130724, 8285758, 16610841, 33285207, 66673209, 133512759, 267294832, 535025408, 1070755840, 2142652160, 4287149680, 8577285255

Offset: 0

David Nacin, Mar 07 2012

Also, the number of bitstrings of length n containing one of the following: 1001, 1101, 1011, 1111.

			When n=4 any such subset must contain 1 and 4.  There are four such subsets so a(4) = 4.

David Nacin, Table of n, a(n) for n = 0..500
Index entries for linear recurrences with constant coefficients, signature (3,-1,-3,3,-1,-1,-3,1,2).

Cf. A209398, A209400, A006500.

[2^n - Fibonacci(Floor(n/3) + 2)*Fibonacci(Floor((n + 1)/3) + 2)*Fibonacci(Floor((n + 2)/3) + 2): n in [0..30]]; // G. C. Greubel, Jan 03 2018

LinearRecurrence[{3, -1, -3, 3, -1, -1, -3, 1, 2}, {0, 0, 0, 0, 4, 14, 37, 83, 181}, 50]
Table[2^n - Product[Fibonacci[Floor[(n + i)/3] + 2], {i, 0, 2}], {n, 0, 50}]

x='x+O('x^30); concat([0,0,0,0], Vec(x^4*(4+2*x-x^2-2*x^3-x^4)/( (1-2*x)*(1-x-x^2)*(1+x^3-x^6)))) \\ G. C. Greubel, Jan 03 2018

#From recurrence
def a(n, adict={0:0, 1:0, 2:0, 3:0, 4:4, 5:14, 6:37, 7:83, 8:181}):
 if n in adict:
  return adict[n]
 adict[n]=3*a(n-1)-a(n-2)-3*a(n-3)+3*a(n-4)-a(n-5)-a(n-6)-3*a(n-7)+a(n-8)+2*a(n-9)
 return adict[n]

#Returns the actual list of valid subsets
def contains1001(n):
 patterns=list()
 for start in range (1,n-2):
  s=set()
  for i in range(4):
   if (1,0,0,1)[i]:
    s.add(start+i)
  patterns.append(s)
 s=list()
 for i in range(2,n+1):
  for temptuple in comb(range(1,n+1),i):
   tempset=set(temptuple)
   for sub in patterns:
    if sub <= tempset:
     s.append(tempset)
     break
 return s
#Counts all such sets
def countcontains1001(n):
 return len(contains1001(n))

a(n) = 3*a(n-1) - a(n-2) - 3*a(n-3) + 3*a(n-4) - a(n-5) - a(n-6) - 3*a(n-7) + a(n-8) + 2*a(n-9).
G.f.: (4*x^4 + 2*x^5 - x^6 - 2*x^7 - x^8)/(1 - 3*x + 1*x^2 + 3*x^3 - 3*x^4 + x^5 + x^6 + 3*x^7 - x^8 - 2*x^9) = x^4*(4 + 2*x - x^2 - 2*x^3 - x^4)/((1 - 2*x)*(1 - x - x^2)*(1 + x^3 - x^6)).
a(n) = 2^n - A006500(n).
a(n) = 2^n - Product(i=0 to 2) F(floor((n+i)/3)+2) where F(n) is the n-th Fibonacci number.

A263442 T(n,k)=Number of nXk arrays of permutations of 0..n*k-1 with each element moved a city block distance of 0 or 3.

Original entry on oeis.org

1, 1, 1, 1, 1, 1, 2, 4, 4, 2, 4, 25, 49, 25, 4, 8, 125, 1770, 1770, 125, 8, 12, 633, 52352, 560436, 52352, 633, 12, 18, 2532, 1095488, 96348384, 96348384, 1095488, 2532, 18, 27, 10288, 20725780, 10716259649

Offset: 1

R. H. Hardin, Oct 18 2015

Table starts
..1....1.......1........2........4...........8.......12....18.27
..1....1.......4.......25......125.........633.....2532.10288
..1....4......49.....1770....52352.....1095488.20725780
..2...25....1770...560436.96348384.10716259649
..4..125...52352.96348384
..8..633.1095488
.12.2532
.18

			Some solutions for n=3 k=4
..9.10..2..5....6..1..9.10....0..7..4..3....6..7..9..3....0..1.11.10
..4..3..8..7....4..5..0..7...10..5..6..9...10.11..0..1....4..5..8..7
..6..0..1.11....8..2..3.11...11..2..1..8....8..2..4..5....6..9..3..2

Column 1 is A006500(n-3).

Empirical for column k:

k=1: a(n) = a(n-1) +a(n-2) -a(n-3) +a(n-4) +a(n-5) +a(n-6) -a(n-7) -a(n-8)

cp's OEIS Frontend

A376033 Number A(n,k) of binary words of length n avoiding distance (i+1) between "1" digits if the i-th bit is set in the binary representation of k; square array A(n,k), n>=0, k>=0, read by antidiagonals.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Maple

PARI

Formula

A031923 Let r and s be consecutive Fibonacci numbers. Sequence is r^4, r^3 s, r^2 s^2, and r s^3.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Maple

Mathematica

PARI

Python

Formula

Extensions

A350110 Triangle read by rows, T(n,k) = T(n-1,k) + T(n-1,k-1) - T(n-2,k-1) + T(n-3,k-1) + T(n-3,k-2) + T(n-3,k-3) - T(n-4,k-3) - T(n-4,k-4) + delta(n,0)*delta(k,0) - delta(n,1)*delta(k,1), T(n

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

Formula

A208742 Number of subsets of the set {1,2,...,n} which do not contain two elements whose difference is 5.

Views

Author

Keywords

Examples

References

Links

Crossrefs

Programs

Mathematica

PARI

Formula

Extensions

A209434 Table T(n,m), read by antidiagonals, is the number of subsets of {1,...,n} which do not contain two elements whose difference is m+1.

Views

Author

Keywords

Comments

Examples

References

Links

Crossrefs

Programs

Mathematica

Formula

A376743 Number of permutations (p(1),p(2),...,p(n)) of (1,2,...,n) such that p(i)-i is in {-2,-1,4} for all i=1,...,n.

Views

Author

Keywords

Comments

References

Links

Crossrefs

Programs

Mathematica

Formula

A208743 Number of subsets of the set {1,2,...,n} which do not contain two elements whose difference is 6.

Views

Author

Keywords

Examples

A350110 Triangle read by rows, T(n,k) = T(n-1,k) + T(n-1,k-1) - T(n-2,k-1) + T(n-3,k-1) + T(n-3,k-2) + T(n-3,k-3) - T(n-4,k-3) - T(n-4,k-4) + delta(n,0)delta(k,0) - delta(n,1)delta(k,1), T(n