Viktar Karatchenia - cp's OEIS frontend

User: Viktar Karatchenia

Viktar Karatchenia has authored 4 sequences.

A328349 Number of binary search trees (BST) on n nodes which have the same height as the optimal BST.

1, 1, 2, 1, 6, 6, 4, 1, 94, 114, 116, 94, 60, 28, 8, 1, 32398, 41658, 49700, 54746, 55308, 50788, 41944, 30782, 19788, 10948, 5096, 1932, 568, 120, 16, 1, 5193067630, 6939692682, 8948546308, 11120136162, 13299362332, 15286065700, 16859410792, 17813777994, 17999433372

Offset: 0

Viktar Karatchenia, Oct 13 2019

For any BST node p, p.left.value < p.value and p.right.value > p.value provided that the left (right) node exists.

			a(1) = 1 - the trivial tree having 1 node.
a(2) = 2 - two trees: one {1,2} rooted at node 1, and {2,1} - at 2.
a(3) = 1 - one BST tree of height 1 with edges {1,2}, {2,3} rooted at the node 2.
      2
    1   3
a(4) = 6. Optimal BST height is 2. When the root is 1, the remaining nodes {2,3,4} can form 1 subtree having height 1. Taking 2 as the root, 1 must go to the left, and {3,4} - right; there can be 2 trees on {3,4}. The cases for root 4,3 are symmetric. Thus, a(4) = 2*(1+1*2) = 6. The 6 BSTs of the optimal height 2 are: ({1,3},{3,2},{3,4}), ({2,1},{2,3},{3,4}), ({2,1},{2,4},{4,3}), ({3,4},{3,2},{2,1}), ({3,4},{3,1},{1,2}), ({4,2},{2,1},{2,3}).
a(5) = 1+1+2*2 = 6. Height=2. Nodes 1,5 cannot be the root, because the remaining 4 nodes cannot be compressed into a BST of height 1. Node 2 as the root implies {3,4,5} must follow to the right (left) producing 1 tree. Node 4 similarly adds 1 more BST. Finally, 3 as the root allows the formation of 2 trees consisting of {1,2} to the left of the root, and 2 trees of {4,5} to the right giving 2*2 = 4 trees.
a(6) = 4. Here height = 2. The nodes 1,2,5,6 can't be the root. When rooting at the third node, {1,2} will form 2 trees, and {4,5,6} to the right will make 1 possible tree of height 1. The node 4 is similar to 3. In total, a(6) = 2*1*2 = 4.

Alois P. Heinz, Table of n, a(n) for n = 0..1023
Wikipedia, Binary search tree
Index entries for sequences related to rooted trees
Index entries for sequences related to trees

Cf. A000225, A000523, A076615, A195581, A244108, A335919, A335920.

# after C++ program
const _cache = Dict{Tuple{Int, Int}, Int}()
function f(k::Int, level::Int)
    (k >= 1 << level) && return 0
    level = min(k, level)
    haskey(_cache, (k, level)) && return _cache[(k, level)]
    r = 0
    for root in 1:k
        left  = root == 1 ? 1 : f(root - 1, level - 1)
        right = root == k ? 1 : f(k - root, level - 1)
        r += left * right
    end
    return _cache[k, level] = r
end
BinaryIntegerLength(n) = n == 0 ? 1 : floor(Int, log2(n)) + 1
[f(n, BinaryIntegerLength(n)) for n in 1:40] |> println # Peter Luschny, Oct 14 2019

b:= proc(n, h) option remember; `if`(n=0, 1, `if`(n<2^h,
      add(b(j-1, h-1)*b(n-j, h-1), j=1..n), 0))
    end:
a:= n-> b(n, ilog2(n)+1):
seq(a(n), n=0..42);  # Alois P. Heinz, Jun 28 2020

b[n_, h_] := b[n, h] = If[n == 0, 1, If[n<2^h, Sum[b[j-1, h-1] b[n-j, h-1], {j, 1, n}], 0]];
a[n_] := b[n, Floor@Log[2, n]+1];
a /@ Range[0, 42] (* Jean-François Alcover, Nov 15 2020, after Alois P. Heinz *)

a(n) = 1 when n = 2^m - 1, m > 0 because the optimal BST represents a full binary tree thus precisely 1 tree is possible.
a(n) = 2^(m-1) when n = 2^m - 2, m > 1. Here the BST is full BST minus 1 node, which must be at the last level. The last level of a full BST has 2^(m-1) nodes. Once the "missing" node is chosen at the last level, there is only 1 BST.
a(n) = f(n, 1+floor(log_2(n))) where f(k, level) is 0 when there are too many nodes (k >= 2^ level), otherwise f(k, level) = Sum_{root=1..n}(root=1 ? 1 : f(root-1, level-1)) * (root=k ? 1 : f(k-root, level-1))).
a(n) = A335919(n,max(0,A000523(n)+1)) = A335920(n,max(0,A000523(n)+1)). - Alois P. Heinz, Jun 29 2020

