A246118 -id:A246118 - cp's OEIS frontend

A007476 Shifts 2 places left under binomial transform.

1, 1, 1, 2, 4, 9, 23, 65, 199, 654, 2296, 8569, 33825, 140581, 612933, 2795182, 13298464, 65852873, 338694479, 1805812309, 9963840219, 56807228074, 334192384460, 2026044619017, 12642938684817, 81118550133657, 534598577947465, 3615474317688778, 25070063421597484

Offset: 0

N. J. A. Sloane

Starting (1, 2, 4, 9, 23, ...) = row sums of triangle A153859. - Gary W. Adamson, Jan 02 2009
Binomial transform of the sequence starting (1, 1, 2, 4, 9, ...) = first differences of (1, 2, 4, 9, 23, ...); that is, (1, 2, 5, 14, 42, 134, 455, 1642, ...). - Gary W. Adamson, May 20 2013
Row sums of triangle A256161. - Margaret A. Readdy, Mar 16 2015
RG-words corresponding to set partitions of {1, ..., n} with every even entry appearing exactly once. - Margaret A. Readdy, Mar 16 2015
a(n) is the number of partitions of [n] whose blocks can be written such that the smallest elements form an increasing sequence and the largest elements form a decreasing sequence. a(5) = 9: 12345, 1235|4, 1245|3, 125|34, 1345|2, 135|24, 145|23, 15|234, 15|24|3. - Alois P. Heinz, Apr 24 2023

N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).

Alois P. Heinz, Table of n, a(n) for n = 0..650 (first 101 terms from T. D. Noe)
M. Bernstein and N. J. A. Sloane, Some canonical sequences of integers, arXiv:math/0205301 [math.CO], 2002; Linear Alg. Applications, 226-228 (1995), 57-72; erratum 320 (2000), 210.
M. Bernstein and N. J. A. Sloane, Some canonical sequences of integers, Linear Alg. Applications, 226-228 (1995), 57-72; erratum 320 (2000), 210. [Link to Lin. Alg. Applic. version together with omitted figures]
Yue Cai and Margaret Readdy, Negative q-Stirling numbers, arXiv:1506.03249 [math.CO], 2015.
A. Claesson and T. Mansour, Permutations avoiding a pair of Babson-Steingrimsson patterns, arXiv:math/0107044 [math.CO], 2001-2010.
Rigoberto Flórez, José L. Ramírez, Fabio A. Velandia, and Diego Villamizar, Some Connections Between Restricted Dyck Paths, Polyominoes, and Non-Crossing Partitions, arXiv:2308.02059 [math.CO], 2023. See Table 1 p. 13.
N. J. A. Sloane, Transforms
L. Sze, OEIS conjecture 70

Cf. A000994, A000995, A092920, A153859.

Row sums of A246118.

a:= proc(n) option remember; `if`(n<2, 1,
      add(a(j)*binomial(n-2, j), j=0..n-2))
    end:
seq(a(n), n=0..31);  # Alois P. Heinz, Jul 29 2019

a[0] = a[1] = 1; a[n_] := a[n] = Sum[Binomial[n-2, k] a[k], {k, 0, n-2}]; Table[a[n], {n, 0, 24}] (* Jean-François Alcover, Aug 08 2012, after Ralf Stephan *)

a(n)=if(n<2, 1, sum(k=0, n-2, binomial(n-2, k)*a(k))) /* Ralf Stephan; corrected by Manuel Blum, May 22 2010 */

G.f.: Sum_{k>=0} x^(2k)/(Product_{m=0..k-1} (1-mx) * Product_{m=0..k+1} (1-mx)).
G.f. A(x) satisfies A(x) = 1 + x + (x^2/(1-x))*A(x/(1-x)). - Vladimir Kruchinin, Nov 28 2011
a(n) = A000994(n) + A000995(n). - Peter Bala, Jan 27 2015

Spelling correction by Jason G. Wurtzel, Aug 22 2010

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

Original entry on oeis.org

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

A256161 Triangle of allowable Stirling numbers of the second kind a(n,k).

Original entry on oeis.org

1, 1, 1, 1, 2, 1, 1, 3, 4, 1, 1, 4, 11, 6, 1, 1, 5, 26, 23, 9, 1, 1, 6, 57, 72, 50, 12, 1, 1, 7, 120, 201, 222, 86, 16, 1, 1, 8, 247, 522, 867, 480, 150, 20, 1, 1, 9, 502, 1291, 3123, 2307, 1080, 230, 25, 1, 1, 10, 1013, 3084, 10660, 10044, 6627, 2000, 355, 30, 1

Offset: 1

Margaret A. Readdy, Mar 16 2015

Row sums = A007476 starting (1, 2, 4, 9, 23, 65, 199, 654, 2296, 8569, ...).

a(n,k) counts restricted growth words of length n in the letters {1, ..., k} where every even entry appears exactly once.

			a(4,1) = 1 via 1111;
a(4,2) = 3 via 1211, 1121, 1112;
a(4,3) = 4 via 1213, 1231, 1233, 1123;
a(4,4) = 1 via 1234.
Triangle starts:
  1;
  1,  1;
  1,  2,  1;
  1,  3,  4,  1;
  1,  4, 11,  6,  1;
  ...

Yue Cai and Margaret Readdy, Negative q-Stirling numbers, arXiv:1506.03249 [math.CO], 2015.

Cf. A007476 (row sums), A246118 (essentially the same triangle).

a[, 1] = a[n, n_] = 1;
a[n_, k_] := a[n, k] = a[n-1, k-1] + Ceiling[k/2] a[n-1, k];
Table[a[n, k], {n, 1, 10}, {k, 1, n}] // Flatten (* Jean-François Alcover, Dec 15 2018 *)

a(n,k) = a(n-1,k-1) + ceiling(k/2)*a(n-1,k) for n >= 1 and 1 <= k <= n with boundary conditions a(n,0) = KroneckerDelta[n,0].
a(n,2) = n-1.
a(n,n-1) = floor(n/2)*ceiling(n/2).

cp's OEIS Frontend

A007476 Shifts 2 places left under binomial transform.

Views

Author

Keywords

Comments

References

Links

Crossrefs

Programs

Maple

Mathematica

PARI

Formula

Extensions

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

A256161 Triangle of allowable Stirling numbers of the second kind a(n,k).

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

Formula