A258427 Number T(n,k) of redundant binary trees with n inner nodes of exactly k different dimensions used for the partition of the k-dimensional hypercube by hierarchical bisection; triangle T(n,k), n>=3, 2<=k<=n-1, read by rows.

1, 12, 18, 112, 420, 336, 956, 6816, 12936, 7200, 7830, 95579, 324540, 414450, 178200, 62744, 1244466, 6755720, 14886300, 14355000, 5045040, 496518, 15537456, 127063596, 430572780, 699460740, 542341800, 161441280

Offset: 3

Author

Alois P. Heinz, May 29 2015

Keywords

• nonn
• tabl

Comments

T(n,k) is defined for all n>=0 and k>=0. The triangle displays only positive terms. T(n,k) = 0 for k in {0, 1} or k>=n.

Examples

			T(3,2) = 1. There are A256061(3,2) = 30 binary trees with 3 inner nodes of exactly 2 different dimensions, 28 of them have unique hypercube partitions, 2 of them have the same partition:
:              :                     : partition :
|--------------|---------------------|-----------|
|              |    (1)       [2]    |           |
|              |    / \       / \    |   .___.   |
|       trees: |  [2] [2]   (1) (1)  |   |_|_|   |
|              |  / \ / \   / \ / \  |   |_|_|   |
|    balanced  |                     |           |
| parentheses: |  ([])[]    [()]()   |           |
|--------------|---------------------|-----------|
Triangle T(n,k) begins:
.
. .
. .     .
. .     1,       .
. .    12,      18,       .
. .   112,     420,     336,        .
. .   956,    6816,   12936,     7200,        .
. .  7830,   95579,  324540,   414450,   178200,       .
. . 62744, 1244466, 6755720, 14886300, 14355000, 5045040,   .
		

Links

• Alois P. Heinz, Rows n = 3..135, flattened

Crossrefs

Cf. A256061, A255982.

Programs

Maple

A:= proc(n, k) option remember; k^n*binomial(2*n, n)/(n+1) end:
B:= proc(n, k) option remember;
       add(A(n, k-i)*(-1)^i*binomial(k, i), i=0..k)
    end:
b:= proc(n, k, t) option remember; `if`(t=0, 1, `if`(t=1,
       H(n-1, k), add(H(j, k)*b(n-j-1, k, t-1), j=0..n-2)))
    end:
H:= proc(n, k) option remember; `if`(n=0, 1,
      -add(binomial(k, j)*(-1)^j*b(n+1, k, 2^j), j=1..k))
    end:
G:= proc(n, k) option remember;
       add(H(n, k-i)*(-1)^i*binomial(k, i), i=0..k)
    end:
T:= (n, k)-> B(n, k)-G(n, k):
seq(seq(T(n, k), k=2..n-1), n=3..12);

Mathematica

A[n_, k_] := A[n, k] = k^n*Binomial[2*n, n]/(n+1); B[n_, k_] := B[n, k] = Sum[A[n, k-i]*(-1)^i*Binomial[k, i], {i, 0, k}]; b[n_, k_, t_] := b[n, k, t] = If[t==0, 1, If[t==1, H[n-1, k], Sum[H[j, k]*b[n-j-1, k, t-1], {j, 0, n-2}]]]; H[n_, k_] := H[n, k] = If[n==0, 1, -Sum[Binomial[k, j]* (-1)^j* b[n+1, k, 2^j], {j, 1, k}]]; G[n_, k_] := G[n, k] = Sum[H[n, k-i]*(-1)^i* Binomial[k, i], {i, 0, k}]; T[n_, k_] := T[n, k] = B[n, k]-G[n, k]; Table[Table[T[n, k], {k, 2, n-1}], {n, 3, 12}] // Flatten (* Jean-François Alcover, Feb 22 2016, after Alois P. Heinz *)

Formula

T(n,k) = A256061(n,k) - A255982(n,k).