login
A171158
The number of walks from (0,0,0) to (n,n,n) with steps that increment one to three coordinates and having the property that no two consecutive steps are orthogonal.
3
1, 1, 19, 235, 3181, 44725, 648439, 9614329, 145020445, 2217212539, 34269961873, 534449721793, 8397498847645, 132785160326593, 2111135363144743, 33723822603109987, 540949658114010583, 8708952402795685879, 140665766088396528829, 2278642960112808284773
OFFSET
0,3
COMMENTS
a(n) is also the number of standard sequence alignments of three strings of length n, counting only those alignments with the property that, for every pair of consecutive alignment columns, there is at least one sequence that contributes a non-gap to both columns. That is, a(n) counts only those standard alignments with a column order that can be unambiguously reconstructed from the knowledge of all pairings, where a pairing is, e.g., that some i-th position of some string x is in the same column as some j-th position of some string y. - Lee A. Newberg, Dec 11 2009
LINKS
FORMULA
a(n) ~ c * d^n / n, where d = 17.073685937995..., c = 0.171212682922... . - Vaclav Kotesovec, Sep 10 2014
EXAMPLE
For n = 2, the 19 walks are:
000 -> 001 -> 012 -> 122 -> 222
000 -> 001 -> 102 -> 212 -> 222
000 -> 001 -> 112 -> 222
000 -> 010 -> 021 -> 122 -> 222
000 -> 010 -> 120 -> 221 -> 222
000 -> 010 -> 121 -> 222
000 -> 011 -> 112 -> 222
000 -> 011 -> 121 -> 222
000 -> 011 -> 122 -> 222
000 -> 100 -> 201 -> 212 -> 222
000 -> 100 -> 210 -> 221 -> 222
000 -> 100 -> 211 -> 222
000 -> 101 -> 112 -> 222
000 -> 101 -> 211 -> 222
000 -> 101 -> 212 -> 222
000 -> 110 -> 121 -> 222
000 -> 110 -> 211 -> 222
000 -> 110 -> 221 -> 222
000 -> 111 -> 222
CROSSREFS
See A171155 for the number of such walks in two dimensions.
See A171563 for the number of such walks in four dimensions. - Lee A. Newberg, Dec 11 2009
Sequence in context: A276201 A025960 A152494 * A022033 A025938 A229026
KEYWORD
nonn,walk
AUTHOR
Lee A. Newberg, Dec 04 2009
EXTENSIONS
Extended beyond a(10) by Alois P. Heinz, Jan 22 2013
STATUS
approved