Let $n$ and $k$ be positive integers. Two infinite sequences $\{s_i\}_{i\geq 1}$ and $\{t_i\}_{i\geq 1}$ are equivalent if, for all positive integers $i$ and $j$, $s_i = s_j$ if and only if $t_i = t_j$. A sequence $\{r_i\}_{i\geq 1}$ has equi-period $k$ if $r_1, r_2, \ldots $ and $r_{k+1}, r_{k+2}, \ldots$ are equivalent. Suppose $M$ infinite sequences with equi-period $k$ whose terms are in the set $\{1, \ldots, n\}$ can be chosen such that no two chosen sequences are equivalent to each other. Determine the largest possible value of $M$ in terms of $n$ and $k$.
Problem
Source:
Tags: combinatorics
24.06.2021 10:13
The answer is $n^k$. The key idea is to rephrase the equivalent condition. Two sequences are equivalent if there is a bijection between them, i.e. there exist a bijection $\pi$ such that $\pi(s_i)=t_i$, where the domain of the bijection is all integers showing up at least once in $s_i$ and the range is all integers showing up at least once in $t_i$. It suffices to show if there are $m$ distinct numbers that are one of $x_1,\cdots,x_k$ then there are $\frac{n!}{(n-m)!}$ pairwise unequivalent sequences starting with $x_1,\cdots,x_k$. Why? For each $x_1,\cdots, x_k$, we can biject this to each of the $\frac{n!}{(n-m)!}$ sequences equivalent to it, so that the number of pairwise unequivalent sequences is bijected to $(x_1,\cdots,x_k) \in \{1,\cdots,n\}^k$. To prove this, we note there exist a permutation $\pi$ mapping the set of numbers in $x_i$ to itself. Each $\pi$ corresponds to a sequence, though those sequences may not be different. We are counting the number of such permutations mapping $\{1,\cdots,n\}$ to itself. The key observation is that we can basically swap any of the terms that are not one of $x_1,\cdots,x_k$, i.e. each permutation is equivalent to $(n-m)!-1$ other ones. We are done. (Here is an example: Say $n=k=3$ then $111333222$ is equivalent to $111222333$)
24.06.2021 10:35
I got a partial attempt quite close I believe but then my brain stopped working. Like @above has already said, it's important to basically transfer the equivalent condition to a hash type of a sequence the equality of which implies an equivalence relation between the 2 sequences.
24.06.2021 11:08
Begin by observing that we can divide any equi-period $k$ sequence $\{a_i\}_{i\ge 1}$ into $k$ sequences $S_i=\{a_{jk+i}\}_{j\ge 0}$ where $i$ is in $\{1,2,\cdots k\}$. Now, any sequence $S_i$ is periodic and within any period no terms are repeated. Also, $S_i, S_j$ are just either rotations of each other or completely disjoint. These two conditions completely classify all equi-period $k$ sequences. Thus, we can just talk about sequences in terms of $S_1,\cdots S_k$. Now, equivalence only means the sequences are distinct up to bijection. So, we claim that the answer is $n^k$ and induct on $k$. For base case, $k=1$, the result is immediate since $S_1$ can be $1,2,\cdots n$ cycle. Now, let's say we are done till $k=m$. For $k=m$, let some sequence upto equivalence be $S=\{S_1,S_2,\cdots S_m\}$. Now, we try to add a sequence $S_{m+1}$. Let $i$ distinct numbers be used in $S_1,\cdots S_m$. Now, if we pick the first term of $S_{m+1}$ from these $i$ things, the entire sequence would be forced due to the cycle condition. Now, if $S_{m+1}$ starts with some other term then it can be a $1, 2,\cdots n-i$ cycle which are $n-i$ more options. Thus, we can form $n$ sequences from every sequence $S$ upto equivalence. All these sequences are clearly non-equivalent and more sequences cannot be found either. Thus, we are done.
24.06.2021 12:38
The answer is \(n^k\). We'll construct a bijection between \((a_1,\ldots,a_k)\in[n]^k\) and equivalence classes of sequences \((s_i)\) of equi-period \(k\). First direction: Suppose we are given \((a_1,\ldots,a_k)\in[n]^k\). Define a counter \(C=0\). For each \(i=1,2,\ldots,k\): If \(a_i\le n-C\), then let \(s_i=C+1\), \(s_{k+i}=C+2\), \(s_{2k+i}=C+3\), \(\ldots\), \(s_{(a-1)k+i}=C+a_1\), and increment \(C\) by \(a_i\). Otherwise let \(s_i=n+1-a_i\le C\), which will determine \(s_{k+i}\), \(s_{2k+i}\), \(\ldots\) through previously-known cycles using numbers \(\le C\). Second direction: Suppose we are given \((s_i)\). Keep a running counter \(C=0\), that we will use to number off the distinct values of observe. For each \(i=1,2,\ldots,k\): If all of \(s_i\), \(s_{k+i}\), \(s_{2k+i}\), \(\ldots\) are greater than \(C\) (i.e.\ we've never seen them before), then let \(a_i\) be the period of this sequence. Without loss of generality (up to equivalence) we may let \(s_i=C+1\), \(s_{k+i}=C+2\), \(\ldots\), \(s_{(a_i-1)k+i}=C+a_i\), and increment \(C\) by \(a_i\). If any of \(s_i\), \(s_{k+i}\), \(s_{2k+i}\), \(\ldots\) is \(\le C\), then all of them are determined by a previously-known cycle and each term \(\le C\), so we may let \(a_i=n+1-s_i\). It is easy to see that the above two operations are inverses of each other, so we have established the desired bijection.
24.06.2021 14:03
Really nice problem. Since my solution was quite long, I'll leave a sketch: Define first a process called normalisation, which is essentially to mark the first element encountered as $a_1$, the second as $a_2$, and so on. This isn't really necessary, but it reduces equivalency to distinctness, which simplifies some arguments later on. Also note that each term in an equi-periodic sequence with terms chosen from ${1,2,...,n}$ appear infinitely many times (not hard to prove). Denote an arbitrary normalised sequence by $r_1,r_2,r_3,...$. Observe that the equi-periodic condition is the same as saying $r_{k+1},r_{k+2},...$ normalises to $r_1,r_2,...$. Consider the graph obtained by considering $a_1,a_2,...,a_t$ as vertices (where there are $t$ distinct terms in the sequence), making the directed edge $a_i \rightarrow a_j$ if the term $a_i$ on normalisation of $r_{k+1},r_{k+2},...$ changes to $a_j$. It's easy to see that the graph is composed entirely of disjoint cycles. Moreover, from a constructive viewpoint, this is the same as applying the inverse of this graph to the first $k$ terms of a normalised sequence to obtain the next $k$ terms, applying it again to get the next $k$ terms and so on, with the constraint that each of the disjoint cycles must contain at least one of the first $k$ terms. There is another constraint to preserve normalisation, but we can ignore via a recursive approach. Finally, before starting with the recursion, observe that $M_{n,1}=n$ - this is easy to observe from our graph structure with the given constraint, as we can essentially choose our cycle length to be one of $1,2,...,n$. Now, we arrive to our main claim, which is- $M_{n,k+1}=n \cdot M_{n,k}$. We seek to produce all $(k+1)-$periodic sequences from $k-$periodic sequences (as each $(k+1)-$periodic sequence with its $r(k+1) ^{\text{th}}$ term removed for all natural $r$ gives a $k-$periodic sequence). We'll ignore normalisation here, for the most part. Now, say some arbitrary $k-$periodic sequence has $t$ distinct terms—$a_1,a_2,...,a_t$. As we'll be inserting a term at all of the $r(k+1)^{\text{th}}$ positions (aka between $(k,k+1),(2k,2k+1),...$ in the current sequence), let's first insert an element at the $(k+1)^{\text{th}}$ position. If it's one of $a_1,a_2,...,a_t$, we immediately get exactly one corresponding sequence for each term since the graph structure for these elements is already established. If it's a distinct element, then we still can't interfere with the established graph structure without changing the original $k-$periodic sequence. However, we can choose our cycle length outside the structure—aka it can be any one of $1,2,3,...,n-t$. Hence, from any single $k-$periodic sequence one can generate $n$ new $k+1$-periodic sequences. It's easy to verify that all such obtained sequences are non-equivalent, and as we've used all $k-$periodic sequences, we have indeed generated all possible non-equivalent $(k+1)-$periodic sequences. Thus, we get $M_{n,k}=n^k$. Hence proved.
25.06.2021 08:06
"Being equivalent" is an equivalence relation, so the answer is simply the number of congruence classes. Let $F(k,t)$ be the number of surjective maps from $[n]$ to $[t]$. We start off with the following observation. Lemma: Two sequences $s,t$ are equivalent iff there exists a permutation $\pi: [n] \rightarrow [n]$ such that $s_i = \pi(t_i)$ Proof: If direction is obvious, so we only prove the only-if direction. Call an index $i$ "first in $s$" if $s_j \neq s_i$ for all $j<i$ (i.e., $i$ is the first occurence of some character in $s$). The set of indices first in $s$ and first in $t$ are equal if they are equivalent, say it is $\{i_1, i_2, \cdots , i_u\}$. Consider the permutation which sends $s_{i_1}$ to $t_{i_1}$, $s_{i_2}$ to $t_{i_2}$, ..., $s_{i_u}$ to $t_{i_u}$. This does the job. By the lemma, for any $k$-equiperiodic sequence there exists a permutation $\pi: [n] \rightarrow [n]$ such that $s_{i+k} = \pi(s_i)$. So if we fix the first $k$ numbers and $\pi$, rest of the sequence is uniquely determined. Suppose we fix the first $k$ numbers of a $k$-equiperiodic sequence. By relabelling them appropriately, we can find another sequence in the same equivalence class whose image restricted to first $k$ indices is $\{1, 2, \cdots , t\}$ for some $t$ and the first occurence of 1 appears before the first occurence of 2, which appears before the first occurence of 3, and so on. It is easy to check that if two such sequences differ in their first $k$ elements, they are not equivalent. Suppose in such a sequence, $t = \max_{i \leq k} s_i$. The number of such sequences is $F(k,t)/t!$ (because in any such surjective map, each ordering of the numbers according to their first occurence is equally likely). We count the number of non-equivalent ways to extend this via a permutation $\pi$. Two permutations $\pi_1, \pi_2$ give rise to equivalent sequences if and only if: (1) The permutations restricted to $\{1, 2, \cdots , t\}$ are the same (i.e., delete all other vertices from the functional graph in the natural manner). Call it $\phi$. (2) The number of nodes in the path from $i$ to $\phi(i)$ in the functional graph is same for both permutations, for each $i$. The details are easy to check. There are $t!$ ways to select the internal permutation. There are $\dbinom{n}{t}$ non-equivalent ways to fill in the remaining permutation (let $a_i$ be the distance between $i$ and $\phi(i)$ in the graph, then we are looking for the number of non-negative integer solutions to $a_1 + a_2 + \cdots + a_t \leq n-t$). The number of equivalence classes thus is $$ \displaystyle \sum_t \dfrac{F(k,t)}{t!} t! \dbinom{n}{t} = \displaystyle \sum_t F(k,t) \dbinom{n}{t}$$However, this is imply the number of maps from $[k]$ to $[n]$ (first fix the image set of the map, say $S$, then number of such maps is $F(k, |S|)$), which is $n^k$.
30.06.2021 01:31
Denote the answer by $M(n,k)$. The crux of the problem is the following observation: the sequences with equi-period $1$ and finitely many different term values are equivalent to $1, 2, \dots, m, 1, 2, \dots, m, \dots$ for some positive integer $m$. To see this, WLOG the terms before the first repetition are $1, 2, \dots, m$. If the next term is $i$, the fact that the sequence has equi-period $1$ implies that $m = i-1$ or $i=1$. The former case is absurd, so $i=1$ and the fact that the sequence has equi-period $1$ finishes. Now, observe that by considering the sets of indices of terms congruent to $1, 2, \dots, k$ we get a partition of the full sequence $\{r_i\}_{i\ge 1}$ into sequences that essentially have equi-period $1$, so we can apply our characterization. Now suppose two of these sequences corresponding to the residues $i\ne j$ contain a common term. That is, for some $a$ and $b$, $r_{ak+i} = r_{bk + j}$. WLOG $a>b$. Then $r_{(a-b)k+i} = r_j$ by the equi-period $k$ condition, so one sequence is a cyclic shift of the other. So either two sequences are cyclic shifts, or they are disjoint. Look at the last sequence. There are two possibilities: it is a cyclic shift of a previous sequence, or it is disjoint from every previous sequence. If it is a cyclic shift, there are $t$ choices for it where $t$ is the number of distinct elements of the previous sequence. If it is disjoint from every previous sequence, there are essentially $n-t$ choices for it where $t$ is the number of distinct elements of the previous sequence, corresponding to the possible numbers of elements of this new sequence. So the overall sum is $nM(n,k-1)$. Thus because $M(n,1)$ is clearly $n$, we see that $M(n,k) = n^k$ for all $n$ and $k$.
30.06.2021 16:53
My rather tedious solution: I claim that $M(n,k)=n^k$. Denote the proposition "sequences $A$ and $B$ are equivalent" by $A \cong B$, and the set $\{1,2,3,...,n\}$ by $[n]$. The proof consists of 3 steps. $\underline{\textit{\textbf{Step I: Characterizing equivalent and equi-periodic sequences}}}$ Note that, if $\{a_i\} \cong \{b_i\}$, then there exists a bijection $f_a: [n] \rightarrow [n]$ such that $f(a_i)=b_i$ for all $i$. Hence, if $\{a_i\}$ has equi-period $k$, then there exists a bijection $f_a: [n] \rightarrow [n]$ such that $f(a_i)=a_{k+i}$ for all $i$. That means each sequence $\{a_i\}$ of equi-period $k$ can be characterized by the $k$ numbers $a_1,a_2,...,a_k$ and a bijection $f_a$. However, note that this characterization is not unique; different combinations of the $k$ numbers and the bijection may refer to the same equi-periodic sequence. At last, note also that equivalence is transitive, that is, if $A \cong B$ and $B \cong C$, then $A \cong C$ as well. $\underline{\textit{\textbf{Step II: Setting up a recursion}}}$ Let the total number of infinite sequences with equi-period $k$, whose terms are in the set $[n]$, and whose terms include all elements of $[n]$ be $P(n,k)$. Note that in our definition, equivalent sequences are counted separately. The key equation is as follows: \[P(n,k)=n^k \times n! - \binom{n}{1}(1!)P(n-1,k) - \binom{n}{2}(2!)P(n-2,k) - ... - \binom{n}{n-1}((n-1)!)P(1,k)\]Firstly, $n^k \times n!$ is the number of combinations of $k$ numbers and a bijection from $[n]$ to $[n]$, hence the presence of this term on the right. Then, all sequences counted in $P(n,k)$ are counted exactly once in $n^k \times n!$, as any 2 bijections lead to different sequences, if all elements of $[n]$ are used in those sequences. However, we have to deduct the number of sequences counted in $n^k \times n!$ containing only $i$ of the elements in $[n]$, for $i=1,2,...,n-1$. Firstly, there are a total of $\binom{n}{n-i}P(i,k)$ sequences with equi-period $k$, whose terms are in the set $[n]$ and exactly $i$ of the elements of $[n]$ are used. Each of these sequences are counted $(n-i)!$ times in the term $n^k \times n!$. This is because: There is only 1 possible choice of $a_1,a_2,...,a_k$. Consider a graph G with vertices $1,2,...,n$, and where there is a directed edge from $x$ to $y$ whenever $f_a(x)=y$. The directed edges starting from vertices $a_1,a_2,...,a_k$ (note that $\vert \{a_1,a_2,...,a_k\} \vert = i$) must lead to vertices $a_1,a_2,...,a_k$ themselves, and these edges are already uniquely determined by the sequence. However, the edges among $[n] \setminus \{a_1,a_2,...,a_k\}$ can be freely chosen, and will still describe the same sequence. Hence, there are $(n-i)!$ possible choices of the bijection $f_a$. This proves the validity of the equation. $\underline{\textit{\textbf{Step III: Finishing}}}$ Simplifing the equation in part II yields \[\frac{P(n,k)}{n!}=n^k - \frac{P(n-1,k)}{(n-1)!} - \frac{P(n-2,k)}{(n-2)!} - ... - \frac{P(1,k)}{(1)!}\]which easily gives (by replacing $n$ by $n-1$ and substituting into the original equation) \[\frac{P(n,k)}{n!}=n^k - (n-1)^k\]Now, due to our characterization of the equivalence between sequences, for each sequence containing exactly $i$ distinct terms, there are $i!$ sequences (including itself) that are equivalent to it. Hence, we have \[M(n,k) = \frac{P(n,k)}{n!} + \frac{P(n-1,k)}{(n-1)!} + ... + \frac{P(1,k)}{(1)!}\]and so \[M(n,k) = [n^k - (n-1)^k] + [(n-1)^k - (n-2)^k] + ... + [1^k] = n^k\]So we are done. \(\blacksquare\) Comment: Recursion is a common technique in counting problems, especially when the answer is in terms of other integer variables. So it is natural to go in this direction immediately after seeing the problem.
13.05.2024 15:59
Note that each residue class mod $k$ contains a repeating pattern in which the terms of the smallest repeating block are all distinct. Moreover, two residue classes are disjoint or contain the same repeating pattern, possibly cyclic shifted. Now we build the residue classes one at a time. In the first residue class, there are simply $n$ choices for the length of the repeating pattern. Now, suppose at some point we have built repeating patterns of length $a_1, a_2, \dots, a_r$ and have $n-a_1-\dots-a_r = b$ unused values. We can choose any of the $a_i$ cyclic shifts of the $i^{\text{th}}$ repeating pattern for some $i$, or build a new repeating pattern of any length $1\le j\le b$. Hence, there are a total of $a_1 + \dots + a_r + b = n$ ways to fill in each residue class, so there are a total of $n^k$ unequivalent sequences.