a(0)=1 prepended by Alois P. Heinz, Jun 28 2020

A309490 Total number of adjacent node merge operations to turn a circular list of size n to a node.

Original entry on oeis.org

0, 1, 6, 28, 145, 876, 6139, 49120, 442089, 4420900, 48629911, 583558944, 7586266285, 106207728004, 1593115920075, 25489854721216, 433327530260689, 7799895544692420, 148198015349155999, 2963960306983120000, 62243166446645520021, 1369349661826201440484, 31495042222002633131155, 755881013328063195147744

Offset: 1

Viktar Karatchenia, Aug 04 2019

nonn

			For n=1, a(1)=0 - no ops since it is already a node.
For n=2, a(2)=1 - there is only 1 possible contraction of the 2 nodes.
For n=3, a(3)=6. Consider an undirected circular list of 3 nodes A,B,C and 3 edges (A,B), (B,C), (C,A). Initially, any of the 3 edges can be contracted to get a 2-node list - here are 3 operations. Then, each 2-node list requires 1 more contraction to become the trivial graph, giving 3 extra operations summing to a(3)=3+3=6.
In general, firstly one of the n edges gets contracted to get a list of size n - 1, secondly the list of size n - 1 is contracted. So, each choice of the initial node has 1 + a(n - 1) operations; the n choices sum up to a(n) = n + n * a(n - 1).

int CircularListContractOps(int n) { if (n <= 1) return 0; if (n == 2) return 1; return n*(CircularListContractOps(n - 1) + 1); }

Flatten[{0, Table[E*n*Gamma[n, 1] - 3/2*Gamma[n+1], {n, 2, 25}]}] (* Vaclav Kotesovec, Aug 05 2019 *)

a(n) = if(n<=2,n-1,n + n * a(n - 1)); \\ Joerg Arndt, Aug 04 2019

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

For n > 1, a(n) = exp(1)*n*Gamma(n, 1) - 3*n!/2. - Vaclav Kotesovec, Aug 05 2019

A270593 Total number of subtrees of the complete simple undirected graph K_n on n vertices.

Original entry on oeis.org

0, 1, 3, 9, 38, 250, 2367, 29197, 441212, 7874244, 161950445, 3770473399, 98009367282, 2813394489022, 88387455559067, 3016497635377545, 111127442649962168, 4395316276005329608, 185766120783135345177, 8355290720655784462507, 398470047793625748742670, 20084626943220497590901346

Offset: 0

Viktar Karatchenia, Mar 19 2016

nonn

A complete graph on n vertices can have subgraphs, having from 1 to n vertices inclusively. To choose k vertices from n vertices, there are binomial(n, k) combinations. Having chosen the k vertices, the complete subgraph on these k vertices, according to A000272, has k^(k-2) spanning trees. To calculate the total number of spanning trees for all subgraphs with k-vertices, the number of combinations must be multiplied by the number of spanning trees: binomial(n, k) * (k^(k-2)). To get the total number of all subtrees, all possible graph sizes, that is k=[1..n], must be accounted for.

			For an empty graph, having no vertices, a(0)=0.
a(1)=1 as there is a trivial tree consisting of a single vertex.
When number of vertices n=2, a(n)=2+1=3: 2 singles A, B; 1 pair: A-B.
For n=3, a(n)=3+3+3=9: 3 singles A, B, C; 3 pairs: A-B, A-C, B-C; 3 triples: A-B|B-C, B-C|C-A, C-A|A-B.
For n=4, a(n)=4+6+12+16=38: 4 singles A, B, C, D; 6 pairs: A-B, A-C, A-D, B-C, B-D, C-D; 12 triples: A-B|A-C, A-B|A-D, A-B|B-C, A-B|B-D, A-C|A-D, A-C|B-C, A-C|C-D, A-D|B-D, A-D|C-D, B-C|C-D, B-D|B-C, B-D|C-D; 16 4-tuples: A-B|A-C|A-D, A-B|A-C|B-D, A-B|A-C|C-D, A-B|A-D|B-C, A-B|A-D|C-D, A-B|B-C|B-D, A-B|B-C|C-D, A-B|B-D|C-D, A-C|A-D|B-C, A-C|A-D|B-D, A-C|B-C|B-D, A-C|B-C|C-D, A-C|B-D|C-D, A-D|B-C|B-D, A-D|B-C|C-D, A-D|B-D|C-D. It is worth noting that A-B|C-D is not a tree, because there is no path from A to C. Also, A-B|A-C|B-C is a cycle, not a tree.
a(8)=8+28+168+1120+7000+36288+134456+262144=441212.

Mathematics Stack Exchange, Graph Theory - Trees, answer by user Thomas Lesgourgues, Jan 22 2019.

