Gerhard Kirchner - cp's OEIS frontend

A380203 With given points 0,1 on the x-axis, a(n) is the number of ways to construct n with m circles where 2^(m-1)

1, 1, 1, 1, 1, 2, 1, 1, 2, 4, 2, 4, 1, 2, 1, 1, 5, 9, 6, 10, 4, 8, 4, 8, 1, 4, 2, 4, 1, 2, 1, 1, 15, 28, 15, 31, 13, 25, 14, 28, 10, 19, 11, 22, 8, 15, 9, 17, 2, 8, 4, 12, 2, 8, 4, 8, 1, 4, 2, 4, 1, 2, 1, 1, 50, 94, 56, 99, 45, 91, 51, 97, 39, 74, 41, 92, 31, 74, 40, 85, 26, 61

Offset: 1

Gerhard Kirchner, Jan 16 2025

nonn

Description of the construction: The first circle with center 1 and radius 1 intersects the x-axis at 2. The center of the next circle is 2. Each circle, except for the last one, intersects the axis at the center of the next one. The last circle intersects the axis at x.
The sequence of indices with a(n)=1 is A379972. Further comments on the construction can be found there. The algorithm generates a tree. In this section, a(6)=2 and a(n)=1 otherwise.
        5
       /
      3
     / \
  1-2   6
     \ /
      4-7
       \
        8

			 n a(n)  intersection points on the x-axis
 5  1    2, 3, 5
 6  2    2, 3, 6 or 2, 4, 6
10  4    2, 3, 5, 10 or 2, 3, 6, 10 or 2, 4, 6, 10 or 2, 4, 7, 10

Cf. A379972.

block(m:7, aa:makelist(i-1,i,1,m+2), freq:makelist(0,i,1,2^m),
recursion(t):=  (freq[aa[t]] : freq[aa[t]] + 1,
 if t< m+2 then
   for k from t-1 thru 1 step -1 do
     (p:2*aa[t] - aa[k] ,
     if p> 2^(t-2) then (aa[t+1]:p, recursion(t+1) ) ) ) ,
 recursion(2), freq );

A379972 Numbers x with 2^(m-1)

Original entry on oeis.org

1, 2, 3, 4, 5, 7, 8, 13, 15, 16, 25, 29, 31, 32, 57, 61, 63, 64, 113, 121, 125, 127, 128, 241, 249, 253, 255, 256, 481, 497, 505, 509, 511, 512, 993, 1009, 1017, 1021, 1023, 1024, 1985, 2017, 2033, 2041, 2045, 2047, 2048

Offset: 1

Gerhard Kirchner, Jan 08 2025

nonn

Each circle, except for the last one, intersects the x-axis at the center of the next one. Any x>1 is represented by intersection points: y(1)=2, y(2),..., y(m)=x, but not necessarily in a unique way. The standard representation can be found by a backward algorithm: If y(j) is even, y(j-1)= y(j)/2, otherwise y(j)=(y(j)+1)/2. This way, only circles intersecting the x-axis at 0 or 1 are used. If no other representation exists, x belongs to the sequence, see examples.

Further comments, proof of the formula and images, see link "Construction with circles".

			Example 1: k=0, x=2^m belongs to the sequence.
 Standard repesentation: (2,..,2^j,..,2^m)
Example 2: m=6, k=3, x=57 belongs to the sequence.
 Standard repesentation: (2,4,8,15,29,57)
Counterexample 3: m=6, k=4, x=49 does not belong to the sequence.
 Standard repesentation: (2,4,7,13,25,49)
 Other repesentation:    (2,4,7,14,28,49)
Counterexample 4: x=48 does not belong to the sequence.
 Standard repesentation: (2,3,6,12,24,48)
 Other repesentation:    (2,4,7,13,25,48)

Gerhard Kirchner, Construction with circles

