A061691 - OEIS

%I #45 Aug 18 2024 03:15:52

%S 1,1,2,1,9,6,1,34,72,24,1,125,650,600,120,1,461,5400,10500,5400,720,1,

%T 1715,43757,161700,161700,52920,5040,1,6434,353192,2361016,4116000,

%U 2493120,564480,40320,1,24309,2862330,33731208,96960024,97161120,39372480,6531840,362880

%N Triangle of generalized Stirling numbers.

%C 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]

%H Alois P. Heinz, <a href="/A061691/b061691.txt">Rows n = 1..141, flattened</a>

%H M. Aguiar and R. C. Orellana, <a href="http://www.math.dartmouth.edu/~orellana/blockperm.pdf">The Hopf algebra of uniform block permutations</a>, 17th International Conference on Formal Power Series and Algebraic Combinatorics, Taormina, July 2005.

%H D. Aldous and P. Diaconis, <a href="http://dx.doi.org/10.1090/S0273-0979-99-00796-X">Longest increasing subsequences: from patience sorting to the Baik-Deift-Johansson theorem</a>, Bull. Amer. Math. Soc. 36 (1999), 413-432.

%H D. G. Fitzgerald, <a href="http://dx.doi.org/10.1017/S0004972700037692">A presentation for the monoid of uniform block permutations</a>, Bull. Austral. Math. Soc. 68 (2003), 317-324.

%H A. T. Irish, F. Quitin, U. Madhow, and M. Rodwell, <a href="http://www.ece.ucsb.edu/wcsl/Publications/Andrew_Asilomar13.pdf">Achieving multiple degrees of freedom in long-range mm-wave MIMO channels using randomly distributed relays</a>, 2014.

%H I. P. Lankham, <a href="http://arxiv.org/abs/0705.4524">Patience Sorting and Its Generalizations</a>, arXiv:0705.4524 [math.CO], 2007.

%H J.-M. Sixdeniers, K. A. Penson and A. I. Solomon, <a href="http://www.cs.uwaterloo.ca/journals/JIS/VOL4/SIXDENIERS/bell.html">Extended Bell and Stirling Numbers From Hypergeometric Exponentiation</a>, J. Integer Seqs. Vol. 4 (2001), #01.1.4.

%F 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

%F From _Peter Bala_, Jul 14 2011: (Start)

%F The table entry T(n,k) may also be expressed as a sum over (unordered) partitions of n into k parts:

%F 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.

%F Generating function:

%F Let J(z) = sum {n>=0} z^n/n!^2. Then

%F 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 + ....

%F Relations with other sequences:

%F T(n,k) = 1/k!*A192722(n,k).

%F Row sums [1,3,16,131,...] = A023998. (End)

%F 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

%e Triangle begins:

%e   1;

%e   1,2;

%e   1,9,6;

%e   1,34,72,24;

%e   1,125,650,600,120;

%e   ...

%e T(4,2) = 34:

%e 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.

%p #A061691

%p #J = sum {n>=0} z^n/n!^2

%p J := BesselJ(0, 2*i*sqrt(z)):

%p G := exp(x*(J(z)-1)):

%p Gser := simplify(series(G, z = 0, 12)):

%p for n from 1 to 10 do

%p P[n] := n!^2*sort(coeff(Gser, z, n)) od:

%p for n from 1 to 10 do seq(coeff(P[n],x,k), k = 1..n) od;

%p # yields sequence in triangular form

%p # second Maple program:

%p b:= proc(n) option remember; expand(`if`(n=0, 1,

%p       add(x*b(n-i)*binomial(n, i)/i!, i=1..n)))

%p     end:

%p T:= n-> (p-> seq(coeff(p, x, i)/i!, i=1..n))(b(n)*n!):

%p seq(T(n), n=1..12);  # _Alois P. Heinz_, Sep 10 2019

%t 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 *)

%Y Diagonals give A010763, A061690, A000142, A001809, A061689. Cf. A061692. A023998 (row sums), A192721, A192722.

%K nonn,tabl

%O 1,3

%A _N. J. A. Sloane_, Jun 18 2001

%E More terms from _Vladeta Jovovic_, Apr 23 2003