login

Year-end appeal: Please make a donation to the OEIS Foundation to support ongoing development and maintenance of the OEIS. We are now in our 61st year, we have over 378,000 sequences, and we’ve reached 11,000 citations (which often say “discovered thanks to the OEIS”).

A061691
Triangle of generalized Stirling numbers.
8
1, 1, 2, 1, 9, 6, 1, 34, 72, 24, 1, 125, 650, 600, 120, 1, 461, 5400, 10500, 5400, 720, 1, 1715, 43757, 161700, 161700, 52920, 5040, 1, 6434, 353192, 2361016, 4116000, 2493120, 564480, 40320, 1, 24309, 2862330, 33731208, 96960024, 97161120, 39372480, 6531840, 362880
OFFSET
1,3
COMMENTS
The Eulerian-type number triangle associated with this triangle of generalized Stirling numbers is A192721. The table entry T(n,k) gives the number of uniform block permutations of the set {1,2,...,n} partitioned into k blocks. An example is given below. T(n,k) also gives the number of games of simple patience with n cards resulting in k piles (adapt Algorithm 1.1.22 of Lankham). [Peter Bala, Jul 14 2011]
LINKS
M. Aguiar and R. C. Orellana, The Hopf algebra of uniform block permutations, 17th International Conference on Formal Power Series and Algebraic Combinatorics, Taormina, July 2005.
D. Aldous and P. Diaconis, Longest increasing subsequences: from patience sorting to the Baik-Deift-Johansson theorem, Bull. Amer. Math. Soc. 36 (1999), 413-432.
D. G. Fitzgerald, A presentation for the monoid of uniform block permutations, Bull. Austral. Math. Soc. 68 (2003), 317-324.
I. P. Lankham, Patience Sorting and Its Generalizations, arXiv:0705.4524 [math.CO], 2007.
J.-M. Sixdeniers, K. A. Penson and A. I. Solomon, Extended Bell and Stirling Numbers From Hypergeometric Exponentiation, J. Integer Seqs. Vol. 4 (2001), #01.1.4.
FORMULA
T(n, k) = 1/k!*Sum multinomial(n, n_1, n_2, ..n_k)^2, where the sum extends over all compositions (n_1, n_2, .., n_k) of n into exactly k nonnegative parts. - Vladeta Jovovic, Apr 23 2003
From Peter Bala, Jul 14 2011: (Start)
The table entry T(n,k) may also be expressed as a sum over (unordered) partitions of n into k parts:
T(n,k) = sum {partitions m_1*1+...+m_n*n = n, m_1+...+m_n = k} 1/(m_1!*...*m_n!)*{n!/(1!^(m_1)*...*n!^(m_n))}^2.
Generating function:
Let J(z) = sum {n>=0} z^n/n!^2. Then
exp(x*(J(z)-1)) = 1 + x*z + (x + 2*x^2)*z^2/2!^2 + (x + 9*x^2 + 6*x^3)*z^3/3!^2 + ....
Relations with other sequences:
T(n,k) = 1/k!*A192722(n,k).
Row sums [1,3,16,131,...] = A023998. (End)
The row polynomials R(n,x) satisfy the recurrence equation R(n,x) = x*( sum {k = 0..n-1} binomial(n,k)*binomial(n-1,k)*R(k,x) ) with R(0,x) = 1. Also R(n,x + y) = sum {k = 0..n} binomial(n,k)^2*R(k,x)*R(n-k,y). - Peter Bala, Sep 17 2013
EXAMPLE
Triangle begins:
1;
1,2;
1,9,6;
1,34,72,24;
1,125,650,600,120;
...
T(4,2) = 34:
There are 7 partitions of the set {1,2,3,4} into 2 blocks. The four partitions {1,2,3}{4}, {1,2,4}{3}, {1,3,4}{2} and {2,3,4}{1} give rise to 4*4 = 16 uniform block permutations while the remaining 3 partitions {1,2}{3,4}, {1,3}{2,4} and {1,4}{2,3} give 2!*3*3 = 18 uniform block permutations : thus in total there are 16+18 = 34 block permutations between the set partitions of {1,2,3,4} into 2 blocks.
MAPLE
#J = sum {n>=0} z^n/n!^2
J := BesselJ(0, 2*i*sqrt(z)):
G := exp(x*(J(z)-1)):
Gser := simplify(series(G, z = 0, 12)):
for n from 1 to 10 do
P[n] := n!^2*sort(coeff(Gser, z, n)) od:
for n from 1 to 10 do seq(coeff(P[n], x, k), k = 1..n) od;
# yields sequence in triangular form
# second Maple program:
b:= proc(n) option remember; expand(`if`(n=0, 1,
add(x*b(n-i)*binomial(n, i)/i!, i=1..n)))
end:
T:= n-> (p-> seq(coeff(p, x, i)/i!, i=1..n))(b(n)*n!):
seq(T(n), n=1..12); # Alois P. Heinz, Sep 10 2019
MATHEMATICA
max = 9; g := Exp[x*(BesselI[0, 2*Sqrt[z]] - 1)]; gser = Series[g, {z, 0, max}, {x, 0, max}]; t[n_, k_] := n!^2*SeriesCoefficient[ gser // Normal, {z, 0, n}, {x, 0, k}]; Flatten[ Table[ t[n, k], {n, 1, max}, {k, 1, n}]] (* Jean-François Alcover, Apr 04 2012, after Maple *)
CROSSREFS
Diagonals give A010763, A061690, A000142, A001809, A061689. Cf. A061692. A023998 (row sums), A192721, A192722.
Sequence in context: A133174 A155545 A141618 * A235595 A061356 A141028
KEYWORD
nonn,tabl
AUTHOR
N. J. A. Sloane, Jun 18 2001
EXTENSIONS
More terms from Vladeta Jovovic, Apr 23 2003
STATUS
approved