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,4

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

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

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 *)

Prog

(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

Crossrefs

Cf. A001266, A006184, A242522.

Sequence in context: A026993 A238115 A228959 * A319228 A216441 A108188

Adjacent sequences: A302731 A302732 A302733 * A302735 A302736 A302737

Keyword

nonn

Author

Eric W. Weisstein, Apr 12 2018

Extensions

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

Status

approved