A049611 -id:A049611 - cp's OEIS frontend

A059474 Triangle read by rows: T(n,k) is coefficient of z^nw^k in 1/(1 - 2z - 2w + 2z*w) read by rows in order 00, 10, 01, 20, 11, 02, ...

1, 2, 2, 4, 6, 4, 8, 16, 16, 8, 16, 40, 52, 40, 16, 32, 96, 152, 152, 96, 32, 64, 224, 416, 504, 416, 224, 64, 128, 512, 1088, 1536, 1536, 1088, 512, 128, 256, 1152, 2752, 4416, 5136, 4416, 2752, 1152, 256, 512, 2560, 6784, 12160, 16032, 16032, 12160, 6784, 2560, 512

Offset: 0

N. J. A. Sloane, Feb 03 2001; revised Jun 12 2005

Pascal-like triangle: start with 1 at top; every subsequent entry is the sum of everything above you, plus 1.

			Triangle begins as:
   n\k [0]  [1]  [2]  [3]  [4]  [5]  [6] ...
  [0]   1;
  [1]   2,   2;
  [2]   4,   6,   4;
  [3]   8,  16,  16,   8;
  [4]  16,  40,  52,  40,  16;
  [5]  32,  96, 152, 152,  96,  32;
  [6]  64, 224, 416, 504, 416, 224,  64;
       ...

G. C. Greubel, Rows n = 0..50 of the triangle, flattened

Cf. A000079, A001792, A007070, A057711, A077957, A084773.

See A059576 for a similar triangle.

A059474:= func< n,k | (&+[(-1)^j*2^(n-j)*Binomial(n-k,j)*Binomial(n-j,n-k): j in [0..n-k]]) >;
[A059474(n,k): k in [0..n], n in [0..12]]; // G. C. Greubel, May 21 2023

read transforms; SERIES2(1/(1-2*z-2*w+2*z*w),x,y,12): SERIES2TOLIST(%,x,y,12);
# Alternative
T := (n, k) -> 2^n*binomial(n, k)*hypergeom([-k, -n + k], [-n], 1/2):
for n from 0 to 10 do seq(simplify(T(n, k)), k = 0 .. n) end do; # Peter Luschny, Nov 26 2021

Table[(-1)^k*2^n*JacobiP[k, -n-1,0,0], {n,0,12}, {k,0,n}]//Flatten (* G. C. Greubel, Oct 04 2017; May 21 2023 *)

def A059474(n,k): return 2^n*binomial(n, k)*simplify(hypergeometric([-k, k-n], [-n], 1/2))
flatten([[A059474(n,k) for k in range(n+1)] for n in range(13)]) # G. C. Greubel, May 21 2023

G.f.: 1/(1 - 2*z - 2*w + 2*z*w).
T(n, k) = Sum_{j=0..n} (-1)^j*2^(n + k - j)*C(n, j)*C(n + k - j, n).
T(n, 0) = T(n, n) = A000079(n).
T(2*n, n) = A084773(n).
T(n, k) = 2^n*binomial(n, k)*hypergeom([-k, k - n], [-n], 1/2). - Peter Luschny, Nov 26 2021
From G. C. Greubel, May 21 2023: (Start)
T(n, n-k) = T(n, k).
Sum_{k=0..n} T(n, k) = A007070(n).
Sum_{k=0..n} (-1)^k * T(n, k) = A077957(n).
T(n, 1) = A057711(n+1) = 2*A001792(n) - [n=0].
T(n, 2) = 4*A049611(n-1). (End)

A081892 Second binomial transform of C(n+2,2).

Original entry on oeis.org

1, 5, 22, 90, 351, 1323, 4860, 17496, 61965, 216513, 747954, 2558790, 8680203, 29229255, 97785144, 325241892, 1076168025, 3544180029, 11622614670, 37967207922, 123587135991, 400980206115, 1297083797172, 4184141281200

Offset: 0

Paul Barry, Mar 30 2003

Binomial transform of A049611(n+1).
2nd binomial transform of C(n+2,2), A000217.
3rd binomial transform of (1,2,1,0,0,0,.....)

G. C. Greubel, Table of n, a(n) for n = 0..1000
Index entries for linear recurrences with constant coefficients, signature (9,-27,27).

Cf. A081893.

A right-edge column of triangle A024462.

