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,2

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.

Links

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

Formula

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

Example

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

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

Crossrefs

Cf. A256061, A255982.

Sequence in context: A232384 A086301 A231094 * A166627 A018957 A238922

Adjacent sequences: A258424 A258425 A258426 * A258428 A258429 A258430

Keyword

nonn,tabl

Author

Alois P. Heinz, May 29 2015

Status

approved