login
Unsigned 4-Stirling numbers of the first kind.
6

%I #42 Oct 02 2024 09:19:09

%S 1,4,1,20,9,1,120,74,15,1,840,638,179,22,1,6720,5944,2070,355,30,1,

%T 60480,60216,24574,5265,625,39,1,604800,662640,305956,77224,11515,

%U 1015,49,1,6652800,7893840,4028156,1155420,203889,22680,1554,60,1,79833600

%N Unsigned 4-Stirling numbers of the first kind.

%C See A049459 for a signed version of the array. The unsigned 4-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, 3 and 4 belong to distinct cycles. This is the case r = 4 of the unsigned r-Stirling numbers of the first kind. For other cases see abs(A008275) (r = 1), A143491 (r = 2) and A143492 (r = 3). See A143496 for the corresponding triangle of 4-Stirling numbers of the second kind.

%C The theory of r-Stirling numbers of both kinds is developed in [Broder]. For details of the related 4-Lah numbers see A143499.

%C With offset n=0 and k=0, this is the Sheffer triangle (1/(1-x)^4,-log(1-x)) (in the umbral notation of S. Roman's book this would be called Sheffer for (exp(-4*t),1-exp(-t))). See the e.g.f given below. Compare also with the e.g.f. for the signed version A049459. - _Wolfdieter Lang_, Oct 10 2011

%C With offset n=0 and k=0: triangle T(n,k), read by rows, given by (4,1,5,2,6,3,7,4,8,5,9,6,...) DELTA (1,0,1,0,1,0,1,0,1,0,1,0,...) 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 [math.CO], 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="https://doi.org/10.37236/5181">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="https://doi.org/10.37236/6121">Elliptic Rook and File Numbers</a>, Electronic Journal of Combinatorics, 24(1) (2017), #P1.31.

%F T(n,k) = (n-4)! * Sum_{j = k-4 .. n-4} C(n-j-1,3)*|stirling1(j,k-4)|/j!.

%F Recurrence relation: T(n,k) = T(n-1,k-1) + (n-1)*T(n-1,k) for n > 4, with boundary conditions: T(n,3) = T(3,n) = 0 for all n; T(4,4) = 1; T(4,k) = 0 for k > 4.

%F Special cases:

%F T(n,4) = (n-1)!/3!.

%F T(n,5) = (n-1)!/3!*(1/4 + ... + 1/(n-1)).

%F T(n,k) = sum {4 <= i_1 < ...< i_(n-k) < n} (i_1*i_2* ...*i_(n-k)). For example, T(7,5) = Sum_{4 <= i < j < 7} (i*j) = 4*5 + 4*6 + 5*6 = 74.

%F Row g.f.: Sum_{k = 4..n} T(n,k)*x^k = x^4*(x+4)*(x+5)* ... *(x+n-1).

%F E.g.f. for column (k+4): Sum_{n = k..inf} T(n+4,k+4)*x^n/n! = 1/k!*1/(1-x)^4 * (log(1/(1-x)))^k.

%F E.g.f.: (1/(1-t))^(x+4) = Sum_{n = 0..inf} Sum_{k = 0..n} T(n+4,k+4)*x^k*t^n/n! = 1 + (4+x)*t/1! + (20+9*x+x^2)*t^2/2! + .... This array is the matrix product St1 * P^3, 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!/4! ( A001720 ). The alternating row sums are (n-2)!/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+4,i) = |f(n,i,3)|, for n=1,2,...;i=0...n. - _Milan Janjic_, Dec 21 2008

%e Triangle begins

%e n\k| 4 5 6 7 8 9

%e ========================================

%e 4 | 1

%e 5 | 4 1

%e 6 | 20 9 1

%e 7 | 120 74 15 1

%e 8 | 840 638 179 22 1

%e 9 | 6720 5944 2070 355 30 1

%e ...

%e T(6,5) = 9. The 9 permutations of {1,2,3,4,5,6} with 5 cycles such that 1, 2, 3 and 4 belong to different cycles are: (1,5)(2)(3)(4)(6), (1,6)(2)(3)(4)(5), (2,5)(1)(3)(4)(6), (2,6)(1)(3)(4)(5), (3,5)(1)(2)(4)(6), (3,6)(1)(2)(4)(5), (4,5)(1)(2)(3)(6), (4,6)(1)(2)(3)(5) and (5,6)(1)(2)(3)(4).

%p with combinat: T := (n, k) -> (n-4)! * add(binomial(n-j-1,3)*abs(stirling1(j,k-4))/j!,j = k-4..n-4): for n from 4 to 13 do seq(T(n, k), k = 4..n) end do;

%Y Cf. A001715 - A001719 (column 4 - column 8), A001720 (row sums), A008275, A049459 (signed version), A143491, A143492, A143496, A143499.

%K easy,nonn,tabl

%O 4,2

%A _Peter Bala_, Aug 20 2008