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

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

Author

N. J. A. Sloane, May 02 2000

Keywords

• nonn
• walk
• more

Comments

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

Links

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

Crossrefs

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

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

Extensions

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