block(u:[],
for m from 0 thru 11 do
  for k from floor((m+1)/2) thru 0 step -1 do
    if m=0 or k

x=2^m-2^k+1 with m>=0 and 0<=k<=(m+1)/2.

For x=1, only m=0 makes sense. Therefore k=m=1 is excluded.

A362297 Array read by antidiagonals for k,n>=0: T(n,k) = number of tilings of a 2k X n rectangle using dominos and 2 X 2 right triangles.

Original entry on oeis.org

1, 1, 1, 1, 1, 1, 1, 1, 4, 1, 1, 1, 19, 7, 1, 1, 1, 97, 55, 19, 1, 1, 1, 508, 445, 472, 40, 1, 1, 1, 2683, 3625, 13249, 2023, 97, 1, 1, 1, 14209, 29575, 392299, 109771, 13249, 217, 1, 1, 1, 75316, 241375, 11877025, 6078148, 2102272, 66325, 508, 1, 1, 1, 399331, 1970125, 362823607, 338504101, 358815535, 22650721, 392299, 1159, 1

Offset: 0

Gerhard Kirchner, Apr 19 2023

Triangles only occur as pairs forming 2 X 2 squares. Combining four triangles, a square with side sqrt(2) can be made, but this side is irrational and the square cannot be used for tiling. A pair of triangles is equivalent to a 2 X 2 square with a 180 degree rotation symmetry (generated by an ornament for example).

			Table begins:
n\k_0__1_____2_______3_________4___________5______________6
0:  1  1     1       1         1           1              1
1:  1  1     1       1         1           1              1
2:  1  4    19      97       508        2683          14209
3:  1  7    55     445      3625       29575         241375
4:  1 19   472   13249    392299    11877025      362823607
5:  1 40  2023  109771   6078148   338504101    18883136617
6:  1 97 13249 2102272 358815535 63483562159 11428502939791

Andrew Howroyd, Table of n, a(n) for n = 0..860 (first 41 antidiagonals).
Gerhard Kirchner, Maxima code
Gerhard Kirchner, Tilings with right triangles

Cf. A351322, A352431, A352432, A352433, A006130, A362298, A362299.

T(n,1) = A006130(n).
T(n,2) = A362298(n).
T(3,k) = A362299(k).

A362299 Number of tilings of a 3 X 2n rectangle using dominos and 2 X 2 right triangles.

Original entry on oeis.org

1, 7, 55, 445, 3625, 29575, 241375, 1970125, 16080625, 131254375, 1071334375, 8744528125, 71375265625, 582584734375, 4755218359375, 38813412578125, 316805850390625, 2585857315234375, 21106485396484375, 172276994236328125, 1406172661416015625

Offset: 0

Gerhard Kirchner, Apr 19 2023

Triangles only occur as pairs forming 2 X 2 squares. For program code and additional details, see A362297.

			a(1)=7:
   ___ _    _ ___    ___ _    _ ___    ___ _    _ ___    ___ _
  |  /| |  | |  /|  |\  | |  | |\  |  |___| |  | |___|  | | | |
  |/__|_|  |_|/__|  |__\|_|  |_|__\|  |___|_|  |_|___|  |_|_|_|

Paolo Xausa, Table of n, a(n) for n = 0..1000
Index entries for linear recurrences with constant coefficients, signature (10,-15).

Row n=3 of A362297.

Cf. A351322, A352432, A352433, A006130, A362298.

LinearRecurrence[{10, -15}, {1, 7}, 30] (* Paolo Xausa, Jul 20 2024 *)

a(n) = 10*a(n-1) - 15*a(n-2).
G.f.: (1 - 3*x)/(1 - 10*x + 15*x^2).
E.g.f.: exp(5*x)*(5*cosh(sqrt(10)*x) + sqrt(10)*sinh(sqrt(10)*x))/5. - Stefano Spezia, Apr 20 2023

A362298 Number of tilings of a 4 X n rectangle using dominos and 2 X 2 right triangles.

Original entry on oeis.org

1, 1, 19, 55, 472, 2023, 13249, 66325, 392299, 2088856, 11877025, 64803157, 362823607, 1998759703, 11123273896, 61509329983, 341492705365, 1891193243713, 10489893539203, 58127214942544, 322296397820593, 1786338231961609, 9903234373856059, 54893955008138983

Offset: 0

Gerhard Kirchner, Apr 19 2023

Triangles only occur as pairs forming 2 X 2 squares. For program code and additional details, see A362297.

			a(2) = 19.
Partitions of a 2 X 2 square (triangles or dominos):
   ___    ___    ___    ___
  |  /|  |\  |  |___|  | | |
  |/__|  |__\|  |___|  |_|_|
       2t            2d
   ___ ___    ___ ___    ___ ___    _ ___ _    _______
  |2t |2t |  |2t |2d |  |2d |2t |  | |2t | |  |only d |
  |___|___|  |___|___|  |___|___|  |_|___|_|  |_______|
    4 ways +   4 ways +  4 ways  +   2 ways +  5 ways  = 19 ways
Only dominos: A005178(3) = 5.

Index entries for linear recurrences with constant coefficients, signature (4,18,-48,-42,99).

Column k=2 of A362297.

Cf. A351322, A352432, A352433, A006130, A362299.

LinearRecurrence[{4,18,-48,-42,99},{1,1,19,55,472},24] (* Stefano Spezia, Apr 20 2023 *)

a(n) = 4*a(n-1) + 18*a(n-2) - 48*a(n-3) - 42*a(n-4) + 99*a(n-5).

G.f.: (9*x^3-3*x^2-3*x+1)/(-99*x^5+42*x^4+48*x^3-18*x^2-4*x+1).

A360800 Numbers Sum_{i=1..2r+1} 2^k(i) such that k(1) is even and, for r > 0 and i < 2r+1, the difference k(i+1)-k(i) is > 0 and odd.

Original entry on oeis.org

1, 4, 7, 16, 19, 25, 28, 31, 64, 67, 73, 76, 79, 97, 100, 103, 112, 115, 121, 124, 127, 256, 259, 265, 268, 271, 289, 292, 295, 304, 307, 313, 316, 319, 385, 388, 391, 400, 403, 409, 412, 415, 448, 451, 457, 460, 463, 481, 484, 487, 496, 499, 505, 508, 511, 1024

Offset: 1

Gerhard Kirchner, Feb 24 2023

nonn

This is a subsequence of A360799. Another description of the terms: in the base-2 representation, the number of ones is odd and all zeros are grouped in blocks of even length.

That is why the terms less than 2^(2j+1) describe start profiles for tiling a (2j+1) X m wall with 1 X 2 dominos, see examples and A360799.

			A 5 X m wall is tiled bottom-up with dominos, start profiles:
            _        _            _ _ _    _     _ _    _ _ _ _ _
    ___ ___| |   ___| |___    ___| | | |  | |___| | |  | | | | | |
   |___|___|_|  |___|_|___|  |___|_|_|_|  |_|___|_|_|  |_|_|_|_|_|
    0 0 0 0 1    0 0 1 0 0    0 0 1 1 1    1 0 0 1 1    1 1 1 1 1
    1 = a(1)     4 = a(2)     7 = a(3)     19 = a(5)    31 = a(7)
    also the mirror images of 1 (16), 19 (25) and 7 (28).

Cf. A001835, A003775, A028469, A028471, A180963, A187616, A360799.

block(kmax: 100, a:[],
 oddsum(y):= block(su1:0, su2:0, pold:0, ok: true,
  while y>0 and ok do(p:mod(y,2), y:(y-p)/2,
   if p=1 then(if pold=0 and su2=1 then ok:false, su1:1-su1, su2:0)
   elseif p=0 then su2:1-su2, pold:p), return(is(ok and su1=1))),
for k from 1 thru kmax do if oddsum(k) then a:append(a,[k]),a);

A360799 Numbers m with m mod 3 = q, q != 2, such that the number of ones in its base-2 representation is even if q=0 and odd if q=1.

Original entry on oeis.org

0, 1, 3, 4, 6, 7, 9, 12, 13, 15, 16, 18, 19, 22, 24, 25, 27, 28, 30, 31, 33, 36, 37, 39, 45, 48, 49, 51, 52, 54, 55, 57, 60, 61, 63, 64, 66, 67, 70, 72, 73, 75, 76, 78, 79, 82, 88, 90, 91, 94, 96, 97, 99, 100, 102, 103, 105, 108, 109, 111, 112, 114, 115, 118, 120, 121

Offset: 0

Gerhard Kirchner, Feb 24 2023

nonn

For q=0, the terms in A180963 are excluded.
The terms of the sequence occur, with some exceptions, while tiling a wall (odd width w) with 1 X 2 dominos. The current tiling status can be described by a number x with 0 <= x < 2^w. In the base-2 representation, 1 stands for an overstanding unit square, see example.
Statement:
The tiling always starts with q=1 and an odd number of ones (type 1) and is followed by a term with q=0 and an even number of ones (type 2) and so on, alternately.
Proof:
Start, provisionally, with w upright dominos. The corresponding term is x = (11..1) = 2^w-1 with x mod 3 = 1 (type 1). Another first profile can be generated by replacing a pair of adjacent upright dominos with one flat domino. In the base-2 representation, this is the subtraction (11..11..1) - (00..11..0) = (11..00..1). The subtrahend is 3*2^j with 0 <= j < w. Therefore, the modified term also is type 1. This way, any first profile can be found and it is type 1.
In the next provisional step, an upright domino is placed on each not overstanding unit square. If p1 is the first profile, then the second is p2 = 2^w - 1 - p1 with p2 mod 3 = 0. Moreover, the transition from p1 to p2 exchanges the ones and zeros such that p2 is type 2. Again, replacing adjacent upright dominos by one flat domino does not change the type of the profile. The next profile is type 1 and so on. QED. Condition to be satisfied by a tiling profile: The continued removal of 00 and 11 (reduction) leads to (0) or (1). Example: a(10)=18=(10010) -> (110) -> (0). The first exceptions are a(314) = 682 = (01010101010), a(611) = 1365 = (10101010101) and a(988) = 2218 = (0100010101010). Note that the reduction of 2218 is 682.

			 5 X 4 wall is tiled bottom-up with 1 X 2 dominos:
                                      _    ___ ___ _
                 _ _          _ _ ___| |  |_ _|___| |
        _       | | |_ ___   | | |_ _|_|  | | |_ _|_|
    ___| |___   |_|_| |___|  |_|_| |___|  |_|_| |___|
   |___|_|___|  |___|_|___|  |___|_|___|  |___|_|___|
    0 0 1 0 0    1 1 0 0 0    0 0 0 0 1    0 0 0 0 0
     4 = a(3)   24 = a(14)     1 = a(1)     0 = a(0)

Cf. A001835, A003775, A028469, A028471, A180963, A187616, A360800.

block(kmax: 100, a:[],
 even_ones(x):= block(su:0,
  while x>0 do(p: mod(x,2), x:(x-p)/2, su:su+p),
   return(mod(su,2))),
for k from 0 thru kmax do(r:mod(k,3),
 if r<2 and r=even_ones(k) then a:append(a,[k])),a);

isok(m) = my(k=m%3); if (hammingweight(m) % 2, k==1, k==0); \\ Michel Marcus, Feb 27 2023

A360645 Number of 4-dimensional tilings of a 2 X 2 X 2 X n box with 2 X 2 X 1 X 1 plates.

Original entry on oeis.org

1, 3, 30, 177, 1281, 8520, 58629, 397887, 2715510, 18490533, 126023349, 858595560, 5850498441, 39863005323, 271617783150, 1850725023657, 12610357769721, 85923544106760, 585460036653789, 3989166905015367, 27181111280961990, 185204779320272253

Offset: 0

Gerhard Kirchner, Feb 15 2023

nonn

The figure shows three 2 X 2 X 2 cubes as intersections of three successive hyperplanes (distance 1) with the box. The 3-d cross-section of a 2 X 2 X 1 X 1 plate is a 2 X 2 X 1 plate (p4) as part of one cube or a 2 X 1 X 1 domino if the plate (p2) connects two cubes. p4 or p2 indicates the number of unit cubes on the current level (hyperplane). PQRS and P'Q'R'S' (not visible: P') is one of three ways to select a pair of p4-plates. Q'Q"R"S' represents a p2-plate.
Suppose the box is completely tiled up to a certain level. Then the next (current) level may be empty (profile A0) or not (profile B0). The index 0 is used for the current level and continued with 1,2... Transitions:
a) A0->3*A1 (3 ways of selecting a pair of p4-plates, also A001045(2)=3).
b) A0->9*A2 (9 ways of tiling a 2 X 2 X 2 cube with 3d-dominos, also A006253(2)=9).
c) A0->12*B1. One p4-plate and two p2-plates can be selected in 12 ways: 6 faces of the 2 X 2 X 2 cube and two ways of selecting a pair of dominos on each face. They tile the next level with corresponding dominos. A further nonempty profile does not occur. Also, A359884(2)-A006253(2)-A001045(2)=24-9-3=12.
d) B0->1*A1 (one accomplishing p4-plate is placed on B0).
e) B0->*2B1 (2 ways of selecting a pair of dominos on B0).
Let a(n) and b(n) be the number of tilings of the 2 X 2 X 2 X n box ending with an A- or a B-profile respectively. With the transitions above, one obtains recurrence 1.
         /\               /\               /\
       /    \           /    \           /    \
     / \  S' /\       / \     /\       / \     /\
   /     \ /    \   /     \ /    \   /     \ /    \
  |\     / \     /||\     / \     /||\     / \     /|
  |  \ /     \ /  ||  \ /     \ /  ||  \ /     \ /  |
  | S |\     /| R'||   |\     /| R"||   |\     /|   |---> 4th dimension
  |\  |  \ /  |  /||\  |  \ /  |  /||\  |  \ /  |  /|
  |  \| R |   |/  ||  \|   |   |/  ||  \|   |   |/  |
  | P |\  |  /| Q'||   |\  |  /| Q"||   |\  |  /|   |
   \  |  \|/  |  /  \  |  \|/  |  /  \  |  \|/  |  /
     \| Q |   |/      \|   |   |/      \|   |   |/
       \  |  /          \  |  /          \  |  /
         \|/              \|/              \|/

