Consider a Graph $G=(V,E)$ with $|V|=n$ where each node $v\in V$ has a label $l_v\in\{1,...,n\}$. Denote by $G^k$ the k-fold Cartesian product of $G$ with itself where $k<n$. The set of nodes is consequently $V^k$. Denote by $D_l = \{w\in V^k|\exists i_1,...,i_l\in\{1,...,n\},\; i_1\neq...\neq i_l: w_{i_1}=w_{i_2}=..w_{i_l}\text{ and }l\text{ is maximal}\}$ for $l\in\{1,...,k\}$. I am wondering about the size of $D_l$ as a function of $l,k,n$.
I approached the problem by looking at each $w\in V^k$ as a vector of $k$ colored balls and if $w\in D_l$ the largest proportion of one color has size $l$. Hence the partition function $p(k,l)$ gives me all possibilities to color the nodes. But then I am stuck because I do not see how to combine the possible permutations of colors and choosing $k$ colors out of $n$ (with replacement).
How can I approach this?
I used the tag "integer-partitions" because of the link to the partition function.
Let say your function is $f(l,k,n)$; we have $l < k < n$.
If I understand correctly, then $f(l,k,n) = n \binom{k}{l} (n-1)^{k-l}$ if $l \geq \frac{k}{2}$, right? Because we're looking for the number of $k$-tuples with $l$ entries all equal to one of $n$ elements, and the other $k - l$ entries all chosen from the other $n-1$ possibilities.
If $l < \frac{k}{2}$, then we have to worry about not allowing more than $l$ of the other entries to be equal. One way to do it is by exclusion:
$$ f(l,k,n) = n \binom{k}{l} (n-1)^{k-l} - n \binom{k}{l} (n-1) \binom{k-l}{l+1} (n-2)^{k-2l-1} - \dotsb - n \binom{k}{l} (n-1) \binom{k-l}{l+(k-2l)} $$
But actually, if $l < \frac{k}{3}$, you have to worry about more possibilities, so this seems like a pain.
Let's see. We want permutations of $k$ out of $n$ things with at most $l$ repetitions, where at least one thing does repeat $l$ times. Roberto Frucht called the number of arrangements with at most $l$ repetitions $P(n,k,l)$ in Permutations with limited repetitions, giving several formulas for it there. A recursive definition which is supposed to be more computationally efficient is given in On permutations with limited repetition by H Mendelson.
With this, we only have to remove those tuples which don't have any elements repeated $l$ times, hence actually have at most $l-1$ repetitions. So
$$ f(l,k,n) = P(n,k,l) - P(n,k,l-1). $$