A047057 -id:A047057 - cp's OEIS frontend

A173380 Number of n-step walks on square lattice (no points repeated, no adjacent points unless consecutive in path).

1, 4, 12, 28, 68, 164, 396, 940, 2244, 5324, 12668, 29940, 71012, 167468, 396172, 932628, 2201636, 5175268, 12195660, 28632804, 67374292, 158017740, 371354012, 870197548, 2042809996, 4783292988, 11218303476, 26250429540, 61514573604, 143857013260, 336865512780, 787374453524, 1842579846180

Offset: 0

Joseph Myers, Nov 22 2010

Fisher and Hiley give 396204 as their last term instead of 396172 (see A002932).  Douglas McNeil confirms 396172 (see seqfan discussion).
Comment from N. J. A. Sloane, Nov 27 2010: Joseph Myers has discovered that several of the sequences listed by Fisher and Riley (1961) contained errors. R. J. Mathar comments that this article has 62 citations in http://adsabs.harvard.edu/abs/1961JChPh..34.1253F and that clicking through these with the "Citations to the Article (62)" button is one way to check the numbers by searching for corrections.
From Petros Hadjicostas, Jan 01 2019: (Start)
Nemirovsky et al. (1992), for a d-dimensional hypercubic lattice, define C_{n,m} to be "the number of configurations of an n-bond self-avoiding chain with m neighbor contacts." For d=2 (square lattice) and m=0 (no neighbor contacts), we have (for the current sequence) a(n) = C(n, m=0). These values (from n=1 to n=11) are listed in Table I (p. 1088) in the paper.
According to Eq. (5), p. 1090, in the above paper, for a general d, the partition number C_{n,m} satisfies C_{n,m} = Sum_{l=1..n} 2^l*l!*Bin(d,l)*p_{n,m}^{(l)}, where the coefficients p_{n,m}^{(l)} (l=1,2,...) are independent of d. For d=2 (square lattice), this becomes C_{n,m} = Sum_{l=1..n} 2^l*l!*Bin(2,l)*p_{n,m}^{(l)}.
According to Eq. (7a) and (7b), p. 1093, in the paper, p_{n,0}^{(1)} = 1 = p_{n,0}^{(n)}, p_{n,m}^{(1)} = 0 for m >= 1, and p_{n,m}^{(l)} = 0 for m >= 1 and n-m+1 <= l <= n.
Now, assume d=2. Since p_{n,0}^{(1)} = 1 for n >= 1, we have C_{1,0} = 2^1*1!*Bin(2,1)*1 = 4, while C_{n,0} = 4 + 2^2*2!*Bin(2,2)*p_{n,0}^{(2)} = 4 + 8*p_{n,0}^{(2)} for n >= 2. The partition numbers p_{n,0}^{(2)} appear in Table II, p. 1093, in the paper. We have p_{n,0}^{(2)} = A038746(n) (with p_{1,0}^{(2)} = 0 to make the formula C_{n,0} = 4 + 8*p_{n,0}^{(2)} valid even for n=1).
(End)

N. J. A. Sloane, A Handbook of Integer Sequences, Academic Press, 1973 (includes this sequence).
N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).

Scott R. Shannon, Table of n, a(n) for n = 0..35
D. Bennett-Wood, I. G. Enting, D. S. Gaunt, A. J. Guttmann, J. L. Leask, A. L. Owczarek, and S. G. Whittington, Exact enumeration study of free energies of interacting polygons and walks in two dimensions, J. Phys. A: Math. Gen. 31 (1998), 4725-4741. [See Table B1 (pp. 4738-4739), where the numbers must be multiplied by 4. - _Petros Hadjicostas_, Jan 05 2019]
M. E. Fisher and B. J. Hiley, Configuration and free energy of a polymer molecule with solvent interaction, J. Chem. Phys., 34 (1961), 1253-1267.
A. M. Nemirovsky, K. F. Freed, T. Ishinabe, and J. F. Douglas, Marriage of exact enumeration and 1/d expansion methods: lattice model of dilute polymers, J. Statist. Phys., 67 (1992), 1083-1108.
Sequence Fans Mailing list, discussion of this sequence, November 2010

Cf. A002932, A002934, A033155, A033323, A034006, A038746, A042949, A046788, A047057, A174319.

A038746 = Cases[Import["https://oeis.org/A038746/b038746.txt", "Table"], {, }][[All, 2]];
a[n_] := If[n == 0, 1, 8 A038746[[n]] + 4];
a /@ Range[0, 32] (* Jean-François Alcover, Feb 24 2020 *)

