A004211 - OEIS

A004211

Shifts one place left under 2nd-order binomial transform.
(Formerly M2900)

1, 1, 3, 11, 49, 257, 1539, 10299, 75905, 609441, 5284451, 49134923, 487026929, 5120905441, 56878092067, 664920021819, 8155340557697, 104652541401025, 1401572711758403, 19546873773314571, 283314887789276721, 4259997696504874817, 66341623494636864963 (list; graph; refs; listen; history; text; internal format)

	OFFSET	`0,3`
	COMMENTS	`Equals the eigensequence of A038207, the square of Pascal's triangle. - Gary W. Adamson, Apr 10 2009` `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` `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` `It appears that the infinite set of "Shifts 1 place left under N-th order binomial transform" sequences has a production matrix of:` `1, N, 0, 0, 0, ...` `1, 1, N, 0, 0, ...` `1, 2, 1, N, 0, ...` `1, 3, 3, 1, N, ...` `... (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` `Number of "unlabeled" hierarchical orderings on set partitions of {1..n}, see comments on A034691. - Gus Wiseman, Mar 03 2016` `From Lorenzo Sauras Altuzarra, Jun 17 2022: (Start)` `Number of n-variate noncontradictory conjunctions of logical equalities of literals (modulo logical equivalence).` `Equivalently, number of n-variate noncontradictory Krom formulas with palindromic truth-vector (modulo logical equivalence).` `a(n) <= A109457(n). (End)`
	REFERENCES	`N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).`
	LINKS	`Vincenzo Librandi, Table of n, a(n) for n = 0..200` `Joerg Arndt, Matters Computational (The Fxtbook), section 17.3.5, pp. 366-368` `Paul Barry, Constructing Exponential Riordan Arrays from Their A and Z Sequences, Journal of Integer Sequences, 17 (2014), #14.2.6.` `Zhanar Berikkyzy, Pamela E. Harris, Anna Pun, Catherine Yan, and Chenchen Zhao, On the Limiting Vacillating Tableaux for Integer Sequences, arXiv:2208.13091 [math.CO], 2022.` `Zhanar Berikkyzy, Pamela E. Harris, Anna Pun, Catherine Yan, and Chenchen Zhao, Combinatorial Identities for Vacillating Tableaux, arXiv:2308.14183 [math.CO], 2023. See pp. 22, 29.` `David Callan (Proposer), Problem 11567, Amer. Math. Monthly, 118 (2011), 371-378.` `Agustina Czenky, Unoriented 2-dimensional TQFTs and the category Rep(S_t wr Z_2), arXiv:2306.08826 [math.QA], 2023. See p. 40.` `I. M. Gessel, Applications of the classical umbral calculus, arXiv:math/0108121v3 [math.CO], 2001.` `Adam M. Goyt and Lara K. Pudwell, Solution to Monthly Problem 11567, 14 May 2011.` `Adalbert Kerber, A matrix of combinatorial numbers related to the symmetric groups, Discrete Math., 21 (1978), 319-321.` `Adalbert Kerber, A matrix of combinatorial numbers related to the symmetric groups<, Discrete Math., 21 (1978), 319-321. [Annotated scanned copy]` `Huyile Liang, Jeffrey Remmel, and Sainan Zheng, Stieltjes moment sequences of polynomials, arXiv:1710.05795 [math.CO], 2017, see page 20.` `Janusz Milek, Quantum Implementation of Risk Analysis-relevant Copulas, arXiv:2002.07389 [stat.ME], 2020.` `N. J. A. Sloane, Transforms`
	FORMULA	`E.g.f. A(x) satisfies A'(x)/A(x) = e^(2x).` `E.g.f.: exp(sinh(x)exp(x)) = exp(int(t=0..x, exp(2t))) = exp((exp(2x)-1)/2). - Joerg Arndt, Apr 30 2011 and May 13 2011` `a(n) = Sum_{k=0..n} 2^(n-k)Stirling2(n, k). - Emeric Deutsch, Feb 11 2002` `G.f.: Sum_{k>=0} x^k/Product_{l=1..k} (1-2lx). - Ralf Stephan, Apr 18 2004` `Stirling transform of A000085. - Vladeta Jovovic May 14 2004` `O.g.f.: A(x) = 1/(1-x-2x^2/(1-3x-4x^2/(1-5x-6x^2/(1-... -(2n-1)x-2nx^2/(1- ...))))) (continued fraction). - Paul D. Hanna, Jan 17 2006` `Define f_1(x), f_2(x), ... such that f_1(x)=e^x, f_{n+1}(x) = (d/dx)(xf_n(x)), for n=2,3,.... Then a(n) = e^(-1/2)2^{n-1}f_n(1/2). - Milan Janjic, May 30 2008` `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` `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:` `1, 2, 0, 0, 0, ...` `1, 1, 2, 0, 0, ...` `1, 2, 1, 2, 0, ...` `1, 3, 3, 1, 2, ...` `... - Gary W. Adamson, Jul 29 2011` `a(n) = D^n(exp(x)) evaluated at x = 0, where D is the operator (1+2x)d/dx. Cf. A000110. - Peter Bala, Nov 25 2011` `G.f. A(x) satisfies A(x)=1+x/(1-2x)A(x/(1-2x)), 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]` Recurrence equation: a(n+1) = Sum_{k = 0..n} 2^(n-k)C(n,k)a(k). Written umbrally this is a(n+1) = (a+2)^n (expand the binomial and replace a^k with a(k)). More generally, af(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. 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. - Peter Bala, May 16 2012 `G.f.: (2/E(0) - 1)/x where E(k) = 1 + 1/(1 + 2x/(1 - 4(k+1)x/E(k+1))); (continued fraction, 3-step). - Sergei N. Gladkovskii, Sep 20 2012` `G.f.: (1/E(0)-1)/x where E(k) = 1 - x/(1 + 2x - 2x(k+1)/E(k+1)); (continued fraction, 2-step). - Sergei N. Gladkovskii, Sep 21 2012` `a(n) = -1 + 2Sum_{k=0..n} C(n,k)A166922(k). - Peter Luschny, Nov 01 2012` `G.f.: G(0)- 1/x where G(k) = 1 - (4xk-1)/(x - x^4/(x^3 - (4xk-1)(4xk+2x-1)(4xk+4x-1)/G(k+1) )); (continued fraction). - Sergei N. Gladkovskii, Jan 08 2013.` `G.f.: (G(0) - 1)/(x-1) where G(k) = 1 - 1/(1-2kx)/(1-x/(x-1/G(k+1) )); (continued fraction). - Sergei N. Gladkovskii, Jan 15 2013` `G.f.: -G(0) where G(k) = 1 + 2(1-kx)/(2kx - 1 - x(2kx - 1)/(x - 2(1-kx)/G(k+1) )); (continued fraction). - Sergei N. Gladkovskii, Jan 29 2013` `G.f.: 1/Q(0), where Q(k) = 1 - x/(1 - 2x(2k+1)/( 1 - x/(1 - 4x(k+1)/Q(k+1) ))); (continued fraction). - Sergei N. Gladkovskii, Apr 15 2013` `G.f.: 1 + x/Q(0), where Q(k)= 1 - x(2k+3) - x^2(2k+2)/Q(k+1); (continued fraction). - Sergei N. Gladkovskii, May 05 2013` `For n > 0, a(n) = exp(-1/2)Sum_{k > 0} (2k)^n/(k!2^k). - Vladimir Reshetnikov, May 09 2013` `G.f.: -(1+(2x+1)/G(0))/x, where G(k)= 2xk - x - 1 - 2(k+1)x^2/G(k+1); (continued fraction). - Sergei N. Gladkovskii, Jul 20 2013` `G.f.: T(0)/(1-x), where T(k) = 1 - 2x^2(k+1)/( 2x^2(k+1) - (1-x-2xk)(1-3x-2xk)/T(k+1) ); (continued fraction). - Sergei N. Gladkovskii, Oct 19 2013` `Sum_{k=0..n} C(n,k)a(k)a(n-k) = 2^nBell(n) = A055882(n). - Vaclav Kotesovec, Apr 03 2016` `a(n) ~ 2^n n^n * exp(n/LambertW(2n) - n - 1/2) / (sqrt(1 + LambertW(2n)) * LambertW(2*n)^n). - Vaclav Kotesovec, Jan 07 2019, simplified Oct 01 2022` `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`
	EXAMPLE	`From Joerg Arndt, Apr 30 2011: (Start)` `Restricted growth strings: a(0)=1 corresponds to the empty string;` `a(1)=1 to [0]; a(2)=3 to [00], [01], and [02]; a(3) = 11 to` `RGS F` `[ 1] [ 0 0 0 ] [ 0 0 0 ]` `[ 2] [ 0 0 1 ] [ 0 0 0 ]` `[ 3] [ 0 0 2 ] [ 0 0 2 ]` `[ 4] [ 0 1 0 ] [ 0 0 0 ]` `[ 5] [ 0 1 1 ] [ 0 0 0 ]` `[ 6] [ 0 1 2 ] [ 0 0 2 ]` `[ 7] [ 0 2 0 ] [ 0 2 2 ]` `[ 8] [ 0 2 1 ] [ 0 2 2 ]` `[ 9] [ 0 2 2 ] [ 0 2 2 ]` `[10] [ 0 2 3 ] [ 0 2 2 ]` `[11] [ 0 2 4 ] [ 0 2 4 ]. (End)` `From Lorenzo Sauras Altuzarra, Jun 17 2022: (Start)` `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).` `The third complete Bell polynomial is x^3 + 3 x y + z; and note that (2^0)^3 + 32^02^1 + 2^2 = 11.` `The truth-vector of (x <-> y) /\ (y <-> z), 10000001, is palindromic. (End)`
	MAPLE	a:= proc(n) option remember; `if`(n=0, 1, add( `a(n-j)binomial(n-1, j-1)2^(j-1), j=1..n))` `end:` `seq(a(n), n=0..23); # Alois P. Heinz, May 30 2021` `# second Maple program:` `a:= n -> CompleteBellB(n, seq(2^k, k=0..n)):` `seq(a(n), n=0..23); # Lorenzo Sauras Altuzarra, Jun 17 2022`
	MATHEMATICA	`Table[ Sum[ StirlingS2[ n, k ] 2^(-k+n), {k, n} ], {n, 16} ] (* Wouter Meeussen )` `Table[2^n BellB[n, 1/2], {n, 0, 20}] ( Vladimir Reshetnikov, Oct 20 2015 *)`
	PROG	`(PARI) x='x+O('x^66);` `egf=exp(intformal(exp(2x))); / = 1 + x + 3/2x^2 + 11/6x^3 + ... /` `/ egf=exp(1/2(exp(2x)-1)) / / alternative e.g.f. /` `Vec(serlaplace(egf)) / Joerg Arndt, Apr 30 2011 /` `(Maxima)` `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 /` `(SageMath)` `def A004211(n): return sum(2^(n-k)stirling_number2(n, k) for k in (0..n))` `print([A004211(n) for n in range(21)]) # Peter Luschny, Apr 15 2020`
	CROSSREFS	`Cf. A075497 (row sums).` `Cf. A038207. - Gary W. Adamson, Apr 10 2009` `Cf. A004212 (RGS where s(k)<=F(k)+3), A004213 (s(k)<=F(k)+4), A005011 (s(k)<=F(k)+5), A000110 (s(k)<=F(k)+1), A009235. - Joerg Arndt, Apr 30 2011` `Main diagonal of A261275.` `Cf. A034691, A075729, A109457.` `Sequence in context: A246985 A326521 A340813 * A180869 A357836 A356291` `Adjacent sequences: A004208 A004209 A004210 * A004212 A004213 A004214`
	KEYWORD	`nonn,easy,nice,eigen`
	AUTHOR	`N. J. A. Sloane`
	STATUS	`approved`