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, 1, 9, 72, 576, 4608, 36864, 294912, 2359296, 18874368, 150994944, 1, 10, 90, 810, 7290, 65610, 590490, 5314410, 47829690, 430467210, 3874204890

Offset: 0

Author

Thomas Wieder, Mar 20 2009

Keywords

• nonn
• tabl

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.

Examples

			Array, A(n, k) = n*(n-1)^(k-1) for n > 1, A(n, k) = 1 otherwise, begins as:
  1,  1,   1,    1,     1,      1,       1,        1,        1, ... A000012;
  1,  1,   1,    1,     1,      1,       1,        1,        1, ... A000012;
  1,  2,   2,    2,     2,      2,       2,        2,        2, ... A040000;
  1,  3,   6,   12,    24,     48,      96,      192,      384, ... A003945;
  1,  4,  12,   36,   108,    324,     972,     2916,     8748, ... A003946;
  1,  5,  20,   80,   320,   1280,    5120,    20480,    81920, ... A003947;
  1,  6,  30,  150,   750,   3750,   18750,    93750,   468750, ... A003948;
  1,  7,  42,  252,  1512,   9072,   54432,   326592,  1959552, ... A003949;
  1,  8,  56,  392,  2744,  19208,  134456,   941192,  6588344, ... A003950;
  1,  9,  72,  576,  4608,  36864,  294912,  2359296, 18874368, ... A003951;
  1, 10,  90,  810,  7290,  65610,  590490,  5314410, 47829690, ... A003952;
  1, 11, 110, 1100, 11000, 110000, 1100000, 11000000, ............. A003953;
  1, 12, 132, 1452, 15972, 175692, 1932612, 21258732, ............. A003954;
  1, 13, 156, 1872, 22464, 269568, 3234816, 38817792, ............. A170732;
  ... ;
The triangle begins as:
  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).
		

Links

• G. C. Greubel, Rows n = 0..50 of the triangle, flattened

Crossrefs

Array rows n: A170733 (n=14), ..., A170769 (n=50).

Columns k: A000012(n) (k=0), A000027(n) (k=1), A002378(n-1) (k=2), A011379(n-1) (k=3), A179824(n) (k=4), A101362(n-1) (k=5), 2*A168351(n-1) (k=6), 2*A168526(n-1) (k=7), 2*A168635(n-1) (k=8), 2*A168675(n-1) (k=9), 2*A170783(n-1) (k=10), 2*A170793(n-1) (k=11).

Diagonals k: A055897 (k=n), A055541 (k=n-1), A373395 (k=n-2), A379612 (k=n-3).

Sums: (-1)^n*A065440(n) (signed row).

Cf. A000045, A000108, A000110, A007318, A079901, A158498.

Programs

Magma

A158497:= func< n,k | k le 1 select n^k else n*(n-1)^(k-1) >;
[A158497(n,k): k in [0..n], n in [0..12]]; // G. C. Greubel, Mar 18 2025

Mathematica

A158497[n_, k_]:= If[n<2 || k==0, 1, n*(n-1)^(k-1)];
Table[A158497[n,k], {n,0,12}, {k,0,n}]//Flatten (* G. C. Greubel, Mar 18 2025 *)

SageMath

def A158497(n,k): return n^k if k<2 else n*(n-1)^(k-1)
print(flatten([[A158497(n,k) for k in range(n+1)] for n in range(13)])) # G. C. Greubel, Mar 18 2025

Formula

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.

Extensions

Edited by R. J. Mathar, Mar 31 2009

More terms added by G. C. Greubel, Mar 18 2025