|
| |
|
|
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, 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
(list;
graph;
refs;
listen;
history;
text;
internal format)
|
|
|
|
OFFSET
|
0,3
|
|
|
COMMENTS
|
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.
|
|
|
LINKS
|
|
|
|
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].
|
|
|
EXAMPLE
|
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;
|
|
|
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
|
|
|
CROSSREFS
|
|
|
|
KEYWORD
|
nonn,tabf
|
|
|
AUTHOR
|
|
|
|
STATUS
|
approved
|
| |
|
|
