login
Number of edge-disjoint paths between opposite corners of a 2 X n grid.
6

%I #21 Sep 08 2022 08:44:39

%S 1,1,4,16,72,335,1562,7273,33850,157534,733148,3412005,15879172,

%T 73900265,343925312,1600598044,7449042040,34667184251,161338016046,

%U 750852888177,3494403076902,16262643529850,75684907767980,352230881365025,1639251436594792,7628931517771089

%N Number of edge-disjoint paths between opposite corners of a 2 X n grid.

%D rec.puzzles Dec 10 1995.

%H Matthew House, <a href="/A013991/b013991.txt">Table of n, a(n) for n = 0..1491</a>

%H <a href="/index/Rec#order_06">Index entries for linear recurrences with constant coefficients</a>, signature (6,-6,-4,16,-16,7).

%F G.f.: (-7*x^6+15*x^5-12*x^4+2*x^3+4*x^2-5*x+1)/[(1-x+x^2)*(1-5*x+9*x^3-7*x^4)].

%t Join[{1}, LinearRecurrence[{6, -6, -4, 16, -16, 7}, {1, 4, 16, 72, 335, 1562}, 25]] (* _Vincenzo Librandi_, Sep 18 2018 *)

%o (PARI) Vec((-7*x^6+15*x^5-12*x^4+2*x^3+4*x^2-5*x+1)/((1-x+x^2)*(1-5*x+9*x^3-7*x^4)) + O(x^30)) \\ _Michel Marcus_, Sep 18 2018

%o (Magma) I:=[1,1,4,16,72,335,1562]; [n le 7 select I[n] else 6*Self(n-1) - 6*Self(n-2) - 4*Self(n-3) + 16*Self(n-4) - 16*Self(n-5) + 7*Self(n-6): n in [1..30]]; // _Vincenzo Librandi_, Sep 18 2018

%Y Cf. A013990, A013992, A013993, A013994, A013995, A013996, A013997.

%K nonn,easy

%O 0,3

%A _Dan Hoey_

%E More terms from _Matthew House_, Dec 24 2016