a(n) = 4 + 8*A038746(n) for n>=1.

a(23)-a(32) from Bert Dobbelaere, Jan 02 2019

a(33)-a(35) from Scott R. Shannon, Aug 25 2020

A038746 Coefficients arising in the enumeration of configurations of linear chains.

Original entry on oeis.org

0, 1, 3, 8, 20, 49, 117, 280, 665, 1583, 3742, 8876, 20933, 49521, 116578, 275204, 646908, 1524457, 3579100, 8421786, 19752217, 46419251, 108774693, 255351249, 597911623, 1402287934, 3281303692, 7689321700, 17982126657, 42108189097, 98421806690, 230322480772

Offset: 1

N. J. A. Sloane, May 02 2000

This counts non-self-intersecting paths of length n on the square lattice, start and end points distinguished, straight line paths not counted, rotations and reflections of a path not counted as distinct from that path.
From Petros Hadjicostas, Jan 01 2019: (Start)
Nemirovsky et al. (1992), for a d-dimensional hypercubic lattice, define C_{n,m} to be "the number of configurations of an n-bond self-avoiding chain with m neighbor contacts." For d=2 (square lattice) and m=0 (no neighbor contacts), we have C(n, m=0) = A173380(n). These values (from n=1 to n=11) are listed in Table I (p. 1088) in the paper.
According to Eq. (5), p. 1090, in the above paper, for a general d, the partition number C_{n,m} satisfies C_{n,m} = Sum_{l=1..n} 2^l*l!*Bin(d,l)*p_{n,m}^{(l)}, where the coefficients p_{n,m}^{(l)} (l=1,2,...) are independent of d. For d=2 (square lattice), this becomes C_{n,m} = Sum_{l=1..n} 2^l*l!*Bin(2,l)*p_{n,m}^{(l)}.
According to Eq. (7a) and (7b), p. 1093, in the paper, p_{n,0}^{(1)} = 1 = p_{n,0}^{(n)}, p_{n,m}^{(1)} = 0 for m >= 1, and p_{n,m}^{(l)} = 0 for m >= 1 and n-m+1 <= l <= n.
Now, assume d=2. Since p_{n,0}^{(1)} = 1 for n >= 1, we have C_{1,0} = 2^1*1!*Bin(2,1)*1 = 4, while C_{n,0} = 4 + 2^2*2!*Bin(2,2)*p_{n,0}^{(2)} = 4 + 8*p_{n,0}^{(2)} for n >= 2. The partition numbers p_{n,0}^{(2)} appear in Table II, p. 1093, in the paper. For the current sequence, we have a(n) = p_{n,0}^{(2)} (with a(1) = p_{1,0}^{(2)} = 0 to make the formula A173380(n) = C_{n,0} = 4 + 8*p_{n,0}^{(2)} = 4 + 8*a(n) valid even for n=1).
Apparently, some of the numbers C_{n,m} (for d=2 and d=3) are calculated in Fisher and Hiley (1961); see Table II, p. 1261 (square and cubic). For d=2, they calculate C(n,0) for 1 <= n < 14, while for d=3, they calculate C(n,0) for 1 <= n <= 10. It seems, however, that there are some possible typos there. The typos (for both d=2 and d=3) become apparent if one compares their results with the numbers in Table I (p. 1088) in Nemirovsky et al. (1992). See the comments for the sequence A173380 for more details.
(End)
No adjacent points allowed unless consecutive in path - Bert Dobbelaere, Jan 02 2019

M. E. Fisher and B. J. Hiley, Configuration and free energy of a polymer molecule with solvent interaction, J. Chem. Phys., 34 (1961), 1253-1267.
A. M. Nemirovsky, K. F. Freed, T. Ishinabe, and J. F. Douglas, Marriage of exact enumeration and 1/d expansion methods: lattice model of dilute polymers, J. Statist. Phys., 67 (1992), 1083-1108; see Eq. 5 (p. 1090).

A173380(n) = 8*a(n) + 4.

Cf. A002932, A002934, A033155, A033323, A034006, A042949, A046788, A047057, A174319.

Initial 0 added to match offset in reference, further explanation and terms a(12) = 8876 to a(22) = 46419251 by Joseph Myers, Nov 22 2010

a(23)-a(32) from Bert Dobbelaere, Jan 02 2019