Paolo Xausa, Table of n, a(n) for n = 0..1000
Index entries for linear recurrences with constant coefficients, signature (5,15,-18).

Cf. A001045, A006253, A359884.

LinearRecurrence[{5, 15, -18}, {1, 3, 30}, 25] (* Paolo Xausa, May 28 2024 *)

Recurrence 1: a(n) = 3*a(n-1) + b(n-1) + 9*a(n-2), b(n) = 12*a(n-1) + 2*b(n-1), with a(0) = 1 and a(-1) = b(0) = 0.
Recurrence 2: a(n) = 5*a(n-1) + 15*a(n-2) - 18*a(n-3).
G.f.: (1-2*x) / (1-5*x-15*x^2+18*x^3).

A360644 Number of 3-dimensional tilings of a 2 X 2 X n box using 1 X 1 X 1 cubes, 2 X 1 X 1 dominos, 2 X 2 X 1 plates and trominos (L-shaped connection of 3 cubes).

Original entry on oeis.org

1, 12, 513, 16194, 547543, 18234354, 609298887, 20344385080, 679408772089, 22688284005780, 757662377924917, 25301659203704234, 844933359518672599, 28216027727373068302, 942256839186226313727, 31466085716246304261600, 1050790517091131646143477

Offset: 0

Gerhard Kirchner, Feb 15 2023