m:=30; R:=PowerSeriesRing(Integers(), m); Coefficients(R!((1-2*x)^2/(1-3*x)^3)); // G. C. Greubel, Oct 18 2018

LinearRecurrence[{9, -27, 27}, {1, 5, 22}, 50] (* G. C. Greubel, Oct 18 2018 *)

x='x+O('x^30); Vec((1-2*x)^2/(1-3*x)^3) \\ G. C. Greubel, Oct 18 2018

a(n) = 3^(n - 2)*(n + 2)*(n + 9)/2 = 3^n*(n^2 + 11*n + 18)/18.
G.f.: (1 - 2*x)^2/(1 - 3*x)^3.
E.g.f.: (2 + 4*x + x^2)*exp(3*x)/2. - G. C. Greubel, Oct 18 2018

A100312 Number of 3 X n binary matrices avoiding simultaneously the right angled numbered polyomino patterns (ranpp) (10;0) and (01;1).

Original entry on oeis.org

1, 8, 32, 104, 304, 832, 2176, 5504, 13568, 32768, 77824, 182272, 421888, 966656, 2195456, 4947968, 11075584, 24641536, 54525952, 120061952, 263192576, 574619648, 1249902592, 2709520384, 5855248384, 12616466432, 27111981056, 58116276224, 124285616128

Offset: 0

Sergey Kitaev, Nov 13 2004

An occurrence of a ranpp (xy;z) in a matrix A=(a(i,j)) is a triple (a(i1,j1), a(i1,j2), a(i2,j1)) where i1 < i2, j1 < j2 and these elements are in the same relative order as those in the triple (x,y,z). In general, the number of m X n 0-1 matrices in question is given by the g.f. 2*x*y/(1-2*(x+y-x*y)).

G. C. Greubel, Table of n, a(n) for n = 0..1000
S. Kitaev, On multi-avoidance of right angled numbered polyomino patterns, Integers: Electronic Journal of Combinatorial Number Theory 4 (2004), A21, 20pp.
Index entries for linear recurrences with constant coefficients, signature (6,-12,8).

Cf. A049611, this sequence (m=3), A100313 (m=4).

[2^(n-1)*(n^2+5*n+2): n in [0..50]]; // G. C. Greubel, Feb 01 2023

Table[2^(n-1)*(n^2+5*n+2), {n,0,50}] (* G. C. Greubel, Feb 01 2023 *)

vector(50, n, (n^2 + 5*n + 2) * 2^(n-1)) \\ Michel Marcus, Dec 01 2014

[2^(n-1)*(n^2+5*n+2) for n in range(51)] # G. C. Greubel, Feb 01 2023

G.f.: 1 + 8*x*(1-x)^2/(1-2*x)^3.
a(n) = 2^(n-1) * (n^2 + 5*n + 2).
a(n) = 8 * A049611(n) for n>0.
E.g.f.: (1 + 6*x + 2*x^2)*exp(2*x). - G. C. Greubel, Feb 01 2023

a(0)=1 prepended by Alois P. Heinz, Dec 21 2018

A240837 Partitions as specified by composition into an even number of parts.

Original entry on oeis.org

1, 1, 1, 2, 1, 1, 1, 2, 2, 3, 2, 1, 1, 1, 1, 1, 2, 2, 2, 3, 3, 2, 2, 1, 4, 3, 1, 2, 1, 1, 3, 2, 1, 1, 1, 1, 1, 2, 2, 2, 2, 3, 3, 3, 2, 2, 2, 1, 4, 4, 3, 3, 1, 2, 2, 1, 1, 3, 3, 2, 5, 4, 1, 3, 1, 1, 4, 2, 2, 1, 1, 1, 3, 2, 2, 4, 3, 3, 2, 1

Offset: 2

Franklin T. Adams-Watters, Apr 13 2014

The composition specifies the run lengths of the boundary of the Ferrers diagram of the partition.

Taking the n-th row as multiple partitions, it consists of those partitions with the first hook size (largest part plus number of parts minus 1) equal to n-1. The number of integers in this n-th row is A001792(n-2), and the row sum is A049611(n-1).

			For row 11, the 11th row in A240750 is 2,1,1,1. This gives us the Ferrers diagram:
* * *
* *
with boundary 2 horizontal, 1 vertical, 1 horizontal, 1 vertical. This is the diagram for partition [2,2,1].
The table starts:
[]
(none)
1
1,1; 2
1,1,1; 2,2; 3; 2,1
1,1,1,1; 2,2,2; 3,3; 2,2,1; 4; 3,1; 2,1,1; 3,2