A038747 Coefficients arising in the enumeration of configurations of linear chains.

Original entry on oeis.org

0, 0, 1, 4, 11, 32, 92, 254, 672, 1778, 4622, 11938, 30442, 77396, 194896, 489620, 1221134, 3040194, 7524933, 18600478, 45756483, 112444948, 275204606, 673031750, 1640168584, 3994716336, 9699476314

Offset: 1

N. J. A. Sloane, May 02 2000

In the notation of Nemirovsky et al. (1992), a(n), the n-th term of this sequence is p_{n,m}^{(l)} with m=1 and l=2. These numbers are given in Table II (p. 1093) in the paper. This sequence can be used for the calculation of sequence A033155(n) via Eq. (5) in the paper by Nemirovsky et al. (1992). (Note that, by equations (7b) in the paper, p_{n,1}^{(1)} = 0 for all n >= 1.) - Petros Hadjicostas, Jan 03 2019

In Table B1 (pp. 4738-4739), Bennett-Wood et al. (1998) tabulated c_n(k)/4, for various values of n and k, where c_n(k) is "the number of SAWs of length n with k nearest-neighbour contacts". (Here, the letter k stands for the letter m in the previous paragraph.) Bennett-Wood et al. (1998) worked only with a square lattice (i.e., d=2) unlike Nemirovsky et al. (1992) who worked with a d-dimensional hypercubic lattice. Both papers deal with SAWs = self-avoiding walks (in a lattice). We have c_n(k=1) = A033155(n) = 8*p_{n,1}^{(2)}, i.e., a(n) = p_{n,1}^{(2)} = (c_n(k=1)/4)/2, and this is the reason the numbers in Table B1 in Bennett-Wood et al. (1998) must be divided by 2 in order to get extra terms for the current sequence (a(12) to a(24)). - Petros Hadjicostas, Jan 05 2019

D. Bennett-Wood, I. G. Enting, D. S. Gaunt, A. J. Guttmann, J. L. Leask, A. L. Owczarek, and S. G. Whittington, Exact enumeration study of free energies of interacting polygons and walks in two dimensions, J. Phys. A: Math. Gen. 31 (1998), 4725-4741.
M. E. Fisher and B. J. Hiley, Configuration and free energy of a polymer molecule with solvent interaction, J. Chem. Phys., 34 (1961), 1253-1267.
A. M. Nemirovsky, K. F. Freed, T. Ishinabe, and J. F. Douglas, Marriage of exact enumeration and 1/d expansion methods: lattice model of dilute polymers, J. Statist. Phys., 67 (1992), 1083-1108; see Eq. 5 (p. 1090) and Eq. 7b (p. 1093).

Cf. A033155, A038749, A047057.

The first two 0's in the sequence were inserted by Petros Hadjicostas, Jan 03 2019 to make it agree with Table II (p. 1093) and Eq. (5) (p. 1090) in the paper by Nemirovsky et al. (1992)
Terms a(12) to a(24) were copied from Table II, p. 4738, in the paper by Bennett-Wood et al. (1998) (after division by 2) by Petros Hadjicostas, Jan 05 2019
a(25)-a(27) from Sean A. Irvine, Jul 03 2020

A042949 Configurations of linear chains in a 4-dimensional hypercubic lattice.

Original entry on oeis.org

0, 0, 48, 576, 4752, 36864, 271680, 1931808, 13384320, 91133664, 610863072, 4051654752, 26592186336, 173304754368, 1121024960064

Offset: 1

N. J. A. Sloane

In the notation of Nemirovsky et al. (1992), a(n), the n-th term of the current sequence is C_{n,m} with m=1 (and d=4). Here, for a d-dimensional hypercubic lattice, C_{n,m} is "the number of configurations of an n-bond self-avoiding chain with m neighbor contacts." (For d=2, we have C_{n,m=1} = A033155(n) while for d=3, we have C_{n,m=1}=A047057(n).) These numbers are given in Table I (p. 1088) in the paper by Nemirovsky et al. (1992). - Petros Hadjicostas, Jan 04 2019

A. M. Nemirovsky, K. F. Freed, T. Ishinabe, and J. F. Douglas, Marriage of exact enumeration and 1/d expansion methods: lattice model of dilute polymers, J. Statist. Phys., 67 (1992), 1083-1108.

Cf. A033155, A047057.

Name edited by Petros Hadjicostas, Jan 04 2019

