A379215 Number of minimal edge cuts in the complete bipartite graph K_{n,n}.
1, 6, 24, 106, 460, 1934, 7952, 32274, 130068, 522262, 2093080, 8380442, 33538076, 134184990, 536805408, 2147352610, 8589672484, 34359214118, 137437904936, 549753716778, 2199019061292, 8796084633646, 35184355311664, 140737454800946, 562949886312500, 2251799679467574
Offset: 1
Links
- Andrew Howroyd, Table of n, a(n) for n = 1..500
- Eric Weisstein's World of Mathematics, Complete Bipartite Graph.
- Eric Weisstein's World of Mathematics, Minimal Edge Cut.
- Index entries for linear recurrences with constant coefficients, signature (8,-21,22,-8).
Crossrefs
Cf. A377649.
Programs
-
Mathematica
Table[Piecewise[{{1, n == 1}}, 2 ((2^(n - 1) - 1)^2 + n)], {n, 20}] {1} ~ Join ~ LinearRecurrence[{8, -21, 22, -8}, {6, 24, 106, 460}, 20] CoefficientList[Series[(1 - 2 x - 3 x^2 + 18 x^3 - 8 x^4)/((-1 + x)^2 (1 - 6 x + 8 x^2)), {x, 0, 20}], x] -
PARI
a(n) = if(n==1, 1, 2*(n + (2^(n-1) - 1)^2)) \\ Andrew Howroyd, Dec 18 2024
Formula
a(n) = 2*(n + (2^(n-1) - 1)^2) for n > 1. - Andrew Howroyd, Dec 18 2024
G.f.: x*(1-2*x-3*x^2+18*x^3-8*x^4)/((-1+x)^2*(1-6*x+8*x^2)). - Eric W. Weisstein, Dec 18 2024
Extensions
a(6) onwards from Andrew Howroyd, Dec 18 2024