A290324 Number of (undirected) paths in the complete tripartite graph K_{n,n,n}.

6, 396, 67554, 28336848, 23986682550, 35931274250076, 87017657752978386, 318992998488391738944, 1683675635040443830593798, 12301777316059025283613106700, 120545445185882926234784081616546, 1543421856441404929844846263740167376

Offset: 1

Author

Eric W. Weisstein, Jul 27 2017

Keywords

• nonn

Links

• Andrew Howroyd, Table of n, a(n) for n = 1..50
• Andrew Howroyd, Formula for the number of paths
• Eric Weisstein's World of Mathematics, Complete Tripartite Graph
• Eric Weisstein's World of Mathematics, Graph Path

Crossrefs

Cf. A234616, A234633.

Programs

Mathematica

c[n_, k_, i_, j_, p_]:=Binomial[n, k] Binomial[n, i + p] Binomial[n, j + p] Binomial[k, i] Binomial[k - i, j] k!*(i + p)!*(j + p)!*2^(k - i - j)*Binomial[p + i + j - 1, k - 1](1 + n - k); a[n_]:=3*Sum[Sum[Sum[Sum[c[n, k, i, j, p], {p, k - i - j, n}], {j, 0, k - i}], {i, 0, k}], {k, n}]/2; Table[a[n], {n, 12}] (* Indranil Ghosh, Aug 14 2017, after PARI *)

PARI

c(n, k, i, j, p) = {binomial(n, k)*binomial(n, i+p)*binomial(n, j+p)*binomial(k, i)
* binomial(k-i, j)*k!*(i+p)!*(j+p)!*2^(k-i-j)*binomial(p+i+j-1, k-1)*(1+n-k)}
a(n)={3*(sum(k=1, n, sum(i=0, k, sum(j=0, k-i, sum(p=k-i-j, n, c(n, k, i, j, p) )))))/2} \\ Andrew Howroyd, Aug 13 2017

Python

from sympy import binomial, factorial
def c(n, k, i, j, p): return binomial(n, k)*binomial(n, i + p)*binomial(n, j + p)*binomial(k, i)*binomial(k - i, j)*factorial(k)*factorial(i + p)*factorial(j + p)*2**(k - i - j)*binomial(p + i + j - 1, k - 1)*(1 + n - k)
def a(n): return 3*sum([sum([sum([sum([c(n, k, i, j, p) for p in range(k - i - j, n + 1)]) for j in range(k - i + 1)]) for i in range(k + 1)]) for k in range(1, n + 1)])/2
print([a(n) for n in range(1, 13)]) # Indranil Ghosh, Aug 14 2017, after PARI

Extensions

Terms a(5) and beyond from Andrew Howroyd, Aug 13 2017