a(12)-a(15) from Sean A. Irvine, Jan 31 2021

A038749 Coefficients arising in the enumeration of configurations of linear chains.

Original entry on oeis.org

0, 0, 0, 2, 16, 96, 510, 2558, 12282, 57498, 263421, 1192480, 5330078, 23657520, 104106655, 455993276, 1984733843, 8609546380, 37164674383

Offset: 1

N. J. A. Sloane, May 02 2000

In the notation of Nemirovsky et al. (1992), a(n), the n-th term of this sequence is p_{n,m}^{(l)} with m=1 and l=3. These numbers are given in Table II (p. 1093) in the paper. This sequence can be used for the calculation of sequence A047057 via Eq. (5) in the paper by Nemirovsky et al. (1992). (Note that, by equations (7b) in the paper, p_{n,m=1}^{(1)} = 0 for all n >= 1. Also, p_{n,m=1}^{(2)} = A038747(n) for n >= 1.) - Petros Hadjicostas, Jan 04 2019

A. M. Nemirovsky, K. F. Freed, T. Ishinabe, and J. F. Douglas, Marriage of exact enumeration and 1/d expansion methods: lattice model of dilute polymers, J. Statist. Phys., 67 (1992), 1083-1108; see Eq. 5 (p. 1090) and Eq. 7b (p. 1093).

Cf. A033155, A038747, A047057.

The first three 0's in the sequence were added by Petros Hadjicostas, Jan 04 2019 to make it agree with Table II (p. 1093) and Eq. (5) (p. 1090) in the paper by Nemirovsky et al. (1992).

a(12)-a(19) from Sean A. Irvine, Feb 02 2021

A336492 Total number of neighbor contacts for n-step self-avoiding walks on a 2D square lattice.

Original entry on oeis.org

0, 0, 8, 32, 152, 512, 1880, 5920, 19464, 59168, 183776, 545392, 1638400, 4778000, 14043224, 40422544, 116977176, 333346928, 953538440, 2695689520, 7642091352, 21464794032, 60417010152, 168787016352, 472315518008, 1313548558528, 3657850909680, 10133559518800

Offset: 1

Scott R. Shannon, Jul 23 2020

nonn

This sequence gives the total number of neighbor contacts for all n-step self avoiding walks on a 2D square lattices. A neighbor contact is when the walk comes within 1 unit distance of a previously visited point, excluding the previous adjacent point.

			a(1) = a(2) = 0 as a 1 and 2 step walk cannot approach a previous step.
a(3) = 8. The single walk where one interaction occurs, which can be taken in eight ways on a 2D square lattice, is:
.
   +---+
       |
   X---+
.
Therefore, the total number of interactions is 1*1*8 = 8.
a(4) = 32. The four walks where one interaction occurs, each of which can be taken in eight ways on a 2D square lattice, are:
.
  +---+---+   +           +---+       +---+
          |   |               |       |   |
      X---+   +---+   X---+---+   X---+   +
                  |
              X---+
.
Therefore, the total number of interactions is 4*1*8 = 32.
a(5) = 152. Considering only walks which start with one or more steps to the right followed by an upward step there are thirty-five different walks. Eleven of these have one neighbor contact (hence A033155(5) = 11*8 = 88) while four have two contacts. These are:
.
  +---+---+   +---+---+   +---+   +---+
  |       |           |   |       |   |
  +   X---+   X---+---+   +---+   +   +
                              |       |
                          X---+   X---+
.
Therefore, the total number of contacts is (11*1 + 4*2)*8 = 152.

D. Bennett-Wood, I. G. Enting, D. S. Gaunt, A. J. Guttmann, J. L. Leask, A. L. Owczarek, and S. G. Whittington, Exact enumeration study of free energies of interacting polygons and walks in two dimensions, J. Phys. A: Math. Gen. 31 (1998), 4725-4741.
M. E. Fisher and B. J. Hiley, Configuration and free energy of a polymer molecule with solvent interaction, J. Chem. Phys., 34 (1961), 1253-1267.
A. M. Nemirovsky, K. F. Freed, T. Ishinabe, and J. F. Douglas, Marriage of exact enumeration and 1/d expansion methods: lattice model of dilute polymers, J. Statist. Phys., 67 (1992), 1083-1108.

Cf. A033155 (total number of n-step walks containing one neighbor contact), A038747, A047057, A173380, A174319.

A038727 Configurations of linear chains in a 5-dimensional hypercubic lattice.

