A100312 -id:A100312 - cp's OEIS frontend

A076616 Number of permutations of {1,2,...,n} that result in a binary search tree (when elements of the permutation are inserted in that order) of height n-1 (i.e., the second largest possible height).

0, 0, 0, 2, 16, 64, 208, 608, 1664, 4352, 11008, 27136, 65536, 155648, 364544, 843776, 1933312, 4390912, 9895936, 22151168, 49283072, 109051904, 240123904, 526385152, 1149239296, 2499805184, 5419040768, 11710496768, 25232932864, 54223962112, 116232552448

Offset: 0

Jeffrey Shallit, Oct 22 2002

			a(3) = 2 because only the permutations (2,1,3) and (2,3,1) result in a search tree of height 2 (notice we count empty external nodes in determining the height). The largest such trees are of height 3.

Alois P. Heinz, Table of n, a(n) for n = 0..1000
Index entries for linear recurrences with constant coefficients, signature (6,-12,8).

Lower diagonal of A195581 or of A244108.

Cf. A049611, A076615, A084851, A100312.

a:= n-> max(-(<<0|1|0>, <0|0|1>, <8|-12|6>>^n. <<1/2, 1, 1>>)[1$2], 0):
seq(a(n), n=0..40);  # Alois P. Heinz, Sep 20 2011

Join[{0, 0, 0}, LinearRecurrence[{6, -12, 8}, {2, 16, 64}, 40]] (* Jean-François Alcover, Jan 09 2025 *)

concat(vector(3), Vec(2*x^3*(1+2*x-4*x^2)/(1-2*x)^3 + O(x^50))) \\ Colin Barker, May 16 2016

G.f.: 2*(4*x^2-2*x-1)*x^3/(2*x-1)^3. - Alois P. Heinz, Sep 20 2011
From Colin Barker, May 16 2016: (Start)
a(n) = 2^(n-3)*(n^2-n-4) for n>2.
a(n) = 6*a(n-1)-12*a(n-2)+8*a(n-3) for n>5.
(End)
From Alois P. Heinz, May 31 2022: (Start)
a(n) = 2 * A100312(n-3) for n>=3.
a(n) = 16 * A049611(n-3) = 16 * A084851(n-4) for n>=4. (End)

More terms from Alois P. Heinz, Sep 20 2011

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

Original entry on oeis.org

1, 16, 96, 400, 1408, 4480, 13312, 37632, 102400, 270336, 696320, 1757184, 4358144, 10649600, 25690112, 61276160, 144703488, 338690048, 786432000, 1812987904, 4152360960, 9453961216, 21407727616, 48234496000, 108179488768, 241591910400, 537407782912

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 (8,-24,32,-16).

Cf. A055585, A100312 (m=3), this sequence (m=4).

[2^n*n*(n^2+9*n+14)/3 +0^n: n in [0..40]]; // G. C. Greubel, Feb 01 2023

Table[If[n==0, 1, 2^n*n*(n^2+9*n+14)/3], {n,0,40}] (* G. C. Greubel, Feb 01 2023 *)

vector(50, n, n*(n^2+9*n+14) * 2^n / 3) \\ Michel Marcus, Dec 01 2014

[2^n*n*(n^2+9*n+14)/3 +0^n for n in range(41)] # G. C. Greubel, Feb 01 2023

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

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

A100631 Triangle read by rows: T(n,k) = 2*(T(n-1,k-1) - T(n-2,k-1) + T(n-1,k)) for 0 < k < n, T(n,0) = T(n,n) = 1.

Original entry on oeis.org

1, 1, 1, 1, 2, 1, 1, 4, 4, 1, 1, 8, 12, 8, 1, 1, 16, 32, 32, 16, 1, 1, 32, 80, 104, 80, 32, 1, 1, 64, 192, 304, 304, 192, 64, 1, 1, 128, 448, 832, 1008, 832, 448, 128, 1, 1, 256, 1024, 2176, 3072, 3072, 2176, 1024, 256, 1, 1, 512, 2304, 5504, 8832, 10272, 8832, 5504, 2304, 512, 1

Offset: 0

Reinhard Zumkeller, Dec 03 2004

From Petros Hadjicostas, Feb 09 2021: (Start)
The rectangular version (R(n,k): n,k >= 0) of this symmetric triangular array (T(n,k): 0 <= k <= n) is given by R(n,k) = T(n+k,k) for n,k >= 0. Conversely, T(n,k) = R(n-k, k) for 0 <= k <= n.
Note that [o.g.f of R](x,y) = [o.g.f. of T](x, y/x) and [o.g.f of T](x,y) = [o.g.f of R](x,x*y). (End)
From Petros Hadjicostas, Feb 10 2021: (Start)
All the conjectures below are true because one has to prove only one of them, and the rest follow from the proved one.
As Peter Luschny pointed out, one has to show only that the function S(n,k) = 2^n*hypergeom([-k + 1, n], [1], -1) satisfies the recurrence S(n,k) = 2*(S(n,k-1) - S(n-1,k-1) + S(n-1,k)) for n, k > 0 and the initial conditions S(n,0) = S(0,n) = 1 for n >= 0.
This is quite easy to achieve because S(n,k) = 2^n*Sum_{s=0}^{k-1} binomial(k-1,s)*binomial(n+s-1,s) for n >= 0 and k >= 1. The proof of the recurrence relies on the identity binomial(m,n) = binomial(m-1, n) + binomial(m-1,n-1).
Note that without the 2^n in the formula R(n,k) = 2^n*hypergeom([-k + 1, n], [1], -1), we essentially get array A049600.
In addition, note that without the 2^(n-k-1) in the formula T(n,k+1) = 2^(n-k-1)*hypergeom([-k, n-k+1], [1], -1), we essentially get A208341 (without the first column and the main diagonal of T). (End)

			From _Petros Hadjicostas_, Feb 09 2021: (Start)
