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

Offset: 0

Author

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

Keywords

• nonn
• nice

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.

Examples

			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.
		

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).

Crossrefs

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

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