A270227 -id:A270227 - 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).

A270228 Number of matchings in the n X n rook graph K_n X K_n.

Original entry on oeis.org

1, 7, 370, 270529, 3337807996, 855404716021831, 5352265402523357926168, 940288991338542314571521981185, 5236753179470435264288904589157765055760, 1029720447530443779943631183186535523331685533812231

Offset: 1

Andrew Howroyd, Mar 13 2016

nonn

K_n X K_n is also called the rook graph or lattice graph.

Andrew Howroyd, Table of n, a(n) for n = 1..16
Andrew Howroyd, C# software related to this sequence
Eric Weisstein's World of Mathematics, Independent Edge Set
Eric Weisstein's World of Mathematics, Matching
Eric Weisstein's World of Mathematics, Rook Graph
Wikipedia, Rook's graph, Hosoya index

Cf. A270227, A270229, A085537 (Wiener index), A002720 (independent vertex sets), A269561, A028420.

A341847 Array read by antidiagonals: T(n,m) is the number of maximal matchings in the rook graph K_n X K_m.

Original entry on oeis.org

1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 3, 2, 3, 1, 1, 3, 10, 10, 3, 1, 1, 15, 40, 84, 40, 15, 1, 1, 15, 296, 852, 852, 296, 15, 1, 1, 105, 1576, 11580, 22368, 11580, 1576, 105, 1, 1, 105, 15352, 197640, 822528, 822528, 197640, 15352, 105, 1, 1, 945, 104000, 4314240, 38772864, 84961440, 38772864, 4314240, 104000, 945, 1

Offset: 0

Andrew Howroyd, Feb 21 2021

			Array begins:
=============================================================
n\m | 0  1    2      3        4           5             6
----+--------------------------------------------------------
  0 | 1  1    1      1        1           1             1 ...
  1 | 1  1    1      3        3          15            15 ...
  2 | 1  1    2     10       40         296          1576 ...
  3 | 1  3   10     84      852       11580        197640 ...
  4 | 1  3   40    852    22368      822528      38772864 ...
  5 | 1 15  296  11580   822528    84961440   12002446080 ...
  6 | 1 15 1576 197640 38772864 12002446080 5429866337280 ...
  ...

Andrew Howroyd, Table of n, a(n) for n = 0..275
Eric Weisstein's World of Mathematics, Maximal Independent Edge Set
Eric Weisstein's World of Mathematics, Rook Graph

Rows n=1..4 are A133221(n+1), A281433, A341848, A341849.
Main diagonal is A289198.
Cf. A270227 (matchings), A297471, A341850 (maximum matchings).

T(n,m) = T(m,n).

A341850 Array read by antidiagonals: T(n,m) is the number of maximum matchings in the rook graph K_n X K_m.

Original entry on oeis.org

1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 3, 2, 3, 1, 1, 3, 4, 4, 3, 1, 1, 15, 16, 72, 16, 15, 1, 1, 15, 56, 132, 132, 56, 15, 1, 1, 105, 376, 7020, 2016, 7020, 376, 105, 1, 1, 105, 1912, 17280, 44928, 44928, 17280, 1912, 105, 1, 1, 945, 17984, 1920240, 1551744, 22615200, 1551744, 1920240, 17984, 945, 1

Offset: 0

Andrew Howroyd, Feb 21 2021

In the case that both m and n are odd a single vertex is not covered, otherwise the maximum matchings are perfect matchings.

			Array begins:
======================================================
n\m | 0  1   2     3       4         5           6
----+-------------------------------------------------
  0 | 1  1   1     1       1         1           1 ...
  1 | 1  1   1     3       3        15          15 ...
  2 | 1  1   2     4      16        56         376 ...
  3 | 1  3   4    72     132      7020       17280 ...
  4 | 1  3  16   132    2016     44928     1551744 ...
  5 | 1 15  56  7020   44928  22615200   243319680 ...
  6 | 1 15 376 17280 1551744 243319680 61903180800 ...
  ...

Andrew Howroyd, Table of n, a(n) for n = 0..527
Eric Weisstein's World of Mathematics, Maximum Independent Edge Set
Eric Weisstein's World of Mathematics, Rook Graph

Rows n=1..4 are A133221(n+1), A081919, A341851, A341852.
Main diagonal is A289197.
Cf. A270227 (matchings), A286070, A341847 (maximal matchings).

