A125300 -id:A125300 - cp's OEIS frontend

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

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

Offset: 1

Peter Bala, Aug 14 2014

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

			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).

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.

A002620 (1st subdiagonal), A008275, A010551 (row sums and column k = 2), A125300, A203151 (column k = 3), A203246 (2nd subdiagonal), A246118 (unsigned matrix inverse).

Cf. A129256, A187235, A274310.

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

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 *)

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

A092186 a(n) = 2(m!)^2 for n = 2m and m!(m+1)! for n = 2m+1.

Original entry on oeis.org

2, 1, 2, 2, 8, 12, 72, 144, 1152, 2880, 28800, 86400, 1036800, 3628800, 50803200, 203212800, 3251404800, 14631321600, 263363788800, 1316818944000, 26336378880000, 144850083840000, 3186701844480000, 19120211066880000, 458885065605120000, 2982752926433280000

Offset: 0

N. J. A. Sloane, based on correspondence from Hugo Pfoertner and Rob Pratt, Apr 02 2004

nonn

Singmaster's problem: "A salesman's office is located on a straight road. His n customers are all located along this road to the east of the office, with the office of customer k at distance k from the salesman's office. The salesman must make a driving trip whereby he leaves the office, visits each customer exactly once, then returns to the office.
"Because he makes a profit on his mileage allowance, the salesman wants to drive as far as possible during his trip. What is the maximum possible distance he can travel on such a trip and how many different such trips are there?
"Assume that if the travel plans call for the salesman to visit customer j immediately after he visits customer i, then he drives directly from i to j."
The solution to the first question is twice A002620(n-1); the solution to the second question is a(n).
Number of permutation of [n] with no pair of consecutive elements of the same parity. - Vladeta Jovovic, Nov 26 2007

A. O. Munagi, Alternating subsets and permutations, Rocky Mountain J. Math. 40 (6) (2010) 1965-1977 doi:10.1216/RJM-2010-40-6-1965, Corollary 3.2.
David Singmaster, Problem 1654, Mathematics Magazine 75 (October 2002). Solution in Mathematics Magazine 76 (October 2003).

Alois P. Heinz, Table of n, a(n) for n = 0..300
David Singmaster, Problem 1654, Mathematics Magazine 75 p. 317 (October 2002). Solution, Mathematics Magazine 76 p. 321-322 (October 2003).
Shinji Tanimoto, Alternate Permutations and Signed Eulerian Numbers, arXiv:math/0612135 [math.CO], 2006; Ann. Comb. 14 (2010), 355.

Cf. A152877.

Row sums of A125300. - Alois P. Heinz, Nov 18 2013

a:= proc(n) option remember; `if`(n<2, 2-n,
      (n*(3*n-1)*(n-1)*a(n-2) -4*a(n-1))/(12*n-16))
    end:
seq(a(n), n=0..30);  # Alois P. Heinz, Nov 11 2013

f[n_] := If[EvenQ[n], 2 (n/2)!^2, ((n + 1)/2)! ((n - 1)/2)!]; Table[
f[n], {n, 0, 25}] (* Geoffrey Critzer, Aug 24 2013 *)

A382232 Irregular triangle read by rows: T(n,k) = [x^k] (1+x) * A_n(x)^2, where A_n(x) is the n-th Eulerian polynomial.

Original entry on oeis.org

1, 1, 1, 1, 1, 3, 3, 1, 1, 9, 26, 26, 9, 1, 1, 23, 165, 387, 387, 165, 23, 1, 1, 53, 860, 4292, 9194, 9194, 4292, 860, 53, 1, 1, 115, 3967, 38885, 160778, 314654, 314654, 160778, 38885, 3967, 115, 1, 1, 241, 17022, 307454, 2291375, 8041695, 14743812, 14743812, 8041695, 2291375, 307454, 17022, 241, 1

Offset: 0

Seiichi Manyama, Mar 19 2025

			Irregular triangle begins:
  1,  1;
  1,  1;
  1,  3,   3,    1;
  1,  9,  26,   26,    9,    1;
  1, 23, 165,  387,  387,  165,   23,   1;
  1, 53, 860, 4292, 9194, 9194, 4292, 860, 53, 1;
  ...

Ryuichi Sakamoto, The h*-polynomial of the cut polytope of K_{2,m} in the lattice spanned by its vertices, arXiv:1904.10667 [math.CO], 2019.
Ryuichi Sakamoto, The h*-polynomial of the cut polytope of K_{2,m} in the lattice spanned by its vertices, Journal of Integer Sequences, Vol. 23, 2020, #20.7.5.
OEIS Wiki, Eulerian polynomials.

Row sums give A048617.

Cf. A125300, A165889, A173018.

a(n) = sum(k=0, n, k!*stirling(n, k, 2)*(x-1)^(n-k));
T(n, k) = polcoef((1+x)*a(n)^2, k);
for(n=0, 7, for(k=0, 2*(n+0^n)-1, print1(T(n, k), ", ")));

T(n,k) = T(n,2*n-1-k) for n > 0.

cp's OEIS Frontend

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

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Maple

Mathematica

Formula

A092186 a(n) = 2(m!)^2 for n = 2m and m!(m+1)! for n = 2m+1.

Views

Author

Keywords

Comments

References

Links

Crossrefs

Programs

Maple

Mathematica

A382232 Irregular triangle read by rows: T(n,k) = [x^k] (1+x) * A_n(x)^2, where A_n(x) is the n-th Eulerian polynomial.

Views

Author

Keywords

Examples

Links

Crossrefs

Programs

PARI

Formula