login
This site is supported by donations to The OEIS Foundation.

 

Logo


Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
A004211 Shifts one place left under 2nd order binomial transform.
(Formerly M2900)
25
1, 1, 3, 11, 49, 257, 1539, 10299, 75905, 609441, 5284451, 49134923, 487026929, 5120905441, 56878092067, 664920021819, 8155340557697, 104652541401025, 1401572711758403, 19546873773314571, 283314887789276721 (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

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

P. Barry, Constructing Exponential Riordan Arrays from Their A and Z Sequences, Journal of Integer Sequences, 17 (2014), #14.2.6.

D. Callan (Proposer), Problem 11567, Amer. Math. Monthly, 118 (2011), 371-378.

I. M. Gessel, Applications of the classical umbral calculus, arXiv:math/0108121v3 [math.CO], 2001.

Adam M. Goyt, 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.

N. J. A. Sloane, Transforms

FORMULA

O.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(2*t))) = exp((exp(2*x)-1)/2). - Joerg Arndt, Apr 30 2011 and May 13 2011

a(n) = sum(2^(n-k)*stirling2(n, k), k=0..n). - Emeric Deutsch, Feb 11 2002

G.f.: sum{k>=0, x^k/prod[l=1..k, 1-2*l*x]}. - Ralf Stephan, Apr 18 2004

Stirling transform of A000085. - Vladeta Jovovic May 14 2004

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

Define f_1(x),f_2(x),... such that f_1(x)=e^x, f_{n+1}(x)=diff(x*f_n(x),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+2*x)*d/dx. Cf. A000110. - Peter Bala, Nov 25 2011

G.f. A(x) satisfies A(x)=1+x/(1-2*x)*A(2*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

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, 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. 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 + 2*x/(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 + 2*x - 2*x*(k+1)/E(k+1)); (continued fraction, 2-step). - Sergei N. Gladkovskii, Sep 21 2012

a(n) = -1 + 2*sum(k=0..n, C(n,k)*A166922(k)). - Peter Luschny, Nov 01 2012

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.

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

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

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

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

For n > 0, a(n) = exp(-1/2)*sum(k > 0, (2*k)^n/k!/2^k) - Vladimir Reshetnikov, May 09 2013

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

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

Sum_{k=0..n} C(n,k)*a(k)*a(n-k) = 2^n*Bell(n) = A055882(n). - Vaclav Kotesovec, Apr 03 2016

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)

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(2*x))); /* = 1 + x + 3/2*x^2 + 11/6*x^3 + ... */

/* egf=exp(1/2*(exp(2*x)-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]

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.

Sequence in context: A268414 A074528 A246985 * A180869 A001339 A012316

Adjacent sequences:  A004208 A004209 A004210 * A004212 A004213 A004214

KEYWORD

nonn,easy,nice,eigen

AUTHOR

N. J. A. Sloane

STATUS

approved

Lookup | Welcome | Wiki | Register | Music | Plot 2 | Demos | Index | Browse | More | WebCam
Contribute new seq. or comment | Format | Style Sheet | Transforms | Superseeker | Recent | More pages
The OEIS Community | Maintained by The OEIS Foundation Inc.

License Agreements, Terms of Use, Privacy Policy .

Last modified May 23 01:01 EDT 2017. Contains 286908 sequences.