A302734 Number of paths in the n-path complement graph.

0, 0, 1, 6, 32, 186, 1245, 9588, 83752, 817980, 8827745, 104277450, 1337781336, 18518728326, 275087536717, 4364152920456, 73637731186160, 1316713607842968, 24869730218182497, 494752411594456110, 10339913354716379440, 226485946787802241650, 5188447062121251600221

Offset: 1

Author

Eric W. Weisstein, Apr 12 2018

Keywords

• nonn

Links

• Andrew Howroyd, Table of n, a(n) for n = 1..200
• Eric Weisstein's World of Mathematics, Graph Path
• Eric Weisstein's World of Mathematics, Path Complement Graph

Crossrefs

Cf. A001266, A006184, A242522.

Programs

Mathematica

Array[(1/2) Sum[Sum[Sum[(-1)^(k - i) i!*2^j*Binomial[# + i - k, i] Binomial[i, j] Binomial[k - i - 1, k - i - j], {j, 0, k - i}], {i, k}], {k, 2, #}] &, 23] (* Michael De Vlieger, Apr 21 2018 *)
Table[Sum[(-1)^(k - i) i! 2^j Binomial[n + i - k, i] Binomial[i, j] Binomial[k - i - 1, k - i - j], {k, 2, n}, {i, k}, {j, 0, k - i}]/2, {n, 20}] (* Eric W. Weisstein, Apr 23 2018 *)

PARI

a(n)={sum(k=2, n, sum(i=1, k, sum(j=0, min(i, k-i), (-1)^(k-i)*i!*2^j*binomial(n+i-k, i)*binomial(i, j)*binomial(k-i-1, k-i-j))))/2} \\ Andrew Howroyd, Apr 21 2018

Formula

a(n) = (1/2)*Sum_{k=2..n} Sum_{i=1..k} Sum_{j=0..k-i} (-1)^(k-i)*i!*2^j*binomial(n+i-k, i)*binomial(i, j)*binomial(k-i-1, k-i-j). - Andrew Howroyd, Apr 21 2018

a(n) ~ n! / (2*exp(1)). - Vaclav Kotesovec, Apr 22 2018

Extensions

Terms a(15) and beyond from Andrew Howroyd, Apr 21 2018