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

Author

Eric W. Weisstein, Dec 18 2024

Keywords

• nonn
• easy

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