|
%I #34 Nov 11 2022 18:34:18
%S 1,3,1,12,7,1,60,47,12,1,360,342,119,18,1,2520,2754,1175,245,25,1,
%T 20160,24552,12154,3135,445,33,1,181440,241128,133938,40369,7140,742,
%U 42,1,1814400,2592720,1580508,537628,111769,14560,1162,52,1,19958400
%N Unsigned 3-Stirling numbers of the first kind.
%C See A049458 for a signed version of this array. The unsigned 3-Stirling numbers of the first kind count the permutations of the set {1,2,...,n} into k disjoint cycles, with the restriction that the elements 1, 2 and 3 belong to distinct cycles. This is the case r = 3 of the unsigned r-Stirling numbers of the first kind. For other cases see abs(A008275) (r = 1), A143491 (r = 2) and A143493 (r = 4). See A143495 for the corresponding 3-Stirling numbers of the second kind. The theory of r-Stirling numbers of both kinds is developed in [Broder]. For details of the related 3-Lah numbers see A143498.
%C With offset n=0 and k=0, this is the Sheffer triangle (1/(1-x)^3, -log(1-x)) (in the umbral notation of S. Roman's book this would be called Sheffer for (exp(-3*t), 1-exp(-t))). See the e.g.f given below. Compare also with the e.g.f. for the signed version A049458. - _Wolfdieter Lang_, Oct 10 2011
%C With offset n=0 and k=0 : triangle T(n,k), read by rows, given by (3,1,4,2,5,3,6,4,7,5,8,6,...) DELTA (1,0,1,0,1,0,1,0,1,0,1,...) where DELTA is the operator defined in A084938. - _Philippe Deléham_, Oct 31 2011
%H Broder Andrei Z., <a href="https://doi.org/10.1016/0012-365X(84)90161-4">The r-Stirling numbers</a>, Discrete Math. 49, 241-259 (1984)
%H A. Dzhumadildaev and D. Yeliussizov, <a href="http://arxiv.org/abs/1408.6764v1">Path decompositions of digraphs and their applications to Weyl algebra</a>, arXiv preprint arXiv:1408.6764v1, 2014. [Version 1 contained many references to the OEIS, which were removed in Version 2. - _N. J. A. Sloane_, Mar 28 2015]
%H Askar Dzhumadil’daev and Damir Yeliussizov, <a href="http://www.combinatorics.org/ojs/index.php/eljc/article/view/v22i4p10">Walks, partitions, and normal ordering</a>, Electronic Journal of Combinatorics, 22(4) (2015), #P4.10.
%H Erich Neuwirth, <a href="https://doi.org/10.1016/S0012-365X(00)00373-3">Recursively defined combinatorial functions: Extending Galton's board</a>, Discrete Math. 239 No. 1-3, 33-51 (2001).
%H Michael J. Schlosser and Meesue Yoo, <a href="http://www.combinatorics.org/ojs/index.php/eljc/article/view/v24i1p31">Elliptic Rook and File Numbers</a>, Electronic Journal of Combinatorics, 24(1) (2017), #P1.31.
%F T(n,k) = (n-3)! * Sum_{j = k-3 .. n-3} C(n-j-1,2)*|Stirling1(j,k-3)|/j!.
%F Recurrence relation: T(n,k) = T(n-1,k-1) + (n-1)*T(n-1,k) for n > 3, with boundary conditions: T(n,2) = T(2,n) = 0, for all n; T(3,3) = 1; T(3,k) = 0 for k > 3.
%F Special cases:
%F T(n,3) = (n-1)!/2! for n >= 3.
%F T(n,4) = (n-1)!/2!*(1/3 + ... + 1/(n-1)) for n >= 3.
%F T(n,k) = Sum_{3 <= i_1 < ... < i_(n-k) < n} (i_1*i_2* ...*i_(n-k)). For example, T(6,4) = Sum_{3 <= i < j < 6} (i*j) = 3*4 + 3*5 + 4*5 = 47.
%F Row g.f.: Sum_{k = 3..n} T(n,k)*x^k = x^3*(x+3)*(x+4)* ... *(x+n-1).
%F E.g.f. for column (k+3): Sum_{n = k..inf} T(n+3,k+3)*x^n/n! = 1/k!*1/(1-x)^3 * (log(1/(1-x)))^k.
%F E.g.f.: (1/(1-t))^(x+3) = Sum_{n = 0..inf} Sum_{k = 0..n} T(n+3,k+3)*x^k*t^n/n! = 1 + (3+x)*t/1! + (12+7*x+x^2)*t^2/2! + ....
%F This array is the matrix product St1 * P^2, where St1 denotes the lower triangular array of unsigned Stirling numbers of the first kind, abs(A008275) and P denotes Pascal's triangle, A007318. The row sums are n!/3! ( A001715 ). The alternating row sums are (n-2)!.
%F If we define f(n,i,a) = sum(binomial(n,k)*Stirling1(n-k,i)*product(-a-j,j=0..k-1),k=0..n-i), then T(n,i) = |f(n,i,3)|, for n=1,2,...;i=0...n. - _Milan Janjic_, Dec 21 2008
%e Triangle begins
%e n\k|.....3.....4.....5.....6.....7.....8
%e ========================================
%e 3..|.....1
%e 4..|.....3.....1
%e 5..|....12.....7.....1
%e 6..|....60....47....12.....1
%e 7..|...360...342...119....18.....1
%e 8..|..2520..2754..1175...245....25.....1
%e ...
%e T(5,4) = 7. The permutations of {1,2,3,4,5} with 4 cycles such that 1, 2 and 3 belong to different cycles are: (14)(2)(3)(5), (15)(2)(3)(4), (24)(1)(3)(5), (25)(1)(3)(4), (34)(1)(2)(5), (35)(1)(2)(4) and (45)(1)(2)(3).
%p with combinat: T := (n, k) -> (n-3)! * add(binomial(n-j-1,2)*abs(stirling1(j,k-3))/j!,j = k-3..n-3): for n from 3 to 12 do seq(T(n, k), k = 3..n) end do;
%Y Cf. A001710 - A001714 (column 3 - column 7), A001715 (row sums), A008275, A049458 (signed version), A143491, A143493, A143495, A143498.
%K easy,nonn,tabl
%O 3,2
%A _Peter Bala_, Aug 20 2008
|
