3
$\begingroup$

From endomorphisms of rank 1 of the full transformation semigroup $[n]^{[n]}$ or idempotents in $[n]^{[n]}$, we have $$c_n:=\sum_{m=1}^n\binom{n}mm^{n-m}.$$ Denote the $2$-adic valuation of $x$ by $\nu_2(x)$.

QUESTION. Is it true that $\nu_2(c_n)=\nu_2(n-1)$, for $n\geq2$?

Improve this question
$\endgroup$
2
  • 1
    $\begingroup$ This is sequence 248 in the OEIS (oeis.org/A000248), which gives some further information including the exponential generating function $\exp(x \exp(x))$ and some references and further interpretations. Possibly one of those might lead to a proof. For what it's worth $c_2 = 3$ seems to be the only multiple of $3$, and I don't see a pattern in the valuation at $5$ and $7$. $\endgroup$
    – Noam D. Elkies
    Commented Dec 29, 2020 at 16:31
  • $\begingroup$ @NoamD.Elkies: thanks for the references which I was aware of. I agree with your mod 3 comments. I also think that no such behavior occurs for other primes. $\endgroup$
    – T. Amdeberhan
    Commented Dec 29, 2020 at 17:04

1 Answer 1

Reset to default
4
$\begingroup$

Yes, this is true. The idea is to get $n-1$ out of the sum as a multiple.

We have $$c_n=1+\sum_{m=1}^{n-1}m{n\choose m}m^{n-1-m}=1+\sum_{m=1}^{n-1}n{n-1\choose m-1}m^{n-1-m}$$ We see that if $n$ is even, then $c_n$ is odd.

Now let $n>1$ be odd. Then proceed this way:$$c_n=1+n\sum_{m=1}^{n-1}{n-1\choose m-1}+n\sum_{m=2}^{n-2}{n-1\choose m-1}(m^{n-1-m}-1)\\=1+n(2^{n-1}-1)+n(n-1)\sum_{m=2}^{n-2}{n-2\choose m-2}\cdot \frac{m^{n-1-m}-1}{m-1}\\=:1+n(2^{n-1}-1)+n(n-1)A.$$ Modulo 2 we have $$\frac{m^{n-1-m}-1}{m-1}=1+m+\ldots+m^{n-m-2}\equiv 1+m(n-m-2)\equiv 1,$$ so $$ A\equiv \sum_{m=2}^{n-2} {n-2\choose m-2}=2^{n-2}-1-(n-2)\equiv 0\pmod 2. $$ Then $c_n=(1-n)+(n2^{n-1})+n(n-1)A$, and $1-n$ has 2-adic valuation strictly smaller than two other summands, thus $\nu_2(c_n)=\nu_2(1-n)$.

Improve this answer
$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .