cp's OEIS Frontend

This is a front-end for the Online Encyclopedia of Integer Sequences, made by Christian Perfect. The idea is to provide OEIS entries in non-ancient HTML, and then to think about how they're presented visually. The source code is on GitHub.

Showing 1-5 of 5 results.

A005773 Number of directed animals of size n (or directed n-ominoes in standard position).

Original entry on oeis.org

1, 1, 2, 5, 13, 35, 96, 267, 750, 2123, 6046, 17303, 49721, 143365, 414584, 1201917, 3492117, 10165779, 29643870, 86574831, 253188111, 741365049, 2173243128, 6377181825, 18730782252, 55062586341, 161995031226, 476941691177, 1405155255055, 4142457992363
Offset: 0

Views

Author

N. J. A. Sloane, Simon Plouffe, Clark Kimberling

Keywords

Comments

This sequence, with first term a(0) deleted, appears to be determined by the conditions that the diagonal and first superdiagonal of U are {1,1,1,1,...} and {2,3,4,5,...,n+1,...} respectively, where A=LU is the LU factorization of the Hankel matrix A given by [{a(1),a(2),...}, {a(2),a(3),...}, ..., {a(n),a(n+1),...}, ...]. - John W. Layman, Jul 21 2000
Also the number of base 3 n-digit numbers (not starting with 0) with digit sum n. For the analogous sequence in base 10 see A071976, see example. - John W. Layman, Jun 22 2002
Also number of paths in an n X n grid from (0,0) to the line x=n-1, using only steps U=(1,1), H=(1,0) and D=(1,-1) (i.e., left factors of length n-1 of Motzkin paths, palindromic Motzkin paths of length 2n-2 or 2n-1). Example: a(3)=5, namely, HH, UD, HU, UH and UU. Also number of ordered trees with n edges and having nonroot nodes of outdegree at most 2. - Emeric Deutsch, Aug 01 2002
Number of symmetric Dyck paths of semilength 2n-1 with no peaks at even level. Example: a(3)=5 because we have UDUDUDUDUD, UDUUUDDDUD, UUUUUDDDDD, UUUDUDUDDD and UUUDDUUDDD, where U=(1,1) and D=(1,-1). Also number of symmetric Dyck paths of semilength 2n with no peaks at even level. Example: a(3)=5 because we have UDUDUDUDUDUD, UDUUUDUDDDUD, UUUDUDUDUDDD, UUUUUDUDDDDD and UUUDDDUUUDDD. - Emeric Deutsch, Nov 21 2003
a(n) is the sum of the (n-1)-st central trinomial coefficient and its predecessor. Example: a(4) = 6 + 7 and (1 + x + x^2)^3 = ... + 6*x^2 + 7*x^3 + ... . - David Callan, Feb 07 2004
a(n) is the number of UDU-free paths of n upsteps (U) and n downsteps (D) that start U (n>=1). Example: a(2)=2 counts UUDD, UDDU. - David Callan, Aug 18 2004
a(n) is also the number of Grand-Dyck paths of semilength n starting with an up-step and avoiding the pattern DUD. - David Bevan, Nov 19 2019
Hankel transform of a(n+1) = [1,2,5,13,35,96,...] gives A000012 = [1,1,1,1,1,1,...]. - Philippe Deléham, Oct 24 2007
Equals row sums of triangle A136787 starting (1, 2, 5, 13, 35, ...). - Gary W. Adamson, Jan 21 2008
a(n) is the number of permutations on [n] that avoid the patterns 1-23-4 and 1-3-2, where the omission of a dash in a pattern means the permutation entries must be adjacent. Example: a(4) = 13 counts all 14 (Catalan number) (1-3-2)-avoiding permutations on [4] except 1234. - David Callan, Jul 22 2008
a(n) is also the number of involutions of length 2n-2 which are invariant under the reverse-complement map and have no decreasing subsequences of length 4. - Eric S. Egge, Oct 21 2008
Hankel transform is A010892. - Paul Barry, Jan 19 2009
a(n) is the number of Dyck words of semilength n with no DUUU. For example, a(4) = 14-1 = 13 because there is only one Dyck 4-word containing DUUU, namely UDUUUDDD. - Eric Rowland, Apr 21 2009
Inverse binomial transform of A024718. - Philippe Deléham, Dec 13 2009
Let w(i, j, n) denote walks in N^2 which satisfy the multivariate recurrence
w(i, j, n) = w(i - 1, j, n - 1) + w(i, j - 1, n - 1) + w(i + 1, j - 1,n - 1) with boundary conditions w(0,0,0) = 1 and w(i,j,n) = 0 if i or j or n is < 0. Let alpha(n) the number of such walks of length n, alpha(n) = Sum_{i = 0..n, j=0..n} w(i, j, n). Then a(n+1) = alpha(n). - Peter Luschny, May 21 2011
Number of length-n strings [d(0),d(1),d(2),...,d(n-1)] where 0 <= d(k) <= k and abs(d(k) - d(k-1)) <= 1 (smooth factorial numbers, see example). - Joerg Arndt, Nov 10 2012
a(n) is the number of n-multisets of {1,...,n} containing no pair of consecutive integers (e.g., 111, 113, 133, 222, 333 for n=3). - David Bevan, Jun 10 2013
a(n) is also the number of n-multisets of [n] in which no integer except n occurs exactly once (e.g., 111, 113, 222, 223, 333 for n=3). - David Bevan, Nov 19 2019
Number of minimax elements in the affine Weyl group of the Lie algebra so(2n+1) or the Lie algebra sp(2n). See Panyushev 2005. Cf. A245455. - Peter Bala, Jul 22 2014
The shifted, signed array belongs to an interpolated family of arrays associated to the Catalan A000108 (t=1), and Riordan, or Motzkin sums A005043 (t=0), with the interpolating (here t=-2) o.g.f. G(x,t) = (1-sqrt(1-4x/(1+(1-t)x)))/2 and inverse o.g.f. Ginv(x,t) = x(1-x)/(1+(t-1)x(1-x)) (A057682). See A091867 for more info on this family. - Tom Copeland, Nov 09 2014
Alternatively, this sequence corresponds to the number of positive walks with n steps {-1,0,1} starting at the origin, ending at any altitude, and staying strictly above the x-axis. - David Nguyen, Dec 01 2016
Let N be a squarefree number with n prime factors: p_1 < p_2 < ... < p_n. Let D be its set of divisors, E the subset of D X D made of the (d_1, d_2) for which, provided that we know which p_i are in d_1, which p_i are in d_2, d_1 <= d_2 is provable without needing to know the numerical values of the p_i. It appears that a(n+1) is the number of (d_1, d_2) in E such that d_1 and d_2 are coprime. - Luc Rousseau, Aug 21 2017
Number of ordered rooted trees with n non-root nodes and all non-root nodes having outdegrees 1 or 2. - Andrew Howroyd, Dec 04 2017
a(n) is the number of compositions (ordered partitions) of n where there are A001006(k-1) sorts of part k (see formula by Andrew Howroyd, Dec 04 2017). - Joerg Arndt, Jan 26 2024

