[seqfan] Re: Highest exponent of 2 dividing A155200(n)

Max Alekseyev maxale at gmail.com
Thu Sep 3 05:08:50 CEST 2009


On Wed, Sep 2, 2009 at 8:59 PM, <franktaw at netscape.net> wrote:
> Not a complete answer, but perhaps some insight.
>
> The power of 2 dividing n! is n - A000120(n).
>
> Thus, the conjecture is equivalent to A155200(n) * n! is divisible by
> exactly 2^n.

The proof is then easily follows from the recurrent formula:

%F A155200 n*a(n) = 2*a(n-1) + sum(k=1,n-1,4^k*a(k)*[2*(k+1)*a(n-1-k)
- (n-k)*a(n-k)] for n>0, with a(0)=1.

Multiplying it by (n-1)!, we have:

a(n)*n! = 2*a(n-1)*(n-1)! + sum(k=1,n-1,
binomial(n-1,k)*4^k*a(k)*k!*[2*(k+1)*a(n-1-k)*(n-1-k)! -
a(n-k)*(n-k)!].

Assume that valuation(a(m)*m!,2) = m for all m<n.

Then for every summand (k=1..n-1), we have
valuation( binomial(n-1,k)*4^k*a(k)*k!*[2*(k+1)*a(n-1-k)*(n-1-k)! -
a(n-k)*(n-k)!], 2 )
>= 2k + k + (n-k) = 2k+n > n.
and thus
valuation(a(n)*n!,2) = valuation(a(n-1)*(n-1)!,2)+1 = n.

By induction, valuation(a(n)*n!,2) = n for all n.

Regards,
Max




More information about the SeqFan mailing list