A102080 -id:A102080 - cp's OEIS frontend

A287428 Array read by antidiagonals: T(m,n) is the number of matchings in the stacked prism graph C_m X P_n.

1, 2, 3, 3, 12, 4, 5, 47, 32, 7, 8, 185, 228, 108, 11, 13, 728, 1655, 1511, 342, 18, 21, 2865, 11978, 21497, 9213, 1104, 29, 34, 11275, 86731, 305184, 253880, 57536, 3544, 47, 55, 44372, 627960, 4334009, 6974078, 3079253, 356863, 11396, 76

Offset: 1

Andrew Howroyd, May 25 2017

Row 1 is the number of matchings in P_n and row 2 is the number of matchings in G X P_n where G is a double edge. These choices give the best fit with the column linear recurrences.

			Table starts:
======================================================================
m\n|  1    2      3        4          5            6              7
---|------------------------------------------------------------------
1  |  1    2      3        5          8           13             21 ...
2  |  3   12     47      185        728         2865          11275 ...
3  |  4   32    228     1655      11978        86731         627960 ...
4  |  7  108   1511    21497     305184      4334009       61545775 ...
5  | 11  342   9213   253880    6974078    191668283     5267252351 ...
6  | 18 1104  57536  3079253  164206124   8761336545   467431319920 ...
7  | 29 3544 356863 37071837 3834744194 396924243197 41080815923665 ...
...

Andrew Howroyd, Table of n, a(n) for n = 1..435
Eric Weisstein's World of Mathematics, Stacked Prism Graph

Rows 2..13 are A088132, A033515, A033516, A033517, A033518, A033519-A033525.
Columns 2..3 are A102080, A102090.
Cf. A028420 (P_m X P_n), A270246 (C_m X C_n), A270227 (K_m X K_n).

A284702 Number of dominating sets in the n-prism graph.

Original entry on oeis.org

3, 11, 51, 183, 663, 2435, 8935, 32775, 120219, 440971, 1617531, 5933271, 21763823, 79831875, 292831311, 1074134535, 3940032883, 14452434635, 53012975555, 194456895863, 713287340551, 2616409296963, 9597250953527, 35203676264199, 129130605057163

Offset: 1

Eric W. Weisstein, Apr 01 2017

Sequence extrapolated to n=1 using recurrence. - Andrew Howroyd, May 10 2017

G. C. Greubel, Table of n, a(n) for n = 1..1000 (terms 1..200 from Andrew Howroyd)
Eric Weisstein's World of Mathematics, Dominating Set
Eric Weisstein's World of Mathematics, Prism Graph
Index entries for linear recurrences with constant coefficients, signature (3,1,5,1,1,-1,-1).

Cf. A051927, A102080, A284699, A218348 (ladder), A284663.

LinearRecurrence[{3, 1, 5, 1, 1, -1, -1}, {3, 11, 51, 183, 663, 2435,
  8935}, 20] (* Eric W. Weisstein, May 17 2017 *)
Rest[CoefficientList[Series[x (-7 x^6 - 6 x^5 + 5 x^4 + 4 x^3 + 15 x^2 + 2 x + 3)/((x^2 + 1) (x^5 + x^4 - 2 x^3 - 2 x^2 - 3 x + 1)), {x, 0, 20}], x]] (* G. C. Greubel, May 17 2017 *)
Table[2 Cos[n Pi/2] + RootSum[1 + #1 - 2 #1^2 - 2 #1^3 - 3 #1^4 + #1^5 &, #^n &], {n, 20}] (* Eric W. Weisstein, May 26 2017 *)

Vec((-7*x^6-6*x^5+5*x^4+4*x^3+15*x^2+2*x+3)/((x^2+1)*(x^5+x^4-2*x^3-2*x^2-3*x+1))+O(x^15)) \\ Andrew Howroyd, May 10 2017

From Andrew Howroyd, May 10 2017: (Start)
a(n) = 3*a(n-1) + a(n-2) + 5*a(n-3) + a(n-4) + a(n-5) - a(n-6) - a(n-7).
G.f.: x*(-7*x^6 - 6*x^5 + 5*x^4 + 4*x^3 + 15*x^2 + 2*x + 3)/((x^2 + 1)*(x^5 + x^4 - 2*x^3 - 2*x^2 - 3*x + 1)). (End)

a(1)-a(2) and a(16)-a(25) from Andrew Howroyd, May 10 2017

A284703 Number of maximal matchings in the n-prism graph.

Original entry on oeis.org

1, 5, 10, 17, 51, 98, 211, 457, 964, 2095, 4489, 9638, 20723, 44469, 95550, 205225, 440777, 946808, 2033571, 4367947, 9381928, 20151345, 43283195, 92967814, 199685501, 428904403, 921243124, 1978737477, 4250128177, 9128846128, 19607840133, 42115660425

Offset: 1

Eric W. Weisstein, Apr 01 2017

nonn

Sequence extrapolated to n=1 using recurrence. - Andrew Howroyd, May 16 2017

Andrew Howroyd, Table of n, a(n) for n = 1..200
Eric Weisstein's World of Mathematics, Matching
Eric Weisstein's World of Mathematics, Maximal Independent Edge Set
Eric Weisstein's World of Mathematics, Prism Graph
Index entries for linear recurrences with constant coefficients, signature (1,2, 1,-1,2,1,-1,-1).

Cf. A284701, A286945, A284710, A102080, A068397, A123304.

I:=[1,5,10,17,51,98,211,457]; [n le 8 select I[n] else Self(n-1)+2*Self(n-2)+Self(n-3)-Self(n-4)+2*Self(n-5)+Self(n-6)-Self(n-7)-Self(n-8): n in [1..40]]; // Vincenzo Librandi, May 17 2017

LinearRecurrence[{1, 2, 1, -1, 2, 1, -1, -1}, {1, 5, 10, 17, 51, 98, 211, 457}, 40] (* Vincenzo Librandi, May 17 2017 *)
CoefficientList[Series[(-8 x^7 - 7 x^6 + 6 x^5 + 10 x^4 - 4 x^3 + 3 x^2 + 4 x + 1) / ((x^2 - x + 1) (x^3 - x - 1) (x^3 + 2 x^2 + x - 1)), {x, 0, 33}], x] (* Vincenzo Librandi, May 17 2017 *)
Table[2 Cos[n Pi/3] + RootSum[-1 - 2 # - #^2 + #^3 &, #^n &] +
  RootSum[-1 + #^2 + #^3 &, #^n &], {n, 20}] (* Eric W. Weisstein, May 17 2017 *)

Vec((-8*x^7-7*x^6+6*x^5+10*x^4-4*x^3+3*x^2+4*x+1)/((x^2-x+1)*(x^3-x-1)*(x^3+2*x^2+x-1))+O(x^20)) \\ Andrew Howroyd, May 16 2017

From Andrew Howroyd, May 16 2017 (Start)
a(n) = a(n-1)+2*a(n-2)+a(n-3)-a(n-4)+2*a(n-5)+a(n-6)-a(n-7)-a(n-8) for n>8.
G.f.: x*(-8*x^7-7*x^6+6*x^5+10*x^4 -4*x^3+3*x^2+4*x+1)/((x^2-x+1)*(x^3-x-1)*(x^3+2*x^2+x-1)).
(End)

a(1)-a(2) and a(20)-a(32) from Andrew Howroyd, May 16 2017

A338153 a(n) is the number of acyclic orientations of the edges of the n-prism.

Original entry on oeis.org

204, 1862, 14700, 109334, 790524, 5633222, 39828300, 280376054, 1968934044, 13807724582, 96754776300, 677686169174, 4745413960764, 33224340503942, 232596153986700, 1628276158432694, 11398345428510684, 79790067272259302, 558537067986067500, 3909785864202510614

Offset: 3

Peter Kagey, Oct 13 2020

nonn

Conjectured linear recurrence and g.f. confirmed by Kagey's formula. - Ray Chandler, Mar 10 2024

			For n = 4, the 4-prism is the 3-dimensional cube, so a(4) = A334247(3) = 1862.

Peter Kagey, Table of n, a(n) for n = 3..1000
Eric Weisstein's World of Mathematics, Prism Graph
Wikipedia, Acyclic orientation
Index entries for linear recurrences with constant coefficients, signature (14, -63, 106, -56).

Cf. A102080, A124349, A284702.

Cf. A033815 (cross-polytope), A058809 (wheel), A334247 (cube), A338152 (n-demihypercube), A338154 (n-antiprism).

A338153[n_] := 5 + 7^n - 2^(n + 1) - 2*4^n (* Peter Kagey, Nov 15 2020 *)

Conjectures from Colin Barker, Oct 13 2020: (Start)
G.f.: 2*x^3*(102 - 497*x + 742*x^2 - 392*x^3) / ((1 - x)*(1 - 2*x)*(1 - 4*x)*(1 - 7*x)).
a(n) = 14*a(n-1) - 63*a(n-2) + 106*a(n-3) - 56*a(n-4) for n>6.
(End)
a(n) = 5 + 7^n - 2^(n+1) - 2*4^n. - Peter Kagey, Nov 15 2020

A270246 Array read by antidiagonals: T(n,m) is the number of matchings in the torus grid graph C_n X C_m.

Original entry on oeis.org

1, 2, 2, 4, 7, 4, 7, 32, 32, 7, 11, 108, 370, 108, 11, 18, 342, 2764, 2764, 342, 18, 29, 1104, 19874, 41025, 19874, 1104, 29, 47, 3544, 144108, 576287, 576287, 144108, 3544, 47, 76, 11396, 1043060, 8205424, 15637256, 8205424, 1043060, 11396, 76

Offset: 1

Andrew Howroyd, Mar 13 2016

			The start of the sequence as table:
*   1    2      4       7        11          18 ...
*   2    7     32     108       342        1104 ...
*   4   32    370    2764     19874      144108 ...
*   7  108   2764   41025    576287     8205424 ...
*  11  342  19874  576287  15637256   430996378 ...
*  18 1104 144108 8205424 430996378 23079663560 ...
* ...

Andrew Howroyd, Table of n, a(n) for n = 1..284
Eric Weisstein's World of Mathematics, Independent Edge Set
Eric Weisstein's World of Mathematics, Matching
Eric Weisstein's World of Mathematics, Torus Grid Graph

Main diagonal is A270247. Row 2 is A102080.

T(1, m) = A000032(m) for m<>2.

A102079 Triangle read by rows: T(n,k) is the number of k-matchings in the C_n X P_2 graph (C_n is the cycle graph on n vertices and P_2 is the path graph on 2 vertices).

Original entry on oeis.org

1, 6, 5, 1, 9, 18, 4, 1, 12, 42, 44, 9, 1, 15, 75, 145, 95, 11, 1, 18, 117, 336, 420, 192, 20, 1, 21, 168, 644, 1225, 1085, 371, 29, 1, 24, 228, 1096, 2834, 3880, 2588, 696, 49, 1, 27, 297, 1719, 5652, 10656, 11097, 5823, 1278, 76, 1, 30, 375, 2540, 10165, 24626, 35645, 29380, 12535, 2310, 125

Offset: 2

Emeric Deutsch, Dec 29 2004

Row n contains n+1 terms.

Equivalently, the n-th row gives the coefficients of the matching-generating polynomial of the n-prism graph. - Eric W. Weisstein, Apr 03 2018

			T(3,3)=4 because in the graph C_3 X P_2 with vertex set {A,B,C,A',B',C'} and edge set {AB,AC,BC, A'B',A'C',B'C',AA',BB',CC'} we have the following
3-matchings: {AA',BB',CC'}, {AA',BC,B'C'}, {BB',AC,A'C'} and {CC',AB,A'B'} (as a matter of fact, these are perfect matchings).
Triangle starts:
1, 6, 5;
1, 9, 18, 4;
1, 12, 42, 44, 9;
1, 15, 75, 145, 95, 11;

H. Hosoya and A. Motoyama, An effective algorithm for obtaining polynomials for dimer statistics. Application of operator technique on the topological index to two- and three-dimensional rectangular and torus lattices, J. Math. Physics 26 (1985) 157-167 (eq. (19) and Table IV).
Eric Weisstein's World of Mathematics, Matching-Generating Polynomial
Eric Weisstein's World of Mathematics, Prism Graph

Cf. A102080, A068397.

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

CoefficientList[LinearRecurrence[{1 + x, 2 x (1 + x), -(-1 + x) x^2, -x^4}, {1 + x, 1 + 6 x + 5 x^2, 1 + 9 x + 18 x^2 + 4 x^3, 1 + 12 x + 42 x^2 + 44 x^3 + 9 x^4}, {2, 10}], x] // Flatten (* Eric W. Weisstein, Apr 03 2018 *)
CoefficientList[CoefficientList[Series[-( -1 - 6 x - 5 x^2 - 2 x z - 7 x^2 z + x^3 z - x^2 z^2 + 5 x^4 z^2 + x^4 z^3 + x^5 z^3)/((1 + x z) (1 - z - 2 x z - x z^2 + x^3 z^3)), {z, 0, 10}], z], x] // Flatten (* Eric W. Weisstein, Apr 03 2018 *)

G.f.: -z^2*(5t^4*z^2-1+t^4*z^3+t^5*z^3-6t-5t^2-2tz-7zt^2+zt^3-t^2*z^2)/[(1+tz)(t^3*z^3-tz^2-2tz-z+1)].

The row generating polynomials A[n] satisfy A[n]=(1+t)A[n-1]+2t(1+t)A[n-2]+ t^2*(1-t)A[n-3]-t^4*A[n-4] with A[2]=1+6t+5t^2, A[3]=1+9t+18t^2+4t^3, A[4]=1+12t+42t^2+44t^3+9t^4 and A[5]=1+15t+75t^2+145t^3+95t^4+11t^5.

A270247 Number of matchings in the n X n torus grid graph C_n X C_n.

Original entry on oeis.org

1, 7, 370, 41025, 15637256, 23079663560, 127193770624285, 2645142169931308801, 206932904585998805434690, 60953421285412135689567940992, 67583556205239600880061198746186383, 282092296203355454009618109524478429807744

Offset: 1

Andrew Howroyd, Mar 13 2016

nonn

C_{n} X C_{n} is also known as the (n,n)-torus grid graph.

Eric Weisstein's World of Mathematics, Matching.
Eric Weisstein's World of Mathematics, Torus Grid Graph.

Cf. A270246, A102080, A028420, A270228, A027683, A228316, A222199.

cp's OEIS Frontend

A287428 Array read by antidiagonals: T(m,n) is the number of matchings in the stacked prism graph C_m X P_n.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

A284702 Number of dominating sets in the n-prism graph.

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Mathematica

PARI

Formula

Extensions

A284703 Number of maximal matchings in the n-prism graph.

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Magma

Mathematica

PARI

Formula

Extensions

A338153 a(n) is the number of acyclic orientations of the edges of the n-prism.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

Formula

A270246 Array read by antidiagonals: T(n,m) is the number of matchings in the torus grid graph C_n X C_m.

Views

Author

Keywords

Examples

Links

Crossrefs

Formula

A102079 Triangle read by rows: T(n,k) is the number of k-matchings in the C_n X P_2 graph (C_n is the cycle graph on n vertices and P_2 is the path graph on 2 vertices).

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Maple

Mathematica

Formula

A270247 Number of matchings in the n X n torus grid graph C_n X C_n.

Views

Author

Keywords

Comments

Links

Crossrefs