A225600 Toothpick sequence related to integer partitions (see Comments lines for definition).

0, 1, 2, 4, 6, 9, 12, 14, 15, 19, 24, 27, 28, 33, 40, 42, 43, 47, 49, 52, 53, 59, 70, 73, 74, 79, 81, 85, 86, 93, 108, 110, 111, 115, 117, 120, 121, 127, 131, 136, 137, 141, 142, 150, 172, 175, 176, 181, 183, 187, 188, 195, 199, 202, 203, 209, 211, 216, 217, 226, 256

Offset: 0

Author

Omar E. Pol, Jul 28 2013

Keywords

• nonn

Comments

This infinite toothpick structure is a minimalist diagram of regions of the set of partitions of all positive integers. For the definition of "region" see A206437. The sequence shows the growth of the diagram as a cellular automaton in which the "input" is A141285 and the "output” is A194446.

To define the sequence we use the following rules:

We start in the first quadrant of the square grid with no toothpicks.

If n is odd we place A141285((n+1)/2) toothpicks of length 1 connected by their endpoints in horizontal direction starting from the grid point (0, (n+1)/2).

If n is even 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. In this case the number of toothpicks added in vertical direction is equal to A194446(n/2).

The sequence gives the number of toothpicks after n stages. A220517 (the first differences) gives the number of toothpicks added at the n-th stage.

Also the toothpick structure (HV/HHVV/HHHVVV/HHV/HHHHVVVVV...) can be transformed in a Dyck path (UDUUDDUUUDDDUUDUUUUDDDDD...) in which the n-th odd-indexed segment has A141285(n) up-steps and the n-th even-indexed segment has A194446(n) down-steps, so the sequence can be represented by the vertices (or the number of steps from the origin) of the Dyck path. Note that the height of the n-th largest peak between two valleys at height 0 is also the partition number A000041(n). See Example section. See also A211978, A220517, A225610.

Examples

			For n = 30 the structure has 108 toothpicks, so a(30) = 108.
.                               Diagram of regions
Partitions of 7                 and partitions of 7
.                                   _ _ _ _ _ _ _
7                               15  _ _ _ _      |
4 + 3                               _ _ _ _|_    |
5 + 2                               _ _ _    |   |
3 + 2 + 2                           _ _ _|_ _|_  |
6 + 1                           11  _ _ _      | |
3 + 3 + 1                           _ _ _|_    | |
4 + 2 + 1                           _ _    |   | |
2 + 2 + 2 + 1                       _ _|_ _|_  | |
5 + 1 + 1                        7  _ _ _    | | |
3 + 2 + 1 + 1                       _ _ _|_  | | |
4 + 1 + 1 + 1                    5  _ _    | | | |
2 + 2 + 1 + 1 + 1                   _ _|_  | | | |
3 + 1 + 1 + 1 + 1                3  _ _  | | | | |
2 + 1 + 1 + 1 + 1 + 1            2  _  | | | | | |
1 + 1 + 1 + 1 + 1 + 1 + 1        1   | | | | | | |
.
.                                   1 2 3 4 5 6 7
.
Illustration of initial terms:
.
.                              _ _ _    _ _ _
.                _ _   _ _     _ _      _ _  |
.      _    _    _     _  |    _  |     _  | |
.            |    |     | |     | |      | | |
.
.      1    2     4     6       9        12
.
.
.                          _ _ _ _     _ _ _ _
.      _ _       _ _       _ _         _ _    |
.      _ _ _     _ _|_     _ _|_       _ _|_  |
.      _ _  |    _ _  |    _ _  |      _ _  | |
.      _  | |    _  | |    _  | |      _  | | |
.       | | |     | | |     | | |       | | | |
.
.        14        15         19          24
.
.
.                          _ _ _ _ _    _ _ _ _ _
.    _ _ _      _ _ _      _ _ _        _ _ _    |
.    _ _ _ _    _ _ _|_    _ _ _|_      _ _ _|_  |
.    _ _    |   _ _    |   _ _    |     _ _    | |
.    _ _|_  |   _ _|_  |   _ _|_  |     _ _|_  | |
.    _ _  | |   _ _  | |   _ _  | |     _ _  | | |
.    _  | | |   _  | | |   _  | | |     _  | | | |
.     | | | |    | | | |    | | | |      | | | | |
.
.       27         28         33            40
.
Illustration of initial terms as vertices (or the number of steps from the origin) of a Dyck path:
.
7                                    33
.                                    /\
5                      19           /  \
.                      /\          /    \
3            9        /  \     27 /      \
2       4    /\   14 /    \    /\/        \
1    1  /\  /  \  /\/      \  / 28         \
.    /\/  \/    \/ 15       \/              \
.   0  2   6    12          24              40
.
		

Links

• Omar E. Pol, Visualization of regions in a diagram for A006128
• N. J. A. Sloane, Catalog of Toothpick and Cellular Automata Sequences in the OEIS
• Index entries for sequences related to toothpick sequences

Crossrefs

Cf. A000041, A006128, A135010, A138137, A139250, A139582, A141285, A186114, A186412, A187219, A194446, A194447, A206437, A207779, A211978, A220517, A225610.

Formula

a(A139582(n)) = a(2*A000041(n)) = 2*A006128(n) = A211978(n), n >= 1.