  In this paper we introduce and study a family of complexity functions of
infinite words indexed by $k \in \ints ^+ \cup {+\infty}.$ Let $k \in \ints ^+
\cup {+\infty}$ and $A$ be a finite non-empty set. Two finite words $u$ and $v$
in $A^*$ are said to be $k$-Abelian equivalent if for all $x\in A^*$ of length
less than or equal to $k,$ the number of occurrences of $x$ in $u$ is equal to
the number of occurrences of $x$ in $v.$ This defines a family of equivalence
relations $\thicksim_k$ on $A^*,$ bridging the gap between the usual notion of
Abelian equivalence (when $k=1$) and equality (when $k=+\infty).$ We show that
the number of $k$-Abelian equivalence classes of words of length $n$ grows
polynomially, although the degree is exponential in $k.$ Given an infinite word
$\omega \in A^\nats,$ we consider the associated complexity function $\mathcal
{P}^{(k)}_\omega :\nats \rightarrow \nats$ which counts the number of
$k$-Abelian equivalence classes of factors of $\omega$ of length $n.$ We show
that the complexity function $\mathcal {P}^{(k)}$ is intimately linked with
periodicity. More precisely we define an auxiliary function $q^k: \nats
\rightarrow \nats$ and show that if $\mathcal {P}^{(k)}_{\omega}(n)<q^k(n)$ for
some $k \in \ints ^+ \cup {+\infty}$ and $n\geq 0,$ the $\omega$ is ultimately
periodic. Moreover if $\omega$ is aperiodic, then $\mathcal
{P}^{(k)}_{\omega}(n)=q^k(n)$ if and only if $\omega$ is Sturmian. We also
study $k$-Abelian complexity in connection with repetitions in words. Using
Szemer\'edi's theorem, we show that if $\omega$ has bounded $k$-Abelian
complexity, then for every $D\subset \nats$ with positive upper density and for
every positive integer $N,$ there exists a $k$-Abelian $N$ power occurring in
$\omega$ at some position $j\in D.$
