|
| |
|
|
A143491
|
|
Unsigned 2-restricted Stirling numbers of the first kind.
|
|
10
| |
|
|
1, 2, 1, 6, 5, 1, 24, 26, 9, 1, 120, 154, 71, 14, 1, 720, 1044, 580, 155, 20, 1, 5040, 8028, 5104, 1665, 295, 27, 1, 40320, 69264, 48860, 18424, 4025, 511, 35, 1, 362880, 663696, 509004, 214676, 54649, 8624, 826, 44, 1, 3628800, 6999840, 5753736, 2655764
(list; table; graph; refs; listen; history; internal format)
|
|
|
|
OFFSET
| 2,2
|
|
|
COMMENTS
| Essentially the same as A136124 but with column numbers differing by one. See A049444 for a signed version of this array. The unsigned 2-restricted Stirling numbers of the first kind count the number of 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-restricted Stirling numbers of the first kind, which count the number of 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-restricted Stirling numbers of the second kind can be found in A143494.
In general, the lower unitriangular array of unsigned r-restricted 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-restricted Stirling numbers of both kinds is developed in [Broder]. For details of the related r-restricted Lah numbers see A143497.
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-restricted Stirling numbers of the first kind see Rotbart link. - Aviv Rotbart, May 05 2011
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. [From DELEHAM Philippe, Sep 29 2011]
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. [From Wolfdieter Lang, Oct 10 2011]
|
|
|
LINKS
| Broder Andrei Z., The r-Stirling numbers, Discrete Math. 49, 241-259 (1984)
Neuwirth Erich, Recursively defined combinatorial functions: Extending Galton's board, Discrete Math. 239 No. 1-3, 33-51 (2001)
Aviv Rotbart, Generator Sets for the Alternating Group, Séminaire Lotharingien de Combinatoire 65 (2011), Article B65b, 16pp.
|
|
|
FORMULA
| T(n,k) = (n-2)! * sum {j = k-2 .. n-2} (n-j-1)*|stirling1(j,k-2)|/j!. 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. Special cases: T(n,2) = (n-1)!; T(n,3) = (n-1)!*(1/2 + 1/3 + ... + 1/(n-1)). 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. Row g.f.: sum {k = 2..n} T(n,k)*x^k = x^2*(x+2)*(x+3)* ... *(x+n-1). E.g.f. for column (k+2): sum {n = k..inf} T(n+2,k+2)*x^n/n! = 1/k!*1/(1-x)^2* (ln(1/(1-x)))^k. E.g.f.: (1/(1-t))^(x+2) = sum {n = 0..inf} sum {k = 0..n} T(n+2,k+2)*x^k*t^n/n! = 1 + (2+x)*t/1! + (6+5x+x^2)*t^2/2! + ... . 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)!.
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-1,i) = |f(n,i,2)|, for n=1,2,...;i=0...n. [From Milan R. Janjic (agnus(AT)blic.net), Dec 21 2008]
Contribution from Gary W. Adamson, Jul 19 2011: (Start)
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:
2, 1, 0, 0, 0, 0,...
2, 3, 1, 0, 0, 0,...
2, 5, 4, 1, 0, 0,...
2, 7, 9, 5, 1, 0,...
... (end)
|
|
|
EXAMPLE
| Triangle begins
n\k|.....2.....3.....4.....5.....6.....7
========================================
2..|.....1
3..|.....2.....1
4..|.....6.....5.....1
5..|....24....26.....9.....1
6..|...120...154....71....14.....1
7..|...720..1044...580...155....20.....1
...
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.
Contribution from Aviv Rotbart, May 05 2011: (Start)
Example of the alternating group permutations numbers:
Triangle begins
n\k|.....0.....1.....2.....3.....4.....5.....6.....7
====================================================
2..|.....1
3..|.....1.....2
4..|.....1.....5.....6
5..|.....1.....9....26....24
6..|.....1....14....71...154...120
7..|.....1....20...155...580..1044..720
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:
(12)(13)(12)(13) = (312)
(12)(13)(12)(14) = (41)(23)
(12)(13)(12)(24) = (432)(1)
(12)(13)(12)(34) = (342)(1)
(12)(23)(12)(24) = (13)(24)
(12)(14)(12)(14) = (412)(3)
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)
|
|
|
MAPLE
| 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;
|
|
|
CROSSREFS
| Cf. A001705 - A001709 (column 3 - column 7), A001710 (row sums), A008275, A049444 (signed version), A136124, A143492, A143493, A143494, A143497.
Sequence in context: A121575 A049444 A136124 * A070918 A113381 A118980
Adjacent sequences: A143488 A143489 A143490 * A143492 A143493 A143494
|
|
|
KEYWORD
| easy,nonn,tabl
|
|
|
AUTHOR
| Peter Bala (pbala(AT)toucansurf.com), Aug 20 2008
|
| |
|
|
