A011117
Triangle of numbers S(x,y) = number of lattice paths from (0,0) to (x,y) that use step set { (0,1), (1,0), (2,0), (3,0), ....} and never pass below y = x.
Original entry on oeis.org
1, 1, 1, 1, 2, 3, 1, 3, 7, 11, 1, 4, 12, 28, 45, 1, 5, 18, 52, 121, 197, 1, 6, 25, 84, 237, 550, 903, 1, 7, 33, 125, 403, 1119, 2591, 4279, 1, 8, 42, 176, 630, 1976, 5424, 12536, 20793, 1, 9, 52, 238, 930, 3206, 9860, 26832, 61921, 103049, 1, 10, 63
Offset: 0
Robert Sulanke (sulanke(AT)diamond.idbsu.edu)
Triangle starts:
[0] [1]
[1] [1, 1]
[2] [1, 2, 3]
[3] [1, 3, 7, 11]
[4] [1, 4, 12, 28, 45]
[5] [1, 5, 18, 52, 121, 197]
[6] [1, 6, 25, 84, 237, 550, 903]
[7] [1, 7, 33, 125, 403, 1119, 2591, 4279]
[8] [1, 8, 42, 176, 630, 1976, 5424, 12536, 20793]
[9] [1, 9, 52, 238, 930, 3206, 9860, 26832, 61921, 103049]
- E. Barcucci, E. Pergola, R. Pinzani and S. Rinaldi, ECO method and hill-free generalized Motzkin paths, Séminaire Lotharingien de Combinatoire, B46b (2001), 14 pp.
- E. Pergola and R. A. Sulanke, Schroeder Triangles, Paths and Parallelogram Polyominoes, J. Integer Sequences, 1 (1998), #98.1.7.
-
f[ x_, y_ ] := f[ x, y ] = Module[ {return}, If[ x == 0, return = 1, If[ y == x-1, return = 0, return = f[ x, y-1 ] + Sum[ f[ k, y ], {k, 0, x-1} ] ] ]; return ]; Do[ Print[ Table[ f[ k, j ], {k, 0, j} ] ], {j, 10, 0, -1} ]
-
def A011117_row(n):
@cached_function
def prec(n, k):
if k==n: return 1
if k==0: return 0
return prec(n-1,k-1)+sum(prec(n,k+i-1) for i in (2..n-k+1))
return [prec(n, n-k) for k in (0..n-1)]
for n in (1..9): print(A011117_row(n)) # Peter Luschny, Mar 16 2016
A026781
a(n) = T(2n,n), T given by A026780.
Original entry on oeis.org
1, 3, 12, 53, 246, 1178, 5768, 28731, 145108, 741392, 3825418, 19907156, 104370554, 550816506, 2924018194, 15603778253, 83661779470, 450479003038, 2435009205992, 13208558795146, 71879906857596, 392320357251928, 2147102400154768, 11780181236675858, 64782405317073968, 357022158144941548
Offset: 0
-
R:=PowerSeriesRing(Rationals(), 30); Coefficients(R!( 2*(1-x -Sqrt(1-6*x+x^2))/(4*x -(1 -Sqrt(1-4*x))*(1 -x -Sqrt(1-6*x+x^2))) )); // G. C. Greubel, Nov 02 2019
-
seq(coeff(series(2*(1-x -sqrt(1-6*x+x^2))/(4*x -(1 -sqrt(1-4*x))*(1 -x -sqrt(1-6*x+x^2))), x, n+1), x, n), n = 0..30); # G. C. Greubel, Nov 02 2019
-
CoefficientList[Series[2*(1-x -Sqrt[1-6*x+x^2])/(4*x -(1 -Sqrt[1-4*x])*(1 -x -Sqrt[1-6*x+x^2])), {x,0,30}], x] (* G. C. Greubel, Nov 02 2019 *)
-
C = (1-sqrt(1-4*x+O(x^51)))/2/x; S = (1-x-sqrt(1-6*x+x^2 +O(x^51) ))/2/x; Vec(S/(1-x*C*S)) /* Max Alekseyev, Jan 13 2015 */
-
def A026781_list(prec):
P. = PowerSeriesRing(ZZ, prec)
return P(2*(1-x -sqrt(1-6*x+x^2))/(4*x -(1 -sqrt(1-4*x))*(1 -x -sqrt(1-6*x+x^2)))).list()
A026781_list(30) # G. C. Greubel, Nov 02 2019
A034015
Small 3-Schroeder numbers: a(n) = A027307(n+1)/2.
Original entry on oeis.org
1, 5, 33, 249, 2033, 17485, 156033, 1431281, 13412193, 127840085, 1235575201, 12080678505, 119276490193, 1187542872989, 11909326179841, 120191310803937, 1219780566014657, 12440630635406245, 127446349676475425, 1310820823328281561, 13530833791486094769
Offset: 0
- 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.
- Alois P. Heinz, Table of n, a(n) for n = 0..500
- J.-C. Novelli and J.-Y. Thibon, Hopf Algebras of m-permutations,(m+1)-ary trees, and m-parking functions, arXiv preprint arXiv:1403.5962 [math.CO], 2014-2020.
- Jun Yan, Results on pattern avoidance in parking functions, arXiv preprint arXiv:2404.07958 [math.CO], 2024. See Theorem 4.4.
Part of a family indexed by m: m=2 (
A001003), m=3 is this sequence, m=4 is
A243675, ....
-
a:= proc(n) option remember; `if`(n<2, 4*n+1,
((110*n^3+66*n^2-17*n-9) *a(n-1)
+(n-1)*(2*n-1)*(5*n+3) *a(n-2)) /
((2*n+3)*(5*n-2)*(n+1)))
end:
seq(a(n), n=0..25); # Alois P. Heinz, Jun 22 2014
-
a[n_] := If[n<0, 0, Sum[2^i*Binomial[2*n+2, i]*Binomial[n+1, i+1]/(n+1), {i, 0, n}]]; Table[a[n], {n, 0, 25}] (* Jean-François Alcover, Oct 13 2014, after PARI *)
a[n_] := Hypergeometric2F1[-n, -2 (n + 1), 2, 2];
Table[a[n], {n, 0, 20}] (* Peter Luschny, Nov 08 2021 *)
-
a(n)=if(n<0,0,sum(i=0,n,2^i*binomial(2*n+2,i)*binomial(n+1,i+1))/(n+1))
A071969
a(n) = Sum_{k=0..floor(n/3)} (binomial(n+1, k)*binomial(2*n-3*k, n-3*k)/(n+1)).
Original entry on oeis.org
1, 1, 2, 6, 19, 63, 219, 787, 2897, 10869, 41414, 159822, 623391, 2453727, 9733866, 38877318, 156206233, 630947421, 2560537092, 10435207116, 42689715279, 175243923783, 721649457417, 2980276087005, 12340456995177, 51222441676513, 213090270498764, 888321276659112
Offset: 0
-
A071969 := n->add( binomial(n+1,k)*binomial(2*n-3*k,n-3*k)/(n+1),k=0..floor(n/3));
Order:=30: g:=solve(series((H-H^2)/(1+H^3),H)=z,H): seq(coeff(g,z^n),n=1..28); # Emeric Deutsch, Dec 15 2004
-
Table[Sum[Binomial[n+1,k] Binomial[2n-3k,n-3k]/(n+1),{k,0,Floor[n/3]}],{n,0,40}] (* Harvey P. Dale, Jul 20 2022 *)
-
a(n)=if(n<0,0,polcoeff(serreverse((x-x^2)/(1+x^3)+x^2*O(x^n)),n+1))
A082298
Expansion of (1-3*x-sqrt(9*x^2-10*x+1))/(2*x).
Original entry on oeis.org
1, 4, 20, 116, 740, 5028, 35700, 261780, 1967300, 15072836, 117297620, 924612532, 7367204260, 59240277988, 480118631220, 3917880562644, 32163325863300, 265446382860420, 2201136740855700, 18329850024033012, 153225552507991140
Offset: 0
- Vincenzo Librandi, Table of n, a(n) for n = 0..300
- Paul Barry, On Integer-Sequence-Based Constructions of Generalized Pascal Triangles, Journal of Integer Sequences, Vol. 9 (2006), Article 06.2.4.
- Paul Barry, Generalized Catalan Numbers Associated with a Family of Pascal-like Triangles, J. Int. Seq., Vol. 22 (2019), Article 19.5.8.
- Paul Barry and Aoife Hennessy, A Note on Narayana Triangles and Related Polynomials, Riordan Arrays, and MIMO Capacity Calculations, J. Int. Seq. 14 (2011), Article 11.3.8.
- Zhi Chen and Hao Pan, Identities involving weighted Catalan, Schroder and Motzkin paths, arXiv:1608.02448 [math.CO], 2016. See eq. (1.13), a=4, b=1.
- Curtis Coker, Enumerating a class of lattice paths, Disc. Math. (2003) Vol. 271, Issues 1-3, 13-28.
- Aoife Hennessy, A Study of Riordan Arrays with Applications to Continued Fractions, Orthogonal Polynomials and Lattice Paths, Ph. D. Thesis, Waterford Institute of Technology, Oct. 2011.
- John Machacek, Lattice walks ending on a coordinate hyperplane avoiding backtracking and repeats, arXiv:2105.02417 [math.CO], 2021. See Thm 4.4, G(x,F^1)
- Greg Morrow, Some probability distributions and integer sequences related to rook paths, Univ. Colorado Springs (2024). See pp. 4, 22
-
Q:=Rationals(); R:=PowerSeriesRing(Q, 40); Coefficients(R!((1-3*x-Sqrt(9*x^2-10*x+1))/(2*x))); // G. C. Greubel, Feb 10 2018
-
A082298_list := proc(n) local j, a, w; a := array(0..n); a[0] := 1;
for w from 1 to n do a[w] := 4*a[w-1]+add(a[j]*a[w-j-1], j=1..w-1) od;convert(a,list)end: A082298_list(20); # Peter Luschny, May 19 2011
a := n -> `if`(n=0, 1, 4*hypergeom([1 - n, -n], [2], 4)):
seq(simplify(a(n)), n=0..20); # Peter Luschny, May 22 2017
-
gf[x_] = (1 - 3*x - Sqrt[(9*x^2 - 10*x + 1)])/(2*x); CoefficientList[Series[gf[x], {x, 0, 20}], x] (* Jean-François Alcover, Jun 01 2011 *)
-
a(n)=if(n<1,1,sum(k=0,n,4^k*binomial(n,k)*binomial(n,k-1))/n)
A023426
a(n) = a(n-1) + Sum_{k=0..n-4} a(k)*a(n-4-k), a(0) = 1. Generalized Catalan Numbers.
Original entry on oeis.org
1, 1, 1, 1, 2, 4, 7, 11, 18, 32, 59, 107, 191, 343, 627, 1159, 2146, 3972, 7373, 13757, 25781, 48437, 91165, 171945, 325096, 616066, 1169667, 2224355, 4236728, 8082374, 15441719, 29542411, 56590472, 108532322, 208387711, 400551615, 770710831, 1484383399
Offset: 0
- Vincenzo Librandi, Table of n, a(n) for n = 0..1000
- Andrei Asinowski, Cyril Banderier and Valerie Roitner, Generating functions for lattice paths with several forbidden patterns, (2019).
- Ricardo Gómez Aíza, Trees with flowers: A catalog of integer partition and integer composition trees with their asymptotic analysis, arXiv:2402.16111 [math.CO], 2024. See pp. 10, 19-21.
- K. Park and G.S. Cheon, Lattice path counting with a bounded strip restriction
-
a := n -> hypergeom([(1 - n)/4, (2 - n)/4, (3 - n)/4, -n/4], [2, (1 - n)/2, -n/2], 2^6): seq(simplify(a(n)), n = 0..35); # Peter Luschny, Jul 12 2024
-
Clear[ a ]; a[ 0 ]=1; a[ n_Integer ] := a[ n ]=a[ n-1 ]+Sum[ a[ k ]*a[ n-4-k ], {k, 0, n-4} ];
CoefficientList[Series[(1-x-Sqrt[(1-x)^2-4*x^4])/(2*x^4), {x, 0, 20}], x] (* Vaclav Kotesovec, Feb 01 2014 *)
Name extended by a formula from the author in Mathematica by
Peter Luschny, Jul 13 2024
A078482
Expansion of g.f. (1 - 3*x + x^2 - sqrt(1 - 6*x + 7*x^2 - 2*x^3 + x^4))/(2*x).
Original entry on oeis.org
0, 1, 2, 6, 20, 70, 254, 948, 3618, 14058, 55432, 221262, 892346, 3630680, 14885042, 61432382, 255025212, 1064190214, 4461325382, 18780710508, 79357572866, 336466650450, 1431007889744, 6103431668830, 26099839562738, 111877997049648, 480635694869218
Offset: 0
G.f.: A(x) = x + 2*x^2 + 6*x^3 + 20*x^4 + 70*x^5 + 254*x^6 + 948*x^7 + ...
From _Paul D. Hanna_, Sep 12 2012: (Start)
The logarithm of the g.f. begins
log(A(x)/x) = (1 + 1/(1-x))*x + (1 + 2^2/(1-x) + 1/(1-x)^2)*x^2/2 +
(1 + 3^2/(1-x) + 3^2/(1-x)^2 + 1/(1-x)^3)*x^3/3 +
(1 + 4^2/(1-x) + 6^2/(1-x)^2 + 4^2/(1-x)^3 + 1/(1-x)^4)*x^4/4 +
(1 + 5^2/(1-x) + 10^2/(1-x)^2 + 10^2/(1-x)^3 + 5^2/(1-x)^4 + 1/(1-x)^5)*x^5/5 + ...
(End)
a(5) = 70 = (1, 1, 2, 6, 20) dot product (1, 1, 3, 9, 29) = (29 + 9 + 6 + 6 + 20). - _Gary W. Adamson_, May 20 2013
- Vincenzo Librandi, Table of n, a(n) for n = 0..1000
- Andrei Asinowski and Cyril Banderier, From geometry to generating functions: rectangulations and permutations, arXiv:2401.05558 [cs.DM], 2024. See page 2.
- Andrei Asinowski, Gill Barequet, Mireille Bousquet-Mélou, Toufik Mansour, and Ron Y. Pinter, Orders induced by segments in floorplan partitions and (2-14-3, 3-41-2)-avoiding permutations arXiv:1011.1889 [math.CO], 2010-2012, page 32.
- Andrei Asinowski and Toufik Mansour, Separable d-Permutations and Guillotine Partitions, arXiv 0803.3414 [math.CO], 2008. Annals of Combinatorics 14 (1) pp.17-43 Springer, 2010; Abstract
- M. D. Atkinson and T. Stitt, Restricted permutations and the wreath product, Preprint, 2002.
- M. D. Atkinson and T. Stitt, Restricted permutations and the wreath product, Discrete Math., 259 (2002), 19-36.
- Christian Bean, Émile Nadeau, and Henning Ulfarsson, Enumeration of Permutation Classes and Weighted Labelled Independent Sets, arXiv:1912.07503 [math.CO], 2019.
- CombOS - Combinatorial Object Server, Generate 1-sided guillotine rectangulations
- Elizabeth Hartung, Hung Phuc Hoang, Torsten Mütze, and Aaron Williams, Combinatorial generation via permutation languages. I. Fundamentals, arXiv:1906.06069 [cs.DM], 2019.
- Arturo Merino and Torsten Mütze, Combinatorial generation via permutation languages. III. Rectangulations, arXiv:2103.09333 [math.CO], 2021.
-
CoefficientList[Series[(1 - 3 x + x^2 - Sqrt[1 - 6 x + 7 x^2 - 2 x^3 + x^4]) / (2 x), {x, 0, 40}], x] (* Vincenzo Librandi, May 28 2016 *)
-
a(n):=if n=0 then 0 else sum((binomial(m,n-m+1)* (sum(binomial(m,i)* binomial(2*m-i-2,m-1),i,0,m-1)) *(-1)^(n-m+1))/m,m,1,n+1); /* Vladimir Kruchinin, May 21 2011 */
-
{a(n)=local(A=x);for(i=1,n,A=x*(1+A)*(1+A/(1-x +x*O(x^n))));polcoeff(A,n)} \\ Paul D. Hanna, Sep 12 2012
-
{a(n)=polcoeff(x*exp(sum(m=1,n+1,x^m/m*sum(k=0,m,binomial(m,k)^2/(1-x +x*O(x^n))^k))),n)} \\ Paul D. Hanna, Sep 12 2012
Replaced definition with g.f. given by Atkinson and Still (2002). -
N. J. A. Sloane, May 24 2016
A103209
Square array T(n,d) read by antidiagonals: number of structurally-different guillotine partitions of a d-dimensional box in R^d by n hyperplanes.
Original entry on oeis.org
1, 1, 2, 1, 6, 3, 1, 22, 15, 4, 1, 90, 93, 28, 5, 1, 394, 645, 244, 45, 6, 1, 1806, 4791, 2380, 505, 66, 7, 1, 8558, 37275, 24868, 6345, 906, 91, 8, 1, 41586, 299865, 272188, 85405, 13926, 1477, 120, 9, 1, 206098, 2474025, 3080596, 1204245, 229326, 26845
Offset: 1
1,...1,....1,.....1,......1,......1,.......1,.......1,.......1,
1,...2,....3,.....4,......5,......6,.......7,.......8,.......9,
1,...6,...15,....28,.....45,.....66,......91,.....120,.....153,
1,..22,...93,...244,....505,....906,....1477,....2248,....3249,
1,..90,..645,..2380,...6345,..13926,...26845,...47160,...77265,
1,.394,.4791,.24868,..85405,.229326,..522739,.1059976,.1968633,
1,1806,37275,272188,1204245,3956106,10663471,24958200,52546473,
- E. Ackerman, G. Barequet, R. Y. Pinter and D. Romik, The number of guillotine partitions in d dimensions, Inf. Proc. Lett 98 (4) (2006) 162-167.
- Andrei Asinowski and Toufik Mansour, Separable d-Permutations and Guillotine Partitions, arXiv 0803.3414 [math.CO], 2008; Annals of Combinatorics 14 (1) pp.17-43 Springer, 2010; Abstract
- Paul Barry, On the Inverses of a Family of Pascal-Like Matrices Defined by Riordan Arrays, Journal of Integer Sequences, 16 (2013), #13.5.6.
- Jean Cardinal, Stefan Felsner, Topological drawings of complete bipartite graphs, Journal of Computational Geometry 9.1 (2018), 213-246. Also arXiv:1608.08324 [cs.CG], 2016 (The OEIS is referenced in version v1 but not in v2).
-
T := (n,k) -> hypergeom([-n, n+1], [2], -k);
seq(print(seq(simplify(T(n, k)), k=0..9)), n=0..6); # Peter Luschny, May 23 2014
-
T[0, ] = T[, 0] = 1;
T[n_, k_] := Sum[Binomial[n+j, 2j] k^j CatalanNumber[j], {j, 0, n}];
Table[T[n-k+1, k], {n, 0, 10}, {k, 0, n}] // Flatten (* Jean-François Alcover, Jun 20 2018, after Paul Barry *)
A349312
G.f. A(x) satisfies: A(x) = (1 + x * A(x)^6) / (1 - x).
Original entry on oeis.org
1, 2, 14, 158, 2106, 30762, 476406, 7683926, 127692530, 2171184146, 37592376734, 660522703886, 11747865153962, 211093333172282, 3826315983647366, 69880933123237958, 1284661783610775010, 23753502514840942882, 441458929706855144494, 8242097867816771820926
Offset: 0
-
nmax = 19; A[] = 0; Do[A[x] = (1 + x A[x]^6)/(1 - x) + O[x]^(nmax + 1) // Normal, nmax + 1]; CoefficientList[A[x], x]
Table[Sum[Binomial[n + 5 k, 6 k] Binomial[6 k, k]/(5 k + 1), {k, 0, n}], {n, 0, 19}]
A000090
Expansion of e.g.f. exp((-x^3)/3)/(1-x).
Original entry on oeis.org
1, 1, 2, 4, 16, 80, 520, 3640, 29120, 259840, 2598400, 28582400, 343235200, 4462057600, 62468806400, 936987251200, 14991796019200, 254860532326400, 4587501779660800, 87162533813555200, 1743250676271104000, 36608259566534656000, 805381710463762432000
Offset: 0
a(3) = 4 because the permutations in S_3 that contain no 3-cycles are the trivial permutation and the 3 transpositions.
- J. Riordan, An Introduction to Combinatorial Analysis, Wiley, 1958, p. 85.
- 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, Wadsworth, Vol. 1, 1986, page 93, problem 7.
-
seq(coeff(convert(series(exp((-x^3)/3)/(1-x),x,50),polynom),x,i)*i!,i=0..30);# series expansion A000090:=n->n!*add((-1)^i/(i!*3^i),i=0..floor(n/3));seq(A000090(n),n=0..30); # formula (Pab Ter)
-
nn=20;Range[0,nn]!CoefficientList[Series[Exp[-x^3/3]/(1-x),{x,0,nn}],x] (* Geoffrey Critzer, Oct 28 2012 *)
-
{a(n) = if( n<0, 0, n! * polcoeff( exp( -(x^3 / 3) + x*O(x^n)) / (1 - x), n))} /* Michael Somos, Jul 28 2009 */
More terms from Pab Ter (pabrlos2(AT)yahoo.com), Oct 22 2005
Comments