login
The OEIS is supported by the many generous donors to the OEIS Foundation.

 

Logo
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

%I #36 Nov 11 2022 18:33:58

%S 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 132,193,144,58,12,1,0,144,564,904,769,376,106,16,1,0,576,2400,4180,

%U 3980,2273,800,170,20,1,0,2880,12576,23300,24080,15345,6273,1650,270,25,1

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

%C An analog of the Stirling numbers of the first kind, A008275.

%C 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 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 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 From _Peter Bala_, Apr 12 2018: (Start)

%C 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 A simple combinatorial argument (cf. Dzhumadil'daev and Yeliussizov, Proposition 5.3) gives the recurrences

%C T(2*n,k,i) = T(2n-1,k-1,i-1) + (n-1)*T(2*n-1,k,i) and

%C T(2*n+1,k,i) = T(2*n,k-1,i) + n*T(2*n,k,i).

%C 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 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 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 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 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 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 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 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 Row sums: A010551; Column 3: A203151;

%F First subdiagonal: A002620; 2nd subdiagonal: A203246.

%F 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 Triangle begins

%e n\k| 1 2 3 4 5 6 7 8

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

%e 1 | 1

%e 2 | 0 1

%e 3 | 0 1 1

%e 4 | 0 1 2 1

%e 5 | 0 2 5 4 1

%e 6 | 0 4 12 13 6 1

%e 7 | 0 12 40 51 31 9 1

%e 8 | 0 36 132 193 144 58 12 1

%e ...

%e n = 5: The 12 parity-preserving permutations of S_5 and their cycle structure are shown in the table below.

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

%e Parity-preserving Cycle structure # cycles

%e permutation

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

%e 54123 (153)(24) 2

%e 34521 (135)(24) 2

%e 34125 (13)(24)(5) 3

%e 14523 (1)(24)(35) 3

%e 32541 (135)(2)(4) 3

%e 52143 (153)(2)(4) 3

%e 54321 (15)(24)(3) 3

%e 32145 (13)(2)(4)(5) 4

%e 14325 (1)(24)(3)(5) 4

%e 12543 (1)(2)(35)(4) 4

%e 52341 (15)(2)(3)(4) 4

%e 12345 (1)(2)(3)(4)(5) 5

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

%e 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 := proc(n,k)

%p if n = k then

%p 1;

%p elif k <= 1 or k > n then

%p 0;

%p else

%p floor((n-1)/2)*procname(n-1,k)+procname(n-1,k-1) ;

%p end if;

%p end proc:

%p seq(seq(A246117(n,k),k=1..n),n=1..8) ; # _R. J. Mathar_, Oct 01 2016

%t 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 A002620 (1st subdiagonal), A008275, A010551 (row sums and column k = 2), A125300, A203151 (column k = 3), A203246 (2nd subdiagonal), A246118 (unsigned matrix inverse).

%Y Cf. A187235, A274310.

%K nonn,easy,tabl

%O 1,9

%A _Peter Bala_, Aug 14 2014

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

License Agreements, Terms of Use, Privacy Policy. .

Last modified March 28 16:12 EDT 2024. Contains 371254 sequences. (Running on oeis4.)