cp's OEIS Frontend

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

%I A173380 #60 Dec 23 2024 14:53:42
%S A173380 1,4,12,28,68,164,396,940,2244,5324,12668,29940,71012,167468,396172,
%T A173380 932628,2201636,5175268,12195660,28632804,67374292,158017740,
%U A173380 371354012,870197548,2042809996,4783292988,11218303476,26250429540,61514573604,143857013260,336865512780,787374453524,1842579846180
%N A173380 Number of n-step walks on square lattice (no points repeated, no adjacent points unless consecutive in path).
%C A173380 Fisher and Hiley give 396204 as their last term instead of 396172 (see A002932).  Douglas McNeil confirms 396172 (see seqfan discussion).
%C A173380 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.
%C A173380 From _Petros Hadjicostas_, Jan 01 2019: (Start)
%C A173380 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.
%C A173380 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)}.
%C A173380 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.
%C A173380 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).
%C A173380 (End)
%D A173380 N. J. A. Sloane, A Handbook of Integer Sequences, Academic Press, 1973 (includes this sequence).
%D A173380 N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).
%H A173380 Scott R. Shannon, <a href="/A173380/b173380.txt">Table of n, a(n) for n = 0..35</a>
%H A173380 D. Bennett-Wood, I. G. Enting, D. S. Gaunt, A. J. Guttmann, J. L. Leask, A. L. Owczarek, and S. G. Whittington, <a href="https://doi.org/10.1088/0305-4470/31/20/010">Exact enumeration study of free energies of interacting polygons and walks in two dimensions</a>, 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]
%H A173380 M. E. Fisher and B. J. Hiley, <a href="http://dx.doi.org/10.1063/1.1731729">Configuration and free energy of a polymer molecule with solvent interaction</a>, J. Chem. Phys., 34 (1961), 1253-1267.
%H A173380 A. M. Nemirovsky, K. F. Freed, T. Ishinabe, and J. F. Douglas, <a href="http://dx.doi.org/10.1007/BF01049010">Marriage of exact enumeration and 1/d expansion methods: lattice model of dilute polymers</a>, J. Statist. Phys., 67 (1992), 1083-1108.
%H A173380 Sequence Fans Mailing list, <a href="https://web.archive.org/web/*/http://list.seqfan.eu/oldermail/seqfan/2010-November/006470.html">discussion of this sequence</a>, November 2010
%F A173380 a(n) = 4 + 8*A038746(n) for n>=1.
%t A173380 A038746 = Cases[Import["https://oeis.org/A038746/b038746.txt", "Table"], {_, _}][[All, 2]];
%t A173380 a[n_] := If[n == 0, 1, 8 A038746[[n]] + 4];
%t A173380 a /@ Range[0, 32] (* _Jean-François Alcover_, Feb 24 2020 *)
%Y A173380 Cf. A002932, A002934, A033155, A033323, A034006, A038746, A042949, A046788, A047057, A174319.
%K A173380 nonn,walk,nice
%O A173380 0,2
%A A173380 _Joseph Myers_, Nov 22 2010
%E A173380 a(23)-a(32) from _Bert Dobbelaere_, Jan 02 2019
%E A173380 a(33)-a(35) from _Scott R. Shannon_, Aug 25 2020