A158497 Triangle T(n,k) formed by the coordination sequences and the number of leaves for trees.

1, 1, 1, 1, 2, 2, 1, 3, 6, 12, 1, 4, 12, 36, 108, 1, 5, 20, 80, 320, 1280, 1, 6, 30, 150, 750, 3750, 18750, 1, 7, 42, 252, 1512, 9072, 54432, 326592, 1, 8, 56, 392, 2744, 19208, 134456, 941192, 6588344

Offset

0,5

Comments

Consider the k-fold Cartesian products CP(n,k) of the vector A(n)=[1,2,3,...,n].

An element of CP(n,k) is a n-tuple T_t of the form T_t=[i_1,i_2,i_3,...,i_k] with t=1,..,n^k.

We count members T of CP(n,k) which satisfy some condition delta(T_t), so delta(.) is an indicator function which attains values of 1 or 0 depending on whether T_t is to be counted or not; the summation sum_{CP(n,k)} delta(T_t) over all elements T_t of CP produces the count.

For the triangle here we have delta(T_t) = 0 if for any two i_j, i_(j+1) in T_t one has i_j = i_(j+1): T(n,k) = Sum_{CP(n,k)} delta(T_t) = Sum_{CP(n,k)} delta(i_j = i_(j+1)).

The test on i_j > i_(j+1) generates A158498. One gets the Pascal triangle A007318 if the indicator function tests whether for any two i_j, i_(j+1) in T_t one has i_j >= i_(j+1).

Use of other indicator functions can also calculate the Bell numbers A000110, A000045 or A000108.

Links

Table of n, a(n) for n=0..44.

Formula

Columns: T(n,2)=A002378(n-1). T(n,3)=A011379(n-1). T(n,5)=A101362(n-1).

Rows: T(2,k) = A040000(k). T(3,k) = A003945(k), T(4,k)=A003946(k), T(5,k)=A003947(k), T(6,k)=A003948(k).

T(n,k) = (n-1)^(k-1)+(n-1)^k = n*A079901(n-1,k-1), k>0.

sum_{k=0..n} T(n,k) = (n*(n-1)^n-2)/(n-2), n>2.

Example

The triangle begins
1
1 1
1 2 2
1 3 6 12
1 4 12 36 108
1 5 20 80 320 1280
1 6 30 150 750 3750 18750
1 7 42 252 1512 9072 54432 326592
1 8 56 392 2744 19208 134456 941192 6588344
T(3,3)=12 counts the triples (1,2,1), (1,2,3), (1,3,1), (1,3,2), (2,1,2), (2,1,3), (2,3,1), (2,3,2), (3,1,2), (3,1,3), (3,2,1), (3,2,3) out of a total of 3^3=27 triples in the CP(3,3).

Crossrefs

Cf. A007318, A158498.

Sequence in context: A239572 A056043 A187005 * A334894 A110564 A210791

Adjacent sequences: A158494 A158495 A158496 * A158498 A158499 A158500

Keyword

nonn,tabl

Author

Thomas Wieder, Mar 20 2009

Extensions

Edited by R. J. Mathar, Mar 31 2009

Status

approved