A073430 -id:A073430 - cp's OEIS frontend

A073346 Table T(n,k) (listed antidiagonalwise in order T(0,0), T(1,0), T(0,1), T(2,0), T(1,1), ...) giving the number of rooted plane binary trees of size n and "contracted height" k.

1, 1, 0, 0, 0, 0, 1, 2, 0, 0, 0, 0, 0, 0, 0, 0, 2, 4, 0, 0, 0, 0, 2, 4, 0, 0, 0, 0, 1, 0, 8, 8, 0, 0, 0, 0, 0, 0, 12, 16, 0, 0, 0, 0, 0, 0, 2, 12, 40, 16, 0, 0, 0, 0, 0, 0, 2, 12, 80, 48, 0, 0, 0, 0, 0, 0, 0, 0, 12, 136, 144, 32, 0, 0, 0, 0, 0, 0, 0, 2, 20, 224, 384, 128, 0, 0, 0, 0, 0, 0, 0, 0, 0, 16

Offset: 0

Antti Karttunen, Jul 31 2002

The height of binary trees is computed here in the same way as in A073345, except that whenever a complete binary tree of (2^k)-1 nodes with all its leaves at the same level, i.e., one of the following trees:
__________________\/\/\/\/_
___________\/\/\/\/
______________\/____\ /__
____.__\/__\/____\/__ etc.
is encountered as a terminating subtree, it is regarded just a variant of . (an empty tree, a single leaf) and contributes nothing to the height of the tree.

			The top-left corner of this square array:
1 1 0 1 0 0 0 1 ...
0 0 2 0 2 2 0 0 ...
0 0 0 4 4 8 12 12 ...
0 0 0 0 8 16 40 80 ...

H. Bottomley and A. Karttunen, Notes concerning diagonals of the square arrays A073345 and A073346.

Variant: A073345. The first row: A036987. Column sums: A000108. Diagonals: T(n, n) = A000007(n), T(n+1, n) = A000079(n), T(n+2, n) = A058922(n), T(n+3, n) = A074092(n) - [see the attached notes.].

A073430 gives the upper triangular region of this array. Used to compute A073431. Entries on row k are all divisible by 2^k, thus dividing them out yields the array/triangle A074079/A074080.

A073346 := n -> A073346bi(A025581(n), A002262(n));
A073346bi := proc(n,k) option remember; local i,j; if(0 = k) then RETURN(A036987(n)); fi; if(0 = n) then RETURN(0); fi; 2 * add(A073346bi(n-i-1,k-1) * add(A073346bi(i,j),j=0..(k-1)),i=0..floor((n-1)/2)) + 2 * add(A073346bi(n-i-1,k-1) * add(A073346bi(i,j),j=0..(k-2)),i=(floor((n-1)/2)+1)..(n-1)) - (`mod`(n,2))*(A073346bi(floor((n-1)/2),k-1)^2) - (`if`((1=k),1,0))*A036987(n); end;
A025581 := n -> binomial(1+floor((1/2)+sqrt(2*(1+n))),2) - (n+1);
A002262 := n -> n - binomial(floor((1/2)+sqrt(2*(1+n))),2);

(See the Maple code below. Note that here we use the same convolution recurrence as with A073345, but only the initial conditions for the first two rows (k=0 and k=1) are different. Is there a nicer formula?)

Sequence number in comments corrected

A074080 Triangle T(n,k) (listed in order T(1,0), T(2,0), T(2,1), T(3,0), T(3,1), T(3,2), T(4,0), etc.) giving the number of 2^k-cycles that occur in the n-th sub-permutation of A069767/A069768 (i.e., in the range [A014137(n-1)..A014138(n-1)] inclusive).

Original entry on oeis.org

1, 0, 1, 1, 0, 1, 0, 1, 1, 1, 0, 1, 2, 2, 1, 0, 0, 3, 5, 3, 1, 1, 0, 3, 10, 9, 4, 1, 0, 1, 3, 17, 24, 14, 5, 1, 0, 1, 3, 28, 57, 44, 20, 6, 1, 0, 0, 5, 41, 128, 128, 71, 27, 7, 1, 0, 1, 4, 60, 271, 354, 234, 106, 35, 8, 1, 0, 0, 5, 81, 549, 937, 738, 384, 150, 44, 9, 1, 0, 0, 5, 106, 1061

Offset: 0

Antti Karttunen, Aug 19 2002

			If we take the fifth such sub-permutation, i.e., the subsequence A069767[23..64]: [45,46,48,49,50,54,55,57,58,59,61,62,63,64,44,47,53,56,60,43,52,40,31,32,41,34,35,36,42,51,39,30,33,38,29,26,27,37,28,25,24,23], subtract 22 from each term and convert the resulting permutation of [1..42] to disjoint cycle notation, we get:
(17,31),(20,21,30,29),(3,26,12,40),(6,32,8,35,7,33,11,39),(15,22,18,34,16,25,19,38),(1,23,9,36,4,27,13,41,2,24,10,37,5,28,14,42)
which implies that T(5,0) = 0 (no fixed elements), T(5,1) = 1 (one transposition), T(5,2) = 2 (two 4-cycles), T(5,3) = 2 (two 8-cycles), T(5,4) = 1 (and one 16-cycle). It is guaranteed that only cycles whose length is a power of 2 occur in A069767/A069768.

Upper triangular region of the square array A074079 (actually, only the area above its main diagonal, excluding also the leftmost column). T(n, k) = A073430(n, k)/(2^k) [with the rightmost edge of A073430 discarded]. Row sums: A073431. A000108(n) = Sum_{i=0..n-1} 2^i * T(n, i). Cf. A073346, A003056, A002262.

A074079bi := (n,k) -> A073346bi(n,k)/(2^k);
A074080 := n -> A074079bi(A003056(n)+1, A002262(n));
A003056 := n -> floor(sqrt(2*(1+n))-(1/2));
A002262 := n -> n - binomial(floor((1/2)+sqrt(2*(1+n))),2);

cp's OEIS Frontend

A073346 Table T(n,k) (listed antidiagonalwise in order T(0,0), T(1,0), T(0,1), T(2,0), T(1,1), ...) giving the number of rooted plane binary trees of size n and "contracted height" k.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Maple

Formula

Extensions