Examples

			G.f. = 1 + x + 2*x^2 + 5*x^3 + 13*x^4 + 35*x^5 + 96*x^6 + 267*x^7 + ...
a(3) = 5, a(4) = 13; since the top row of M^3 = (5, 5, 2, 1, ...)
From _Eric Rowland_, Sep 25 2021: (Start)
There are a(4) = 13 directed animals of size 4:
  O
  O    O    O    OO              O         O
  O    O    OO   O    OO   O    OO   OOO   O    O    OO    O
  O    OO   O    O    OO   OOO  O    O    OO   OOO  OO   OOO  OOOO
(End)
From _Joerg Arndt_, Nov 10 2012: (Start)
There are a(4)=13 smooth factorial numbers of length 4 (dots for zeros):
[ 1]   [ . . . . ]
[ 2]   [ . . . 1 ]
[ 3]   [ . . 1 . ]
[ 4]   [ . . 1 1 ]
[ 5]   [ . . 1 2 ]
[ 6]   [ . 1 . . ]
[ 7]   [ . 1 . 1 ]
[ 8]   [ . 1 1 . ]
[ 9]   [ . 1 1 1 ]
[10]   [ . 1 1 2 ]
[11]   [ . 1 2 1 ]
[12]   [ . 1 2 2 ]
[13]   [ . 1 2 3 ]
(End)
From _Joerg Arndt_, Nov 22 2012: (Start)
There are a(4)=13 base 3 4-digit numbers (not starting with 0) with digit sum 4:
[ 1]   [ 2 2 . . ]
[ 2]   [ 2 1 1 . ]
[ 3]   [ 1 2 1 . ]
[ 4]   [ 2 . 2 . ]
[ 5]   [ 1 1 2 . ]
[ 6]   [ 2 1 . 1 ]
[ 7]   [ 1 2 . 1 ]
[ 8]   [ 2 . 1 1 ]
[ 9]   [ 1 1 1 1 ]
[10]   [ 1 . 2 1 ]
[11]   [ 2 . . 2 ]
[12]   [ 1 1 . 2 ]
[13]   [ 1 . 1 2 ]
(End)

References

  • J. E. Goodman and J. O'Rourke, editors, Handbook of Discrete and Computational Geometry, CRC Press, 1997, p. 237.
  • T. Mansour, Combinatorics of Set Partitions, Discrete Mathematics and Its Applications, CRC Press, 2013, p. 377.
  • N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).
  • R. P. Stanley, Enumerative Combinatorics, Cambridge, Vol. 2, 1999; see Problem 6.46a.
  • R. P. Stanley, Catalan Numbers, Cambridge, 2015, p. 132.

Links

Crossrefs