Triangle T(n,k) (with rows n >= 0 and columns 0 <= k <= n) begins:
  1,
  1,   1,
  1,   2,    1,
  1,   4,    4,    1,
  1,   8,   12,    8,    1,
  1,  16,   32,   32,   16,    1,
  1,  32,   80,  104,   80,   32,    1,
  1,  64,  192,  304,  304,  192,   64,    1,
  1, 128,  448,  832, 1008,  832,  448,  128,   1,
  1, 256, 1024, 2176, 3072, 3072, 2176, 1024, 256, 1,
  ...
Rectangular array R(n,k) (with rows n >= 0 and columns k >= 0) begins:
  1,   1,    1,    1,     1,     1,      1,       1, ...
  1,   2,    4,    8,    16,    32,     64,     128, ...
  1,   4,   12,   32,    80,   192,    448,    1024, ...
  1,   8,   32,  104,   304,   832,   2176,    5504, ...
  1,  16,   80,  304,  1008,  3072,   8832,   24320, ...
  1,  32,  192,  832,  3072, 10272,  32064,   95104, ...
  1,  64,  448, 2176,  8832, 32064, 107712,  341504, ...
  1, 128, 1024, 5504, 24320, 95104, 341504, 1150592, ...
  ... (End)

Index entries for triangles and arrays related to Pascal's triangle

Cf. A000079, A001787, A049600, A084773, A087161, A100312, A152254, A208341, A341344.

T[, 0] = T[n, n_] = 1;
T[n_, k_] /; 0, ] = 0;
Table[T[n, k], {n, 0, 10}, {k, 0, n}] // Flatten (* Jean-François Alcover, Oct 03 2021 *)

From Petros Hadjicostas, Feb 09 2021: (Start)
Formulas for the triangular array (T(n,k): 0 <= k <= n):
T(n,k) = T(n,n-k) for 0 <= k <= n.
Sum_{k=0..n} T(n,k) = A087161(n+1).
T(n,1) = T(n,n-1) = 2^(n-1) = A000079(n-1) for n >= 1.
T(n,2) = T(n,n-2) = (n-1)*2^(n-2) = A001787(n-1) for n >= 2.
T(n,3) = T(n,n-3) = (n^2-n-4)*2^(n-4) = A100312(n-3) for n >= 3.
T(n,floor(n/2)) = T(n,ceiling(n/2)) = A341344(n).
Bivariate o.g.f.: Sum_{n,k >= 0} T(n,k)*x^n*y^k = (3*x^2*y - 2*x*y - 2*x + 1)/((1 - x)*(-x*y + 1)*(2*x^2*y - 2*x*y - 2*x + 1)).
Conjecture based on Peter Luschny's formulas in other sequences: T(n,k) = 2^(n-k)*hypergeom([-k + 1, n-k], [1], -1) = 2^k*hypergeom([-(n-k) + 1, k], [1], -1).
Formulas for the rectangular array (R(n,k): n,k >= 0):
R(n,k) = 2*(R(n,k-1) - R(n-1,k-1) + R(n-1,k)) for n,k > 0 with R(n,0) = R(0,n) = 1 for n >= 0.
R(n,k) = R(k, n) for n,k >= 0.
R(1,n) = R(n,1) = 2^n = A000079(n).
R(2,n) = R(n,2) = (n+1)*2^n = A001787(n+1).
R(3,n) = R(n,3) = (n^2+5*n+2)*2^(n-1) = A100312(n).
R(n,n) = A152254(n-1) = 2*A084773(n-1) for n >= 1.
Bivariate o.g.f.: Sum_{n,k >= 0} R(n,k)*x^n*y^k = (3*x*y - 2*x - 2*y - 1)/((1 - x)*(1 - y)*(2*x*y - 2*x - 2*y - 1)).
Conjecture based on Peter Luschny's formulas in other sequences: R(n,k) = 2^n*hypergeom([-k + 1, n], [1], -1) = 2^k*hypergeom([-n + 1, k], [1], -1). (End)
From Petros Hadjicostas, Feb 10 2021: (Start)
The above conjecture is true (see the comments).
R(n,k) = 2^k*Sum_{s=0}^{n-1} binomial(n-1,s)*binomial(k+s-1,s) = 2^n*Sum_{s=0}^{k-1} binomial(k-1,s)*binomial(n+s-1,s) for n, k >= 1.
To get two binomial formulas for T(n,k), use the equation T(n,k) = R(n-k, k) for 1 <= k <= n and the above formulas for R(n,k). (End)

Offset changed by Petros Hadjicostas, Feb 09 2021

cp's OEIS Frontend

A076616 Number of permutations of {1,2,...,n} that result in a binary search tree (when elements of the permutation are inserted in that order) of height n-1 (i.e., the second largest possible height).

Views

Author

Keywords

Examples

Links

Crossrefs

Programs

Maple

Mathematica

PARI

Formula

Extensions

A100313 Number of 4 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

A100631 Triangle read by rows: T(n,k) = 2*(T(n-1,k-1) - T(n-2,k-1) + T(n-1,k)) for 0 < k < n, T(n,0) = T(n,n) = 1.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

Formula

Extensions