%I M2900 #228 Aug 01 2024 21:51:19
%S 1,1,3,11,49,257,1539,10299,75905,609441,5284451,49134923,487026929,
%T 5120905441,56878092067,664920021819,8155340557697,104652541401025,
%U 1401572711758403,19546873773314571,283314887789276721,4259997696504874817,66341623494636864963
%N Shifts one place left under 2nd-order binomial transform.
%C Equals the eigensequence of A038207, the square of Pascal's triangle. - _Gary W. Adamson_, Apr 10 2009
%C The g.f. of the second binomial transform is 1/(1-2x-x/(1-2x/(1-2x-x/(1-4x/(1-2x-x/(1-6x/(1-2x-x/(1-8x/(1-... (continued fraction). - _Paul Barry_, Dec 04 2009
%C Length-n restricted growth strings (RGS) [s(0),s(1),...,s(n-1)] where s(k)<=F(k)+2 where F(0)=0 and F(k+1)=s(k+1) if s(k+1)-s(k)=2, otherwise F(k+1)=F(k); see example and Fxtbook link. - _Joerg Arndt_, Apr 30 2011
%C It appears that the infinite set of "Shifts 1 place left under N-th order binomial transform" sequences has a production matrix of:
%C 1, N, 0, 0, 0, ...
%C 1, 1, N, 0, 0, ...
%C 1, 2, 1, N, 0, ...
%C 1, 3, 3, 1, N, ...
%C ... (where a diagonal of (N,N,N,...) is appended to the right of Pascal's triangle). a(n) in each sequence is the upper left term of M^n such that N=1 generates A000110, then (N=2 - A004211), (N=3 - A004212), (N=4 - A004213), (N=5 - A005011), ... - _Gary W. Adamson_, Jul 29 2011
%C Number of "unlabeled" hierarchical orderings on set partitions of {1..n}, see comments on A034691. - _Gus Wiseman_, Mar 03 2016
%C From _Lorenzo Sauras Altuzarra_, Jun 17 2022: (Start)
%C Number of n-variate noncontradictory conjunctions of logical equalities of literals (modulo logical equivalence).
%C Equivalently, number of n-variate noncontradictory Krom formulas with palindromic truth-vector (modulo logical equivalence).
%C a(n) <= A109457(n). (End)
%D N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).
%H Vincenzo Librandi, <a href="/A004211/b004211.txt">Table of n, a(n) for n = 0..200</a>
%H Joerg Arndt, <a href="http://www.jjj.de/fxt/#fxtbook">Matters Computational (The Fxtbook)</a>, section 17.3.5, pp. 366-368
%H Paul Barry, <a href="https://cs.uwaterloo.ca/journals/JIS/VOL17/Barry2/barry281.html">Constructing Exponential Riordan Arrays from Their A and Z Sequences</a>, Journal of Integer Sequences, 17 (2014), #14.2.6.
%H Zhanar Berikkyzy, Pamela E. Harris, Anna Pun, Catherine Yan, and Chenchen Zhao, <a href="https://arxiv.org/abs/2208.13091">On the Limiting Vacillating Tableaux for Integer Sequences</a>, arXiv:2208.13091 [math.CO], 2022.
%H Zhanar Berikkyzy, Pamela E. Harris, Anna Pun, Catherine Yan, and Chenchen Zhao, <a href="https://arxiv.org/abs/2308.14183">Combinatorial Identities for Vacillating Tableaux</a>, arXiv:2308.14183 [math.CO], 2023. See pp. 22, 29.
%H David Callan (Proposer), <a href="http://www.jstor.org/stable/10.4169/amer.math.monthly.118.04.371">Problem 11567</a>, Amer. Math. Monthly, 118 (2011), 371-378.
%H Agustina Czenky, <a href="https://arxiv.org/abs/2306.08826">Unoriented 2-dimensional TQFTs and the category Rep(S_t wr Z_2)</a>, arXiv:2306.08826 [math.QA], 2023. See p. 40.
%H I. M. Gessel, <a href="https://arxiv.org/abs/math/0108121">Applications of the classical umbral calculus</a>, arXiv:math/0108121v3 [math.CO], 2001.
%H Adam M. Goyt and Lara K. Pudwell, <a href="http://faculty.valpo.edu/lpudwell/papers/MonthlyStirling.pdf">Solution to Monthly Problem 11567</a>, 14 May 2011.
%H Adalbert Kerber, <a href="http://dx.doi.org/10.1016/0012-365X(78)90163-2">A matrix of combinatorial numbers related to the symmetric groups</a>, Discrete Math., 21 (1978), 319-321.
%H Adalbert Kerber, <a href="/A004211/a004211.pdf">A matrix of combinatorial numbers related to the symmetric groups<</a>, Discrete Math., 21 (1978), 319-321. [Annotated scanned copy]
%H Huyile Liang, Jeffrey Remmel, and Sainan Zheng, <a href="https://arxiv.org/abs/1710.05795">Stieltjes moment sequences of polynomials</a>, arXiv:1710.05795 [math.CO], 2017, see page 20.
%H Janusz Milek, <a href="https://arxiv.org/abs/2002.07389">Quantum Implementation of Risk Analysis-relevant Copulas</a>, arXiv:2002.07389 [stat.ME], 2020.
%H N. J. A. Sloane, <a href="/transforms.txt">Transforms</a>
%F E.g.f. A(x) satisfies A'(x)/A(x) = e^(2x).
%F E.g.f.: exp(sinh(x)*exp(x)) = exp(Integral_{t = 0..x} exp(2*t)) = exp((exp(2*x)-1)/2). - _Joerg Arndt_, Apr 30 2011 and May 13 2011
%F a(n) = Sum_{k=0..n} 2^(n-k)*Stirling2(n, k). - _Emeric Deutsch_, Feb 11 2002
%F G.f.: Sum_{k >= 0} x^k/Product_{j = 1..k} (1-2*j*x). - _Ralf Stephan_, Apr 18 2004
%F Stirling transform of A000085. - _Vladeta Jovovic_ May 14 2004
%F O.g.f.: A(x) = 1/(1-x-2*x^2/(1-3*x-4*x^2/(1-5*x-6*x^2/(1-... -(2*n-1)*x-2*n*x^2/(1- ...))))) (continued fraction). - _Paul D. Hanna_, Jan 17 2006
%F Define f_1(x), f_2(x), ... such that f_1(x)=e^x, f_{n+1}(x) = (d/dx)(x*f_n(x)), for n=2,3,.... Then a(n) = e^(-1/2)*2^{n-1}*f_n(1/2). - _Milan Janjic_, May 30 2008
%F G.f.: 1/(1-x/(1-2x/(1-x/(1-4x/(1-x/(1-6x/(1-x/(1-8x/(1-... (continued fraction). - _Paul Barry_, Dec 04 2009
%F a(n) = upper left term in M^n, M = an infinite square production matrix with an appended diagonal of (2,2,2,...) to the right of Pascal's triangle:
%F 1, 2, 0, 0, 0, ...
%F 1, 1, 2, 0, 0, ...
%F 1, 2, 1, 2, 0, ...
%F 1, 3, 3, 1, 2, ...
%F ... - _Gary W. Adamson_, Jul 29 2011
%F a(n) = D^n(exp(x)) evaluated at x = 0, where D is the operator (1+2*x)*d/dx. Cf. A000110. - _Peter Bala_, Nov 25 2011
%F G.f. A(x) satisfies A(x)=1+x/(1-2*x)*A(x/(1-2*x)), a(n) = Sum_{k=1..n} binomial(n-1,k-1)*2^(n-k)*a(k-1), a(0)=1. - _Vladimir Kruchinin_, Nov 28 2011 [corrected by _Ilya Gutkovskiy_, May 02 2019]
%F From _Peter Bala_, May 16 2012: (Start)
%F Recurrence equation: a(n+1) = Sum_{k = 0..n} 2^(n-k)*C(n,k)*a(k).
%F Written umbrally this is a(n+1) = (a + 2)^n (expand the binomial and replace a^k with a(k)). More generally, a*f(a) = f(a+2) holds umbrally for any polynomial f(x). An inductive argument then establishes the umbral recurrence a*(a-2)*(a-4)*...*(a-2*(n-1)) = 1 with a(0) = 1. Compare with the Bell numbers B(n) = A000110(n), which satisfy the umbral recurrence B*(B-1)*...*(B-(n-1)) = 1 with B(0) = 1. Cf. A009235.
%F Touchard's congruence holds: for odd prime p, a(p+k) == (a(k) + a(k+1)) (mod p) for k = 0,1,2,... (adapt the proof of Theorem 10.1 in Gessel). In particular, a(p) == 2 (mod p) for odd prime p. (End)
%F G.f.: (2/E(0) - 1)/x where E(k) = 1 + 1/(1 + 2*x/(1 - 4*(k+1)*x/E(k+1))); (continued fraction, 3-step). - _Sergei N. Gladkovskii_, Sep 20 2012
%F G.f.: (1/E(0)-1)/x where E(k) = 1 - x/(1 + 2*x - 2*x*(k+1)/E(k+1)); (continued fraction, 2-step). - _Sergei N. Gladkovskii_, Sep 21 2012
%F a(n) = -1 + 2*Sum_{k=0..n} C(n,k)*A166922(k). - _Peter Luschny_, Nov 01 2012
%F G.f.: G(0)- 1/x where G(k) = 1 - (4*x*k-1)/(x - x^4/(x^3 - (4*x*k-1)*(4*x*k+2*x-1)*(4*x*k+4*x-1)/G(k+1) )); (continued fraction). - _Sergei N. Gladkovskii_, Jan 08 2013.
%F G.f.: (G(0) - 1)/(x-1) where G(k) = 1 - 1/(1-2*k*x)/(1-x/(x-1/G(k+1) )); (continued fraction). - _Sergei N. Gladkovskii_, Jan 15 2013
%F G.f.: -G(0) where G(k) = 1 + 2*(1-k*x)/(2*k*x - 1 - x*(2*k*x - 1)/(x - 2*(1-k*x)/G(k+1) )); (continued fraction). - _Sergei N. Gladkovskii_, Jan 29 2013
%F G.f.: 1/Q(0), where Q(k) = 1 - x/(1 - 2*x*(2*k+1)/( 1 - x/(1 - 4*x*(k+1)/Q(k+1) ))); (continued fraction). - _Sergei N. Gladkovskii_, Apr 15 2013
%F G.f.: 1 + x/Q(0), where Q(k)= 1 - x*(2*k+3) - x^2*(2*k+2)/Q(k+1); (continued fraction). - _Sergei N. Gladkovskii_, May 05 2013
%F For n > 0, a(n) = exp(-1/2)*Sum_{k > 0} (2*k)^n/(k!*2^k). - _Vladimir Reshetnikov_, May 09 2013
%F G.f.: -(1+(2*x+1)/G(0))/x, where G(k)= 2*x*k - x - 1 - 2*(k+1)*x^2/G(k+1); (continued fraction). - _Sergei N. Gladkovskii_, Jul 20 2013
%F G.f.: T(0)/(1-x), where T(k) = 1 - 2*x^2*(k+1)/( 2*x^2*(k+1) - (1-x-2*x*k)*(1-3*x-2*x*k)/T(k+1) ); (continued fraction). - _Sergei N. Gladkovskii_, Oct 19 2013
%F Sum_{k=0..n} C(n,k)*a(k)*a(n-k) = 2^n*Bell(n) = A055882(n). - _Vaclav Kotesovec_, Apr 03 2016
%F a(n) ~ 2^n * n^n * exp(n/LambertW(2*n) - n - 1/2) / (sqrt(1 + LambertW(2*n)) * LambertW(2*n)^n). - _Vaclav Kotesovec_, Jan 07 2019, simplified Oct 01 2022
%F a(n) = B_n(2^0, ..., 2^(n - 1)), where B_n(x_1, ..., x_n) is the n-th complete Bell polynomial. - _Lorenzo Sauras Altuzarra_, Jun 17 2022
%e From _Joerg Arndt_, Apr 30 2011: (Start)
%e Restricted growth strings: a(0)=1 corresponds to the empty string;
%e a(1)=1 to [0]; a(2)=3 to [00], [01], and [02]; a(3) = 11 to
%e RGS F
%e [ 1] [ 0 0 0 ] [ 0 0 0 ]
%e [ 2] [ 0 0 1 ] [ 0 0 0 ]
%e [ 3] [ 0 0 2 ] [ 0 0 2 ]
%e [ 4] [ 0 1 0 ] [ 0 0 0 ]
%e [ 5] [ 0 1 1 ] [ 0 0 0 ]
%e [ 6] [ 0 1 2 ] [ 0 0 2 ]
%e [ 7] [ 0 2 0 ] [ 0 2 2 ]
%e [ 8] [ 0 2 1 ] [ 0 2 2 ]
%e [ 9] [ 0 2 2 ] [ 0 2 2 ]
%e [10] [ 0 2 3 ] [ 0 2 2 ]
%e [11] [ 0 2 4 ] [ 0 2 4 ]. (End)
%e From _Lorenzo Sauras Altuzarra_, Jun 17 2022: (Start)
%e The 11 trivariate noncontradictory conjunctions of logical equalities of literals are (x <-> y) /\ (y <-> z), (~ x <-> y) /\ (y <-> z), (x <-> ~ y) /\ (~ y <-> z), (x <-> y) /\ (y <-> ~ z), (x <-> y) /\ (z <-> z), (~ x <-> y) /\ (z <-> z), (x <-> z) /\ (y <-> y), (~ x <-> z) /\ (y <-> y), (y <-> z) /\ (x <-> x), (~ y <-> z) /\ (x <-> x), and (x <-> x) /\ (y <-> y) /\ (z <-> z) (modulo logical equivalence).
%e The third complete Bell polynomial is x^3 + 3 x y + z; and note that (2^0)^3 + 3*2^0*2^1 + 2^2 = 11.
%e The truth-vector of (x <-> y) /\ (y <-> z), 10000001, is palindromic. (End)
%p a:= proc(n) option remember; `if`(n=0, 1, add(
%p a(n-j)*binomial(n-1, j-1)*2^(j-1), j=1..n))
%p end:
%p seq(a(n), n=0..23); # _Alois P. Heinz_, May 30 2021
%p # second Maple program:
%p a:= n -> CompleteBellB(n, seq(2^k, k=0..n)):
%p seq(a(n), n=0..23); # _Lorenzo Sauras Altuzarra_, Jun 17 2022
%t Table[ Sum[ StirlingS2[ n, k ] 2^(-k+n), {k, n} ], {n, 16} ] (* _Wouter Meeussen_ *)
%t Table[2^n BellB[n, 1/2], {n, 0, 20}] (* _Vladimir Reshetnikov_, Oct 20 2015 *)
%o (PARI) x='x+O('x^66);
%o egf=exp(intformal(exp(2*x))); /* = 1 + x + 3/2*x^2 + 11/6*x^3 + ... */
%o /* egf=exp(1/2*(exp(2*x)-1)) */ /* alternative e.g.f. */
%o Vec(serlaplace(egf)) /* _Joerg Arndt_, Apr 30 2011 */
%o (Maxima)
%o a(n):=if n=0 then 1 else sum(2^(n-k)*binomial(n-1,k-1)*a(k-1),k,1,n); /* _Vladimir Kruchinin_, Nov 28 2011 */
%o (SageMath)
%o def A004211(n): return sum(2^(n-k)*stirling_number2(n, k) for k in (0..n))
%o print([A004211(n) for n in range(21)]) # _Peter Luschny_, Apr 15 2020
%Y Cf. A075497 (row sums).
%Y Cf. A038207.
%Y Cf. A000110 (RGS where s(k) <= F(k) + 1), A004212 (RGS where s(k) <= F(k) + 3), A004213 (s(k) <= F(k) + 4), A005011 (s(k) <= F(k) + 5), A005012 (s(k) <= F(k) + 6), A075506 (s(k) <= F(k) + 7), A075507 (s(k) <= F(k) + 8), A075508 (s(k) <= F(k) + 9), A075509 (s(k) <= F(k) + 10).
%Y Cf. A000587, A009235, A317996, A318179 - A318181.
%Y Main diagonal of A261275.
%Y Cf. A034691, A075729, A109457.
%K nonn,easy,nice,eigen
%O 0,3
%A _N. J. A. Sloane_