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,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

Table of n, a(n) for n=0..63.

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

Cf. A102436, A046741.

Sequence in context: A359575 A034801 A331890 * A340882 A152570 A100537

Adjacent sequences: A102432 A102433 A102434 * A102436 A102437 A102438

Keyword

nonn,tabf

Author

Emeric Deutsch, Jan 08 2005

Status

approved