login
The OEIS Foundation is supported by donations from users of the OEIS and by a grant from the Simons Foundation.

 

Logo


Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
A186366 Triangle read by rows: T(n,k) is the number of cycle-up-down permutations of {1,2,...,n} having k cycles (1<=k<=n). 8
1, 1, 1, 1, 3, 1, 2, 7, 6, 1, 5, 20, 25, 10, 1, 16, 70, 105, 65, 15, 1, 61, 287, 490, 385, 140, 21, 1, 272, 1356, 2548, 2345, 1120, 266, 28, 1, 1385, 7248, 14698, 15204, 8715, 2772, 462, 36, 1, 7936, 43280, 93420, 105880, 69405, 26985, 6090, 750, 45, 1, 50521, 285571, 649715, 793210, 577225, 260337, 72765, 12210, 1155, 55, 1 (list; table; graph; refs; listen; history; text; internal format)
OFFSET

1,5

COMMENTS

A permutation is said to be cycle-up-down if it is a product of up-down cycles. A cycle (b(1), b(2), ...) is said to be up-down if, when written with its smallest element in the first position, it satisfies b(1) < b(2) > b(3) < ... .

Sum of entries in row n is A000111(n+1) (the Euler or up-down numbers).

The row generating polynomial of row n is c_n(t) from the Johnson reference (p. 127).

T(n,1) = A000111(n-1).

Sum_{k=1..n} k*T(n,k) = A186367(n).

With a different offset, appears to be the same as the table of sub-permutations of a class of Andre permutations given by Disanto. - Peter Bala, Feb 11 2012. That is, this triangle appears to be identical to the triangle giving the number of binary increasing trees with n nodes and a "min-path" of length k. - N. J. A. Sloane, May 12 2012

The Bell transform of A000111. For the definition of the Bell transform see A264428. - Peter Luschny, Jan 18 2016

An apparent signed version is presented on p. 6 of the Csikvari preprint, related to graph polynomials of the complete graphs K_n. - Tom Copeland, Jan 17 2017

The trivariate e.g.f. below may be expressed as H = [e^(-z) e^(xz) / (1-sin (z))]^t = [e^(z*(p.(x)-1))]^t = [e^(z*(p.(x-1)))]^t, where (p.(x))^n = p_n(x) are a sequence of Appell polynomials. For t=m, an integer, the formalism of A248120 related to the Hirzebruch criterion for convolutions applies and that of the Scott and Sokal preprint (see eqn. 3.1 on p. 10 and eqn. 3.62 on p. 24). - Tom Copeland, Jan 17 2017

LINKS

Alois P. Heinz, Rows n = 1..141, flattened

P. Csikvari, Co-adjoint polynomial, arXiv:1603.0259 [math.CO], 2016.

Emeric Deutsch and Sergi Elizalde, Cycle up-down permutations, arXiv:0909.5199 [math.CO], 2009; and also, Australas. J. Combin. 50 (2011), 187-199.

F. Disanto, André permutations, right-to-left and left-to-right minima, arXiv:1202.1139 [math.CO], 2012-2014; and also, Séminaire Lotharingien de Combinatoire, B70f (2014), 13 pp.

W. P. Johnson, Some polynomials associated with up-down permutations, Discrete Math., 210 (2000), 117-136.

D. E. Knuth, Convolution polynomials, Mathematica J. 2.1 (1992), no. 4, 67-78.

A. Scott and A. Sokal, Some variants of the exponential formula, with application to the multivariate Tutte polynomial (alias Potts model), arXiv:0803.1477 [math.CO], 2009.

FORMULA

E.g.f.: 1/(1-sin(z))^t.

The trivariate e.g.f. H(t,s,z) of the cycle-up-down permutations of {1,2,...,n} with respect to size (marked by z), number of cycles (marked by t), and number of fixed points (marked by x) is given by H(t,x,z)=exp((x-1)tz)/(1-sin z)^t.

