|
| |
|
|
A228370
|
|
Toothpick sequence from a diagram of compositions of the positive integers (see Comments lines for definition).
|
|
9
|
|
|
|
0, 1, 2, 4, 6, 7, 8, 11, 15, 16, 17, 19, 21, 22, 23, 27, 35, 36, 37, 39, 41, 42, 43, 46, 50, 51, 52, 54, 56, 57, 58, 63, 79, 80, 81, 83, 85, 86, 87, 90, 94, 95, 96, 98, 100, 101, 102, 106, 114, 115, 116, 118, 120, 121, 122, 125, 129, 130, 131, 133, 135, 136, 137, 143, 175
(list;
graph;
refs;
listen;
history;
text;
internal format)
|
|
|
|
OFFSET
|
0,3
|
|
|
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.
If n is odd then 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+1)/2) 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.
If n is even then at stage n 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.
Note that the number of toothpick of added at stage (n+1)/2 in horizontal direction is also A001511(n) and the number of toothpicks added at stage n/2 in vertical direction is also A006519(n).
The sequence gives the number of toothpicks after n stages. A228371 (the first differences) gives the number of toothpicks added at the n-th stage.
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.
The equivalent sequence for partitions is A225600.
|
|
|
LINKS
|
|
|
|
FORMULA
|
a(n) = sum_{k=1..n} A228371(k), n >= 1.
|
|
|
EXAMPLE
|
For n = 32 the diagram represents the 16 compositions of 5. The structure has 79 toothpicks, so a(32) = 79. Note that the k-th horizontal line segment has length A001511(k) equals the largest part of the k-th region, and the k-th vertical line segment has length A006519(k) equals the number of parts of the k-th region.
----------------------------------------------------------
. Triangle
Compositions of compositions (rows)
of 5 Diagram and regions (columns)
----------------------------------------------------------
. _ _ _ _ _
5 _ | 5
1+4 _|_ | 1 4
2+3 _ | | 2 3
1+1+3 _|_|_ | 1 1 3
3+2 _ | | 3 2
1+2+2 _|_ | | 1 2 2
2+1+2 _ | | | 2 1 2
1+1+1+2 _|_|_|_ | 1 1 1 2
4+1 _ | | 4 1
1+3+1 _|_ | | 1 3 1
2+2+1 _ | | | 2 2 1
1+1+2+1 _|_|_ | | 1 1 2 1
3+1+1 _ | | | 3 1 1
1+2+1+1 _|_ | | | 1 2 1 1
2+1+1+1 _ | | | | 2 1 1 1
1+1+1+1+1 | | | | | 1 1 1 1 1
.
Illustration of initial terms (n = 1..16):
.
. _ _
. _ _ _ _ _ _ _|_
. _ _ _ _ | _ | _ |
. | | | | | | | |
.
. 1 2 4 6 7 8
.
.
. _ _
. _ _ _
. _ _ _ _ _ _ _ _ _ _|_ _ _|_ _
. _ _ | _ | _ | _ |
. _|_ _|_ | _|_ | _|_ | _|_ |
. _ | _ | | _ | | _ | | _ | |
. | | | | | | | | | | | | | |
.
. 11 15 16 17 19
.
.
. _ _ _ _ _ _ _ _
. _ _ _ _ |
. _ _ _ _ _|_ _|_ _|_ |
. _ | _ | _ | _ | _ | |
. _|_|_ _|_|_ _|_|_ _|_|_ _|_|_ |
. _ | _ | _ | _ | _ | |
. _|_ | _|_ | _|_ | _|_ | _|_ | |
. _ | | _ | | _ | | _ | | _ | | |
. | | | | | | | | | | | | | | | |
.
. 21 22 23 27 35
.
|
|
|
PROG
|
(Python)
def A228370(n): return sum(((m:=(i>>1)+1)&-m).bit_length() if i&1 else (m:=i>>1)&-m for i in range(1, n+1)) # Chai Wah Wu, Jul 14 2022
|
|
|
CROSSREFS
|
Cf. A001511, A005187, A006519, A006520, A011782, A139250, A187816, A187818, A206437, A225600, A228350, A228351, A228366, A228367, A228368, A228371, A228525, A228526.
|
|
|
KEYWORD
|
nonn
|
|
|
AUTHOR
|
|
|
|
STATUS
|
approved
|
| |
|
|
