A192856 Number of matchings in the n-sun graph.

1, 3, 8, 27, 100, 393, 1624, 7017, 31558, 147177, 709592, 3527769, 18045428, 94797147, 510594056, 2815698483, 15877236898, 91442860467, 537363872008, 3219075448251, 19641501806932, 121974079707225, 770381455577048, 4945495555291017, 32249369951426822

Offset: 0

Author

Eric W. Weisstein, Jul 11 2011

Keywords

• nonn

Comments

Extended to a(0)-a(2) using the sum/recurrence. - Eric W. Weisstein, Oct 03 2017

Links

• Andrew Howroyd and Vaclav Kotesovec, Table of n, a(n) for n = 0..780 (terms 3..50 from Andrew Howroyd; terms a(0..2) corrected by _Georg Fischer_, Jan 20 2019)
• Eric Weisstein's World of Mathematics, Independent Edge Set
• Eric Weisstein's World of Mathematics, Matching
• Eric Weisstein's World of Mathematics, Sun Graph

Crossrefs

Cf. A000085.

Programs

Mathematica

Table[Sum[(2 j - 1)!! Binomial[n, 2 j], {j, 0, n/2}] + 2 Sum[n Binomial[2 n - k - 1, k - 1] Sum[(2 j - 1)!! Binomial[n - k, 2 j], {j, 0, (n - k)/2}]/k, {k, n}], {n, 0, 20}] (* Vaclav Kotesovec, Mar 06 2016 *)
Join[{1}, RecurrenceTable[{(n - 3) a[n] == 3 (n - 3) a[n - 1] + (n^2 - 4 n
+ 5) a[n - 2] - 3 (n - 1) a[n - 3] + (n - 1) a[n - 4], a[1]==3, a[2]==8, a[3]==27, a[4] == 100}, a, {n, 1, 20}]] (* Eric W. Weisstein, Oct 03 2017, amended by Georg Fischer, Dec 05 2019 *)

Formula

a(n) = A000085(n) + 2*(Sum_{ k=1..n } n * binomial(2*n-k-1, k-1) * A000085(n-k) / k). - Andrew Howroyd, Feb 28 2016, corrected by Vaclav Kotesovec, Mar 06 2016

Recurrence (for n>=7): (n-3)*a(n) = 3*(n-3)*a(n-1) + (n^2 - 4*n + 5)*a(n-2) - 3*(n-1)*a(n-3) + (n-1)*a(n-4). - Vaclav Kotesovec, Mar 06 2016

a(n) ~ exp(3*sqrt(n) - n/2 - 13/4) * n^(n/2) / sqrt(2) * (1 + 39/(8*sqrt(n))). - Vaclav Kotesovec, Mar 06 2016

Extensions

a(7)-a(20) from Andrew Howroyd, Feb 28 2016

a(0)-a(2) from Eric W. Weisstein, Oct 03 2017