A209435 -id:A209435 - 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).

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.

A209436 Table of a(n,m) = number of subsets of {1,...,n} which contain two elements whose difference is m+1.

Original entry on oeis.org

0, 0, 0, 1, 0, 0, 3, 0, 0, 0, 8, 2, 0, 0, 0, 19, 7, 0, 0, 0, 0, 43, 17, 4, 0, 0, 0, 0, 94, 39, 14, 0, 0, 0, 0, 0, 201, 88, 37, 8, 0, 0, 0, 0, 0, 423, 192, 83, 28, 0, 0, 0, 0, 0, 0, 880, 408, 181, 74, 16, 0, 0, 0, 0, 0, 0, 1815, 855, 387, 175, 56, 0, 0, 0, 0

Offset: 0

David Nacin, Mar 09 2012

			Table begins:
0,   0,   0,   0,   0,   0,   0,   0,   0,   0, 0, ...
0,   0,   0,   0,   0,   0,   0,   0,   0,   0, 0, ...
1,   0,   0,   0,   0,   0,   0,   0,   0,   0, 0, ...
3,   2,   0,   0,   0,   0,   0,   0,   0,   0, 0, ...
8,   7,   4,   0,   0,   0,   0,   0,   0,   0, 0, ...
19,  17,  14,  8,   0,   0,   0,   0,   0,   0, 0, ...
43,  39,  37,  28,  16,  0,   0,   0,   0,   0, 0, ...
94,  88,  83,  74,  56,  32,  0,   0,   0,   0, 0, ...
201, 192, 181, 175, 148, 112, 64,  0,   0,   0, 0, ...
423, 408, 387, 377, 350, 296, 224, 128, 0,   0, 0, ...
880, 855, 824, 799, 781, 700, 592, 448, 256, 0, 0, ...
......................................................
a(3,1) is the number of subsets of {1,2,3} containing two elements whose difference is two.  There are 2 of these: {1,3} and {1,2,3} so a(1,3) = 2.

G. C. Greubel, Table of n, a(n) for the first 100 aintidiagonals, flattened
M. Tetiva, Subsets that make no difference d, Mathematics Magazine 84 (2011), no. 4, 300-301.

Cf. A209434, A209435, A209437.

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

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

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

Original entry on oeis.org

1, 0, 3, 0, 2, 8, 0, 0, 7, 19, 0, 0, 4, 17, 43, 0, 0, 0, 14, 39, 94, 0, 0, 0, 8, 37, 88, 201, 0, 0, 0, 0, 28, 83, 192, 423, 0, 0, 0, 0, 16, 74, 181, 408, 880, 0, 0, 0, 0, 0, 56, 175, 387, 855, 1815, 0, 0, 0, 0, 0, 32, 148, 377, 824, 1775, 3719, 0, 0, 0, 0, 0

Offset: 1

David Nacin, Mar 09 2012

m offset is 1, n offset is 2 so 1st entry is T(1,2).

			Table begins:
1, 3, 8, 19, 43, 94, 201, 423, 880, ...
0, 2, 7, 17, 39, 88, 192, 408, 855, ...
0, 0, 4, 14, 37, 83, 181, 387, 824, ...
0, 0, 0,  8, 28, 74, 175, 377, 799, ...
0, 0, 0,  0, 16, 56, 148, 350, 781, ...
0, 0, 0,  0,  0, 32, 112, 296, 700, ...
0, 0, 0,  0,  0,  0,  64, 224, 592, ...
0, 0, 0,  0,  0,  0,   0, 128, 448, ...
0, 0, 0,  0,  0,  0,   0,   0, 256, ...
0, 0, 0,  0,  0,  0,   0,   0,   0, ...
0, 0, 0,  0,  0,  0,   0,   0,   0, ...
.......................................
T(2,3) is the number of subsets of {1,2,3} containing two elements whose difference is two. There are 2 of these: {1,3} and {1,2,3} so T(2,3) = 2.

G. C. Greubel, Table of n, a(n) for the first 100 antidiagonals, flattened
M. Tetiva, Subsets that make no difference d, Mathematics Magazine 84 (2011), no. 4, 300-301.

Cf. A209434, A209435, A209436.

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

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

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

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

A209436 Table of a(n,m) = number of subsets of {1,...,n} which contain two elements whose difference is m+1.

Views

Author

Keywords

Examples

Links

Crossrefs

Programs

Mathematica

Formula

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

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

Formula