I am relatively new to general relativity, and I am puzzled about the relationship between two ways of introducing connection coefficients on a differentiable manifold.
One way (e.g. in S. Carroll's "Spacetime & Geometry") defines the connection coefficients, $\Gamma^\nu_{\mu\lambda}$, as arising from a linear correction added to the partial derivative of a vector field, $\partial_\mu V^{\nu}$, to make the whole thing --- $\nabla_\mu V^\nu = \partial_\mu V^{\nu} + \Gamma^\nu_{\mu\lambda}V^\lambda$ --- transform like a tensor. To achieve this, the $\Gamma^\nu_{\mu\lambda}$ have to satisfy a certain transformation law, but otherwise there are no constraints. So it seems this leaves us with a lot of freedom in choosing the connection coefficients: Fixing a coordinate system, I can choose any combination of $4\cdot 4\cdot 4 = 64$ smooth functions to define my connection coefficients.
The other way introduces connection coefficients (as far as I understand) as arising from the change in the basis vectors when traveling between tangent spaces (as seen from the perspective of the basis of the original tangent space): \begin{align} &\partial_\mu \left(V^{\nu}\cdot \mathbf{e}_{(\nu)}\right)\\ =& \left(\partial_\mu V^\nu\right)\cdot \mathbf{e}_{(\nu)} + V^\lambda \cdot \left(\partial_\mu \mathbf{e}_{(\lambda)}\right)\\ =& \left(\partial_\mu V^\nu\right)\cdot \mathbf{e}_{(\nu)} + V^\lambda \cdot \left(\Gamma^\nu_{\mu\lambda}\mathbf{e}_{(\nu)}\right)\\ =&\left(\partial_\mu V^\nu + V^\lambda \Gamma^\nu_{\mu\lambda}\right)\cdot \mathbf{e}_{(\nu)} \end{align} where in the third step we have defined $\Gamma^\nu_{\mu\lambda}\mathbf{e}_{(\nu)} := \partial_\mu \mathbf{e}_{(\lambda)}$.
I'm puzzled because this second way of defining the connection coefficients doesn't seem to come with the same freedom in choosing the coefficients: By fixing a chart, we already fix a basis of the tangent space at each point within the chart's domain, and so it seems we automatically fix the connection coefficients as expressed in that chart. Whereas previously we could choose the connection coefficients by freely choosing $64$ different functions, now there seems to be a unique connection (at least within that part of the chart's domain which doesn't overlap with any other chart's domain).
What am I getting wrong here?
In the first approach, you're taking the $\Gamma$'s as the primitive objects, and from that you're defining $\nabla$. More explicitly, you're considering a collection $(U,x,\Gamma_{(x), ij}^k)_{i,j,k=1}^n$ where $(U,x)$ is a chart, and each $\Gamma_{(x),ij}^k:U\to\Bbb{R}$ is a smooth function, such that if you consider two different charts, there is a certain compatibility condition between $\Gamma_{(x)}$ and $\Gamma_{(y)}$. Using these guys, one defines $(\nabla_{\mu}V)^{\nu}$ (by the formula you wrote down) and checks that the formula is independent of charts, so using $\Gamma$'s we arrive at a definition for $\nabla$.
In the second approach, the use of $\partial_{\mu}$ acting on the basis vector fields is erroneous; I suspect you meant to use $\nabla_{\mu}$ throughout. In this case, $\nabla$ is taken as the primitive object (a certain operator satisfying a bunch of axioms), and one is using this to define the $\Gamma$'s as $\Gamma_{(x)\,ij}^k:=dx^k\left(\nabla_{\frac{\partial}{\partial x^i}}\frac{\partial}{\partial x^j}\right)$, so that $\nabla_{\frac{\partial}{\partial x^i}}\frac{\partial}{\partial x^j}=\Gamma_{(x),ij}^k\frac{\partial}{\partial x^k}$. You can now check that the $\Gamma_{(x)}$ and $\Gamma_{(y)}$ as defined here satisfy the same transformation law as in the first case.
Therefore, both approaches are equivalent (though the second is more algebraic hence slicker).