|
| |
|
|
A005773
|
|
Number of directed animals of size n (or directed n-ominoes in standard position).
(Formerly M1443)
|
|
96
|
|
|
|
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
(list;
graph;
refs;
listen;
history;
text;
internal format)
|
|
|
|
OFFSET
|
0,3
|
|
|
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
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
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
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
|
|
|
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
|
|
|
|
FORMULA
|
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
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
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
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
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
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) = 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
a(n) = (-1)^(n + 1)*2*JacobiP(n - 1, 3, -n - 1/2, -7)/(n^2 + n). - Peter Luschny, May 25 2021
|
|
|
EXAMPLE
|
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, ...)
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)
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)
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)
|
|
|
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
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;
# 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:
option remember;
if n <= 1 then
1 ;
else
2*n*procname(n-1)+3*(n-2)*procname(n-2) ;
%/n ;
end if;
end proc:
|
|
|
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 *)
|
|
|
PROG
|
(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
(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)
(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
(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
(Magma) R<x>:=PowerSeriesRing(Rationals(), 30); Coefficients(R!( 2*x/(3*x-1+Sqrt(1-2*x-3*x^2)) )); // G. C. Greubel, Apr 05 2019
|
|
|
CROSSREFS
|
The right edge of the triangle A062105.
Except for the first term a(0), sequence is the binomial transform of A001405.
|
|
|
KEYWORD
|
nonn,easy,nice
|
|
|
AUTHOR
|
|
|
|
STATUS
|
approved
|
| |
|
|
