cp's OEIS Frontend

A246117 Number of parity preserving permutations of the set {1,2,...,n} with exactly k cycles.

%I A246117 #41 May 12 2025 10:00:25
%S A246117 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,
%T A246117 132,193,144,58,12,1,0,144,564,904,769,376,106,16,1,0,576,2400,4180,
%U A246117 3980,2273,800,170,20,1,0,2880,12576,23300,24080,15345,6273,1650,270,25,1
%N A246117 Number of parity preserving permutations of the set {1,2,...,n} with exactly k cycles.
%C A246117 An analog of the Stirling numbers of the first kind, A008275.
%C A246117 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.
%C A246117 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.
%C A246117 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.
%C A246117 From _Peter Bala_, Apr 12 2018: (Start)
%C A246117 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).
%C A246117 A simple combinatorial argument (cf. Dzhumadil'daev and Yeliussizov, Proposition 5.3) gives the recurrences
%C A246117 T(2*n,k,i) = T(2n-1,k-1,i-1) + (n-1)*T(2*n-1,k,i) and
%C A246117 T(2*n+1,k,i) = T(2*n,k-1,i) + n*T(2*n,k,i).
%C A246117 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)
%C A246117 Triangle of allowable Stirling numbers of the first kind (with a different offset). See Cai and Readdy, Table 4. - _Peter Bala_, Apr 14 2018
%H A246117 Y. Cai and M. Readdy, <a href="http://arxiv.org/abs/1506.03249">Negative q-Stirling numbers</a>, arXiv:1506.03249 [math.CO], 2015.
%H A246117 A. Dzhumadil'daev and D. 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 A246117 E. 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 (2001) 33-51.
%H A246117 Shinji Tanimoto, <a href="https://arxiv.org/abs/math/0612135">Alternate Permutations and Signed Eulerian Numbers</a>, arXiv:math/0612135 [math.CO], 2006; Ann. Comb. 14 (2010), 355.
%F A246117 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).
%F A246117 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.
%F A246117 Row sums: A010551; Column 3: A203151;
%F A246117 First subdiagonal: A002620; 2nd subdiagonal: A203246.
%F A246117 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
%e A246117 Triangle begins
%e A246117 n\k| 1   2    3    4    5   6   7   8
%e A246117 = = = = = = = = = = = = = = = = = = =
%e A246117 1  | 1
%e A246117 2  | 0   1
%e A246117 3  | 0   1    1
%e A246117 4  | 0   1    2    1
%e A246117 5  | 0   2    5    4    1
%e A246117 6  | 0   4   12   13    6   1
%e A246117 7  | 0  12   40   51   31   9   1
%e A246117 8  | 0  36  132  193  144  58  12  1
%e A246117 ...
%e A246117 n = 5: The 12 parity-preserving permutations of S_5 and their cycle structure are shown in the table below.
%e A246117 = = = = = = = = = = = = = = = = = = = = = = = = = =
%e A246117 Parity-preserving      Cycle structure     # cycles
%e A246117 permutation
%e A246117 = = = = = = = = = = = = = = = = = = = = = = = = = =
%e A246117 54123                   (153)(24)              2
%e A246117 34521                   (135)(24)              2
%e A246117 34125                   (13)(24)(5)            3
%e A246117 14523                   (1)(24)(35)            3
%e A246117 32541                   (135)(2)(4)            3
%e A246117 52143                   (153)(2)(4)            3
%e A246117 54321                   (15)(24)(3)            3
%e A246117 32145                   (13)(2)(4)(5)          4
%e A246117 14325                   (1)(24)(3)(5)          4
%e A246117 12543                   (1)(2)(35)(4)          4
%e A246117 52341                   (15)(2)(3)(4)          4
%e A246117 12345                   (1)(2)(3)(4)(5)        5
%e A246117 = = = = = = = = = = = = = = = = = = = = = = = = = =
%e A246117 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).
%p A246117 A246117 := proc(n,k)
%p A246117     if n = k then
%p A246117         1;
%p A246117     elif k <= 1 or k > n then
%p A246117         0;
%p A246117     else
%p A246117         floor((n-1)/2)*procname(n-1,k)+procname(n-1,k-1) ;
%p A246117     end if;
%p A246117 end proc:
%p A246117 seq(seq(A246117(n,k),k=1..n),n=1..8) ; # _R. J. Mathar_, Oct 01 2016
%t A246117 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 *)
%Y A246117 A002620 (1st subdiagonal), A008275, A010551 (row sums and column k = 2), A125300, A203151 (column k = 3), A203246 (2nd subdiagonal), A246118 (unsigned matrix inverse).
%Y A246117 Cf. A129256, A187235, A274310.
%K A246117 nonn,easy,tabl
%O A246117 1,9
%A A246117 _Peter Bala_, Aug 14 2014