nonn

Recurrence 1 is derived in A359884, "3d-tilings of a 2 X 2 X n box" as a special case of a more general tiling problem: III, example 14.

Index entries for linear recurrences with constant coefficients, signature (28,195,-497,30,-79,66).

Cf. A006253, A001045, A033516, A335559, A359884, A359885, A360064, A360065.

G.f.: (1-16*x-18*x^2-13*x^3+10*x^4) / (1-28*x-195*x^2+497*x^3-30*x^4+79*x^5-66*x^6)
Recurrence 1:
a(n) = 12*a(n-1) + 4*b(n-1) + 2*c(n-1) + d(n-1) + e(n-1) + 43*a(n-2) + 8*b(n-2) + c(n-2) + 2*d(n-2)
b(n) = 32*a(n-1) + 9*b(n-1) + 4*c(n-1) + 2*d(n-1) + e(n-1)
c(n) = 60*a(n-1) + 16*b(n-1) + 6*c(n-1) + 4*d(n-1) + 2*e(n-1)
d(n) = 14*a(n-1) + 3*b(n-1) + d(n-1)
e(n) = 64*a(n-1) + 13*b(n-1) + 2*c(n-1) + 2*d(n-1)
with a(n),b(n),c(n),d(n),e(n)= 0 for n<=0 except for a(0)=1.
Recurrence 2:
a(n)=28*a(n-1) + 195*a(n-2) - 497*a(n-3) + 30*a(n-4) - 79*a(n-5) + 66*a(n-6)
for n>=6. For n<6, recurrence 1 can be used.

