login
This site is supported by donations 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
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.

LINKS

Table of n, a(n) for n=1..66.

E. Neuwirth, Recursively defined combinatorial functions: Extending Galton's board, Discrete Math. 239 (2001) 33-51.

Shinji Tanimoto, Alternate Permutations and Signed Eulerian Numbers, math.CO/0612135, 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.

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.

License Agreements, Terms of Use, Privacy Policy .

Last modified February 25 11:08 EST 2018. Contains 299653 sequences. (Running on oeis4.)