See also A005775. Inverse of A001006. Also sum of numbers in row n+1 of array T in A026300. Leading column of array in A038622.
The right edge of the triangle A062105.
Column k=3 of A295679.
Interpolates between Motzkin numbers (A001006) and Catalan numbers (A000108). Cf. A054391, A054392, A054393, A055898.
Except for the first term a(0), sequence is the binomial transform of A001405.
a(n) = A002426(n-1) + A005717(n-1) if n > 0. - Emeric Deutsch, Aug 14 2002
Cf. A001405, A001700, A132814, A245455.
Cf. A005043, A005717, A057682, A064189, A091867.

Programs

  • Haskell
    a005773 n = a005773_list !! n
a005773_list = 1 : f a001006_list [] where
   f (x:xs) ys = y : f xs (y : ys) where
     y = x + sum (zipWith (*) a001006_list ys)
-- Reinhard Zumkeller, Mar 30 2012
  • Magma
    R:=PowerSeriesRing(Rationals(), 30); Coefficients(R!( 2*x/(3*x-1+Sqrt(1-2*x-3*x^2)) )); // G. C. Greubel, Apr 05 2019
  • Maple
    seq( sum(binomial(i-1, k)*binomial(i-k, k), k=0..floor(i/2)), i=0..30 ); # Detlef Pauly (dettodet(AT)yahoo.de), Nov 09 2001
A005773:=proc(n::integer)
local i, j, A, istart, iend, KartProd, Liste, Term, delta;
    A:=0;
    for i from 0 to n do
        Liste[i]:=NULL;
        istart[i]:=0;
        iend[i]:=n-i+1:
        for j from istart[i] to iend[i] do
            Liste[i]:=Liste[i], j;
        end do;
        Liste[i]:=[Liste[i]]:
    end do;
    KartProd:=cartprod([seq(Liste[i], i=1..n)]);
    while not KartProd[finished] do
        Term:=KartProd[nextvalue]();
        delta:=1;
        for i from 1 to n-1 do
            if (op(i, Term) - op(i+1, Term))^2 >= 2 then
                delta:=0;
                break;
            end if;
        end do;
        A:=A+delta;
    end do;
end proc; # Thomas Wieder, Feb 22 2009:
# n -> [a(0),a(1),..,a(n)]
A005773_list := proc(n) local W, m, j, i;
W := proc(i, j, n) option remember;
if min(i, j, n) < 0 or max(i, j) > n then 0
elif n = 0 then if i = 0 and j = 0 then 1 else 0 fi
else W(i-1,j,n-1)+W(i,j-1,n-1)+W(i+1,j-1,n-1) fi end:
[1,seq(add(add(W(i,j,m),i=0..m),j=0..m),m=0..n-1)] end:
A005773_list(27); # Peter Luschny, May 21 2011
A005773 := proc(n)
    option remember;
    if n <= 1 then
        1 ;
    else
        2*n*procname(n-1)+3*(n-2)*procname(n-2) ;
        %/n ;
    end if;
end proc:
seq(A005773(n),n=0..10) ; # R. J. Mathar, Jul 25 2017
  • Mathematica
    CoefficientList[Series[(2x)/(3x-1+Sqrt[1-2x-3x^2]), {x,0,40}], x] (* Harvey P. Dale, Apr 03 2011 *)
a[0]=1; a[n_] := Sum[k/n*Sum[Binomial[n, j]*Binomial[j, 2*j-n-k], {j, 0, n}], {k, 1, n}]; Table[a[n], {n, 0, 40}] (* Jean-François Alcover, Mar 31 2015, after Vladimir Kruchinin *)
A005773[n_] := 2 (-1)^(n+1) JacobiP[n - 1, 3, -n -1/2, -7] / (n^2 + n); A005773[0] := 1; Table[A005773[n], {n, 0, 27}] (* Peter Luschny, May 25 2021 *)
  • PARI
    a(n)=if(n<2,n>=0,(2*n*a(n-1)+3*(n-2)*a(n-2))/n)
  • PARI
    for(n=0, 27, print1(if(n==0, 1, sum(k=0, n-1, (-1)^(n - 1 + k)*binomial(n - 1, k)*binomial(2*k + 1, k + 1))),", ")) \\ Indranil Ghosh, Mar 14 2017
  • PARI
    Vec(1/(1-serreverse(x*(1-x)/(1-x^3) + O(x*x^25)))) \\ Andrew Howroyd, Dec 04 2017
  • Sage
    def da():
    a, b, c, d, n = 0, 1, 1, -1, 1
    yield 1
    yield 1
    while True:
        yield b + (-1)^n*d
        n += 1
        a, b = b, (3*(n-1)*n*a+(2*n-1)*n*b)//((n+1)*(n-1))
        c, d = d, (3*(n-1)*c-(2*n-1)*d)//n
A005773 = da()
print([next(A005773) for  in range(28)]) # _Peter Luschny, May 16 2016
  • Sage
    (2*x/(3*x-1+sqrt(1-2*x-3*x^2))).series(x, 30).coefficients(x, sparse=False) # G. C. Greubel, Apr 05 2019

Formula

