|
%I #2 Mar 30 2012 17:36:00
%S 1,1,3,1,1,8,16,8,1,1,13,54,87,54,13,1,1,18,117,348,501,348,117,18,1,
%T 1,23,205,914,2210,2966,2210,914,205,23,1,1,28,318,1910,6658,13980,
%U 17895,13980,6658,1910,318,28,1,1,33,456,3461,15945,46648,88425,109391,88425,46648,15945,3461,456,33,1
%N Triangle read by rows: T(n,k) is the number of k-matchings of the corona L'(n) of the ladder graph L(n)=P_2 X P_n. and the complete graph K(1); in other words, L'(n) is the graph constructed from L(n) by adding for each vertex v a new vertex v' and the edge vv'.
%C Row n contains 2n+1 terms. Row sums yield A102436 T(n,k)=T(n,2n-k). The number of k-matchings of the ladder graph L(n)=P_2 X P_n is given in A046741.
%F P[0]=1, P[1]=1+3t+t^2, P[2]=1+8t+16t^2+8t^3+t^4, P[n]=(1+4t+t^2)P[n-1]+t(1+t)^2*P[n-2]-t^3*P[n-3] for n>=3. G.f.= (1-tz)/[1-(1+4t+t^2)z-t(t+1)^2*z^2+t^3*z^3].
%e T(2,2)=16 because in the graph L'(2) with vertex set {A,B,C,D,a,b,c,d} and edge set {AB,BC,CD,AD,Aa,Bb,Cc,Dd} we have sixteen 2-matchings. Indeed, each of the edges Aa,Bb,Cc,Dd can be matched with five edges and each of the edges AB,BC,CD,AD can be matched with three edges. Thus we have (4*5+4*3)/2=16 matchings.
%e Triangle begins:
%e 1;
%e 1,3,1;
%e 1,8,16,8,1;
%e 1,13,54,87,54,13,1;
%p P[0]:=1: P[1]:=1+3*t+t^2: P[2]:=1+8*t+16*t^2+8*t^3+t^4: for n from 3 to 8 do P[n]:=sort(expand((1+4*t+t^2)*P[n-1]+t*(1+t)^2*P[n-2]-t^3*P[n-3])) od: for n from 0 to 8 do seq(coeff(t*P[n],t^k),k=1..2*n+1) od; # yields sequence in triangular form
%Y Cf. A102436, A046741.
%K nonn,tabf
%O 0,3
%A _Emeric Deutsch_, Jan 08 2005
|
