cp's OEIS Frontend

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.

%I A171158 #12 Nov 14 2014 19:50:57
%S A171158 1,1,19,235,3181,44725,648439,9614329,145020445,2217212539,
%T A171158 34269961873,534449721793,8397498847645,132785160326593,
%U A171158 2111135363144743,33723822603109987,540949658114010583,8708952402795685879,140665766088396528829,2278642960112808284773
%N 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.
%C A171158 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
%H A171158 Alois P. Heinz, <a href="/A171158/b171158.txt">Table of n, a(n) for n = 0..150</a>
%F A171158 a(n) ~ c * d^n / n, where d = 17.073685937995..., c = 0.171212682922... . - _Vaclav Kotesovec_, Sep 10 2014
%e A171158 For n = 2, the 19 walks are:
%e A171158 000 -> 001 -> 012 -> 122 -> 222
%e A171158 000 -> 001 -> 102 -> 212 -> 222
%e A171158 000 -> 001 -> 112 -> 222
%e A171158 000 -> 010 -> 021 -> 122 -> 222
%e A171158 000 -> 010 -> 120 -> 221 -> 222
%e A171158 000 -> 010 -> 121 -> 222
%e A171158 000 -> 011 -> 112 -> 222
%e A171158 000 -> 011 -> 121 -> 222
%e A171158 000 -> 011 -> 122 -> 222
%e A171158 000 -> 100 -> 201 -> 212 -> 222
%e A171158 000 -> 100 -> 210 -> 221 -> 222
%e A171158 000 -> 100 -> 211 -> 222
%e A171158 000 -> 101 -> 112 -> 222
%e A171158 000 -> 101 -> 211 -> 222
%e A171158 000 -> 101 -> 212 -> 222
%e A171158 000 -> 110 -> 121 -> 222
%e A171158 000 -> 110 -> 211 -> 222
%e A171158 000 -> 110 -> 221 -> 222
%e A171158 000 -> 111 -> 222
%Y A171158 See A171155 for the number of such walks in two dimensions.
%Y A171158 See A171563 for the number of such walks in four dimensions. - _Lee A. Newberg_, Dec 11 2009
%K A171158 nonn,walk
%O A171158 0,3
%A A171158 _Lee A. Newberg_, Dec 04 2009
%E A171158 Extended beyond a(10) by _Alois P. Heinz_, Jan 22 2013