login
Total number of walks with length > 0 in the Hasse diagram of a Boolean algebra of order n.
10

%I #38 Jun 12 2021 02:44:39

%S 0,1,6,30,152,840,5232,37072,297600,2680704,26812160,294945024,

%T 3539364864,46011796480,644165265408,9662479226880,154599668154368,

%U 2628194359738368,47307498477649920,898842471080329216

%N Total number of walks with length > 0 in the Hasse diagram of a Boolean algebra of order n.

%C Let P(A) be the power set of an n-element set A. Then a(n) = the total number of ways to add 1 or more elements of A to each element x of P(A) where the elements to add are not elements of x and order of addition is important. - _Ross La Haye_, Nov 19 2007

%H T. D. Noe, <a href="/A066534/b066534.txt">Table of n, a(n) for n=0..100</a>

%H Eric Weisstein, <a href="http://mathworld.wolfram.com/Walk.html">Walk</a>

%H Eric Weisstein, <a href="http://mathworld.wolfram.com/BooleanAlgebra.html">Boolean Algebra</a>

%H Eric Weisstein, <a href="http://mathworld.wolfram.com/HasseDiagram.html">Hasse Diagram</a>

%F a(n) = n!*Sum_{i+j<n, i, j >= 0} 1/(i!*j!). - _Benoit Cloitre_, Nov 01 2002

%F E.g.f.: x*exp(2*x)/(1-x). a(n) = n*(a(n-1)+2^(n-1)). - _Vladeta Jovovic_, Oct 29 2003

%F a(n) = Sum_{k=0..n-1} (n! / k!) * 2^k = Sum_{k=0..n-1} P(n, n-k) * 2^k = n! * Sum_{k=0..n-1} 2^k / k! = Sum_{k=1..n} P(n, k) * 2^(n-k) = sum of the n-th row of A090802 from column 1 on = A010842(n) - 2^n = n * A010842(n-1) = binomial transform of A007526 - _Ross La Haye_, Sep 15 2004

%F E.g.f.: x/U(0) where U(k) = 1 - 2*x/(2 - 4/(2 + (k+1)/U(k+1))); (continued fraction, 3-step). - _Sergei N. Gladkovskii_, Oct 18 2012

%F Conjecture: a(n) + (-n-4)*a(n-1) + 4*(n)*a(n-2) + 4*(-n+2)*a(n-3) = 0. - _R. J. Mathar_, Dec 04 2012

%F a(n) ~ n! * exp(2). - _Vaclav Kotesovec_, Jun 01 2013

%F Mathar's conjectural third-order recurrence above is an easy consequence of Jovovic's first-order recurrence a(n) = n*(a(n-1) + 2^(n-1)). - _Peter Bala_, Sep 23 2013

%e a(2) = 6 because (2! / 0! * 2^0) + (2! / 1! * 2^1) = 6

%t a[ n_ ] := n!Sum[ 2^k/k!, {k, 0, n-1} ]

%t Table[n*Gamma[n, 2]*E^2, {n, 0, 19}] (* _Ross La Haye_, Oct 09 2005 *)

%Y Cf. A010842, A067273, A090802, A007526.

%K easy,nonn,nice,walk

%O 0,3

%A Peter Bertok (peter(AT)bertok.com), Jan 07 2002

%E Edited by _Dean Hickerson_, Jan 12 2002

%E Entry revised by _Ross La Haye_, Aug 18 2006