G.f.: 2*x/(3*x-1+sqrt(1-2*x-3*x^2)). - Len Smiley
Also a(0)=1, a(n) = Sum_{k=0..n-1} M(k)*a(n-k-1), where M(n) are the Motzkin numbers (A001006).
D-finite with recurrence n*a(n) = 2*n*a(n-1) + 3*(n-2)*a(n-2), a(0)=a(1)=1. - Michael Somos, Feb 02 2002
G.f.: 1/2+(1/2)*((1+x)/(1-3*x))^(1/2). Related to Motzkin numbers A001006 by a(n+1) = 3*a(n) - A001006(n-1) [see Yaqubi Lemma 2.6].
a(n) = Sum_{q=0..n} binomial(q, floor(q/2))*binomial(n-1, q) for n > 0. - Emeric Deutsch, Aug 15 2002
From Paul Barry, Jun 22 2004: (Start)
a(n+1) = Sum_{k=0..n} (-1)^(n+k)*C(n, k)*C(2*k+1, k+1).
a(n) = 0^n + Sum_{k=0..n-1} (-1)^(n+k-1)*C(n-1, k)*C(2*k+1, k+1). (End)
a(n+1) = Sum_{k=0..n} (-1)^k*3^(n-k)*binomial(n, k)*A000108(k). - Paul Barry, Jan 27 2005
Starting (1, 2, 5, 13, ...) gives binomial transform of A001405 and inverse binomial transform of A001700. - Gary W. Adamson, Aug 31 2007
Starting (1, 2, 5, 13, 35, 96, ...) gives row sums of triangle A132814. - Gary W. Adamson, Aug 31 2007
G.f.: 1/(1-x/(1-x-x^2/(1-x-x^2/(1-x-x^2/(1-x-x^2/(1-x-x^2/(1-... (continued fraction). - Paul Barry, Jan 19 2009
G.f.: 1+x/(1-2*x-x^2/(1-x-x^2/(1-x-x^2/(1-x-x^2/(1-.... (continued fraction). - Paul Barry, Jan 19 2009
a(n) = Sum_{l_1=0..n+1} Sum_{l_2=0..n}...Sum_{l_i=0..n-i}...Sum_{l_n=0..1} delta(l_1,l_2,...,l_i,...,l_n) where delta(l_1,l_2,...,l_i,...,l_n) = 0 if any (l_i - l_(i+1))^2 >= 2 for i=1..n-1 and delta(l_1,l_2,..., l_i,...,l_n) = 1 otherwise. - Thomas Wieder, Feb 25 2009
INVERT transform of offset Motzkin numbers (A001006): (a(n)){n>=1}=(1,1,2,4,9,21,...). - _David Callan, Aug 27 2009
A005773(n) = ((n+3)*A001006(n+1) + (n-3)*A001006(n)) * (n+2)/(18*n) for n > 0. - Mark van Hoeij, Jul 02 2010
a(n) = Sum_{k=1..n} (k/n * Sum_{j=0..n} binomial(n,j)*binomial(j,2*j-n-k)). - Vladimir Kruchinin, Sep 06 2010
a(0) = 1; a(n+1) = Sum_{t=0..n} n!/((n-t)!*ceiling(t/2)!*floor(t/2)!). - Andrew S. Hays, Feb 02 2011
a(n) = leftmost column term of M^n*V, where M = an infinite quadradiagonal matrix with all 1's in the main, super and subdiagonals, [1,0,0,0,...] in the diagonal starting at position (2,0); and rest zeros. V = vector [1,0,0,0,...]. - Gary W. Adamson, Jun 16 2011
From Gary W. Adamson, Jul 29 2011: (Start)
a(n) = upper left term of M^n, a(n+1) = sum of top row terms of M^n; M = an infinite square production matrix in which the main diagonal is (1,1,0,0,0,...) as follows:
1, 1, 0, 0, 0, 0, ...
1, 1, 1, 0, 0, 0, ...
1, 1, 0, 1, 0, 0, ...
1, 1, 1, 0, 1, 0, ...
1, 1, 1, 1, 0, 1, ...
1, 1, 1, 1, 1, 0, ... (End)
Limit_{n->oo} a(n+1)/a(n) = 3.0 = lim_{n->oo} (1 + 2*cos(Pi/n)). - Gary W. Adamson, Feb 10 2012
a(n) = A025565(n+1) / 2 for n > 0. - Reinhard Zumkeller, Mar 30 2012
With first term deleted: E.g.f.: a(n) = n! * [x^n] exp(x)*(BesselI(0, 2*x) + BesselI(1, 2*x)). - Peter Luschny, Aug 25 2012
G.f.: G(0)/2 + 1/2, where G(k) = 1 + 2*x*(4*k+1)/( (2*k+1)*(1+x) - x*(1+x)*(2*k+1)*(4*k+3)/(x*(4*k+3) + (1+x)*(k+1)/G(k+1))); (continued fraction). - Sergei N. Gladkovskii, Jun 24 2013
a(n) ~ 3^(n-1/2)/sqrt(Pi*n). - Vaclav Kotesovec, Jul 30 2013
For n > 0, a(n) = (-1)^(n+1) * hypergeom([3/2, 1-n], [2], 4). - Vladimir Reshetnikov, Apr 25 2016
a(n) = GegenbauerC(n-2,-n+1,-1/2) + GegenbauerC(n-1,-n+1,-1/2) for n >= 1. - Peter Luschny, May 12 2016
0 = a(n)*(+9*a(n+1) + 18*a(n+2) - 9*a(n+3)) + a(n+1)*(-6*a(n+1) + 7*a(n+2) - 2*a(n+3)) + a(n+2)*(-2*a(n+2) + a(n+3)) for n >= 0. - Michael Somos, Dec 01 2016
G.f.: 1/(1-x*G(x)) where G(x) is g.f. of A001006. - Andrew Howroyd, Dec 04 2017
a(n) = (-1)^(n + 1)*2*JacobiP(n - 1, 3, -n - 1/2, -7)/(n^2 + n). - Peter Luschny, May 25 2021
a(n+1) = A005043(n) + 2*A005717(n) for n >= 1. - Peter Bala, Feb 11 2022
a(n) = Sum_{k=0..n-1} A064189(n-1,k) for n >= 1. - Alois P. Heinz, Aug 29 2022

A038622 Triangular array that counts rooted polyominoes.

Original entry on oeis.org

1, 2, 1, 5, 3, 1, 13, 9, 4, 1, 35, 26, 14, 5, 1, 96, 75, 45, 20, 6, 1, 267, 216, 140, 71, 27, 7, 1, 750, 623, 427, 238, 105, 35, 8, 1, 2123, 1800, 1288, 770, 378, 148, 44, 9, 1, 6046, 5211, 3858, 2436, 1296, 570, 201, 54, 10, 1, 17303, 15115, 11505, 7590, 4302, 2067, 825, 265
Offset: 0

Views

Author

N. J. A. Sloane, torsten.sillke(AT)lhsystems.com

Keywords

Comments

The PARI program gives any row k and any n-th term for this triangular array in square or right triangle array format. - Randall L Rathbun, Jan 20 2002
Triangle T(n,k), 0 <= k <= n, read by rows given by: T(0,0)=1, T(n,k)=0 if k < 0 or if k > n, T(n,0) = 2*T(n-1,0) + T(n-1,1), T(n,k) = T(n-1,k-1) + T(n-1,k) + T(n-1,k+1) for k >= 1. - Philippe Deléham, Mar 27 2007
This triangle belongs to the family of triangles defined by: T(0,0)=1, T(n,k)=0 if k < 0 or if k > n, T(n,0) = x*T(n-1,0) + T(n-1,1), T(n,k) = T(n-1,k-1) + y*T(n-1,k) + T(n-1,k+1) for k >= 1. Other triangles arise by choosing different values for (x,y): (0,0) -> A053121; (0,1) -> A089942; (0,2) -> A126093; (0,3) -> A126970; (1,0)-> A061554; (1,1) -> A064189; (1,2) -> A039599; (1,3) -> A110877; (1,4) -> A124576; (2,0) -> A126075; (2,1) -> A038622; (2,2) -> A039598; (2,3) -> A124733; (2,4) -> A124575; (3,0) -> A126953; (3,1) -> A126954; (3,2) -> A111418; (3,3) -> A091965; (3,4) -> A124574; (4,3) -> A126791; (4,4) -> A052179; (4,5) -> A126331; (5,5) -> A125906. - Philippe Deléham, Sep 25 2007
Triangle read by rows = partial sums of A064189 terms starting from the right. - Gary W. Adamson, Oct 25 2008
Column k has e.g.f. exp(x)*(Bessel_I(k,2x)+Bessel_I(k+1,2x)). - Paul Barry, Mar 08 2011

Examples

			From _Paul Barry_, Mar 08 2011: (Start)
Triangle begins
     1;
     2,    1;
     5,    3,    1;
    13,    9,    4,   1;
    35,   26,   14,   5,   1;
    96,   75,   45,  20,   6,   1;
   267,  216,  140,  71,  27,   7,  1;
   750,  623,  427, 238, 105,  35,  8, 1;
  2123, 1800, 1288, 770, 378, 148, 44, 9, 1;
Production matrix is
  2, 1,
  1, 1, 1,
  0, 1, 1, 1,
  0, 0, 1, 1, 1,
  0, 0, 0, 1, 1, 1,
  0, 0, 0, 0, 1, 1, 1,
  0, 0, 0, 0, 0, 1, 1, 1,
  0, 0, 0, 0, 0, 0, 1, 1, 1,
  0, 0, 0, 0, 0, 0, 0, 1, 1, 1
(End)

Links

Crossrefs

Cf. A005773 (1st column), A005774 (2nd column), A005775, A066822, A000244 (row sums).
Cf. A064189, A007318, A061554, A092392.

Programs

  • Haskell
    import Data.List (transpose)
a038622 n k = a038622_tabl !! n !! k
a038622_row n = a038622_tabl !! n
a038622_tabl = iterate (\row -> map sum $
   transpose [tail row ++ [0,0], row ++ [0], [head row] ++ row]) [1]
-- Reinhard Zumkeller, Feb 26 2013
  • Maple
    T := (n,k) -> simplify(GegenbauerC(n-k,-n+1,-1/2)+GegenbauerC(n-k-1,-n+1,-1/2)):
for n from 1 to 9 do seq(T(n,k),k=1..n) od; # Peter Luschny, May 12 2016
  • Mathematica
    nmax = 10; t[n_ /; n > 0, k_ /; k >= 1] := t[n, k] = t[n-1, k-1] + t[n-1, k] + t[n-1, k+1]; t[0, 0] = 1; t[0, ] = 0; t[?Negative, ?Negative] = 0; t[n, 0] := 2 t[n-1, 0] + t[n-1, 1]; Flatten[ Table[ t[n, k], {n, 0, nmax}, {k, 0, n}]](* Jean-François Alcover, Nov 09 2011 *)
  • PARI
    s=[0,1]; {A038622(n,k)=if(n==0,1,t=(2*(n+k)*(n+k-1)*s[2]+3*(n+k-1)*(n+k-2)*s[1])/((n+2*k-1)*n); s[1]=s[2]; s[2]=t; t)}

Formula

a(n, k) = a(n-1, k-1) + a(n-1, k) + a(n-1, k+1) for k>0, a(n, k) = 2*a(n-1, k) + a(n-1, k+1) for k=0.
Riordan array ((sqrt(1-2x-3x^2)+3x-1)/(2x(1-3x)),(1-x-sqrt(1-2x-3x^2))/(2x)). Inverse of Riordan array ((1-x)/(1+x+x^2),x/(1+x+x^2)). First column is A005773(n+1). Row sums are 3^n (A000244). If L=A038622, then L*L' is the Hankel matrix for A005773(n+1), where L' is the transpose of L. - Paul Barry, Sep 18 2006
T(n,k) = GegenbauerC(n-k,-n+1,-1/2) + GegenbauerC(n-k-1,-n+1,-1/2). In this form also the missing first column of the triangle 1,1,1,3,7,19,... (cf. A002426) can be computed. - Peter Luschny, May 12 2016
From Peter Bala, Jul 12 2021: (Start)
T(n,k) = Sum_{j = k..n} binomial(n,j)*binomial(j,floor((j-k)/2)).
Matrix product of Riordan arrays ( 1/(1 - x), x/(1 - x) ) * ( (1 - x*c(x^2))/(1 - 2*x), x*c(x^2) ) = A007318 * A061554 (triangle version), where c(x) = (1 - sqrt(1 - 4*x))/(2*x) is the g.f. of the Catalan numbers A000108.
Triangle equals A007318^(-1) * A092392 * A007318. (End)
The n-th row polynomial R(n,x) equals the n-th degree Taylor polynomial of the function (1 + x)*(1 + x + x^2)^n expanded about the point x = 0. - Peter Bala, Sep 06 2022

Extensions

More terms from David W. Wilson

A005774 Number of directed animals of size n (k=1 column of A038622); number of (s(0), s(1), ..., s(n)) such that s(i) is a nonnegative integer and |s(i) - s(i-1)| <= 1 for i = 1,2,...,n, where s(0) = 2; also sum of row n+1 of array T in A026323.

Original entry on oeis.org

0, 1, 3, 9, 26, 75, 216, 623, 1800, 5211, 15115, 43923, 127854, 372749, 1088283, 3181545, 9312312, 27287091, 80038449, 234988827, 690513030, 2030695569, 5976418602, 17601021837, 51869858544, 152951628725, 451271872701, 1332147482253
Offset: 0

Views

Author

Simon Plouffe

Keywords

Comments

Number of ordered trees with n+1 edges, having root degree at least 2 and nonroot outdegrees at most 2. - Emeric Deutsch, Aug 02 2002
From Petkovsek's algorithm, this recurrence does not have any closed form solutions. So there is no hypergeometric closed form for a(n). - Herbert S. Wilf
Sum of two consecutive trinomial coefficients starting two positions before central one. Example: a(4) = 10+16 and (1 + x + x^2)^4 = ... + 10*x^2 + 16*x^3 + 19*x^4 + ... - David Callan, Feb 07 2004
Image of n (A001477) under the Motzkin related matrix A107131. Binomial transform of A037952. - Paul Barry, May 12 2005
a(n) = total number of ascents (maximal runs of consecutive upsteps) in all Motzkin (n+1)-paths. For example, the 9 Motzkin 4-paths are FFFF, FFUD, FUDF, FUFD, UDFF, UDUD, UFDF, UFFD, UUDD and they contain a total of 9 ascents and so a(3)=9 (U=upstep, D=downstep, F=flatstep). - David Callan, Aug 16 2006
Image of the sequence (0,1,2,3,3,3,...) under the array A122896. - Paul Barry, Sep 18 2006
This is some kind of Motzkin transform of A079978 because the substitution x-> x*A001006(x) in the independent variable of the g.f. A079978(x) yields 1,0 followed by this sequence here. - R. J. Mathar, Nov 08 2008

Examples

			G.f.: x + 3*x^2 + 9*x^3 + 26*x^4 + 75*x^5 + 216*x^6 + 623*x^7 + ...

References

  • N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).

Links

Crossrefs

Cf. A038622, A098494, A026010, A005773, A005775, A066822.

Programs

  • Haskell
    a005774 0 = 0
a005774 n = a038622 n 1 -- Reinhard Zumkeller, Feb 26 2013
  • Maple
    seq( add(binomial(i,k+1)*binomial(i-k,k), k=0..floor(i/2)), i=0..30 ); # Detlef Pauly (dettodet(AT)yahoo.de), Nov 09 2001
seq(simplify(GegenbauerC(n-2,-n,-1/2) + GegenbauerC(n-1,-n,-1/2)), n=0..27); # Peter Luschny, May 12 2016
  • Mathematica
    CoefficientList[Series[(1-x-Sqrt[1-2x-3x^2])/(x(1-3x+Sqrt[1-2x-3x^2])),{x,0,30}],x] (* Harvey P. Dale, Sep 20 2011 *)
RecurrenceTable[{a[0]==0, a[1]==1,a[n]==(2n(n+1)a[n-1]+3n(n-1)a[n-2])/ ((n+2)(n-1))},a,{n,30}] (* Harvey P. Dale, Nov 09 2012 *)
  • PARI
    s=[0,1]; {A005774(n)=k=(2*(n+2)*(n+1)*s[2]+3*(n+1)*n*s[1])/((n+3)*n); s[1]=s[2]; s[2]=k; k}
  • PARI
    {a(n) = if( n<2, n>0, (2 * (n+1) * n *a(n-1) + 3 * (n-1) * n * a(n-2)) / (n+2) / (n-1))}; /* Michael Somos, May 01 2003 */

Formula

Inverse binomial transform of [ 0, 1, 5, 21, 84, ... ] (A002054). - John W. Layman
D-finite with recurrence (n+2)*(n-1)*a(n) = 2*n*(n+1)*a(n-1) + 3*n*(n-1)*a(n-2) for all n in Z. - Michael Somos, May 01 2003
E.g.f.: exp(x)*(BesselI(1, 2*x)+BesselI(2, 2*x)). - Vladeta Jovovic, Jan 01 2004
G.f.: (1-x-sqrt(1-2x-3x^2))/(x(1-3x+sqrt(1-2x-3x^2))); a(n)= Sum_{k=0..n} C(k+1, n-k+1)*C(n, k)*k/(k+1); a(n) = Sum_{k=0..n} C(n, k)*C(k, floor((k-1)/2)). - Paul Barry, May 12 2005
Starting (1, 3, 9, 26, ...) = binomial transform of A026010: (1, 2, 4, 7, 14, 25, 50, 91, ...). - Gary W. Adamson, Oct 22 2007
a(n)*(2+n) = (4+4*n)*a(n-1) - n*a(n-2) + (12-6*n)*a(n-3). - Simon Plouffe, Feb 09 2012
a(n) ~ 3^(n+1/2) / sqrt(Pi*n). - Vaclav Kotesovec, Mar 10 2014
0 = a(n)*(+36*a(n+1) + 18*a(n+2) - 96*a(n+3) + 30*a(n+4)) + a(n+1)*(-6*a(n+1) + 49*a(n+2) - 26*a(n+3) + 3*a(n+4)) + a(n+2)*(+15*a(n+3) - 8*a(n+4)) + a(n+3)*(a(n+4)) if n >= 0. - Michael Somos, Aug 06 2014
a(n) = GegenbauerC(n-2,-n,-1/2) + GegenbauerC(n-1,-n,-1/2). - Peter Luschny, May 12 2016

Extensions

Further descriptions from Clark Kimberling

A066822 The fourth column of A038622, triangular array that counts rooted polyominoes.

Original entry on oeis.org

1, 5, 20, 71, 238, 770, 2436, 7590, 23397, 71566, 217646, 659022, 1988805, 5986176, 17980968, 53922096, 161492571, 483149385, 1444245936, 4314214443, 12880107548, 38436170366, 114657076900, 341926185770, 1019435748435, 3038815305981, 9056974493700
Offset: 0

Views

Author

Randall L Rathbun, Jan 19 2002

Keywords

Comments

There is a general solution for all rows of this triangular array: For the k-th row and n-th term on this row: a(0)=0; a(1)=1; a(n) = (2*k-1+n)*n*a(n) = 2*(n+k)*(n+k-1)*a(n-1) + 3*(n+k-1)*(n+k-2)*a(n-2).

Links

Crossrefs

Cf. A038622.
Cf. A005773, A005774, A005775.

Programs

  • Haskell
    a066822 = flip a038622 3 . (+ 3)  -- Reinhard Zumkeller, Feb 26 2013
  • Maple
    a := n -> simplify(GegenbauerC(n,-n+1-4,-1/2)+GegenbauerC(n-1,-n-3,-1/2)):
seq(a(n), n=0..20); # Peter Luschny, May 12 2016
  • Mathematica
    Table[GegenbauerC[n,-n-3,-1/2]+GegenbauerC[n-1,-n-3,-1/2],{n,0,40}] (* Harvey P. Dale, Feb 20 2017 *)
  • PARI
    s=[0,1]; {A038622(n,k)=if(n==0,1,t=(2*(n+k)*(n+k-1)*s[2]+3*(n+k-1)*(n+k-2)*s[1])/((n+2*k-1)*n); s[1]=s[2]; s[2]=t; t)}

Formula

a(0)=0; a(1)=1; (n+7)*n*a(n)=2*(n+4)*(n+3)*a(n-1) + 3*(n+3)*(n+2)*a(n-2).
a(n) = ((-3)^(1/2)/9)*(-2*(n+7)^(-1)*(n+4)*(-1)^n*hypergeom([3/2, n+6],[2],4/3)-(n+6)^(-1)*(-1)^n*(5*n+18)*hypergeom([3/2, n+5],[2],4/3)). - Mark van Hoeij, Oct 31 2011
a(n) ~ 3^(n+7/2) / sqrt(Pi*n). - Vaclav Kotesovec, Mar 10 2014
a(n) = GegenbauerC(n,-n+1-4,-1/2)+GegenbauerC(n-1,-n-3,-1/2). - Peter Luschny, May 12 2016

Extensions

More terms from Harvey P. Dale, Feb 20 2017

A383527 Partial sums of A005773.

Original entry on oeis.org

1, 2, 4, 9, 22, 57, 153, 420, 1170, 3293, 9339, 26642, 76363, 219728, 634312, 1836229, 5328346, 15494125, 45137995, 131712826, 384900937, 1126265986, 3299509114, 9676690939, 28407473191, 83470059532, 245465090758, 722406781935, 2127562036990, 6270020029353
Offset: 0

Views

Author

Mélika Tebni, Apr 29 2025

Keywords

Comments

For p prime of the form 4*k+3 (A002145), a(p) == 0 (mod p).
For p Pythagorean prime (A002144), a(p) - 2 == 0 (mod p).
a(n) (mod 2) = A010059(n).
a(A000069(n+1)) is even.
a(A001969(n+1)) is odd.

Links

Crossrefs

Cf. A000069, A001969, A002144, A002145, A005773, A005774, A005775, A010059, A097893, A122896, A167630, A210736, A211278, A257520.

Programs

  • Maple
    gf := (1 + sqrt((1 + x) / (1 - 3*x))) / (2*(1 - x)):
a := n-> coeff(series(gf, x, n+1), x, n):
seq(a(n), n = 0 .. 29);
# Recurrence:
a:= proc(n) option remember; `if`(n<=2, 2^n, 3*a(n-1) - (6/n-1)*a(n-2) + (6/n-3)*a(n-3)) end:
seq(a(n), n = 0 .. 29);
  • Mathematica
    Module[{a, n}, RecurrenceTable[{a[n] == 3*a[n-1] - (6-n)*a[n-2]/n + 3*(2-n)*a[n-3]/n, a[0] == 1, a[1] == 2, a[2] == 4}, a, {n, 0, 30}]] (* Paolo Xausa, May 05 2025 *)
  • Python
    from math import comb as C
def a(n):
  return sum(C(n, k)*abs(sum((-1)**j*C(k, j) for j in range(k//2 + 1))) for k in range(n + 1))
print([a(n) for n in range(30)])

Formula

First differences of A211278.
a(n) = Sum_{k=0..n} A167630(n, k).
Binomial transform of A210736 (see Python program).
G.f.: (1 + sqrt((1 + x) / (1 - 3*x))) / (2*(1 - x)).
E.g.f.: (Integral_{x=-oo..oo} BesselI(0,2*x) dx + (1 + BesselI(0,2*x)) / 2)*exp(x).
Recurrence: n*a(n) = 3*n*a(n-1) - (6-n)*a(n-2) + 3*(2-n)*a(n-3). If n <= 2, a(n) = 2^n.
a(n) ~ 3^(n + 1/2) / (2*sqrt(Pi*n)). - Vaclav Kotesovec, May 02 2025
From Mélika Tebni, May 09 2025: (Start)
a(n) = A257520(n) + A097893(n-1) for n > 0.
a(n) = Sum_{j=0..n}(Sum_{k=0..j} A122896(j, k)).
a(n+2) - 3*a(n+1) + 2*a(n) = A005774(n).
a(n+2) - 4*a(n+1) + 4*a(n) - a(n-1) = A005775(n) for n >= 3. (End)
Showing 1-5 of 5 results.

Started in 1964 by Neil J. A. Sloane | Maintained by The OEIS Foundation Inc.

Content is available under The OEIS End-User License Agreement.