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
T. D. Noe, Table of n, a(n) for n=0..100
Eric Weisstein, Walk
Eric Weisstein, Boolean Algebra
Eric Weisstein, Hasse Diagram
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
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
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
Edited by Dean Hickerson, Jan 12 2002
Entry revised by Ross La Haye, Aug 18 2006
STATUS
approved