Original entry on oeis.org

0, 0, 80, 1280, 14320, 148480, 1459840, 13835680, 127784640, 1158460000, 10342876480, 91312921760, 798077066720, 6922857067840

Offset: 1

N. J. A. Sloane, May 02 2000

In the notation of Nemirovsky et al. (1992), a(n), the n-th term of the current sequence is C_{n,m} with m=1 (and d=5). Here, for a d-dimensional hypercubic lattice, C_{n,m} is "the number of configurations of an n-bond self-avoiding chain with m neighbor contacts." (For d=2, we have C_{n,m=1} = A033155(n); for d=3, we have C_{n, m=1} = A047057(n); for d=4, we have C_{n,m=1} = A042949(n); and for d=6, we have C_{n,m=1} = A038745(n). These values appear in Table 1, pp. 1088-1090, of Nemirovsky et al. (1992).) - Petros Hadjicostas, Jan 06 2019

A. M. Nemirovsky, K. F. Freed, T. Ishinabe, and J. F. Douglas, Marriage of exact enumeration and 1/d expansion methods: lattice model of dilute polymers, J. Statist. Phys., 67 (1992), 1083-1108.

Cf. A033155, A038745, A042949, A047057.

Name was edited by Petros Hadjicostas, Jan 06 2019
Terms a(10) and a(11) were copied from Table I, p. 1090, in Nemirovsky et al. (1992) by Petros Hadjicostas, Jan 06 2019
a(12)-a(14) from Sean A. Irvine, Jan 31 2021

A038745 Configurations of linear chains in a 6-dimensional hypercubic lattice.

Original entry on oeis.org

0, 0, 120, 2400, 33960, 441600, 5436960, 64509840, 745845120, 8461348080, 94558053840, 1044594244080, 11426874632880

Offset: 1

N. J. A. Sloane, May 02 2000

In the notation of Nemirovsky et al. (1992), a(n), the n-th term of the current sequence is C_{n,m} with m=1 (and d=6). Here, for a d-dimensional hypercubic lattice, C_{n,m} is "the number of configurations of an n-bond self-avoiding chain with m neighbor contacts." (For d=2, we have C_{n,m=1} = A033155(n); for d=3, we have C_{n, m=1} = A047057(n); for d=4, we have C_{n,m=1} = A042949(n); and for d=5, we have C_{n,m=1} = A038727(n). These values appear in Table 1, pp. 1088-1090, of Nemirovsky et al. (1992).) - Petros Hadjicostas, Jan 06 2019

A. M. Nemirovsky, K. F. Freed, T. Ishinabe, and J. F. Douglas, Marriage of exact enumeration and 1/d expansion methods: lattice model of dilute polymers, J. Statist. Phys., 67 (1992), 1083-1108; see Eq. 5 (p. 1090) and Eq. 7b (p. 1093).

Cf. A033155, A038727, A042949, A047057.

a(10)-a(11) copied from Table 1, p. 1090, of Nemirovsky et al. (1992) by Petros Hadjicostas, Jan 06 2019
Name edited by Petros Hadjicostas, Jan 06 2019
a(12)-a(13) from Sean A. Irvine, Jan 31 2021

cp's OEIS Frontend

A173380 Number of n-step walks on square lattice (no points repeated, no adjacent points unless consecutive in path).

Views

Author

Keywords

Comments

References

Links

Crossrefs

Programs

Mathematica

Formula

Extensions

A038746 Coefficients arising in the enumeration of configurations of linear chains.

Views

Author

Keywords

Comments

Links

Crossrefs

Extensions

A038747 Coefficients arising in the enumeration of configurations of linear chains.

Views

Author

Keywords

Comments

Links

Crossrefs

Extensions

A042949 Configurations of linear chains in a 4-dimensional hypercubic lattice.

Views

Author

Keywords

Comments

Links

Crossrefs

Extensions

A038749 Coefficients arising in the enumeration of configurations of linear chains.

Views

Author

Keywords

Comments

Links

Crossrefs

Extensions

A336492 Total number of neighbor contacts for n-step self-avoiding walks on a 2D square lattice.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

A038727 Configurations of linear chains in a 5-dimensional hypercubic lattice.

Views

Author

Keywords

Comments

Links

Crossrefs

Extensions

A038745 Configurations of linear chains in a 6-dimensional hypercubic lattice.

Views

Author

Keywords

Comments

Links

Crossrefs

Extensions