A007846 - OEIS

A007846

There are three equivalent descriptions: 1. Number of (horizontally or vertically) connected arrays of 1..n on rectangular grid (otherwise zero) with only one local maximum. 2. Number of n-polyominoes labeled 1...n such that each successive labeled cell is the neighbor of a previously labeled cell. 3. Number of connected n-step paths on a rectangular lattice, diagonal or repeated steps not allowed.

1, 1, 4, 24, 176, 1504, 14560, 156768, 1852512, 23783264, 329070176, 4874845920, 76898357216, 1285734871520, 22695759641440, 421508294003424, 8211642378316768

(list; graph; refs; listen; history; text; internal format)

OFFSET

0,3

COMMENTS

Description #1 and the extended sequence are from R. H. Hardin, Oct 25 2003. The sequence was originally submitted by Joel Yellin (yellin(AT)soe.ucsc.edu), who referenced the literature on random sequential adsorption (RSA) and used description #3.

Mapping between Descriptions 1 and 3: Renumber 1..n in Description #1 as n..1, so that there is only one local minimum.

REFERENCES

A. Baram and D. Kutasov, "On the dynamics of random sequential absorption," J. Physics A: Math. Gen. 22, L251-L254 (1989).

Y. Fan and J. K. Percus, Use of Model Solutions in RSA on a Lattice, Phys. Rev. Lett. 67, 1677 (1991).

LINKS

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

EXAMPLE

Examples for description #1:

For n=2 there are 4 possibilities:

.................

..1..2..12..21...

..2..1...........

.................

For n=3 there are 24 possibilities:

....................

.123..132..231..321.

....................

.1..1..2..3.........

.2..3..3..2.........

.3..2..1..1.........

.........................

.12.21..1.32.3...3.1..23.

..3.3..32..1.21.12.23.1..

.........................

.31.13..1.23.2...2.1..32.

.2...2.23..1.31.13.32.1..

.........................

Examples for description #3. n=3: Place step #3 on each of six possible nearest neighbor (NN) sites of the 4 n=2 configurations given below for description #1. Total instances = 4 X 6 = 24. n=4: Place step #4 on each of 8 NN sites of 8 (straight line) configurations of the form 123. Place step #4 on each of 7 NN sites of 16 configurations of the form 12/3 (with the 3 under the 1). Total instances = 8 X 8 + 7 X 16 = 176.

CROSSREFS

If the numbers are constrained to be on a line: A000079, in a square array: A087518, in an n X k array: A087783.

Sequence in context: A000309 A112914 A308543 * A337507 A139702 A213591

Adjacent sequences: A007843 A007844 A007845 * A007847 A007848 A007849

KEYWORD

nonn,nice

AUTHOR

Joel Yellin (yellin(AT)soe.ucsc.edu)

EXTENSIONS

New description and more terms from R. H. Hardin, Oct 25 2003

Entry revised following comments from Joel Yellin (yellin(AT)soe.ucsc.edu), Mar 04, 2004

STATUS

approved