0,5

Consider 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-tupel 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 indicator function which tests on i_j = i_(j+1) generates A158497, which contains further examples of this type of counting.

Thomas Wieder, Home Page.

Thomas Wieder, (Old) Home Page

Columns: T(n,2)= A000217(n). T(n,3) = A000292(n). T(n,4)=A001405(n+3). T(n,5)=A000389(n+4).

Rows: T(5,k)= A000332(k+4). T(6,k) = A000389(k+5). T(7,k) = A000579(k+6).

Diagonals: T(n,n)= A001700(n-1). T(n,n-1) = A000984(n-1).

T(n,k)=A046899(n-1,k). sum_{k=0..n} T(n,k) = A000984(n). [From R. J. Mathar (mathar(AT)strw.leidenuniv.nl), Mar 26 2009]

The triangle T(n,k), n>=0, 0<=k<n, begins

1

1 1

1 2 3

1 3 6 10

1 4 10 20 35

1 5 15 35 70 126

1 6 21 56 126 252 462

1 7 28 84 210 462 924 1716

1 8 36 120 330 792 1716 3432 6435

T(3,2)=6 considers the CP with the 3^2=9 elements (1,1),(1,2),(1,3),(2,1),(2,2),(2,3),(3,1),(3,2),(3,3),

and does not count the 3 of them which are (2,1),(3,1) and (3,2).

for n from 0 to 10 do for k from 0 to n do printf("%d, ", binomial(n+k-1, k)) ; od: od: # R. J. Mathar, Mar 31 2009

A007318, A158497.

Sequence in context: A081422 A027555 A059481 this_sequence A113592 A136555 A063967

Adjacent sequences: A158495 A158496 A158497 this_sequence A158499 A158500 A158501

nonn,tabl

Thomas Wieder (thomas.wieder(AT)t-online.de), Mar 20 2009

Edited by R. J. Mathar (mathar(AT)strw.leidenuniv.nl), Mar 31 2009