A084851 -id:A084851 - cp's OEIS frontend

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

1, 0, 1, 1, 2, 1, 2, 5, 4, 1, 4, 12, 13, 6, 1, 8, 28, 38, 25, 8, 1, 16, 64, 104, 88, 41, 10, 1, 32, 144, 272, 280, 170, 61, 12, 1, 64, 320, 688, 832, 620, 292, 85, 14, 1, 128, 704, 1696, 2352, 2072, 1204, 462, 113, 16, 1

Offset: 0

Philippe Deléham, Dec 05 2011

Diagonals ascending: 1, 0, 1, 1, 2, 2, 4, 5, 1, 8, 12, 4, ... (see A201509).

			Triangle begins:
  1;
  0,  1;
  1,  2,  1;
  2,  5,  4,  1;
  4, 12, 13,  6,  1;
  8, 28, 38, 25,  8,  1;

Benjamin Braun, W. K. Hough, Matching and Independence Complexes Related to Small Grids, arXiv preprint arXiv:1606.01204 [math.CO], 2016.
Wesley K. Hough, On Independence, Matching, and Homomorphism Complexes, (2017), Theses and Dissertations--Mathematics, 42.

Diagonals: A000012, A005843, A001844, A035597,
Columns: A034008, A045623, A084851, A055585,
Row sums: A052156

CoefficientList[#, y]& /@ CoefficientList[(1-x)^2/(1-(y+2)*x) + O[x]^10, x] // Flatten (* Jean-François Alcover, Nov 03 2018 *)

T(n,k) = 2*T(n-1,k) + T(n-1,k-1) with T(0,0) = 0, T(1,0) = 0, T(2,0) = 0 and T(n,k)= 0 if k < 0 or if n < k.
Sum_{k=0..n} T(n,k)*x^k = A154955(n+1), A034008(n), A052156(n), A055841(n), A055842(n), A055846(n), A055270(n), A055847(n), A055995(n), A055996(n), A056002(n), A056116(n) for x = -1,0,1,2,3,4,5,6,7,8,9,10 respectively.
G.f.: (1-x)^2/(1-(y+2)*x).

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).

Original entry on oeis.org

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

A109436 Triangle of numbers: row n gives the elements along the subdiagonal of A109435 that connects 2^n with (n+2)*2^(n-1).

Original entry on oeis.org

0, 0, 1, 1, 2, 3, 4, 7, 8, 8, 15, 19, 20, 16, 31, 43, 47, 48, 32, 63, 94, 107, 111, 112, 64, 127, 201, 238, 251, 255, 256, 128, 255, 423, 520, 558, 571, 575, 576, 256, 511, 880, 1121, 1224, 1262, 1275, 1279, 1280, 512, 1023, 1815, 2391, 2656, 2760, 2798, 2811

Offset: 0

Robert G. Wilson v, Jun 28 2005

In the limit of row number n->infinity, the differences of the n-th row of the table, read from right to left, are 1, 4, 13, 38, 104,... = A084851.

			The triangle A109435 begins
    1;
    2,   1;
    4,   3,   1;
    8,   7,   3,   1;
   16,  15,   8,   3,   1;
   32,  31,  19,   8,   3,   1;
   64,  63,  43,  20,   8,   3,   1;
  128, 127,  94,  47,  20,   8,   3,   1;
If we read this triangle starting at 2^n in its first column along its n-th subdiagonal up to the first occurrence of (n+2)*2^(n-1), we get row n of the current triangle, which begins:
   0,   0;
   1,   1;
   2,   3;
   4,   7,   8;
   8,  15,  19,  20;
  16,  31,  43,  47,  48;
  32,  63,  94, 107, 111, 112;

Cf. A109435, A001792, A109434, A084851.

