OFFSET
0,2
COMMENTS
In order to construct this sequence we use the following rules:
We start in the first quadrant of the square grid with no toothpicks, so a(0) = 0.
At stage n we place the smallest possible number of toothpicks of length 1 connected by their endpoints in horizontal direction starting from the grid point (0, n) such that the x-coordinate of the exposed endpoint of the last toothpick is not equal to the x-coordinate of any outer corner of the structure. Then we place toothpicks of length 1 connected by their endpoints in vertical direction, starting from the exposed toothpick endpoint, downward up to touch the structure or up to touch the x-axis.
The sequence gives the number of toothpicks after n stages. A228367 (the first differences) gives the number of toothpicks added at the n-th stage.
Note that the number of toothpick of added at n-th stage in horizontal direction is also A001511(n) and the number of toothpicks added at n-th stage in vertical direction is also A006519(n). Also counting both the x-axis and the y-axis we have that A001511(n) is also the largest part of the n-th region of the diagram and A006519(n) is also the number of parts of the n-th region of the diagram.
After 2^k stages a new section of the structure is completed, so the structure can be interpreted as a diagram of the 2^(k-1) compositions of k in colexicographic order, if k >= 1 (see A228525). The infinite diagram can be interpreted as a table of compositions of the positive integers.
LINKS
FORMULA
EXAMPLE
Illustration of initial terms (n = 1..8):
. _ _ _ _
. _ _ |
. _ _ _|_ _|_ |
. _ _ | _ | _ | |
. _ _ _ _|_ _ _|_|_ _|_|_ _|_|_ |
. _ _ | _ | _ | _ | _ | |
. _ _ _|_ _|_ | _|_ | _|_ | _|_ | _|_ | |
._ _ | _ | _ | | _ | | _ | | _ | | _ | | |
. | | | | | | | | | | | | | | | | | | | | |
.
.2 6 8 15 17 21 23 35
.
After 16 stages there are 79 toothpicks in the structure which represents the compositions of 5 in colexicographic order as shown below:
-------------------------------
n Diagram Composition
-------------------------------
. _ _ _ _ _
16 _ | 5
15 _|_ | 1+4
14 _ | | 2+3
13 _|_|_ | 1+1+3
12 _ | | 3+2
11 _|_ | | 1+2+2
10 _ | | | 2+1+2
9 _|_|_|_ | 1+1+1+2
8 _ | | 4+1
7 _|_ | | 1+3+1
6 _ | | | 2+2+1
5 _|_|_ | | 1+1+2+1
4 _ | | | 3+1+1
3 _|_ | | | 1+2+1+1
2 _ | | | | 2+1+1+1
1 | | | | | 1+1+1+1+1
.
PROG
(Python)
def A228366(n): return sum(((m:=(i>>1)+1)&-m).bit_length() if i&1 else (m:=i>>1)&-m for i in range(1, 2*n+1)) # Chai Wah Wu, Jul 15 2022
CROSSREFS
KEYWORD
nonn
AUTHOR
Omar E. Pol, Aug 22 2013
STATUS
approved