T(n,m) = T(m,n).

A270229 Number of matchings in the 2 X n rook graph P_2 X K_n.

Original entry on oeis.org

1, 2, 7, 32, 193, 1382, 11719, 112604, 1221889, 14639786, 192949639, 2760749048, 42732172993, 709490574158, 12596398359367, 237750425419508, 4757710386662401, 100516614496518866, 2236829315345704711, 52262526676903613264, 1279512810244450887361

Offset: 0

Andrew Howroyd, Mar 13 2016

nonn

Sequence extended to n=0 using closed form. (binomial transform of A111883)

Andrew Howroyd, Table of n, a(n) for n = 0..50

Cf. A270227, A270228, A000085, A081919 (perfect matchings).

a[n_] := Sum[Binomial[n, k]*Abs[HermiteH[k, I/Sqrt[2]]]^2/2^k, {k, 0, n}];
Table[a[n], {n, 0, 20}] (* Jean-François Alcover, Oct 01 2017 *)
CoefficientList[Series[E^((2-x)*x/(1-x)) / Sqrt[1-x^2], {x, 0, 20}], x] * Range[0, 20]! (* Vaclav Kotesovec, Oct 01 2017 *)

Binomial transform of A111883.
From Vaclav Kotesovec, Oct 01 2017: (Start)
a(n) = (n+1)*a(n-1) + (n-1)^2*a(n-2) - (n-2)*(n-1)^2*a(n-3) + (n-3)*(n-2)*(n-1)*a(n-4).
E.g.f.: exp((2-x)*x/(1-x)) / sqrt(1-x^2).
a(n) ~ exp(1/2 + 2*sqrt(n) - n) * n^n / 2.
(End)

A341502 Number of matchings in the 3 X n rook graph.

Original entry on oeis.org

1, 4, 32, 370, 5950, 122984, 3175696, 98815588, 3638940860, 155377163440, 7598445388096, 420034502219864, 26014375783223272, 1788772035008337760, 135644687161742899520, 11268192704027639350384, 1020100484786824631520016, 100126060947226759050509888

Offset: 0

Andrew Howroyd, Feb 21 2021

nonn

Andrew Howroyd, Table of n, a(n) for n = 0..100

Row 3 of A270227.

Cf. A000085, A341848, A341851.

\\ here b(n) is A000085.
b(n)={sum(k=0, n\2, n!/((n-2*k)!*2^k*k!))}
a(n)={my(v=vector(n+1, i, b(i-1))); sum(i=0,n, sum(j=0, n-i, sum(k=0, n-i-j, n!/(i!*j!*k!*(n-i-j-k)!)*v[1+n-i-j]*v[1+n-i-k]*v[1+n-j-k] )))}

a(n) = Sum{i,j,k>=0, i+j+k<=n} n!/(i!*j!*k!*(n-i-j-k)!) * A000085(n-i-j) * A000085(n-i-k) * A000085(n-j-k).

A341503 Number of matchings in the 4 X n rook graph.

Original entry on oeis.org

1, 10, 193, 5950, 270529, 16873930, 1384880065, 144218696590, 18583827550465, 2898418007316970, 538034003700151105, 117117180185558050750, 29538673951318735414465, 8540274169019607609510250, 2805241403079208727201012545, 1038436904586470317663800172750

Offset: 0

Andrew Howroyd, Feb 21 2021

nonn

			The a(1) = 10 matchings consist of the empty matching, 6 matchings with a single edge and 3 perfect matchings.

Andrew Howroyd, Table of n, a(n) for n = 0..50

Row 4 of A270227.

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

A270228 Number of matchings in the n X n rook graph K_n X K_n.

Views

Author

Keywords

Comments

Links

Crossrefs

A341847 Array read by antidiagonals: T(n,m) is the number of maximal matchings in the rook graph K_n X K_m.

Views

Author

Keywords

Examples

Links

Crossrefs

Formula

A341850 Array read by antidiagonals: T(n,m) is the number of maximum matchings in the rook graph K_n X K_m.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Formula

A270229 Number of matchings in the 2 X n rook graph P_2 X K_n.

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Mathematica

Formula

A341502 Number of matchings in the 3 X n rook graph.

Views

Author

Keywords

Links

Crossrefs

Programs

PARI

Formula

A341503 Number of matchings in the 4 X n rook graph.

Views

Author

Keywords

Examples

Links

Crossrefs