Cf. A000272 (number of trees on n labeled nodes).

a(n) = sum(k=1, n, binomial(n,k)*(k^(k-2))); \\ Michel Marcus, Mar 20 2016

a(n) = Sum_{k=1..n} binomial(n,k)*(k^(k-2)).

a(n) ~ exp(exp(-1)) * n^(n-2). - Vaclav Kotesovec, Apr 02 2016

More terms from Michel Marcus, Mar 20 2016

A262875 Number of equal-sized disjoint subset combinations from a set of n items.

Original entry on oeis.org

0, 1, 4, 14, 41, 127, 400, 1297, 4520, 17064, 64857, 262286, 1156325, 5199261, 23835336, 117674608, 609741279, 3268286263, 18109939168, 102866828839, 620474818814, 4005211833858, 25747541532731, 166978138395205, 1168773990780772

Offset: 1

Viktar Karatchenia, Oct 03 2015

nonn

a(n) is the total number of combinations of m disjoint subsets of equal size k from a set of n>=2 items, for 2 <= m <= n, 1 <= k <= n/m. m starts at 2 in order to have more than one subset, and m <= n because a subset must contain at least one item.
Given m, for each subset size k, k items are chosen from n; then k items are chosen from the remaining n-k items; then k items are chosen from the remaining n-2*k items; and so on until there are fewer than k items left. Since each m-tuple "kSubSet|kSubSet| ... |kSubSet" is chosen m! times (for example, pairs are chosen as "A|B" and as "B|A"), in order to remove repetitions, we must then divide by m!. Since binomial(n, n + d) = 0 when d>0, the upper limit can be safely increased from floor(n/m) to n.
Thus a(n) = Sum_{m=2..n} b(n,m), where b(n,m) = Sum_{k=1..floor(n/m)} (Product_{j=0..m-1} binomial(n-k*j, k))/m!.

			a(5) = 25+10+5+1 = 41 combinations of equal size disjoint subsets, i.e., given 5 items, there can be 2, 3, 4 or 5 subsets:
A) Pairs can have 1 or 2 items, contributing 10+15=25:
A.1) There are 10 distinct pairs of size 1: "1|2, 1|3, 1|4, 1|5, and 2|3, 2|4, 2|5, and 3|4, 3|5, 4|5".
A.2) And 15 distinct pairs of size 2: "12|34, 12|35, 12|45, and 13|24, 13|25, 13|45, and 14|23, 14|25, 14|35, and 15|23, 15|24, 15|34, and 23|45, 24|35, 25|34".
B) Triplet can have only 1 item, 10 of them: 1|2|3, 1|2|4, 1|2|5, and 1|3|4, 1|3|5, 1|4|5, and 2|3|4, 2|3|5, 2|4|5, 3|4|5.
C) Four-tuple from one item, 5 in total: 1|2|3|4, and 1|2|3|5, 1|2|4|5, 1|3|4|5, finally 2|3|4|5.
D) There is one 5-tuple: 1|2|3|4|5.

Vaclav Kotesovec, Table of n, a(n) for n = 1..600 (terms 1..100 from Viktar Karatchenia)
Viktar Karatchenia, C++ program to calculate b(n,m) and a(n).
Viktar Karatchenia, C++ file for InfInt class
Viktar Karatchenia, Header file for InfInt class

Cf. A097861 (b(n,2)).

Table[Sum[Sum[Product[Binomial[n - k*j, k], {j, 0, m - 1}]/m!, {k, 1, Floor[n/m]}], {m, 2, n}], {n, 1, 30}] (* Vaclav Kotesovec, Aug 05 2019 *)
Table[Sum[Sum[n!/(k!^m * (n - k*m)! * m!), {k, 1, Floor[n/m]}], {m, 2, n}], {n, 1, 30}] (* Vaclav Kotesovec, Aug 05 2019 *)

a(n) = sum(m=2, n, sum(k=1, n\m, prod(j=0, m-1, binomial(n-k*j, k))/m!)); \\ Michel Marcus, Oct 04 2015

a(n) = Sum_{m=2..n} b(n,m), where b(n,m) = Sum_{k=1..floor(n/m)} (Product_{j=0..(m-1)} binomial(n-k*j, k))/m!.

cp's OEIS Frontend

User: Viktar Karatchenia

A328349 Number of binary search trees (BST) on n nodes which have the same height as the optimal BST.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Julia

Maple

Mathematica

Formula

Extensions

A309490 Total number of adjacent node merge operations to turn a circular list of size n to a node.

Views

Author

Keywords

Examples

Programs

C

Mathematica

PARI

Formula

A270593 Total number of subtrees of the complete simple undirected graph K_n on n vertices.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

PARI

Formula

Extensions

A262875 Number of equal-sized disjoint subset combinations from a set of n items.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

PARI

Formula