Putnam

The desired count is $\frac{2016!}{1953!}- 63! \cdot 2016$, which we compute using the principle of inclusion-exclusion. As in A2, we use the fact that 2017 is prime; this means that we can do linear algebra over the field $\mathbb{F}_{2017}.$ In particular, every nonzero homogeneous linear equation in $n$ variables over $\mathbb{F}_{2017}$$has exactly$2017^{n-1}$solutions. For$$\pi$$a partition of$$\{0,\dots,63\}$$, let$$|\pi|$ denote the number of distinct parts of $\pi$$, Let$$\pi_0$$denote the partition of$$\{0,\dots,63\}$$into 64 singleton parts. Let$$\pi_1$$denote the partition of$$\{0,\dots,63\}$ into one 64-element part. For $\pi, \sigma$$two partitions of$$\{0,\dots,63\}$$, write$$\pi | \sigma$$if$$\pi$$is a refinement of$$\sigma$$(that is, every part in$$\sigma$$is a union of parts in$$\pi$$). By induction on$$|\pi|$$, we may construct a collection of integers$$\mu_\pi$$, one for each$$\pi$$\text{, with the properties that [ | = 1 = 0 0 0 . ] Define the sequence}$c_0, $\dots, c_{63}$$by setting$c_0 = 1$and$c_i = i$for$i>1$. Let$$N_\pi$$be the number of ordered 64-tuples$$(x_0,\dots,x_{63})$$of elements of \mathbb{F}_{2017}$ such that $x_i = x_j$ whenever $i$ and $j$ belong to the same part and $\sum_{i=0}^{63} c_i x_i$ is divisible by 2017. Then $N_\pi$ equals $2017^{|\pi|-1}$ unless for each part $S$ of $\pi$, the sum $\sum_{i \in S} c_i$ vanishes; in that case, $N_\pi$ instead equals $2017^{|\pi|}$. Since $c_0, \dots, c_{63}$ are positive integers which sum to $1 + \frac{63 \cdot 64}{2} = 2017$, the second outcome only occurs for $\pi = \pi_1$. By inclusion-exclusion, the desired count may be written as $$\sum_{\pi} \mu_\pi N_\pi = 2016 \cdot \mu_{\pi_1} + \sum_{\pi} \mu_\pi 2017^{|\pi|-1}.$$ Similarly, the number of ordered 64-tuples with no repeated elements may be written as $$64! \binom{2017}{64} = \sum_{\pi} \mu_\pi 2017^{|\pi|}.$$ The desired quantity may thus be written as $\frac{2016!}{1953!} + 2016 \mu_{\pi_1}$. It remains to compute $\mu_{\pi_1}$. We adopt an approach suggested by David Savitt: apply inclusion-exclusion to count distinct 64-tuples in an $\emph{arbitrary}$ set $A$. As above, this yields $$|A|(|A|-1) \cdots (|A|-63) = \sum_{\pi} \mu_\pi |A|^{|\pi|}.$$ Viewing both sides as polynomials in $|A|$ and comparing coefficients in degree 1 yields $\mu_\pi = -63!$ and thus the claimed answer.