| Displaying 1-7 of 7 results found.
page
1
0, 0, 1, 12, 98, 684, 4403, 27048, 161412, 945288, 5466549, 31340628, 178604998, 1013573652, 5735117479, 32385232272, 182622362504, 1028897389008, 5793703249449, 32615362319580, 183593293074730, 1033535639454780, 5819389057957211, 32775522041862072, 184658694508103180
FORMULA
Recurrence: (n+6)*a(n) = 225*(6-n)*a(n-8) + 1020*(2*n-9)*a(n-7) + 5164*(3-n)*a(n-6) + 76*(78*n-117)*a(n-5) - 3590*n*a(n-4) + 36*(34*n+51)*a(n-3) - 236*(n+3)*a(n-2) + 12*(2*n+9)*a(n-1), n>=8.
Recurrence (of order 2): (n-2)*(n+6)*a(n) = 3*(n+1)*(2*n+3)*a(n-1) - n*(n+1)*a(n-2). - Vaclav Kotesovec, Mar 05 2014 a(n) ~ (3*sqrt(2)-4)^(7/2) * (3+2*sqrt(2))^(n+6) / (8*sqrt(Pi)*n^(3/2)). - Vaclav Kotesovec, Mar 05 2014
MATHEMATICA
CoefficientList[Series[(1-3*x-Sqrt[1-6*x+x^2])^4/(16*x^3)^2, {x, 0, 20}], x] (* Vaclav Kotesovec, Mar 05 2014 *)
PROG
(PARI) x='x+O('x^50); concat([0, 0], Vec((1-3*x-sqrt(1-6*x+x^2))^4/(16*x^3)^2)) \\ G. C. Greubel, Apr 05 2017
Schroeder's second problem (generalized parentheses); also called super-Catalan numbers or little Schroeder numbers.
(Formerly M2898 N1163)
+10
236
1, 1, 3, 11, 45, 197, 903, 4279, 20793, 103049, 518859, 2646723, 13648869, 71039373, 372693519, 1968801519, 10463578353, 55909013009, 300159426963, 1618362158587, 8759309660445, 47574827600981, 259215937709463, 1416461675464871
COMMENTS
If you are looking for the Schroeder numbers (a.k.a. large Schroder numbers, or big Schroeder numbers), see A006318. Yang & Jiang (2021) call these the small 2-Schroeder numbers. - N. J. A. Sloane, Mar 28 2021 There are two schools of thought about the index for the first term. I prefer the indexing a(0) = a(1) = 1, a(2) = 3, a(3) = 11, etc.
a(n) is the number of ways to insert parentheses in a string of n+1 symbols. The parentheses must be balanced but there is no restriction on the number of pairs of parentheses. The number of letters inside a pair of parentheses must be at least 2. Parentheses enclosing the whole string are ignored.
Also length of list produced by a variant of the Catalan producing iteration: replace each integer k with the list 0,1,..,k,k+1,k,...,1,0 and get the length a(n) of the resulting (flattened) list after n iterations. - Wouter Meeussen, Nov 11 2001 Stanley gives several other interpretations for these numbers.
Number of Schroeder paths of semilength n (i.e., lattice paths from (0,0) to (2n,0), with steps H=(2,0), U=(1,1) and D(1,-1) and not going below the x-axis) with no peaks at level 1. Example: a(2)=3 because among the six Schroeder paths of semilength two HH, UHD, UUDD, HUD, UDH and UDUD, only the first three have no peaks at level 1. - Emeric Deutsch, Dec 27 2003 a(n+1) is the number of Dyck n-paths in which the interior vertices of the ascents are colored white or black. - David Callan, Mar 14 2004 Number of possible schedules for n time slots in the first-come first-served (FCFS) printer policy.
a(n+1) is the number of pairs (u,v) of same-length compositions of n, 0's allowed in u but not in v and u dominates v (meaning u_1 >= v_1, u_1 + u_2 >= v_1 + v_2 and so on). For example, with n=2, a(3) counts (2,2), (1+1,1+1), (2+0,1+1). - David Callan, Jul 20 2005 The big Schroeder number ( A006318) is the number of Schroeder paths from (0,0) to (n,n) (subdiagonal paths with steps (1,0) (0,1) and (1,1)). These paths fall in two classes: those with steps on the main diagonal and those without. These two classes are equinumerous and the number of paths in either class is the little Schroeder number a(n) (half the big Schroeder number). - Marcelo Aguiar (maguiar(AT)math.tamu.edu), Oct 14 2005 With offset 0, a(n) = number of (colored) Motzkin (n-1)-paths with each upstep U getting one of 2 colors and each flatstep F getting one of 3 colors. Example. With their colors immediately following upsteps/flatsteps, a(2) = 3 counts F1, F2, F3 and a(3)=11 counts U1D, U2D, F1F1, F1F2, F1F3, F2F1, F2F2, F2F3, F3F1, F3F2, F3F3. - David Callan, Aug 16 2006 Shifts left when INVERT transform applied twice. - Alois P. Heinz, Apr 01 2009 Number of increasing tableaux of shape (n,n). An increasing tableau is a semistandard tableaux with strictly increasing rows and columns, and set of entries an initial segment of the positive integers. Example: a(2) = 3 because of the three tableaux (12)(34), (13)(24), (12)(23). - Oliver Pechenik, Apr 22 2014 Number of ordered trees with no vertex of outdegree 1 and having n+1 leaves (called sometimes Schröder trees). - Emeric Deutsch, Dec 13 2014 Number of dissections of a convex (n+2)-gon by nonintersecting diagonals. Example: a(2)=3 because for a square ABCD we have (i) no diagonal, (ii) dissection with diagonal AC, and (iii) dissection with diagonal BD. - Emeric Deutsch, Dec 13 2014 The little Schroeder numbers are the moments of the Marchenko-Pastur law for the case c=2 (although the moment m0 is 1/2 instead of 1): 1/2, 1, 3, 11, 45, 197, 903, ... - Jose-Javier Martinez, Apr 07 2015 Number of generalized Motzkin paths with no level steps at height 0, from (0,0) to (2n,0), and consisting of steps U=(1,1), D=(1,-1) and H2=(2,0). For example, for n=3, we have the 11 paths: UDUDUD, UUDDUD, UDUUDD, UH2DUD, UDUH2D, UH2H2D, UUDUDD, UUUDDD, UUH2DD, UUDH2D, UH2UDD. - José Luis Ramírez Ramírez, Apr 20 2015 Total number of (nonempty) faces of all dimensions in the associahedron K_{n+1} of dimension n-1. For example, K_4 (a pentagon) includes 5 vertices and 5 edges together with K_4 itself (5 + 5 + 1 = 11), while K_5 includes 14 vertices, 21 edges and 9 faces together with K_5 itself (14 + 21 + 9 + 1 = 45). - Noam Zeilberger, Sep 17 2018 a(n) is the number of interval posets of permutations with n minimal elements that have exactly two realizers, up to a shift by 1 in a(4). See M. Bouvel, L. Cioni, B. Izart, Theorem 17 page 13. - Mathilde Bouvel, Oct 21 2021 a(n) is the number of sequences of nonnegative integers (u_1, u_2, ..., u_n) such that (i) u_1 = 1, (ii) u_i <= i for all i, (iii) the nonzero u_i are weakly increasing. For example, a(2) = 3 counts 10, 11, 12, and a(3) = 11 counts 100, 101, 102, 103, 110, 111, 112, 113, 120, 122, 123. See link below. - David Callan, Dec 19 2021 a(n) is the number of parking functions of size n avoiding the patterns 132 and 213. - Lara Pudwell, Apr 10 2023 a(n+1) is the number of Schroeder paths from (0,0) to (2n,0) in which level steps at height 0 come in 2 colors. - Alexander Burstein, Jul 23 2023
REFERENCES
D. Arques and A. Giorgetti, Une bijection géometrique entre une famille d'hypercartes et une famille de polygones énumérées par la série de Schroeder, Discrete Math., 217 (2000), 17-32.
P Barry, Riordan arrays, generalized Narayana triangles, and series reversion, Linear Algebra and its Applications, 491 (2016) 343-385.
N. Bernasconi et al., On properties of random dissections and triangulations, Combinatorica, 30 (6) (2010), 627-654.
Miklos Bona, editor, Handbook of Enumerative Combinatorics, CRC Press, 2015, page 618.
Cameron, Peter J. Some treelike objects. Quart. J. Math. Oxford Ser. (2) 38 (1987), no. 150, 155--183. MR0891613 (89a:05009). See p. 155, also p. 179, line -9. - N. J. A. Sloane, Apr 18 2014 C. Coker, A family of eigensequences, Discrete Math. 282 (2004), 249-250.
L. Comtet, Advanced Combinatorics, Reidel, 1974, p. 57.
D. E. Davenport, L. W. Shapiro and L. C. Woodson, The Double Riordan Group, The Electronic Journal of Combinatorics, 18(2) (2012), #P33. - From N. J. A. Sloane, May 11 2012 E. Deutsch, A bijective proof of an equation linking the Schroeder numbers, large and small, Discrete Math., 241 (2001), 235-240.
Doslic, Tomislav and Veljan, Darko. Logarithmic behavior of some combinatorial sequences. Discrete Math. 308 (2008), no. 11, 2182--2212. MR2404544 (2009j:05019) - From N. J. A. Sloane, May 01 2012 Drmota, Michael; de Mier, Anna; Noy, Marc. Extremal statistics on non-crossing configurations. Discrete Math. 327 (2014), 103--117. MR3192420. See Eq. (2). - N. J. A. Sloane, May 18 2014 I. M. H. Etherington, On non-associative combinations, Proc. Royal Soc. Edinburgh, 59 (Part 2, 1938-39), 153-162.
I. M. H. Etherington, Some problems of non-associative combinations (I), Edinburgh Math. Notes, 32 (1940), pp. i-vi. Part II is by A. Erdelyi and I. M. H. Etherington, and is on pages vii-xiv of the same issue.
P. Flajolet and M. Noy, Analytic combinatorics of non-crossing permutations, Discrete Math., 204 (1999), 203-229, Section 3.1.
D. Foata and D. Zeilberger, A classic proof of a recurrence for a very classical sequence, J. Comb Thy A 80 380-384 1997
Wolfgang Gatterbauer, Dan Suciu, Dissociation and propagation for approximate lifted inference with standard relational database management systems, The VLDB Journal, February 2017, Volume 26, Issue 1, pp. 5-30; DOI 10.1007/s00778-016-0434-5
Ivan Geffner, Marc Noy, Counting Outerplanar Maps, Electronic Journal of Combinatorics 24(2) (2017), #P2.3
D. Gouyou-Beauchamps and B. Vauquelin, Deux proprietes combinatoires des nombres de Schroeder, Theor. Inform. Appl., 22 (1988), 361-388.
N. S. S. Gu, N. Y. Li and T. Mansour, 2-Binary trees: bijections and related issues, Discr. Math., 308 (2008), 1209-1221.
P.-Y. Huang, S.-C. Liu, Y.-N. Yeh, Congruences of Finite Summations of the Coefficients in certain Generating Functions, The Electronic Journal of Combinatorics, 21 (2014), #P2.45.
M. Klazar, On numbers of Davenport-Schinzel sequences, Discr. Math., 185 (1998), 77-87.
D. E. Knuth, The Art of Computer Programming, Vol. 1, various sections (e.g. p. 534 of 2nd ed.).
D. E. Knuth, The Art of Computer Programming, Vol. 1, (p. 539 of 3rd ed.).
D. E. Knuth, The Art of Computer Programming, Vol. 4A, Section 7.2.1.6, Problem 66, p. 479.
J. S. Lew, Polynomial enumeration of multidimensional lattices, Math. Systems Theory, 12 (1979), 253-270.
Ana Marco, J.-J. Martinez, A total positivity property of the Marchenko-Pastur Law, Electronic Journal of Linear Algebra, 30 (2015), #7.
T. S. Motzkin, Relations between hypersurface cross ratios and a combinatorial formula for partitions of a polygon, for permanent preponderance and for non-associative products, Bull. Amer. Math. Soc., 54 (1948), 352-360.
L. Ozsvart, Counting ordered graphs that avoid certain subgraphs, Discr. Math., 339 (2016), 1871-1877.
R. C. Read, On general dissections of a polygon, Aequat. Mathem. 18 (1978) 370-388, Table 6
J. Riordan, Combinatorial Identities, Wiley, 1968, p. 168.
E. Schroeder, Vier combinatorische Probleme, Zeit. f. Math. Phys., 15 (1870), 361-376.
N. J. A. Sloane, A Handbook of Integer Sequences, Academic Press, 1973 (includes this sequence).
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 page 178; see page 239, Exercise 6.39b.
H. N. V. Temperley and D. G. Rogers, A note on Baxter's generalization of the Temperley-Lieb operators, pp. 324-328 of Combinatorial Mathematics (Canberra, 1977), Lect. Notes Math. 686, 1978.
I. Vardi, Computational Recreations in Mathematica. Addison-Wesley, Redwood City, CA, 1991, p. 198.
Sheng-Liang Yang and Mei-yang Jiang, The m-Schröder paths and m-Schröder numbers, Disc. Math. (2021) Vol. 344, Issue 2, 112209. doi:10.1016/j.disc.2020.112209. See Table 1.
LINKS
M. Abramowitz and I. A. Stegun, eds., Handbook of Mathematical Functions, National Bureau of Standards, Applied Math. Series 55, Tenth Printing, 1972 [alternative scanned copy]. P. J. Cameron, Some sequences of integers, in "Graph Theory and Combinatorics 1988", ed. B. Bollobas, Annals of Discrete Math., 43 (1989), 89-102. I. M. H. Etherington, Some problems of non-associative combinations (I), Edinburgh Math. Notes, 32 (1940), pp. i-vi. [Annotated scanned copy]. Part II [not scanned] is by A. Erdelyi and I. M. H. Etherington, and is on pages vii-xiv of the same issue. G. Kreweras, Sur les hiérarchies de segments, Cahiers du Bureau Universitaire de Recherche Opérationnelle, Institut de Statistique, Université de Paris, #20 (1973). G. Kreweras, Sur les hiérarchies de segments, Cahiers du Bureau Universitaire de Recherche Opérationnelle, Institut de Statistique, Université de Paris, #20 (1973). (Annotated scanned copy) Vincent Pilaud, Pebble trees, arXiv:2205.06686 [math.CO], 2022. Vincent Pilaud and V. Pons, Permutrees, arXiv preprint arXiv:1606.09643 [math.CO], 2016.
FORMULA
D-finite with recurrence: (n+1) * a(n) = (6*n-3) * a(n-1) - (n-2) * a(n-2) if n>1. a(0) = a(1) = 1.
a(n) = 3*a(n-1) + 2* A065096(n-2) (n>2). If g(x) = 1 + 3*x + 11*x^2 + 45*x^3 + ... + a(n)*x^n + ..., then g(x) = 1 + 3(x*g(x)) + 2(x*g(x))^2, g(x)^2 = 1 + 6*x + 31*x^2 + 156*x^3 + ... + A065096(n)*x^n + ... - Paul D. Hanna, Jun 10 2002 a(n-2) = (1/(n-1))*Sum_{k=0..n-3} binomial(n-1,k+1)*binomial(n-3,k)*2^(n-3-k) for n >= 3 [G. Polya, Elemente de Math., 12 (1957), p. 115.] - N. J. A. Sloane, Jun 13 2015 G.f.: (1 + x - sqrt(1 - 6*x + x^2) )/(4*x) = 2/(1 + x + sqrt(1 - 6*x + x^2)).
a(n) ~ W*(3+sqrt(8))^n*n^(-3/2) where W = (1/4)*sqrt((sqrt(18)-4)/Pi) [See Knuth I, p. 534, or Perez. Note that the formula on line 3, page 475 of Flajolet and Sedgewick seems to be wrong - it has to be multiplied by 2^(1/4).] - N. J. A. Sloane, Apr 10 2011 The correct asymptotic for this sequence is a(n) ~ W*(3+sqrt(8))^n*n^(-3/2), where W = (1+sqrt(2))/(2*2^(3/4)*sqrt(Pi)) = 0.404947065905750651736243... Result in book by D. Knuth (p. 539 of 3rd edition, exercise 12) is for sequence b(n), but a(n) = b(n+1)/2. Therefore is asymptotic a(n) ~ b(n) * (3+sqrt(8))/2. - Vaclav Kotesovec, Sep 09 2012 The Hankel transform of this sequence gives A006125 = 1, 1, 2, 8, 64, 1024, ...; example: det([1, 1, 3, 11; 1, 3, 11, 45; 3, 11, 45, 197; 11, 45, 197, 903]) = 2^6 = 64. - Philippe Deléham, Mar 02 2004 a(n+1) = Sum_{k=0..floor((n-1)/2)} 2^k * 3^(n-1-2k) * binomial(n-1, 2k) * Catalan(k). This formula counts colored Dyck paths by the same parameter by which Touchard's identity counts ordinary Dyck paths: number of DDUs (U=up step, D=down step). See also Gouyou-Beauchamps reference. - David Callan, Mar 14 2004 a(n) = (1/(n+1))*Sum_{k=0..n} C(n+1, k)*C(2n-k, n)*(-1)^k*2^(n-k) [with offset 0].
a(n) = (1/(n+1))*Sum_{k=0..n} C(n+1, k+1)*C(n+k, k)*(-1)^(n-k)*2^k [with offset 0].
a(n) = Sum_{k=0..n} (1/(k+1))*C(n, k)*C(n+k, k)*(-1)^(n-k)*2^k [with offset 0].
a(n) = Sum_{k=0..n} A088617(n, k)*(-1)^(n-k)*2^k [with offset 0]. (End) E.g.f. of a(n+1) is exp(3*x)*BesselI(1, 2*sqrt(2)*x)/(sqrt(2)*x). - Vladeta Jovovic, Mar 31 2004 Reversion of (x-2*x^2)/(1-x) is g.f. offset 1.
For n>=1, a(n) = Sum_{k=0..n} 2^k*N(n, k) where N(n, k) = (1/n)*C(n, k)*C(n, k+1) are the Narayana numbers ( A001263). - Benoit Cloitre, May 10 2003 [This formula counts colored Dyck paths by number of peaks, which is easy to see because the Narayana numbers count Dyck paths by number of peaks and the number of peaks determines the number of interior ascent vertices.] For n > 0, a(n) = (1/(n+1)) * Sum_{k = 0 .. n-1} binomial(2*n-k, n) * binomial(n-1, k). This formula counts colored Dyck paths (as above) by number of white vertices. - David Callan, Mar 14 2004 a(n-1) = (d^(n-1)/dx^(n-1))((1-x)/(1-2*x))^n/n!|_{x=0}. (For a proof see the comment on the unsigned row sums of triangle A111785.) a(n) = (1/n)*Sum_{k=1..n} binomial(n, k)*binomial(n+k, k-1).
a(n) = hypergeom([1-n, n+2], [2], -1), n>=1. (End)
a(n) = hypergeom([1-n, -n], [2], 2) for n>=0. - Peter Luschny, Sep 22 2014 Sum over partitions formula (reference Schroeder paper p. 362, eq. (1) II). Number the partitions of n according to Abramowitz-Stegun pp. 831-832 (see reference under A105805) with k=1..p(n)= A000041(n). For n>=1: a(n-1) = Sum_{k=2..p(n)} A048996(n,k)*a(1)^e(k, 1)*a(1)^e(k, 2)*...*a(n-2)^e(k, n-1) if the k-th partition of n in the mentioned order is written as (1^e(k, 1), 2^e(k, 2), ..., (n-1)e(k, n-1)). Note that the first (k=1) partition (n^1) has to be omitted. - Wolfdieter Lang, Aug 23 2005 Starting (1, 3, 11, 45, ...), = row sums of triangle A126216 = A001263 * [1, 2, 4, 8, 16, ...]. - Gary W. Adamson, Nov 30 2007 G.f.: 1/(1+x-2x/(1+x-2x/(1+x-2x/(1+x-2x/(1-.... (continued fraction).
G.f.: 1/(1-x/(1-x-x/(1-x-x/(1-x-x/(1-... (continued fraction).
G.f.: 1/(1-x-2x^2/(1-3x-2x^2/(1-3x-2x^2/(1-... (continued fraction). (End)
G.f.: 1 / (1 - x / (1 - 2*x / (1 - x / (1 - 2*x / ... )))). - Michael Somos, May 19 2013 a(n) = (LegendreP(n+1,3)-3*LegendreP(n,3))/(4*n) for n>0. - Mark van Hoeij, Jul 12 2010 [This formula is mentioned in S.-J. Kettle's 1982 letter - see link. N. J. A. Sloane, Jun 13 2015] a(n) = upper left term in M^n, where M is the production matrix:
1, 1, 0, 0, 0, 0, ...
2, 2, 2, 0, 0, 0, ...
1, 1, 1, 1, 0, 0, ...
2, 2, 2, 2, 2, 0, ...
1, 1, 1, 1, 1, 1, ...
... (End)
a(n) is the sum of top row terms of Q^(n-1), where Q is the infinite square production matrix:
1, 2, 0, 0, 0, ...
1, 1, 2, 0, 0, ...
1, 1, 1, 2, 0, ...
1, 1, 1, 1, 2, ...
... (End)
Let h(t) = (1-t)^2/(2*(1-t)^2-1) = 1/(1-(2*t+3*t^2+4*t^3+...)), an o.g.f. for A003480, then for A001003 a(n) = (1/n!)*((h(t)*d/dt)^n) t, evaluated at t=0, with initial n=1. (Cf. A086810.) - Tom Copeland, Sep 06 2011 G.f.: 1 + x/(Q(0) - x) where Q(k) = 1 + k*(1-x) - x - x*(k+1)*(k+2)/Q(k+1) ; (continued fraction). - Sergei N. Gladkovskii, Mar 14 2013 a(n)=(-1)^n*LegendreP(n,-1,-3)/sqrt(2), n > 0, LegendreP(n,a,b) is the Legendre function. - Karol A. Penson, Jul 06 2013 Integral representation as n-th moment of a positive weight function W(x) = W_a(x) + W_c(x), where W_a(x) = Dirac(x)/2, is the discrete (atomic) part, and W_c(x) = sqrt(8-(x-3)^2)/(4*Pi*x) is the continuous part of W(x) defined on (3 sqrt(8),3+sqrt(8)): a(n) = int( x^n*W_a(x), x=-eps..eps ) + int( x^n*W_c(x), x = 3-sqrt(8)..3+sqrt(8) ), for any eps>0, n>=0. W_c(x) is unimodal, of bounded variation and W_c(3-sqrt(8)) = W_c(3+sqrt(8)) = 0. Note that the position of the Dirac peak (x=0) lies outside support of W_c(x). - Karol A. Penson and Wojciech Mlotkowski, Aug 05 2013 G.f.: 1 + x/G(x) with G(x) = 1 - 3*x - 2*x^2/G(x) (continued fraction). - Nikolaos Pantelidis, Dec 17 2022
EXAMPLE
G.f. = 1 + x + 3*x^2 + 11*x^3 + 45*x^4 + 197*x^5 + 903*x^6 + 4279*x^7 + ...
a(2) = 3: abc, a(bc), (ab)c; a(3) = 11: abcd, (ab)cd, a(bc)d, ab(cd), (ab)(cd), a(bcd), a(b(cd)), a((bc)d), (abc)d, (a(bc))d, ((ab)c)d.
Sum over partitions formula: a(3) = 2*a(0)*a(2) + 1*a(1)^2 + 3*(a(0)^2)*a(1) + 1*a(0)^4 = 6 + 1 + 3 + 1 = 11.
a(4) = 45 since the top row of Q^3 = (11, 14, 12, 8, 0, 0, 0, ...); (11 + 14 + 12 + 8) = 45.
MAPLE
t1 := (1/(4*x))*(1+x-sqrt(1-6*x+x^2)); series(t1, x, 40);
invtr:= proc(p) local b; b:= proc(n) option remember; local i; `if`(n<1, 1, add(b(n-i) *p(i-1), i=1..n+1)) end end: a:='a': f:= (invtr@@2)(a): a:= proc(n) if n<0 then 1 else f(n-1) fi end: seq(a(n), n=0..30); # Alois P. Heinz, Apr 01 2009 # Computes n -> [a[0], a[1], .., a[n]]
A001003_list := proc(n) local j, a, w; a := array(0..n); a[0] := 1;
for w from 1 to n do a[w] := a[w-1]+2*add(a[j]*a[w-j-1], j=1..w-1) od;
MATHEMATICA
Table[Length[Flatten[Nest[ #/.a_Integer:> Join[Range[0, a + 1], Range[a, 0, -1]] &, {0}, n]]], {n, 0, 10}]; Sch[ 0 ] = Sch[ 1 ] = 1; Sch[ n_Integer ] := Sch[ n ] = (3(2n - 1)Sch[ n - 1 ] - (n - 2)Sch[ n - 2 ])/(n + 1); Array[ Sch, 24, 0]
(* Second program: *)
a[ n_] := SeriesCoefficient[ (1 + x - Sqrt[1 - 6 x + x^2]) / (4 x), {x, 0, n}]; (* Michael Somos, Aug 26 2015 *) Table[(KroneckerDelta[n] - GegenbauerC[n+1, -1/2, 3])/4, {n, 0, 20}] (* Vladimir Reshetnikov, Oct 25 2015 *) a[n_] := -LegendreP[n, -1, 2, 3] I / Sqrt[2]; a[0] = 1;
a[1]:=1; a[2]:=1; a[n_]:=a[n] = a[n-1]+2 Sum[a[k] a[n-k], {k, 2, n-1}]; Map[a, Range[24]] (* Oliver Seipel, Nov 03 2024, after Schröder 1870 *)
PROG
(PARI) {a(n) = if( n<1, n==0, sum( k=0, n, 2^k * binomial(n, k) * binomial(n, k-1) ) / (2*n))}; /* Michael Somos, Mar 31 2007 */ (PARI) {a(n) = my(A); if( n<1, n==0, n--; A = x * O(x^n); n! * simplify( polcoef( exp(3*x + A) * besseli(1, 2*x * quadgen(8) + A), n)))}; /* Michael Somos, Mar 31 2007 */ (PARI) {a(n) = if( n<0, 0, n++; polcoef( serreverse( (x - 2*x^2) / (1 - x) + x * O(x^n)), n))}; /* Michael Somos, Mar 31 2007 */ (PARI) N=30; x='x+O('x^N); Vec( (1+x-(1-6*x+x^2)^(1/2))/(4*x) ) \\ Hugo Pfoertner, Nov 19 2018 (Python) # The objective of this implementation is efficiency.
# n -> [a(0), a(1), ..., a(n)]
a = [0 for i in range(n)]
a[0] = 1
for w in range(1, n):
s = 0
for j in range(1, w):
s += a[j]*a[w-j-1]
a[w] = a[w-1]+2*s
return a
(Sage) # Generalized algorithm of L. Seidel
D = [0]*(n+1); D[1] = 1/2
b = True; h = 2; R = [1]
for i in range(2*n-2) :
if b :
for k in range(h, 0, -1) : D[k] += D[k-1]
h += 1;
else :
for k in range(1, h, 1) : D[k] += D[k-1]
R.append(D[h-1]);
b = not b
return R
(Haskell)
(Python)
from gmpy2 import divexact
for n in range(3, 10**3):
(Magma)
R<x>:=PowerSeriesRing(Rationals(), 50);
Coefficients(R!( (1+x -Sqrt(1-6*x+x^2) )/(4*x) )); // G. C. Greubel, Oct 27 2024
CROSSREFS
Right-hand column 1 of convolution triangle A011117.
KEYWORD
nonn,easy,nice,core,changed
Triangular array formed by the little Schröder numbers s(n,k).
+10
6
1, 3, 1, 11, 6, 1, 45, 31, 9, 1, 197, 156, 60, 12, 1, 903, 785, 360, 98, 15, 1, 4279, 3978, 2061, 684, 145, 18, 1, 20793, 20335, 11529, 4403, 1155, 201, 21, 1, 103049, 104856, 63728, 27048, 8270, 1800, 266, 24, 1, 518859, 545073, 350136, 161412, 55458, 14202
COMMENTS
s(n,k) is the number of unit step restricted paths (i.e., they never go below the x-axis) from the origin (0,0) to (n-1,k-1) using up step U(1,1), three types of level steps L(1,0), L'(1,0), L"(1,0) and two types of down steps D(1,-1), D'(1,-1). s(0,0)=1 and the leftmost column s(n,0) is A001003. The sequence factors A038255 into a product of Riordan arrays.
FORMULA
s(n+1,0) = 3s(n,0) + 2s(n,1) and for k > 0: s(n+1,k) = s(n,k-1) + 3s(n,k) + 2s(n,k+1). [Typo fixed by Reinhard Zumkeller, Nov 21 2013] Riordan array ((1 - 3z - sqrt(1-6z+z^2))/4z*z, (1 - 3z - sqrt(1-6z+z^2))/4z).
G.f.: 2/( 1 - x*L -2*x*y*U + sqrt( (1 - x*L)^2 - 4*x^2*D*U ) ) where L=3, U = 1, D = 2. - Michael Somos, Mar 31 2007 T(n,k) = Sum_{i=0..k + 1} i*(-1)^(k-i+1)*C(k+1,i)*Sum_{j=0..n+1} (-1)^j*2^(n+1-j)*(2*n+i-j+1)!/((n+i-j+1)!*j!*(n-j+1)!))). - Vladimir Kruchinin, Oct 17 2011 T(n,k) = (k+1)/(n+1)*Sum_{j=ceiling((n+k+2)/2)..n + 1} C(j,2*j-n-k-2)*3^(2*j-n-k- 2)*2^(n+1-j)*C(n+1,j)). - Vladimir Kruchinin, Jan 28 2013 T(n,k) = ((k+1)/(n+1))*Sum_{m=0..n} 2^(n-m)*C(n+1,m+1)*C(n+1,m-k). - Vladimir Kruchinin, Jan 09 2022
EXAMPLE
Triangle starts:
[0] 1;
[1] 3, 1;
[2] 11, 6, 1;
[3] 45, 31, 9, 1;
[4] 197, 156, 60, 12, 1;
[5] 903, 785, 360, 98, 15, 1;
[6] 4279, 3978, 2061, 684, 145, 18, 1;
[7] 20793, 20335, 11529, 4403, 1155, 201, 21, 1;
[8] 103049, 104856, 63728, 27048, 8270, 1800, 266, 24, 1;
[9] 518859, 545073, 350136, 161412, 55458, 14202, 2646, 340, 27, 1;
MAPLE
T := (n, k) -> ((k + 1)/(n + 1))*add(2^(n - m)*binomial(n+1, m+1)*binomial(n+1, m-k), m = 0..n): seq(seq(T(n, k), k = 0..n), n = 0..9); # Peter Luschny, Jan 09 2022
MATHEMATICA
nmax = 9; t[n_, k_] := Sum[(i*(-1)^(k-i+1)*Binomial[k+1, i]*Sum[(-1)^j*2^(n+1-j)*(2n+i-j+1)! / ((n+i-j+1)!*j!*(n-j+1)!), {j, 0, n+1}]), {i, 0, k+1}]; Flatten[ Table[ t[n, k], {n, 0, nmax}, {k, 0, n}]] (* Jean-François Alcover, Nov 14 2011, after Vladimir Kruchinin *)
PROG
(PARI) {T(n, k)= if(n<0|| k>n, 0, polcoeff(polcoeff( 2/(1 -3*x -2*x*y +sqrt( 1 -6*x +x^2 +x*O(x^n)) ), n), k))} \\ Michael Somos, Mar 31 2007 (Maxima)
T(n, k):=sum((i*(-1)^(k-i+1)*binomial(k+1, i)*sum((-1)^j*2^(n+1-j)*(2*n+i-j+1)!/((n+i-j+1)!*j!*(n-j+1)!), j, 0, n+1)), i, 0, k+1); /* Vladimir Kruchinin, Oct 17 2011 */ (Sage)
T = matrix(ZZ, dim, dim)
for n in range(dim): T[n, n] = 1
for n in (1..dim-1):
for k in (0..n-1):
T[n, k] = T[n-1, k-1]+3*T[n-1, k]+2*T[n-1, k+1]
return T
(Maxima) T(n, k):=((k+1)/(n+1)*sum(binomial(j, -n-k+2*j-2)*3^(-n-k+2*j-2)*2^(n+1-j)*binomial(n+1, j), j, ceiling((n+k+2)/2), n+1)); \\ Vladimir Kruchinin, Jan 28 2013 (Haskell)
a110440 n k = a110440_tabl !! n !! k
a110440_row n = a110440_tabl !! n
a110440_tabl = iterate (\xs ->
zipWith (+) ([0] ++ xs) $
zipWith (+) (map (* 3) (xs ++ [0]))
(map (* 2) (tail xs ++ [0, 0]))) [1]
AUTHOR
Asamoah Nkwanta (nkwanta(AT)jewel.morgan.edu), Aug 08 2005
Expansion of (1 - 4*x - (1-2*x)*sqrt(1-4*x-4*x^2))/(8*x^3).
+10
2
0, 1, 4, 16, 64, 260, 1072, 4480, 18944, 80928, 348800, 1515008, 6625280, 29147456, 128918272, 572928000, 2557100032, 11457170944, 51514963968, 232370167808, 1051235287040, 4768568354816, 21684663148544, 98835356778496, 451433970008064
FORMULA
a(n) = (1/Pi)*Integral_{x=2-2*sqrt(2)..2+2*sqrt(2)} x^n*sqrt(-x^2+4x+4)*(x-2)/8. - Paul Barry, Sep 16 2006 a(n) = Sum_{k=0..n} 2^(n-k)*binomial(n,k)*2^((k-1)/2)*C((k-1)/2+1)*(1-(-1)^k)/2, where C(n)= A000108(n). - Paul Barry, Sep 16 2006 D-finite with recurrence: a(n) = (1/(n+3))*((6*n+8)*a(n-1) - (4*n-4)*a(n-2) - (8*n-16)*a(n-3)) for n > 2, with a(0)=0, a(1)=1, a(2)=4. - Tani Akinari, Jul 04 2013 a(n) ~ 2^(n + 1/4) * (1 + sqrt(2))^(n + 3/2) / (sqrt(Pi) * n^(3/2)). - Vaclav Kotesovec, Sep 03 2019
MATHEMATICA
CoefficientList[Series[(1-4x-(1-2x)Sqrt[1-4x-4x^2])/(8x^3), {x, 0, 30}], x] (* Harvey P. Dale, Aug 09 2016 *) Table[Sum[2^(n-k) * Binomial[n, k] * 2^((k-1)/2) * CatalanNumber[(k+1)/2] * (1 - (-1)^k)/2, {k, 0, n}], {n, 0, 20}] (* Vaclav Kotesovec, Sep 03 2019 *)
Cayley's triangle of V numbers; triangle V(n,k), n >= 4, n <= k <= 2*n-4, read by rows.
+10
1
1, 2, 4, 3, 14, 14, 4, 32, 72, 48, 5, 60, 225, 330, 165, 6, 100, 550, 1320, 1430, 572, 7, 154, 1155, 4004, 7007, 6006, 2002, 8, 224, 2184, 10192, 25480, 34944, 24752, 7072, 9, 312, 3822, 22932, 76440, 148512, 167076, 100776, 25194, 10, 420, 6300, 47040, 199920, 514080, 813960, 775200, 406980, 90440, 11, 550, 9900, 89760, 471240, 1534896, 3197700, 4263600, 3517470, 1634380, 326876
LINKS
A. Cayley, On the partitions of a polygon, Proc. London Math. Soc., 22 (1891), 237-262 = Collected Mathematical Papers. Vols. 1-13, Cambridge Univ. Press, London, 1889-1897, Vol. 13, pp. 93ff.
FORMULA
G.f.: (1-x*y*(1+2*y)-sqrt(1-2*x*y*(1+2*y)+x^2*y^2))^2/(4*y^4*(1+y)^2). - Vladimir Kruchinin, Jan 27 2022
EXAMPLE
Triangle begins:
1;
2, 4;
3, 14, 14;
4, 32, 72, 48;
5, 60, 225, 330, 165;
6, 100, 550, 1320, 1430, 572;
...
MAPLE
V := proc(n, x)
local X, g, i ;
X := x^2/(1-x) ;
g := X^n ;
for i from 1 to n-2 do
g := diff(g, x) ;
end do;
x^2*g*2*(n-1)/n! ;
end proc;
V(k-n+2, x) ;
coeftayl(%, x=0, n+2) ;
end proc:
for n from 4 to 14 do
for k from n to 2*n-4 do
end do:
printf("\n") ;
MATHEMATICA
T[n_, m_] := 2 Binomial[m, n] Binomial[n-2, m-n+2]/(n-2);
PROG
(Maxima)
T(n, m):=if n<4 then 0 else (2*binomial(m, n)*binomial(n-2, m-n+2))/(n-2); /* Vladimir Kruchinin, Jan 27 2022 */
CROSSREFS
Row sums give A065096 (with a different offset).
Triangle T read by rows: T(n,0) = T(n,n) = 1 for n>=0, for n>=2 and 1<=k<=n-1, T(n,k) = T(n-1,k-1) + T(n-1,k) if k = [n/2] or k = [(n+1)/2], else T(n,k) = T(n-1,k-1) + T(n-2,k-1) + T(n-1,k).
+10
0
1, 1, 1, 1, 2, 1, 1, 3, 3, 1, 1, 5, 6, 5, 1, 1, 7, 11, 11, 7, 1, 1, 9, 23, 22, 23, 9, 1, 1, 11, 39, 45, 45, 39, 11, 1, 1, 13, 59, 107, 90, 107, 59, 13, 1, 1, 15, 83, 205, 197, 197, 205, 83, 15, 1
FORMULA
Sum_{k, 0<=k<=n} T(n,k) = A110110(n), number of symmetric Schroeder paths of length 2n. Sum_{k, 0<=k<=n-2} T(n+k,k) = A065096(n-1), n>=2. T(2n,n) = A006318(n), large Schroeder numbers. T(2n+1,n) = A001003(n+1), little Schroeder numbers.
EXAMPLE
Triangle begins
1
1, 1
1, 2, 1
1, 3, 3, 1
1, 5, 6, 5, 1
1, 7, 11, 11, 7, 1
1, 9, 23, 22, 23, 9, 1
1, 11, 39, 45, 45, 39, 11, 1
1, 13, 59, 107, 90, 107, 59, 13, 1
1, 15, 83, 205, 197, 197, 205, 83, 15, 1
1, 17, 111, 347, 509, 394, 509, 347, 111, 17, 1
1, 19, 143, 541, 1061, 903, 903, 1061, 541, 143, 19, 1
1, 21, 179, 795, 1949, 2473, 1806, 2473, 1949, 795, 179, 21, 1
...
a(n) = Sum_{k = 0..n} E1(n, k)*k^2, where E1 are the Eulerian numbers A173018.
+10
0
0, 0, 1, 8, 64, 540, 4920, 48720, 524160, 6108480, 76809600, 1037836800, 15008716800, 231437606400, 3792255667200, 65819609856000, 1206547550208000, 23297526540288000, 472708591939584000, 10055994967130112000, 223826984752250880000, 5202760944485744640000, 126075414965721661440000, 3179798058882852126720000, 83346901966165164687360000, 2267221868000212451328000000
COMMENTS
The Eulerian transform of the squares.
FORMULA
a(n) = n! * [x^n] x^2*(-x^2 + x - 3)/(6*(x - 1)^3).
a(n) = Sum_{k=0..n} Sum_{j=0..k} (-1)^j*binomial(n + 1, j)*k^2*(k + 1 - j)^n.
a(n) = ((n - 3)*(n - 1)*(23*n - 44)*a(n-2) + ((159 - 7*n)*n - 286)*a(n-1))/(16*(n - 2)) for n >= 3.
MAPLE
a := n -> add(combinat[eulerian1](n, k)*k^2, k = 0..n):
# Recurrence:
a := proc(n) option remember; if n < 2 then 0 elif n = 2 then 1 else
((n-3)*(n-1)*(23*n-44)*a(n-2) + ((159 - 7*n)*n - 286)*a(n-1))/(16*(n - 2)) fi end:
seq(a(n), n = 0..29);
MATHEMATICA
a[n_] := Sum[Sum[(-1)^j Binomial[n + 1, j] k^2 (k + 1 - j)^n, {j, 0, k}], {k, 0, n}]; a[0] := 0; Table[a[n], {n, 0, 25}]
PROG
(SageMath)
def aList(len):
R.<x> = PowerSeriesRing(QQ, default_prec=len+2)
f = x^2*(-x^2 + x - 3)/(6*(x - 1)^3)
return f.egf_to_ogf().list()[:len]
print(aList(20))
Search completed in 0.031 seconds
| 