A360577 Number of 3-dimensional tilings of a 2 X 2 X n box using 2 X 2 X 1 plates, 2 X 1 X 1 dominos and trominos (L-shaped connection of 3 cubes).

Original entry on oeis.org

1, 3, 60, 657, 8311, 101284, 1246049, 15292819, 187803572, 2305968393, 28315208039, 347681742812, 4269186204201, 52421329940803, 643681521419708, 7903765218510353, 97050331862075975, 1191681006432895780, 14632650860374551265, 179674317212728197891, 2206220907971874345652

Offset: 0

Gerhard Kirchner, Feb 12 2023

nonn

Recurrence 1 is derived in A359884, "3d-tilings of a 2 X 2 X n box" as a special case of a more general tiling problem: III, example 13.

Index entries for linear recurrences with constant coefficients, signature (8,51,27,-96,-43,66).

Cf. A006253, A001045, A033516, A335559, A359884, A359885, A360064, A360065, A360575, A360576.

G.f.: (1-5*x-15*x^2-3*x^3+10*x^4) / (1-8*x-51*x^2-27*x^3+96*x^4+43*x^5-66*x^6).
Recurrence 1:
a(n) = 3*a(n-1) + b(n-1) + c(n-1) + 19*a(n-2) + 4*b(n-2) + c(n-2) + 2*d(n-2)
b(n) = 12*a(n-1) + 2*b(n-1) + 2*c(n-1) + e(n-1)
c(n) = 20*a(n-1) + 6*b(n-1) + 2*c(n-1) + 2*e(n-1)
d(n) = 4*a(n-1) + 2*b(n-1) + d(n-1)
e(n) = 24*a(n-1) + 7*b(n-1) + 2*c(n-1) + 2*d(n-1)
with a(n),b(n),c(n),d(n),e(n)= 0 for n<=0 except for a(0)=1.
Recurrence 2:
a(n)=8*a(n-1) + 51*a(n-2) + 27*a(n-3) - 96*a(n-4) - 43*a(n-5) + 66*a(n-6)
for n>=6. For n<6, recurrence 1 can be used.

