

A102413


Triangle read by rows: T(n,k) is the number of kmatchings of the corona C'(n) of the cycle graph C(n) and the complete graph K(1); in other words, C'(n) is the graph constructed from C(n) to which for each vertex v a new vertex v' and the edge vv' is added.


7



1, 1, 1, 1, 4, 1, 1, 6, 6, 1, 1, 8, 16, 8, 1, 1, 10, 30, 30, 10, 1, 1, 12, 48, 76, 48, 12, 1, 1, 14, 70, 154, 154, 70, 14, 1, 1, 16, 96, 272, 384, 272, 96, 16, 1, 1, 18, 126, 438, 810, 810, 438, 126, 18, 1, 1, 20, 160, 660, 1520, 2004, 1520, 660, 160, 20, 1, 1, 22, 198, 946, 2618, 4334, 4334, 2618, 946, 198, 22, 1
(list;
table;
graph;
refs;
listen;
history;
text;
internal format)



OFFSET

0,5


COMMENTS

Row n contains n+1 terms. Row sums yield A099425. T(n,k) = T(n,nk).
For n > 2: same recurrence like A008288 and A128966.  Reinhard Zumkeller, Apr 15 2014


REFERENCES

J. L. Gross and J. Yellen, Handbook of Graph Theory, CRC Press, Boca Raton, 2004, p. 894.
F. Harary, Graph Theory, AddisonWesley, Reading, Mass., 1969, p. 167.


LINKS

Reinhard Zumkeller, Rows n = 0..125 of table, flattened


FORMULA

G.f.: G(t,z) = (1 + t*z^2) / (1  (1+t)*z  t*z^2).
For n > 2: T(n,k) = T(n1,k1) + T(n1,k) + T(n2,k1), 0 < k < n.  Reinhard Zumkeller, Apr 15 2014 (corrected by Andrew Woods, Dec 08 2014)
From Peter Bala, Jun 25 2015: (Start)
The nth row polynomial R(n,t) = [z^n] G(z,t)^n, where G(z,t) = 1/2*( 1 + (1 + t)*z + sqrt(1 + 2*(1 + t)*z + (1 + 6*t + t^2)*z^2) ).
exp( Sum_{n >= 1} R(n,t)*z^n/n ) = 1 + (1 + t)*z + (1 + 3*t + t^2)*z^2 + (1 + 5*t + 5*t^2 + t^3)*z^3 + ... is the o.g.f for A008288 read as a triangular array. (End)


EXAMPLE

T(3,2)=6 because in the graph with vertex set {A,B,C,a,b,c} and edge set {AB,AC,BC,Aa,Bb,Cc} we have the following six 2matchings: {Aa,BC},{Bb,AC},{Cc,AB},{Aa,Bb},{Aa,Cc} and {Bb,Cc}.
The triangle starts:
1;
1,1;
1,4,1;
1,6,6,1;
1,8,16,8,1;


MAPLE

G:=(1+t*z^2)/(1(1+t)*zt*z^2): Gser:=simplify(series(G, z=0, 38)): P[0]:=1: for n from 1 to 11 do P[n]:=coeff(Gser, z^n) od:for n from 0 to 11 do seq(coeff(t*P[n], t^k), k=1..n+1) od; # yields sequence in triangular form


PROG

(Haskell)
a102413 n k = a102413_tabl !! n !! k
a102413_row n = a102413_tabl !! n
a102413_tabl = [1] : [1, 1] : f [2] [1, 1] where
f us vs = ws : f vs ws where
ws = zipWith3 (((+) .) . (+))
([0] ++ us ++ [0]) ([0] ++ vs) (vs ++ [0])
 Reinhard Zumkeller, Apr 15 2014


CROSSREFS

Cf. A099425, A008288.
Cf. A241023 (central terms).
Sequence in context: A132046 A141540 A143188 * A144480 A144463 A174376
Adjacent sequences: A102410 A102411 A102412 * A102414 A102415 A102416


KEYWORD

nonn,tabl,easy


AUTHOR

Emeric Deutsch, Jan 07 2005


STATUS

approved



