|
%I #79 Jun 05 2021 08:41:53
%S 1,2,1,6,5,1,24,26,9,1,120,154,71,14,1,720,1044,580,155,20,1,5040,
%T 8028,5104,1665,295,27,1,40320,69264,48860,18424,4025,511,35,1,362880,
%U 663696,509004,214676,54649,8624,826,44,1,3628800,6999840,5753736,2655764
%N Unsigned 2-Stirling numbers of the first kind.
%C Essentially the same as A136124 but with column numbers differing by one. See A049444 for a signed version of this array. The unsigned 2-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 and 2 belong to distinct cycles. This is the particular case r = 2 of the unsigned r-Stirling numbers of the first kind, which count the permutations of the set {1,2,...,n} into k disjoint cycles, with the restriction that the numbers 1, 2, ..., r belong to distinct cycles. The case r = 1 gives the usual unsigned Stirling numbers of the first kind, abs(A008275); for other cases see A143492 (r = 3) and A143493 (r = 4). The corresponding 2-Stirling numbers of the second kind can be found in A143494.
%C In general, the lower unitriangular array of unsigned r-Stirling numbers of the first kind (with suitable offsets in the row and column indexing) equals the matrix product St1 * P^(r-1), where St1 is the array of unsigned Stirling numbers of the first kind, abs(A008275) and P is Pascal's triangle, A007318. The theory of r-Stirling numbers of both kinds is developed in [Broder]. For details of the related r-Lah numbers see A143497.
%C This sequence also represents the number of permutations in the alternating group An of length k, where the length is taken with respect to the generators set {(12)(ij)}. For a bijective proof of the relation between these numbers and the 2-Stirling numbers of the first kind see the Rotbart link. - _Aviv Rotbart_, May 05 2011
%C With offset n=0,k=0 : triangle T(n,k), read by rows, given by [2,1,3,2,4,3,5,4,6,5,...] DELTA [1,0,1,0,1,0,1,0,1,0,...] where DELTA is the operator defined in A084938. - _Philippe Deléham_, Sep 29 2011
%C With offset n=0 and k=0, this is the Sheffer triangle (1/(1-x)^2,-log(1-x)) (in the umbral notation of S. Roman's book this would be called Sheffer for (exp(-2*t),1-exp(-t))). See the e.g.f. given below. Compare also with the e.g.f. for the signed version A049444. - _Wolfdieter Lang_, Oct 10 2011
%C Reversed rows correspond to the Betti numbers of the moduli space M(0,n) of smooth Riemann surfaces (see Murri link). - _Tom Copeland_, Sep 19 2012
%H G. C. Greubel, <a href="/A143491/b143491.txt">Table of n, a(n) for the first 50 rows, flattened</a>
%H Olivier Bodini, Antoine Genitrini, and Mehdi Naima, <a href="https://arxiv.org/abs/1808.08376">Ranked Schröder Trees</a>, arXiv:1808.08376 [cs.DS], 2018.
%H Andrei Z. Broder, <a href="http://infolab.stanford.edu/TR/CS-TR-82-949.html">The r-Stirling numbers</a>, Discrete Math. 49, 241-259 (1984)
%H A. Dzhumadildaev and D. Yeliussizov, <a href="https://arxiv.org/abs/1408.6764">Path decompositions of digraphs and their applications to Weyl algebra</a>, arXiv preprint arXiv:1408.6764 [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="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 Neuwirth Erich, <a href="http://homepage.univie.ac.at/erich.neuwirth/papers/TechRep99-05.pdf">Recursively defined combinatorial functions: Extending Galton's board</a>, Discrete Math. 239 No. 1-3, 33-51 (2001)
%H R. Murri, <a href="http://arxiv.org/abs/1202.1820">Fatgraph Algorithms and the Homology of the Kontsevich Complex</a>, arXiv:1202.1820 [math.AG], 2012. (see Table 1, p. 3)
%H Aviv Rotbart, <a href="http://radon.mat.univie.ac.at/~slc/s/s65rotbart.html">Generator Sets for the Alternating Group</a>, Séminaire Lotharingien de Combinatoire 65 (2011), Article B65b, 16pp.
%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.
%H M. Shattuck, <a href="https://arxiv.org/abs/1412.8721">Generalized r-Lah numbers</a>, arXiv:1412.8721 [math.CO], 2014.
%F T(n,k) = (n-2)! * Sum_{j = k-2 .. n-2} (n-j-1)*|stirling1(j,k-2)|/j!.
%F Recurrence relation: T(n,k) = T(n-1,k-1) + (n-1)*T(n-1,k) for n > 2, with boundary conditions: T(n,1) = T(1,n) = 0, for all n; T(2,2) = 1; T(2,k) = 0 for k > 2.
%F Special cases: T(n,2) = (n-1)!; T(n,3) = (n-1)!*(1/2 + 1/3 + ... + 1/(n-1)).
%F T(n,k) = Sum_{2 <= i_1 < ... < i_(n-k) < n} (i_1*i_2*...*i_(n-k)). For example, T(6,4) = Sum_{2 <= i < j < 6} (i*j) = 2*3 + 2*4 + 2*5 + 3*4 + 3*5 + 4*5 = 71.
%F Row g.f.: Sum_{k = 2..n} T(n,k)*x^k = x^2*(x+2)*(x+3)*...*(x+n-1).
%F E.g.f. for column (k+2): Sum_{n>=k} T(n+2,k+2)*x^n/n! = (1/k!)*(1/(1-x)^2)*(log(1/(1-x)))^k.
%F E.g.f.: (1/(1-t))^(x+2) = Sum_{n>=0} Sum_{k = 0..n} T(n+2,k+2)*x^k*t^n/n! = 1 + (2+x)*t/1! + (6+5*x+x^2)*t^2/2! + ... .
%F This array is the matrix product St1 * P, 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!/2 ( A001710 ). The alternating row sums are (n-2)!.
%F If we define f(n,i,a) = Sum_{k=0..n-i} binomial(n,k)*Stirling1(n-k,i)*Product_{j=0..k-1} (-a - j), then T(n-1,i) = |f(n,i,2)|, for n=1,2,...; i=0..n. - _Milan Janjic_, Dec 21 2008
%F From _Gary W. Adamson_, Jul 19 2011: (Start)
%F n-th row of the triangle = top row of M^(n-2), M = a reversed variant of the (1,2) Pascal triangle (Cf. A029635); as follows:
%F 2, 1, 0, 0, 0, 0, ...
%F 2, 3, 1, 0, 0, 0, ...
%F 2, 5, 4, 1, 0, 0, ...
%F 2, 7, 9, 5, 1, 0, ...
%F ... (End)
%F The reversed, row polynomials of this entry multiplied by (1+x) are the row polynomials of A094638. E.g., (1+x)(1+5x+6x^2) = (1+6x+11x^2+6x^3). - _Tom Copeland_, Dec 11 2016
%e Triangle begins
%e n\k|.....2.....3.....4.....5.....6.....7
%e ========================================
%e 2..|.....1
%e 3..|.....2.....1
%e 4..|.....6.....5.....1
%e 5..|....24....26.....9.....1
%e 6..|...120...154....71....14.....1
%e 7..|...720..1044...580...155....20.....1
%e ...
%e T(4,3) = 5. The permutations of {1,2,3,4} with 3 cycles such that 1 and 2 belong to different cycles are: (1)(2)(3 4), (1)(3)(24), (1)(4)(23), (2)(3)(14) and (2)(4)(13). The remaining possibility (3)(4)(12) is not allowed.
%e From _Aviv Rotbart_, May 05 2011: (Start)
%e Example of the alternating group permutations numbers:
%e Triangle begins
%e n\k|.....0.....1.....2.....3.....4.....5.....6.....7
%e ====================================================
%e 2..|.....1
%e 3..|.....1.....2
%e 4..|.....1.....5.....6
%e 5..|.....1.....9....26....24
%e 6..|.....1....14....71...154...120
%e 7..|.....1....20...155...580..1044..720
%e A(n,k) = number of permutations in An of length k, with respect to the generators set {(12)(ij)}. For example, A(2,0)=1 (only the identity is there), for A4, the generators are {(12)(13),(12)(14),(12,23),(12)(24),(12)(34)}, thus we have A(4,1)=5 (exactly 5 generators), the permutations of length 2 are:
%e (12)(13)(12)(13) = (312)
%e (12)(13)(12)(14) = (41)(23)
%e (12)(13)(12)(24) = (432)(1)
%e (12)(13)(12)(34) = (342)(1)
%e (12)(23)(12)(24) = (13)(24)
%e (12)(14)(12)(14) = (412)(3)
%e Namely, A(4,2)=6. Together with the identity [=(12)(12), of length 0. therefore A(4,0)=1] we have 12 permutations, comprising all A4 (4!/2=12). (End)
%p with combinat: T := (n, k) -> (n-2)! * add((n-j-1)*abs(stirling1(j,k-2))/j!,j = k-2..n-2): for n from 2 to 10 do seq(T(n, k), k = 2..n) end do;
%t t[n_, k_] := (n-2)!*Sum[(n-j-1)*Abs[StirlingS1[j, k-2]]/j!, {j, k-2, n-2}]; Table[t[n, k], {n, 2, 11}, {k, 2, n}] // Flatten (* _Jean-François Alcover_, Apr 16 2013, after Maple *)
%Y Cf. A001705 - A001709 (column 3..7), A001710 (row sums), A008275, A049444 (signed version), A136124, A143492, A143493, A143494, A143497.
%Y Cf. A094638.
%K easy,nonn,tabl
%O 2,2
%A _Peter Bala_, Aug 20 2008
|