T[n_, m_] := Length[ Select[ StringPosition[ #, StringDrop[ ToString[10^m], 1]] & /@ Table[ ToString[ FromDigits[ IntegerDigits[i, 2]]], {i, 2^n, 2^(n + 1) - 1}], # != {} &]]; Flatten[ Table[ T[n + i, i], {n, 0, 9}, {i, 0, n}]]

Edited by R. J. Mathar, Nov 17 2009

A127718 A007318 * A002260 as infinite lower triangular matrices; A002260 = [1; 1,2; 1,2,3; ...].

Original entry on oeis.org

1, 2, 2, 4, 6, 3, 8, 14, 12, 4, 16, 30, 33, 20, 5, 32, 62, 78, 64, 30, 6, 64, 126, 171, 168, 110, 42, 7, 128, 254, 360, 396, 320, 174, 56, 8, 256, 510, 741, 876, 815, 558, 259, 72, 9, 512, 1022, 1506, 1864, 1910, 1536, 910, 368, 90, 10, 1024, 2046, 3039, 3872, 4240

Offset: 1

Gary W. Adamson, Jan 25 2007

Binomial transform of A002260.

Row sums = A084851: (1, 4, 13, 38, 104, 272, ...) A002260 * A007318 = A127717.

			First few rows of the triangle:
   1;
   2,   2;
   4,   6,   3;
   8,  14,  12,   4;
  16,  30,  33,  20,   5;
  32,  62,  78,  64,  30,  6;
  64, 126, 171, 168, 110, 42, 7;
  ...

Cf. A002260, A007318, A084851, A127717.

A007318 := proc(n,k) binomial(n,k) ; end: A002260 := proc(n,k) if k <= n then k; else 0 ; fi ; end: A127718 := proc(n,k) add( A007318(n-1,i-1)*A002260(i,k),i=1..n) ; end: for n from 1 to 15 do for k from 1 to n do printf("%d,",A127718(n,k)) ; od: od: # R. J. Mathar, Oct 02 2007

T(n,k) = Sum_{i=1..n} A007318(n-1,i-1)*A002260(i,k). - R. J. Mathar, Oct 02 2007

More terms from R. J. Mathar, Oct 02 2007

A332496 Triangular array T(n,k): the number of not necessarily proper colorings of the complete graph on n unlabeled vertices minus an edge using exactly k colors.

Original entry on oeis.org

0, 1, 1, 1, 4, 3, 1, 7, 12, 6, 1, 10, 27, 28, 10, 1, 13, 48, 76, 55, 15, 1, 16, 75, 160, 175, 96, 21, 1, 19, 108, 290, 425, 351, 154, 28, 1, 22, 147, 476, 875, 966, 637, 232, 36, 1, 25, 192, 728, 1610, 2226, 1960, 1072, 333, 45, 1, 28, 243, 1056, 2730, 4536, 4998, 3648, 1701, 460, 55

Offset: 1

Marko Riedel, Feb 14 2020

It is not possible to remove an edge from an ordinary graph on one node and there is no remaining graph to color, hence we determine the first term for n=1 and k=1 to be zero. The automorphism group of the graph obtained from the complete graph by removing an edge is the so-called product group of two symmetric groups S_2 S_{n-2} in the sense of Harary and Palmer, section 2.2.

			T(n,n) = C(n,2) because we need to select the two colors that color the vertices of the removed edge from the n available colors. The remaining vertices are not distinguishable.
Triangle T(n,k) begins:
  0;
  1,  1;
  1,  4,   3;
  1,  7,  12,   6;
  1, 10,  27,  28,  10;
  1, 13,  48,  76,  55,  15;
  1, 16,  75, 160, 175,  96,  21;
  1, 19, 108, 290, 425, 351, 154,  28;
  1, 22, 147, 476, 875, 966, 637, 232, 36;
  ...
T(4,2) = 7 because when n = 4 there are two unordered pairs of vertices, each of which can be colored in 3 ways using a maximum of 2 colors giving 9 colorings. From this, the two coloring using only one of the two colors needs to be subtracted, so T(4,2) = 9 - 2 = 7. - _Andrew Howroyd_, Feb 15 2020

E. Palmer and F. Harary, Graphical Enumeration, Academic Press, 1973.

Marko Riedel, Table of n, a(n) for n = 1..1275 (first 50 rows)
Marko Riedel et al., Math.StackExchange, Calculate number of possible colorings.
Marko Riedel, Maple code for colorings using at most k colors and exactly k colors, including cycle index.

Cf. A008277, A048994.
Main diagonal gives A000217(n-1).
Row sums give 2 * A084851(n-2) for n>1.

T:= (n, k)-> `if`(n=1, 0, (k!/2/(n-2)!)*add(abs(Stirling1(n-2, p))
              *(Stirling2(p+1, k)+Stirling2(p+2, k)), p=0..n-2)):
seq(seq(T(n, k), k=1..n), n=1..12);  # Alois P. Heinz, Feb 14 2020

T(n,k) = {if(n<2,0,(k!/2/(n-2)!)*sum(p=0,n-2,abs(stirling(n-2,p,1))* (stirling(p+1, k,2)+stirling(p+2, k,2))))};
for(n=1,11,print(" ");for(k=1,n,print1(T(n,k),", "))) \\ Hugo Pfoertner, Feb 14 2020

T(n,k) = (k!/2/(n-2)!) Sum_{p=0..n-2} |s(n-2,p)| (S(p+1, k)+S(p+2, k)). Here s(n,k) is the signed Stirling number of the first kind (A048994) and S(n,k) the Stirling number of the second kind (A008277).

cp's OEIS Frontend

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

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

Formula

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

A109436 Triangle of numbers: row n gives the elements along the subdiagonal of A109435 that connects 2^n with (n+2)*2^(n-1).

Views

Author

Keywords

Comments

Examples

Crossrefs

Programs

Mathematica

Extensions

A127718 A007318 * A002260 as infinite lower triangular matrices; A002260 = [1; 1,2; 1,2,3; ...].

Views

Author

Keywords

Comments

Examples

Crossrefs

Programs

Maple

Formula

Extensions

A332496 Triangular array T(n,k): the number of not necessarily proper colorings of the complete graph on n unlabeled vertices minus an edge using exactly k colors.

Views

Author

Keywords

Comments

Examples

References

Links

Crossrefs

Programs

Maple

PARI

Formula