A147746 -id:A147746 - cp's OEIS frontend

A124302 Number of set partitions with at most 3 blocks; number of Dyck paths of height at most 4; dimension of space of symmetric polynomials in 3 noncommuting variables.

1, 1, 2, 5, 14, 41, 122, 365, 1094, 3281, 9842, 29525, 88574, 265721, 797162, 2391485, 7174454, 21523361, 64570082, 193710245, 581130734, 1743392201, 5230176602, 15690529805, 47071589414, 141214768241, 423644304722, 1270932914165, 3812798742494, 11438396227481

Offset: 0

Mike Zabrocki, Oct 25 2006

Row sums of triangle in A056241. - Philippe Deléham, Oct 30 2006
Row sums of triangle in A147746. - Philippe Deléham, Dec 04 2008
Hankel transform is := [1, 1, 1, 0, 0, 0, 0, 0, 0, 0, 0, ...]. - Philippe Deléham, Dec 04 2008
Number of nonisomorphic graded posets with 0 and 1 and uniform Hasse graph of rank n with no 3-element antichain. (Uniform used in the sense of Retakh, Serconek and Wilson.  Graded used in Stanley's sense that every maximal chain has the same length n.) - David Nacin, Feb 26 2012
Number of Dyck paths of length 2n and height at most 4. - Ira M. Gessel, Aug 06 2012

			There are 15 set partitions of {1,2,3,4}, only {{1},{2},{3},{4}} has more than 3 blocks, so a(4) = 14.
G.f. = 1 + x + 2*x^2 + 5*x^3 + 14*x^4 + 41*x^5 + 122*x^6 + 365*x^7 + ...

R. Stanley, Enumerative combinatorics, Vol. 1, Cambridge University Press, Cambridge, 1997, pp. 96-100.

Vincenzo Librandi, Table of n, a(n) for n = 0..1000
Per Alexandersson and Frether Getachew, An involution on derangements, arXiv:2105.08455 [math.CO], 2021.
N. Bergeron, C. Reutenauer, M. Rosas and M. Zabrocki, Invariants and Coinvariants of the Symmetric Group in Noncommuting Variables, arXiv:math/0502082 [math.CO], 2005; Canad. J. Math. 60 (2008), no. 2, 266-296.
Giulio Cerbai, Anders Claesson, and Luca Ferrari, Stack sorting with restricted stacks, arXiv:1907.08142 [cs.DS], 2019.
S. Felsner and D. Heldt, Lattice Path Enumeration and Toeplitz Matrices, J. Int. Seq. 18 (2015) # 15.1.3.
Daniel Heldt, On the mixing time of the face flip-and up/down Markov chain for some families of graphs, Dissertation, Mathematik und Naturwissenschaften der Technischen Universitat Berlin zur Erlangung des akademischen Grades Doktor der Naturwissenschaften, 2016.
M. Hyatt and J. Remmel, The classification of 231-avoiding permutations by descents and maximum drop, arXiv preprint arXiv:1208.1052 [math.CO], 2012. - From _N. J. A. Sloane_, Dec 24 2012
V. Jelinek, T. Mansour, and M. Shattuck, On multiple pattern avoiding set partitions, Adv. Appl. Math. 50 (2) (2013) 292-326, - From _N. J. A. Sloane_, Jan 01 2013
Sergey Kitaev, Jeffrey Remmel and Mark Tiefenbruck, Marked mesh patterns in 132-avoiding permutations I, arXiv:1201.6243 [math.CO], 2012-2014 (Corollary 3, case k=4, pages 10-11). - From _N. J. A. Sloane_, May 09 2012
Sergey Kitaev, Jeffrey Remmel, and Mark Tiefenbruck, Quadrant Marked Mesh Patterns in 132-Avoiding Permutations II, Electronic Journal of Combinatorial Number Theory, Volume 15 #A16. (arXiv:1302.2274)
László Németh and László Szalay, Sequences Involving Square Zig-Zag Shapes, J. Int. Seq., Vol. 24 (2021), Article 21.5.2.
V. Retakh, S. Serconek, and R. Wilson, Hilbert Series of Algebras Associated to Directed Graphs and Order Homology, arXiv:1010.6295 [math.RA], 2010-2011.
Santiago Rojas-Rojas, Camila Muñoz, Edgar Barriga, Pablo Solano, Aldo Delgado, and Carla Hermann-Avigliano, Analytic Evolution for Complex Coupled Tight-Binding Models: Applications to Quantum Light Manipulation, arXiv:2310.12366 [quant-ph], 2023. See p. 12.
M. Rosas and B. Sagan, Symmetric Functions in Noncommuting Variables, Transactions of the American Mathematical Society, 358 (2006), no. 1, 215-232.
Index entries for linear recurrences with constant coefficients, signature (4,-3).

Cf. A056272, A123183, A001519, A000110, A008277, A038754, A048328, A068911, A211216.

Essentially the same as A007051.

I:=[1, 1, 2]; [n le 3 select I[n] else  4*Self(n-1) - 3*Self(n-2): n in [1..30]]; // Vincenzo Librandi, Dec 25 2012

a:= proc(n); if n<3 then [1,1,2][n+1]; else 4*a(n-1)-3*a(n-2); fi; end:
# Mike Zabrocki, Oct 25 2006
with(GraphTheory): G:=PathGraph(5): A:= AdjacencyMatrix(G): nmax:=27; for n from 0 to 2*nmax do B(n):=A^n; b(n):=B(n)[1,1]; od: for n from 0 to nmax do a(n):=b(2*n) od: seq(a(n),n=0..nmax);
# Johannes W. Meijer, May 29 2010

a=Exp[x]-1; Range[0, 20]! CoefficientList[Series[1+a+a^2/2+a^3/6, {x,0,20}],x]
Join[{1}, LinearRecurrence[{4, -3}, {1, 2}, 20]] (* David Nacin, Feb 26 2012 *)
CoefficientList[Series[1 / (1 - x / (1 - x / (1 - x / (1 - x)))), {x, 0, 30}], x] (* Vincenzo Librandi, Dec 25 2012 *)
Table[Sum[StirlingS2[n,k],{k,0,3}],{n,0,30}] (* Robert A. Russell, Mar 29 2018 *)

{a(n) = if( n<1, n==0, (3^(n-1) + 1) / 2)}; /* Michael Somos, Apr 03 2014 */

def a(n, adict={0:1, 1:1, 2:2}):
    if n in adict:
        return adict[n]
    adict[n]=4*a(n-1) - 3*a(n-2)
    return adict[n] # David Nacin, Mar 04 2012

O.g.f.: (q^2 - 3*q + 1)/(3*q^2 - 4*q + 1) = Sum_{k=0..3} (q^k/Product_{i=1..k} (1-i*q)).
a(n) = 4*a(n-1) - 3*a(n-2); a(0) = 1, a(1) = 1, a(2) = 2, a(n) = Sum_{k=1..3} A008277(n,k).
Inverse binomial transform of A007581. - Philippe Deléham, Oct 30 2006
a(n) = Sum_{k=0..n} A056241(n,k), n >= 1. - Philippe Deléham, Oct 30 2006
a(0) = 1, a(n) = (3^(n-1) + 1)/2 for n >= 1, see A007051. - Philippe Deléham, Oct 30 2006
E.g.f.: (2 + 3*exp(x) + exp(3x))/6.
G.f.: 1 / (1 - x / (1 - x / (1 - x / (1 - x)))). - Michael Somos, May 03 2012
G.f.: 1 + x + 3*x^2*U(0)/2 where U(k) = 1 + 2/(3*3^k + 3*3^k/(1 - 18*x*3^k/ (9*x*3^k - 1/U(k+1)))); (continued fraction, 4-step). - Sergei N. Gladkovskii, Nov 01 2012
G.f.: 1+x*G(0) where G(k) = 1 + 2*x/( 1-2*x - x*(1-2*x)/(x + (1-2*x)*2/G(k+1) )); (recursively defined continued fraction). - Sergei N. Gladkovskii, Dec 10 2012
a(n) = Sum_{k=0..3} Stirling2(n,k). - Robert A. Russell, Mar 29 2018
G.f.: Sum_{j=0..k} A248925(k,j)*x^j / Product_{j=1..k} 1-j*x with k=3. - Robert A. Russell, Apr 25 2018

A147748 Row sums of Riordan array ((1-3x+x^2)/(1-4x+3x^2), x(1-2x)/(1-4x+3x^2)).

Original entry on oeis.org

1, 2, 6, 20, 70, 250, 900, 3250, 11750, 42500, 153750, 556250, 2012500, 7281250, 26343750, 95312500, 344843750, 1247656250, 4514062500, 16332031250, 59089843750, 213789062500, 773496093750, 2798535156250, 10125195312500

Offset: 0

Paul Barry, Nov 11 2008

Row sums of A147747. Binomial transform of A061646.
Counts all paths of length (2*n), n>=0, starting at the initial node on the path graph P_9, see the Maple program. - Johannes W. Meijer, May 29 2010
From L. Edson Jeffery, Apr 19 2011: (Start)
For the 5 X 5 unit-primitive matrix (see [Jeffery])
A_(10,1) = [0,1,0,0,0; 1,0,1,0,0; 0,1,0,1,0; 0,0,1,0,1; 0,0,0,2,0],
a(n) = (Trace([A_(10,1)]^(2*n)))/5. (See also A189315.) (End)

S. Felsner and D. Heldt, Lattice Path Enumeration and Toeplitz Matrices, J. Int. Seq. 18 (2015) # 15.1.3.
L. Edson Jeffery, Unit-primitive matrices.
Index entries for linear recurrences with constant coefficients, signature (5,-5).

Cf. A000984, A030191, A061646, A081567, A147746, A147747, A178381, A189315.

with(GraphTheory): G:=PathGraph(9): A:= AdjacencyMatrix(G): nmax:=24; n2:=nmax*2: for n from 0 to n2 do B(n):=A^n; a(n):= add(B(n)[1,k], k=1..9); od: seq(a(2*n), n=0..nmax); # Johannes W. Meijer, May 29 2010

(1 - 3x + x^2)/(1 - 5x + 5x^2) + O[x]^25 // CoefficientList[#, x]& (* Jean-François Alcover, Oct 05 2016 *)

G.f.: (1-3*x+x^2)/(1-5*x+5*x^2).
a(n) = 5*a(n-1) - 5*a(n-2) for n > 2, a(0)=1, a(1)=2, a(2)=6. - Philippe Deléham, Nov 13 2008
For n >= 1: a(n) = (2/5)*((5-sqrt(5))/2)^n + (2/5)*((5+sqrt(5))/2)^n. - Richard Choulet, Nov 14 2008
G.f.: 1/(1-2x/(1-x/(1-x/(1-x)))) (hence sequence approximates A000984 in first few terms). - Paul Barry, Aug 05 2009
a(n) = (1/5)*Sum_{k=1..5} (x_k)^(2*n), x_k=2*cos((2*k-1)*Pi/10). - L. Edson Jeffery, Apr 19 2011
From R. J. Mathar, Apr 20 2011: (Start)
a(n) = A030191(n) - 3*A030191(n-1) + A030191(n-2).
a(n) = 2*A081567(n-1), n > 0. (End)
a(n) = Sum_{k=0..n} A147746(n,k)*2^k. - Philippe Deléham, Oct 30 2011
E.g.f.: (1 + 4*exp(5*x/2)*cosh(sqrt(5)*x/2))/5. - Stefano Spezia, Jul 09 2024

A215936 a(n) = -2*a(n-1) + a(n-2) for n > 2, with a(0) = a(1) = 1, a(2) = 0.

Original entry on oeis.org

1, 1, 0, 1, -2, 5, -12, 29, -70, 169, -408, 985, -2378, 5741, -13860, 33461, -80782, 195025, -470832, 1136689, -2744210, 6625109, -15994428, 38613965, -93222358, 225058681, -543339720, 1311738121, -3166815962, 7645370045, -18457556052, 44560482149

Offset: 0

Michael Somos, Aug 28 2012

BINOMIAL transform is A052955.

Essentially the same as A000129, A069306, A048624, A215928, A077985, and A176981. - R. J. Mathar, Sep 08 2013

			G.f. = 1 + x + x^3 - 2*x^4 + 5*x^5 - 12*x^6 + 29*x^7 - 70*x^8 + 169*x^9 - 408*x^10 + ...

Vincenzo Librandi, Table of n, a(n) for n = 0..1000
M. C. Firengiz and A. Dil, Generalized Euler-Seidel method for second order recurrence relations, Notes on Number Theory and Discrete Mathematics, Vol. 20, 2014, No. 4, 21-32.
Index entries for linear recurrences with constant coefficients, signature (-2,1).

Cf. A001542, A001653, A052955, A077985.

[1,1] cat [n le 2 select (n-1) else -2*Self(n-1)+Self(n-2): n in [1..35] ]; // Vincenzo Librandi, Sep 09 2013

CoefficientList[Series[(1 + 3 x + x^2)/(1 + 2 x - x^2), {x, 0, 40}], x] (* Vincenzo Librandi, Sep 09 2013 *)
a[ n_] := With[ {m = If[ n < 1, 1 - n, n], s = If[ n < 1, (-1)^n, 1]}, s SeriesCoefficient[ x (1 + 2 x) / (1 + 2 x - x^2), {x, 0, m}]]; (* Michael Somos, Mar 19 2019 *)

{a(n) = my(m=n, s=1); if(n<1, m=1-n; s=(-1)^n); s * polcoeff( x * (1 + 2*x) / (1 + 2*x - x^2) + x * O(x^m), m)}; /* Michael Somos, Mar 19 2019 */

G.f.: 1 / (1 - x / (1 + x / (1 + x / (1 + x)))) = (1 + 3*x + x^2) / (1 + 2*x - x^2).
a(n + 3) = A077985(n). a(n) * a(n+2) - a(n+1)^2 = -(-1)^n.
a(2*n + 1) = A001653(n). a(2*n + 2) = -A001542(n).
a(n) = Sum_{k=0..n} A147746(n,k)*(-1)^(n-k). - Philippe Deléham, Aug 30 2012
G.f.: 1 + x + x^2/(1-x)  - G(0)*x^2 /(2-2*x), where G(k)= 1 + 1/(1 - x*(2*k-1)/(x*(2*k+1) + 1/G(k+1) )); (continued fraction). - Sergei N. Gladkovskii, Aug 10 2013
a(n) = (-1)^n a(1-n) = A000129(-1-n) if n < 0. a(n-2) = 2*a(n-1) + a(n) if n<1 or n>2. - Michael Somos, Mar 19 2019
E.g.f.: exp(-x)*(4*cosh(sqrt(2)*x) + 3*sqrt(2)*sinh(sqrt(2)*x))/2 - 1. - Stefano Spezia, Oct 31 2024

A147747 Riordan array ((1-3x+x^2)/(1-4x+3x^2), x(1-2x)/(1-4x+3x^2)).

Original entry on oeis.org

1, 1, 1, 2, 3, 1, 5, 9, 5, 1, 14, 28, 20, 7, 1, 41, 89, 75, 35, 9, 1, 122, 285, 273, 154, 54, 11, 1, 365, 913, 974, 634, 273, 77, 13, 1, 1094, 2918, 3420, 2502, 1256, 440, 104, 15, 1, 3281, 9297, 11850, 9578, 5439, 2239, 663, 135, 17, 1

Offset: 0

Paul Barry, Nov 11 2008

Triangle [1,1,1,1,0,0,0,....] DELTA [1,0,0,0,....] with DELTA as in A084938.

Row sums are A147748. A147747=A147746*A007318.

			Triangle begins
1,
1, 1,
2, 3, 1,
5, 9, 5, 1,
14, 28, 20, 7, 1,
41, 89, 75, 35, 9, 1,
122, 285, 273, 154, 54, 11, 1

(* The function RiordanArray is defined in A256893. *)
RiordanArray[(1-3#+#^2)/(1-4#+3#^2)&, # (1-2#)/(1-4#+3#^2)&, 10] // Flatten (* Jean-François Alcover, Jul 19 2019 *)

T(n,k) = 4*T(n-1,k) + T(n-1,k-1) - 3*T(n-2,k) - 2*T(n-2,k-1), T(0,0) = T(0,1) = T(1,1) = T(2,2) = 1, T(2,0) = 2, T(2,1) = 3, T(n,k) = 0 if k>n or if k<0. - Philippe Deléham, Oct 29 2013

G.f.: (1 - 3*x + x^2)/(1 - 4*x + 3*x^2 - x*y + 2*x^2*y). - Philippe Deléham, Oct 29 2013

cp's OEIS Frontend

A124302 Number of set partitions with at most 3 blocks; number of Dyck paths of height at most 4; dimension of space of symmetric polynomials in 3 noncommuting variables.

Views

Author

Keywords

Comments

Examples

References

Links

Crossrefs

Programs

Magma

Maple

Mathematica

PARI

Python

Formula

A147748 Row sums of Riordan array ((1-3x+x^2)/(1-4x+3x^2), x(1-2x)/(1-4x+3x^2)).

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Maple

Mathematica

Formula

A215936 a(n) = -2*a(n-1) + a(n-2) for n > 2, with a(0) = a(1) = 1, a(2) = 0.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Magma

Mathematica

PARI

Formula

A147747 Riordan array ((1-3x+x^2)/(1-4x+3x^2), x(1-2x)/(1-4x+3x^2)).

Views

Author

Keywords

Comments

Examples

Programs

Mathematica

Formula