A102435 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'.
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, 1, 23, 205, 914, 2210, 2966, 2210, 914, 205, 23, 1, 1, 28, 318, 1910, 6658, 13980, 17895, 13980, 6658, 1910, 318, 28, 1, 1, 33, 456, 3461, 15945, 46648, 88425, 109391, 88425, 46648, 15945, 3461, 456, 33, 1
Offset: 0
Examples
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.
Triangle begins:
1;
1,3,1;
1,8,16,8,1;
1,13,54,87,54,13,1;
Programs
-
Maple
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
Formula
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].
Comments