cp's OEIS Frontend

User: Gerhard Kirchner

A380203 With given points 0,1 on the x-axis, a(n) is the number of ways to construct n with m circles where 2^(m-1)

Views

Author

Keywords

Comments

Examples

Crossrefs

Programs

Maxima

A379972 Numbers x with 2^(m-1)

Views

Author

Keywords

Comments

Examples

Links

Programs

Maxima

Formula

A362297 Array read by antidiagonals for k,n>=0: T(n,k) = number of tilings of a 2k X n rectangle using dominos and 2 X 2 right triangles.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Formula

A362299 Number of tilings of a 3 X 2n rectangle using dominos and 2 X 2 right triangles.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

Formula

A362298 Number of tilings of a 4 X n rectangle using dominos and 2 X 2 right triangles.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

Formula

A360800 Numbers Sum_{i=1..2r+1} 2^k(i) such that k(1) is even and, for r > 0 and i < 2r+1, the difference k(i+1)-k(i) is > 0 and odd.

Views

Author

Keywords

Comments

Examples

Crossrefs

Programs

Maxima

A360799 Numbers m with m mod 3 = q, q != 2, such that the number of ones in its base-2 representation is even if q=0 and odd if q=1.

Views

Author

Keywords

Comments

Examples

Crossrefs

Programs

Maxima

PARI

A360645 Number of 4-dimensional tilings of a 2 X 2 X 2 X n box with 2 X 2 X 1 X 1 plates.

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Mathematica