Let $p(n,m)$ be the number of partitions of the integer $n$ into exactly $m$ parts. Consider the sequence $a_n = p(n,m)$. What is known about the sequence $a_n$ mod $k$? In particular, is it known/obvious that $a_n$ mod $k$ is periodic?
$\begingroup$
$\endgroup$
0
Add a comment
|
1 Answer
$\begingroup$
$\endgroup$
2
By duality (transposing Young diagram) this is the same as number of partitions of $n$ with maximal part $m$, hence the same as number of partitions of $n-m$ onto parts $1,2,\dots,m$, hence it is a coefficient of $x^{n-m}$ in the product $$\prod_{j\leq m} (1-x^j)^{-1}.$$ This product is a rational function, hence coefficients are periodic modulo any given $k$. I am afraid that finding the period is difficult.
answered Jan 2, 2016 at 11:56
-
$\begingroup$ At least when $k$ is squarefree, it seems we can take the period as $m! k^m$. Explanation: Let $f(k,m)$ be the period. Use the recurrence $p(n,m) = p(n-m, m) + p(n-1,m-1)$ to deduce that $a_n \mod k$ satisfies the recurrence corresponding to the polynomial $(1-x^m)(1-x^{f(k,m-1)})$. We can find a multiple of $f(k,m)$ by finding $t$ satisfying $(1-x^m)(1-x^{f(k,m-1)}) \mid 1-x^t \mod k$. In characteristic 0 this is unsolvable ($1-x^n$ has no repeated roots), but for instance, if $k$ is a prime, we can take $t = k \cdot m \cdot f(k,m-1)$, hence $f(k,m) \mid km \cdot f(k,m-1)$. $\endgroup$ Commented Jan 2, 2016 at 12:23
-
$\begingroup$ Yes, something like this, but is it minimal? $\endgroup$ Commented Jan 2, 2016 at 13:21