conjecture related to A027471

[Alec Mihailovs]

----- Original Message ----- 
From: "Ross La Haye" <rlahaye at new.rr.com>
Sent: Saturday, January 14, 2006 9:48 PM

> Let G be the Hasse diagram of a Boolean algebra of order n.  Define a 
> matrix
> M for G in the following manner --
>
> M_ij = 0 if there is no (directed) walk from v_i to v_j of G.
> M_ij = the length of the longest (directed) walk from v_i to v_j of G, if 
> a
> walk exists.

In other words, M is an n-dimensional hypercube (directed) and M_ij is the 
dimension of the sub-cube, starting at i and ending at j.

> Summing all the entries in M by hand for n =0,1,2,3,4 I get 0,1,6,27,108
> which seems to be Sum[Binomial(n,k)*k*2^(k-1),{k,0,n}] = n*3^(n-1) =
> A027471(n+1).  I'm wondering if anyone can prove or disprove this...

So, the sum of of M_ij is the sum of k*(# of sub-cubes of dimension k) for k 
from 0 to n.

It is well known that the number of k-dimensional sub-cubes is 
binomial(n,k)*2^(n-k). That gives formula

sum(k*binomial(n,k)*2^(n-k),k=0..n)

which is the value of sum(k*binomial(n,k)*2^(n-k)*x^(k-1),k=0..n) for x=1, 
and this is the derivative of the binomial expansion of (2+x)^n which equals 
n*(2+x)^(n-1). Substituting x=1, we get n*3^(n-1).

Alec Mihailovs
http://math.tntech.edu/alec/