This site is supported by donations to The OEIS Foundation.

 Hints (Greetings from The On-Line Encyclopedia of Integer Sequences!)
 A246117 Number of parity preserving permutations of the set {1,2,...,n} with exactly k cycles. 10
 1, 0, 1, 0, 1, 1, 0, 1, 2, 1, 0, 2, 5, 4, 1, 0, 4, 12, 13, 6, 1, 0, 12, 40, 51, 31, 9, 1, 0, 36, 132, 193, 144, 58, 12, 1, 0, 144, 564, 904, 769, 376, 106, 16, 1, 0, 576, 2400, 4180, 3980, 2273, 800, 170, 20, 1, 0, 2880, 12576, 23300, 24080, 15345, 6273, 1650, 270, 25, 1 (list; table; graph; refs; listen; history; text; internal format)
 OFFSET 1,9 COMMENTS An analog of the Stirling numbers of the first kind, A008275. A permutation p of the set {1,2,...,n} is called a parity-preserving permutation if p(i) = i (mod 2) for i = 1,2,...,n. The set of all such permutations forms a subgroup of order A010551 of the symmetric group on n letters. This triangle gives the number of parity preserving permutations of the set {1,2,...,n} with exactly k cycles. An example is given below. If we write a parity-preserving permutation p in one line notation as ( p(1) p(2) p(3)... p(n) ) then the first entry p(1) is odd and thereafter the entries alternate in parity. Thus the permutation p belongs to the set of parity-alternate permutations studied by Tanimoto. The row generating polynomials form the polynomial sequence x, x^2, x^2*(x + 1), x^2*(x + 1)^2, x^2*(x + 1)^2*(x + 2), x^2*(x + 1)^2*(x + 2)^2, .... Except for differences in offset, this triangle is the Galton array G(floor(n/2),1) in the notation of Neuwirth with inverse array G(-floor(k/2),1). See A246118 for the unsigned version of the inverse array. From Peter Bala, Apr 12 2018: (Start) In the cycle decomposition of a parity preserving permutation, the entries in a given cycle are either all even or all odd. Define T(n,k,i), 1 <= i <= k-1, (a refinement of the table number T(n,k)) to be the number of parity preserving permutations of the set {1,2,...,n} with exactly k cycles and with i of the cycles having all even entries. Clearly, T(n,k) = Sum_{i = 1..k-1} T(n,k,i). A simple combinatorial argument (cf. Dzhumadil'daev and Yeliussizov, Proposition 5.3) gives the recurrences T(2*n,k,i) = T(2n-1,k-1,i-1) + (n-1)*T(2*n-1,k,i) and T(2*n+1,k,i) = T(2*n,k-1,i) + n*T(2*n,k,i). The solution to these recurrences for n >= 1 is T(2*n,k,i) = S1(n,i)*S1(n,k-i) and T(2*n+1,k,i) = S1(n,i)*S1(n+1,k-i), where S1(n,k) = |A008275(n,k)| denotes the (unsigned) Stirling cycle numbers of the first kind. Kotesovec's formula for T(n,k) below follows immediately from this. Cf. A274310. (End) Triangle of allowable Stirling numbers of the first kind (with a different offset). See Cai and Readdy, Table 4. - Peter Bala, Apr 14 2018 LINKS Y. Cai and M. Readdy, Negative q-Stirling numbers, arXiv:1506.03249 [math.CO], 2015. A. Dzhumadil'daev and D. Yeliussizov, Walks, partitions, and normal ordering, Electronic Journal of Combinatorics, 22(4) (2015), #P4.10. E. Neuwirth, Recursively defined combinatorial functions: Extending Galton's board, Discrete Math. 239 (2001) 33-51. Shinji Tanimoto, Alternate Permutations and Signed Eulerian Numbers, arXiv:math/0612135 [math.CO], 2006; Ann. Comb. 14 (2010), 355. FORMULA Recurrence equations: T(1,1) = 1, T(n,1) = 0 for n >= 2; T(n,k) = 0 for k > n; otherwise T(n+1,k) = floor(n/2)*T(n,k) + T(n,k-1). Row generating polynomials R(n,x): R(2*n,x) = ( x*(x + 1)*...*(x + n - 1) )^2; R(2*n + 1,x) = R(2*n,x)*(x + n) with the convention R(0,x) = 1. Row sums: A010551; Column 3: A203151; First subdiagonal: A002620; 2nd subdiagonal: A203246. T(n,k) = (-1)^(n-k) * sum_{j=1..k-1} Stirling1(floor((n+1)/2),j) * Stirling1(floor(n/2),k-j), for k>1. - Vaclav Kotesovec, Feb 09 2015 EXAMPLE Triangle begins n\k| 1   2    3    4    5   6   7   8 = = = = = = = = = = = = = = = = = = = 1  | 1 2  | 0   1 3  | 0   1    1 4  | 0   1    2    1 5  | 0   2    5    4    1 6  | 0   4   12   13    6   1 7  | 0  12   40   51   31   9   1 8  | 0  36  132  193  144  58  12  1 ... n = 5: The 12 parity-preserving permutations of S_5 and their cycle structure are shown in the table below. = = = = = = = = = = = = = = = = = = = = = = = = = = Parity-preserving      Cycle structure     # cycles permutation = = = = = = = = = = = = = = = = = = = = = = = = = = 54123                   (153)(24)              2 34521                   (135)(24)              2 34125                   (13)(24)(5)            3 14523                   (1)(24)(35)            3 32541                   (135)(2)(4)            3 52143                   (153)(2)(4)            3 54321                   (15)(24)(3)            3 32145                   (13)(2)(4)(5)          4 14325                   (1)(24)(3)(5)          4 12543                   (1)(2)(35)(4)          4 52341                   (15)(2)(3)(4)          4 12345                   (1)(2)(3)(4)(5)        5 = = = = = = = = = = = = = = = = = = = = = = = = = = This gives row 5 as [2, 5, 4, 1] with generating function 2*x^2 + 5*x^3 + 4*x^4 + x^5 = ( x*(x + 1) )^2 * (x + 2). MAPLE A246117 := proc(n, k)     if n = k then         1;     elif k <= 1 or k > n then         0;     else         floor((n-1)/2)*procname(n-1, k)+procname(n-1, k-1) ;     end if; end proc: seq(seq(A246117(n, k), k=1..n), n=1..8) ; # R. J. Mathar, Oct 01 2016 MATHEMATICA Flatten[{1, Rest[Table[Table[(-1)^(n-k) * Sum[StirlingS1[Floor[(n+1)/2], j] * StirlingS1[Floor[n/2], k-j], {j, 1, k-1}], {k, 1, n}], {n, 1, 12}]]}] (* Vaclav Kotesovec, Feb 09 2015 *) CROSSREFS A002620 (1st subdiagonal), A008275, A010551 (row sums and column k = 2), A125300, A203151 (column k = 3), A203246 (2nd subdiagonal), A246118 (unsigned matrix inverse). Cf. A187235, A274310. Sequence in context: A292892 A074142 A059084 * A295688 A266994 A267072 Adjacent sequences:  A246114 A246115 A246116 * A246118 A246119 A246120 KEYWORD nonn,easy,tabl AUTHOR Peter Bala, Aug 14 2014 STATUS approved

Lookup | Welcome | Wiki | Register | Music | Plot 2 | Demos | Index | Browse | More | WebCam
Contribute new seq. or comment | Format | Style Sheet | Transforms | Superseeker | Recent | More pages
The OEIS Community | Maintained by The OEIS Foundation Inc.

Last modified May 27 08:27 EDT 2018. Contains 304690 sequences. (Running on oeis4.)