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,3

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.

Links

Table of n, a(n) for n=0..60.

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

Formula

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

Example

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
.

Crossrefs

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

Sequence in context: A077220 A128716 A258934 * A183422 A025057 A189753

Adjacent sequences: A225597 A225598 A225599 * A225601 A225602 A225603

Keyword

nonn

Author

Omar E. Pol, Jul 28 2013

Status

approved