A172106 The triangle T_2(n, m), where T_2(n, m) is the number of surjective multi-valued functions from {1, 1, 2, 3, ..., n-1} to {1, 2, 3, ..., m} by rows (n >= 1, 1 <= m <= n).

0, 1, 1, 1, 4, 3, 1, 10, 21, 12, 1, 22, 93, 132, 60, 1, 46, 345, 900, 960, 360, 1, 94, 1173, 4980, 9300, 7920, 2520, 1, 190, 3801, 24612, 71400, 103320, 73080, 20160, 1, 382, 11973, 113652, 480060, 1048320, 1234800, 745920, 181440, 1, 766, 37065, 502500, 2968560, 9170280, 15981840, 15845760, 8346240, 1814400

Offset

1,5

Comments

T_2(1, m) = 0 by definition. T_2(n, m) also gives the number of compositions (ordered partitions) of {1, 1, 2, 3, ..., n-1} into exactly m parts.

Links

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

M. Griffiths and I. Mezo, A generalization of Stirling Numbers of the Second Kind via a special multiset, JIS 13 (2010) #10.2.5.

Formula

T_2(n, m) = Sum_{j=0..m} binomial(m,j)*binomial(j+1,2)*(-1)^(m-j)*j^(n-2), for n >= 2, with T(1, 1) = 0.

Sum_{k=1..n} T_2(n, k) = A172109(n).

Sum_{k=1..n} (-1)^k*T_2(n, k) = 0. - G. C. Greubel, Apr 13 2022

Example

Triangle begins as:
  0;
  1,   1;
  1,   4,     3;
  1,  10,    21,     12;
  1,  22,    93,    132,      60;
  1,  46,   345,    900,     960,     360;
  1,  94,  1173,   4980,    9300,    7920,     2520;
  1, 190,  3801,  24612,   71400,  103320,    73080,    20160;
  1, 382, 11973, 113652,  480060, 1048320,  1234800,   745920,  181440;
  1, 766, 37065, 502500, 2968560, 9170280, 15981840, 15845760, 8346240, 1814400;
  ...
T_2(3, 2) = 4 since there are 4 ordered partitions of {1, 1, 2} into exactly 2 parts: (1) {{1}, {1, 2}} (2) {{1, 2}, {1}} (3) {{2}, {1, 1}} (4) {{1, 1},{2}}.

Mathematica

f[r_, n_, m_]:= Sum[Binomial[m, l] Binomial[l+r-1, r] (-1)^(m-l) l^(n-r), {l, m}]; For[n = 2, n <= 10, n++, Print[Table[f[2, n, m], {m, 1, n}]]]

Prog

(Magma)
T:= func< n, k, m | n eq 1 select 0 else (&+[(-1)^(k+j)*Binomial(k, j)*Binomial(j+m-1, m)*j^(n-m): j in [1..k]]) >;
[T(n, k, 2): k in [1..n], n in [1..12]]; // G. C. Greubel, Apr 13 2022
(SageMath)
def T(n, k, m): return sum( (-1)^(k-j)*binomial(k, j)*binomial(j+m-1, m)*j^(n-m) for j in (1..k) ) - bool(n==1)
flatten([[T(n, k, 2) for k in (1..n)] for n in (1..12)]) # G. C. Greubel, Apr 13 2022

Crossrefs

This is related to A019538, A172107 and A172108.

Row sums give A172109.

Sequence in context: A109692 A039758 A157894 * A128813 A109062 A112493

Adjacent sequences: A172103 A172104 A172105 * A172107 A172108 A172109

Keyword

nonn,tabl

Author

Martin Griffiths, Jan 25 2010

Status

approved