T(n,m) = 2*sum(j=floor((n+m)/2)..n, (stirling1(2*j-n,m)*(-1)^(m-n)*sum(i=0..(2*j-n)/2, (2*i-2*j+n)^n*binomial(2*j-n,i)*(-1)^(j-i)))/(2^(2*j-n)*(2*j-n)!)). - Vladimir Kruchinin, Mar 26 2013

EXAMPLE

T(3,2)=3 because we have (1)(23), (12)(3), and (13)(2).

T(4,3)=6 because we have (1)(2)(34), (1)(23)(4), (1)(24)(3), (12)(3)(4), (13)(2)(4), and (14)(2)(3).

Triangle starts:

     1;

     1,    1;

     1,    3,     1;

     2,    7,     6,     1;

     5,   20,    25,    10,    1;

    16,   70,   105,    65,   15,    1;

    61,  287,   490,   385,  140,   21,   1;

   272, 1356,  2548,  2345, 1120,  266,  28,  1;

  1385, 7248, 14698, 15204, 8715, 2772, 462, 36, 1;

  ...

MAPLE

G := 1/(1-sin(z))^t: Gser := simplify(series(G, z = 0, 16)): for n to 11 do P[n] := sort(expand(factorial(n)*coeff(Gser, z, n))) end do: for n from 0 to 11 do seq(coeff(P[n], t, j), j = 1 .. n) end do; # yields sequence in triangular form

# second Maple program:

b:= proc(u, o) option remember; `if`(u+o=0, 1,

      add(b(o-1+j, u-j), j=1..u))

    end:

g:= proc(n) option remember; expand(`if`(n=0, 1,

      add(g(n-j)*binomial(n-1, j-1)*x*b(j-1, 0), j=1..n)))

    end:

T:= n-> (p-> seq(coeff(p, x, i), i=1..n))(g(n)):

seq(T(n), n=1..12);  # Alois P. Heinz, May 21 2021

MATHEMATICA

rows = 12;

a111[n_] := If[EvenQ[n], Abs[EulerE[n]], Abs[(2^(n+1)*(2^(n+1) - 1)* BernoulliB[n+1])/(n+1)]];

BellMatrix[f_, len_] := With[{t = Array[f, len, 0]}, Table[BellY[n, k, t], {n, 0, len-1}, {k, 0, len-1}]];

B = BellMatrix[a111, rows];

Table[B[[n, k]], {n, 2, rows}, {k, 2, n}] // Flatten (* Jean-François Alcover, Jul 23 2018, after Peter Luschny *)

PROG

(Maxima)

T(n, m):=2*sum((stirling1(2*j-n, m)*(-1)^(m-n)*sum((2*i-2*j+n)^n*binomial(2*j-n, i)*(-1)^(j-i), i, 0, (2*j-n)/2))/(2^(2*j-n)*(2*j-n)!), j, floor((n+m)/2), n); /* Vladimir Kruchinin, Mar 26 2013 */

(Sage) # uses[bell_matrix from A264428]

# Adds a column 1, 0, 0, 0, ... at the left side of the triangle.

bell_matrix(lambda n: A000111(n), 10) # Peter Luschny, Jan 18 2016

CROSSREFS

Cf. A186367. Diagonals: A000111, A211602, A212258, A212259.

Cf. A248120.

T(2n,n) gives A344445.

T(n^2,n) gives A344532.

Sequence in context: A266055 A074305 A151855 * A135338 A084602 A297858

Adjacent sequences:  A186363 A186364 A186365 * A186367 A186368 A186369

KEYWORD

nonn,tabl

AUTHOR

Emeric Deutsch, Feb 28 2011

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
The OEIS Community | Maintained by The OEIS Foundation Inc.

License Agreements, Terms of Use, Privacy Policy. .

Last modified October 20 03:04 EDT 2021. Contains 348099 sequences. (Running on oeis4.)