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

0, 1, 6, 30, 152, 840, 5232, 37072, 297600, 2680704, 26812160, 294945024, 3539364864, 46011796480, 644165265408, 9662479226880, 154599668154368, 2628194359738368, 47307498477649920, 898842471080329216

Offset: 0

Author

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

Keywords

• easy
• nonn
• nice
• walk

Comments

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

Examples

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

Links

• T. D. Noe, Table of n, a(n) for n=0..100
• Eric Weisstein, Walk
• Eric Weisstein, Boolean Algebra
• Eric Weisstein, Hasse Diagram

Crossrefs

Cf. A010842, A067273, A090802, A007526.

Programs

Mathematica

a[ n_ ] := n!Sum[ 2^k/k!, {k, 0, n-1} ]
Table[n*Gamma[n, 2]*E^2, {n, 0, 19}] (* Ross La Haye, Oct 09 2005 *)

Formula

a(n) = n!*Sum_{i+j= 0} 1/(i!*j!). - Benoit Cloitre, Nov 01 2002

E.g.f.: x*exp(2*x)/(1-x). a(n) = n*(a(n-1)+2^(n-1)). - Vladeta Jovovic, Oct 29 2003

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

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

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

a(n) ~ n! * exp(2). - Vaclav Kotesovec, Jun 01 2013

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

Extensions

Edited by Dean Hickerson, Jan 12 2002

Entry revised by Ross La Haye, Aug 18 2006