|
|
A066534
|
|
Total number of walks with length > 0 in the Hasse diagram of a Boolean algebra of order n.
|
|
10
|
|
|
0, 1, 6, 30, 152, 840, 5232, 37072, 297600, 2680704, 26812160, 294945024, 3539364864, 46011796480, 644165265408, 9662479226880, 154599668154368, 2628194359738368, 47307498477649920, 898842471080329216
(list;
graph;
refs;
listen;
history;
text;
internal format)
|
|
|
OFFSET
|
0,3
|
|
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
|
|
LINKS
|
|
|
FORMULA
|
a(n) = n!*Sum_{i+j<n, 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
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
|
|
EXAMPLE
|
a(2) = 6 because (2! / 0! * 2^0) + (2! / 1! * 2^1) = 6
|
|
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 *)
|
|
CROSSREFS
|
|
|
KEYWORD
|
easy,nonn,nice,walk
|
|
AUTHOR
|
Peter Bertok (peter(AT)bertok.com), Jan 07 2002
|
|
EXTENSIONS
|
|
|
STATUS
|
approved
|
|
|
|