login
Number of n X 2 arrays containing 2 copies of 0..n-1 with no equal horizontal or vertical neighbors and new values introduced sequentially from 0.
3

%I #17 Mar 18 2020 11:08:31

%S 0,1,2,21,186,2113,27856,422481,7241480,138478561,2923183474,

%T 67520866405,1694065383154,45878853274945,1333966056696224,

%U 41446945223914337,1370476678395567376,48051281596087884289

%N Number of n X 2 arrays containing 2 copies of 0..n-1 with no equal horizontal or vertical neighbors and new values introduced sequentially from 0.

%C Column 2 of A265170.

%C a(n) is also the number of configurations of n indistinguishable pairs placed on the vertices of the ladder graph P_2 X P_n such that no such pair is joined by an edge; equivalently this is the number of "0-domino" configurations in the game of memory played on a 2 X n rectangular array, see [Young]. - _Donovan Young_, Oct 22 2018

%H D. Young, <a href="http://cs.uwaterloo.ca/journals/JIS/VOL21/Young/young2.pdf">The Number of Domino Matchings in the Game of Memory</a>, Journal of Integer Sequences, Vol. 21 (2018), Article 18.8.1.

%H Donovan Young, <a href="https://arxiv.org/abs/1905.13165">Generating Functions for Domino Matchings in the 2 * k Game of Memory</a>, arXiv:1905.13165 [math.CO], 2019. Also in <a href="https://www.emis.de/journals/JIS/VOL22/Young/young13.html">J. Int. Seq.</a>, Vol. 22 (2019), Article 19.8.7.

%F a(n) = Sum_{k=0..n} (-1)^k*(2*n-2*k-1)!! * A046741(n,k) where and 0!! = (-1)!! = 1; proved by inclusion-exclusion, see [Young].

%e Some solutions for n=4

%e ..0..1....0..1....0..1....0..1....0..1....0..1....0..1....0..1....0..1....0..1

%e ..2..3....2..3....2..3....2..0....2..3....2..3....2..3....2..3....2..3....2..3

%e ..0..1....3..2....0..2....1..3....0..1....3..0....3..1....1..2....3..2....0..2

%e ..2..3....1..0....3..1....3..2....3..2....2..1....0..2....0..3....0..1....1..3

%Y Cf. A265170, A046741.

%K nonn

%O 1,3

%A _R. H. Hardin_, Dec 03 2015