A240750, A066099, A125106.

evil(n) = local(r=0, m=n); while(m>0, if(m%2==1, r=1-r); m\=2); n*2+r
A066099row(n) = {local(v=vector(n), j=0, k=0);
   while(n>0, k++; if(n%2==1, v[j++]=k; k=0); n\=2);
   vector(j, i, v[j-i+1])}
A240750row(n) = A066099row(evil(n))
partpath(v) = {local(j=0,n=0,m=0,r);
   forstep(k=1,#v,2,n+=v[k];m+=v[k+1]);
   r=vector(n);
   forstep(k=1,#v,2,for(i=1,v[k],r[j++]=m);m-=v[k+1]);
   r}
arow(n) = partpath(A240750row(n))

A089378 Number of one-step transitions between all unlabeled hierarchies of n elements.

Original entry on oeis.org

0, 6, 24, 104, 382, 1414, 4870

Offset: 1

Thomas Wieder, Dec 27 2003

nonn

For given n (= number of elements) we consider two hierarchies H1 and H2. We ask whether a one-step transition is possible from H1 to H2 (if it is possible, then there is also a one-step transition from H2 to H1). In a one-step transition just one single element is moved from its position in H1 to its position in H2.
For example, consider n=4 and H1 = [[2], [2]], H2 = [[2], [1, 1]]. H1 consists of two subhierarchies S1H1 = [2] and S2H1 = [2] with two elements on level 1 in both cases. In H2, we have S1H2 = [2] and S2H2 = [1,1] which means one element on level 1 and one element on level 2 in S2H2. A one-step transition is possible, just move one element in S2H1 (or S1H1) from level 1 to level 2.
As a counterexample, for H1 = [[2], [2]] and H2 = [[1], [1, 1, 1]], a one-step transition does not exist; one needs to move two elements here. For given n, consider the set of all possible unlabeled hierarchies.
How many one-step transitions exist among them? (We count H1 -> H2 and H2 -> H1 as one transition only, not two. The transition H1 -> H1 is a zero-step transition and is not counted.) Answer: For unlabeled hierarchies, one has (with NOOST = number of one-step transitions) n = 1, NOOST = 0; n = 2, NOOST = 3; n = 3, NOOST = 12; n = 4, NOOST = 51; n = 5, NOOST = 175; n = 6, NOOST = 570; n = 7, NOOST = 1914.
We may ask for the number of one-step transitions (NOOST) between all unlabeled hierarchies of n elements with the restriction that no subhierarchies are allowed. As an example, consider n = 4 and the hierarchy H1 = [[2,2]] with two elements on level 1 and two on level 2. Starting from H1 the hierarchies [[1, 3]], [[2, 1, 1]], [[1, 2, 1]] can be reached by moving one element only, but [[1, 1, 2]] cannot be reached in a one-step transitition. The solution is n = 1, NOOST = 0; n = 2, NOOST = 1; n = 3, NOOST = 4; n = 4, NOOST = 13; n = 5, NOOST = 38; n = 6, NOOST = 104; n = 7, NOOST = 272; n = 8, NOOST = 688; n = 9, NOOST = 1696. This is sequence A049611.

			Consider the unlabeled hierarchies for n = 3 elements. Take for example H1 = [1,2] and H2 = [1,1,1]. A one-step transition is possible between H1 and H2 by moving one element of the second level (occupied by two elements) of H1 on the third level, which gives H2.
As a counterexample, consider H1 and H3 = [[1], [1], [1]]. H3 consists of three subhierarchies. In order to get from H1 to H3 one needs to move two elements; no one-step transition is possible.

N. J. A. Sloane and Thomas Wieder, The Number of Hierarchical Orderings, Order 21 (2004), 83-89.

Cf. A034691, A049611, A075729, A093694.

A (rather long) Maple program is available from the author.

A114693 Number of returns to the x-axis in all hill-free Schroeder paths of length 2n+4. A Schroeder path of length 2n is a lattice path from (0,0) to (2n,0) consisting of U=(1,1), D=(1,-1) and H=(2,0) steps and never going below the x-axis. A hill is a peak at height 1.

Original entry on oeis.org

2, 10, 48, 232, 1138, 5666, 28592, 145984, 752978, 3918282, 20547456, 108482952, 576187554, 3076640898, 16506527392, 88938911296, 481067145826, 2611212958154, 14218923060752, 77653486423528, 425227486222482

Offset: 0

Emeric Deutsch, Dec 26 2005

nonn

			a(0)=2 because in the three hill-free Schroeder paths of length 4, namely HH, UH(D) and UUD(D), we have altogether 2 returns to the x-axis (shown between parentheses).

Vincenzo Librandi, Table of n, a(n) for n = 0..300

Cf. A049611, A104219, A114692.

G:=2*(1-3*z-sqrt(1-6*z+z^2))/z^2/(1+z+sqrt(1-6*z+z^2))^2: Gser:=series(G,z=0,30): 2,seq(coeff(Gser,z^n),n=1..23);

CoefficientList[Series[2*(1-3*x-Sqrt[1-6*x+x^2])/(x*(1+x+Sqrt[1 -6*x+x^2]))^2, {x, 0, 20}], x] (* Vaclav Kotesovec, Oct 19 2012 *)

a(n):=sum((k^3+8*k^2+15*k+8)*sum((-1)^j*2^(n+1-j)*binomial(n+1,j)*binomial(2*n-k-j,n),j,0,n-k),k,0,(n+1))/(8*(n+1)); /* Vladimir Kruchinin, Feb 27 2016 */

G.f.: 2*(1-3*z-sqrt(1-6*z+z^2))/(z*(1+z+sqrt(1-6*z+z^2)))^2.
a(n) = Sum_{k=0..1+floor(n/2)} k*A114692(n+2,k).
Recurrence: (n+4)*(7*n+1)*a(n) = (42*n^2 + 109*n + 49)*a(n-1) - (7*n^2 - 4*n - 5)*a(n-2) - 2*(n-2)*a(n-3). - Vaclav Kotesovec, Oct 19 2012
a(n) ~ sqrt(15900+11243*sqrt(2))*(3+2*sqrt(2))^n/(4*sqrt(Pi)*n^(3/2)). - Vaclav Kotesovec, Oct 19 2012
a(n) = Sum_{k=0..n+1} ( (k^3+8*k^2+15*k+8) * Sum_{j=0..n-k} ((-1)^j*2^(n+1-j)*binomial(n+1,j)*binomial(2*n-k-j,n)) )/(8*(n+1)). - Vladimir Kruchinin, Feb 27 2016.

A236471 Riordan array ((1-x)/(1-2x), x(1-x)/(1-2x)^2).

Original entry on oeis.org

1, 1, 1, 2, 4, 1, 4, 13, 7, 1, 8, 38, 33, 10, 1, 16, 104, 129, 62, 13, 1, 32, 272, 450, 304, 100, 16, 1, 64, 688, 1452, 1289, 590, 147, 19, 1, 128, 1696, 4424, 4942, 2945, 1014, 203, 22, 1, 256, 4096, 12896, 17584, 13073, 5823, 1603, 268, 25, 1, 512, 9728

Offset: 0

Philippe Deléham, Jan 26 2014

Row sums are A052936(n).
Diagonal sums are A121449(n).
The triangle T'(n,k) = T(n,k)*(-1)^(n+k) is the inverse of the Riordan array in A090285.

			Triangle begins:
1;
1, 1;
2, 4, 1;
4, 13, 7, 1;
8, 38, 33, 10, 1;
16, 104, 129, 62, 13, 1;
32, 272, 450, 304, 100, 16, 1;
64, 688, 1452, 1289, 590, 147, 19, 1;

G. C. Greubel, Table of n, a(n) for the first 100 rows, flattened

Cf. A011782, A049611, A000012, A016777, A062708.

CoefficientList[CoefficientList[Series[(2*x^2-3*x+1)/((x^2-x)*y +4*x^2 - 4*x+1), {x,0,20}, {y,0,20}], x], y]//Flatten (* G. C. Greubel, Apr 19 2018 *)

T(n,k):=sum(binomial(m+k,2*k)*binomial(n-1,n-m),m,0,n); /* Vladimir Kruchinin, Apr 21 2015 */

for(n=0,20, for(k=0,n, print1(sum(m=0, n, binomial(m+k,2*k)* binomial(n-1,n-m)), ", "))) \\ G. C. Greubel, Apr 19 2018

T(n,0) = A011782(n), T(n,1) = A049611(n), T(n,n) = A000012(n) = 1, T(n+1,n) = A016777(n), T(n+2,n) = A062708(n+1).
G.f.: (2*x^2-3*x+1)/((x^2-x)*y+4*x^2-4*x+1). - Vladimir Kruchinin, Apr 21 2015
T(n,k) = Sum_{m=0..n} C(m+k,2*k)*C(n-1,n-m). - Vladimir Kruchinin, Apr 21 2015

A124847 Triangle read by rows: T(n,k) = k(k+1)*binomial(n-1, k-1)/2 (1 <= k <= n).

Original entry on oeis.org

1, 1, 3, 1, 6, 6, 1, 9, 18, 10, 1, 12, 36, 40, 15, 1, 15, 60, 100, 75, 21, 1, 18, 90, 200, 225, 126, 28, 1, 21, 126, 350, 525, 441, 196, 36, 1, 24, 168, 560, 1050, 1176, 784, 288, 45, 1, 27, 216, 840, 1890, 2646, 2352, 1296, 405, 55, 1, 30, 270, 1200, 3150, 5292, 5880

Offset: 1

Gary W. Adamson, Nov 10 2006

Sum of row n gives A049611(n).

Triangle is P*A, where P is the Pascal triangle written as a lower triangular matrix and C is the diagonal matrix of the triangular numbers 1, 3, 6, 10, ....

			First few rows of the triangle:
  1;
  1,   3;
  1,   6,   6;
  1,   9,  18,  10;
  1,  12,  36,  40,  15;
  1,  15,  60, 100,  75,  21;
  ...
Sum of row 3 = 38 = (1 + 9 + 18 + 10) = A049611(3).

Cf. A049611.

T:=(n,k)->k*(k+1)*binomial(n-1,k-1)/2: for n from 1 to 12 do seq(T(n,k),k=1..n) od; # yields sequence in triangular form

Edited by N. J. A. Sloane, Nov 24 2006

A133729 A007318 * A133728.

Original entry on oeis.org

1, 1, 3, 2, 6, 5, 4, 12, 15, 7, 8, 24, 35, 28, 9, 16, 48, 75, 77, 45, 11, 32, 96, 155, 182, 144, 66, 13, 64, 192, 315, 399, 378, 242, 91, 15, 128, 384, 635, 840, 891, 704, 377, 120, 17

Offset: 1

Gary W. Adamson, Sep 21 2007

Row sums = A049611: (1, 4, 13, 38, 104, 272, ...).

			First few rows of the triangle:
   1;
   1,  3;
   2,  6,  5;
   4, 12, 15,  7;
   8, 24, 35, 28,  9;
  16, 48, 75, 77, 45, 11;
  ...

Cf. A133728, A049611.

Binomial transform of triangle A133728.

cp's OEIS Frontend

A059474 Triangle read by rows: T(n,k) is coefficient of z^n*w^k in 1/(1 - 2*z - 2*w + 2*z*w) read by rows in order 00, 10, 01, 20, 11, 02, ...

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Magma

Maple

Mathematica

SageMath

Formula

A081892 Second binomial transform of C(n+2,2).

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Magma

Mathematica

PARI

Formula

A100312 Number of 3 X n binary matrices avoiding simultaneously the right angled numbered polyomino patterns (ranpp) (10;0) and (01;1).

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Magma

Mathematica

PARI

SageMath

Formula

Extensions

A240837 Partitions as specified by composition into an even number of parts.

Views

Author

Keywords

Comments

Examples

Crossrefs

Programs

PARI

A089378 Number of one-step transitions between all unlabeled hierarchies of n elements.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Maple

A114693 Number of returns to the x-axis in all hill-free Schroeder paths of length 2n+4. A Schroeder path of length 2n is a lattice path from (0,0) to (2n,0) consisting of U=(1,1), D=(1,-1) and H=(2,0) steps and never going below the x-axis. A hill is a peak at height 1.

Views

Author

Keywords

Examples

Links

Crossrefs

Programs

Maple

Mathematica

Maxima

Formula

A236471 Riordan array ((1-x)/(1-2*x), x(1-x)/(1-2*x)^2).

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

A059474 Triangle read by rows: T(n,k) is coefficient of z^nw^k in 1/(1 - 2z - 2w + 2z*w) read by rows in order 00, 10, 01, 20, 11, 02, ...

A236471 Riordan array ((1-x)/(1-2x), x(1-x)/(1-2x)^2).