A034720 Number of different words that can be formed from an n X n grid of letters, reading horizontally, vertically or diagonally.

1, 16, 65, 168, 345, 616, 1001, 1520, 2193, 3040, 4081, 5336, 6825, 8568, 10585, 12896, 15521, 18480, 21793, 25480, 29561, 34056, 38985, 44368, 50225, 56576, 63441, 70840, 78793, 87320, 96441, 106176, 116545, 127568, 139265, 151656

Offset

1,2

Comments

Also variance of (i.e., expectation of the square of) area under a random walk with 2n steps whose first return to the origin is at point 2n. - Henry Bottomley, Apr 11 2002

Also number of numbers to be checked for primality in the n X n generalization of the Gordon Lee puzzle (see A109943). - Hugo Pfoertner, Jul 09 2005

Links

Table of n, a(n) for n=1..36.

Formula

n^2 + 4*(n+1)*Sum {(n-j-1); j=0..n-1} + 8*Sum {(n-k-j-1); j=0..n-2, k=1..n-1-j}.

a(n) = n*(2n-1)*(5n-2)/3. - Henry Bottomley, Apr 11 2002

Example

For n=2, from the array
  ab
  cd
we get 16 words:
  a,b,c,d,ab,ba,cd,dc,ac,ca,bd,db,ad,da,cb,bc.
For n=3, from abc/def/ghi we get 9 of length 1, 40 of length 2, 16 of length 3, a total of 65.
Gordon Lee puzzle: In a 3 X 3 matrix ((1 2 3)(4 5 6)(7 8 9)) the following numbers have to be checked: 9 single-digit numbers 1...9;
40 2-digit numbers: row-wise 12, 21, 23, 32, 45, 54, 56, 65, 78, 87, 89, 98; column-wise 14, 41, 47, 74, 25, 52, 58, 85, 36, 63, 69, 96; diagonals 15, 51, 59, 95, 48, 84, 26, 62; antidiagonals 35, 53, 57, 75, 24, 42, 68, 86;
16 3-digit numbers: 123, 321, 456, 654, 789, 987, 147, 741, 258, 852, 369, 963, 159, 951, 357, 753.

Crossrefs

Cf. A109943 [Number of primes in the solution of the Gordon Lee puzzle].

Sequence in context: A043402 A044154 A044535 * A232050 A119285 A253673

Adjacent sequences: A034717 A034718 A034719 * A034721 A034722 A034723

Keyword

nonn

Author

Felice Russo

Extensions

More terms from Hugo Pfoertner, Jul 09 2005

Status

approved