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

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

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

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]

Prog

(PARI) a(n) = if(n==1, 1, 2*(n + (2^(n-1) - 1)^2)) \\ Andrew Howroyd, Dec 18 2024

Crossrefs

Cf. A377649.

Sequence in context: A344274 A372225 A122740 * A034432 A026962 A026972

Adjacent sequences: A379212 A379213 A379214 * A379216 A379217 A379218

Keyword

nonn,easy

Author

Eric W. Weisstein, Dec 18 2024

Extensions

a(6) onwards from Andrew Howroyd, Dec 18 2024

Status

approved