cp's OEIS Frontend

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

%I A186366 #69 May 22 2021 13:42:52
%S A186366 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,
%T A186366 140,21,1,272,1356,2548,2345,1120,266,28,1,1385,7248,14698,15204,8715,
%U A186366 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
%N 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).
%C A186366 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) < ... .
%C A186366 Sum of entries in row n is A000111(n+1) (the Euler or up-down numbers).
%C A186366 The row generating polynomial of row n is c_n(t) from the Johnson reference (p. 127).
%C A186366 T(n,1) = A000111(n-1).
%C A186366 Sum_{k=1..n} k*T(n,k) = A186367(n).
%C A186366 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
%C A186366 The Bell transform of A000111. For the definition of the Bell transform see A264428. - _Peter Luschny_, Jan 18 2016
%C A186366 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
%C A186366 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
%H A186366 Alois P. Heinz, <a href="/A186366/b186366.txt">Rows n = 1..141, flattened</a>
%H A186366 P. Csikvari, <a href="http://arxiv.org/abs/1603.02594">Co-adjoint polynomial</a>, arXiv:1603.0259 [math.CO], 2016.
%H A186366 Emeric Deutsch and Sergi Elizalde, <a href="http://arxiv.org/abs/0909.5199">Cycle up-down permutations</a>, arXiv:0909.5199 [math.CO], 2009; and <a href="https://ajc.maths.uq.edu.au/pdf/50/ajc_v50_p187.pdf">also</a>, Australas. J. Combin. 50 (2011), 187-199.
%H A186366 F. Disanto, <a href="http://arxiv.org/abs/1202.1139">André permutations, right-to-left and left-to-right minima</a>, arXiv:1202.1139 [math.CO], 2012-2014; and <a href="https://www.emis.de/journals/SLC/wpapers/s70disanto.html">also</a>, Séminaire Lotharingien de Combinatoire, B70f (2014), 13 pp.
%H A186366 W. P. Johnson, <a href="http://dx.doi.org/10.1016/S0012-365X(99)00122-3">Some polynomials associated with up-down permutations</a>, Discrete Math., 210 (2000), 117-136.
%H A186366 D. E. Knuth, <a href="http://arxiv.org/abs/math/9207221">Convolution polynomials</a>, Mathematica J. 2.1 (1992), no. 4, 67-78.
%H A186366 A. Scott and A. Sokal, <a href="http://arxiv.org/abs/0803.1477">Some variants of the exponential formula, with application to the multivariate Tutte polynomial (alias Potts model)</a>, arXiv:0803.1477 [math.CO], 2009.
%F A186366 E.g.f.: 1/(1-sin(z))^t.
%F A186366 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.
%F A186366 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
%e A186366 T(3,2)=3 because we have (1)(23), (12)(3), and (13)(2).
%e A186366 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).
%e A186366 Triangle starts:
%e A186366      1;
%e A186366      1,    1;
%e A186366      1,    3,     1;
%e A186366      2,    7,     6,     1;
%e A186366      5,   20,    25,    10,    1;
%e A186366     16,   70,   105,    65,   15,    1;
%e A186366     61,  287,   490,   385,  140,   21,   1;
%e A186366    272, 1356,  2548,  2345, 1120,  266,  28,  1;
%e A186366   1385, 7248, 14698, 15204, 8715, 2772, 462, 36, 1;
%e A186366   ...
%p A186366 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
%p A186366 # second Maple program:
%p A186366 b:= proc(u, o) option remember; `if`(u+o=0, 1,
%p A186366       add(b(o-1+j, u-j), j=1..u))
%p A186366     end:
%p A186366 g:= proc(n) option remember; expand(`if`(n=0, 1,
%p A186366       add(g(n-j)*binomial(n-1, j-1)*x*b(j-1, 0), j=1..n)))
%p A186366     end:
%p A186366 T:= n-> (p-> seq(coeff(p, x, i), i=1..n))(g(n)):
%p A186366 seq(T(n), n=1..12);  # _Alois P. Heinz_, May 21 2021
%t A186366 rows = 12;
%t A186366 a111[n_] := If[EvenQ[n], Abs[EulerE[n]], Abs[(2^(n+1)*(2^(n+1) - 1)* BernoulliB[n+1])/(n+1)]];
%t A186366 BellMatrix[f_, len_] := With[{t = Array[f, len, 0]}, Table[BellY[n, k, t], {n, 0, len-1}, {k, 0, len-1}]];
%t A186366 B = BellMatrix[a111, rows];
%t A186366 Table[B[[n, k]], {n, 2, rows}, {k, 2, n}] // Flatten (* _Jean-François Alcover_, Jul 23 2018, after _Peter Luschny_ *)
%o A186366 (Maxima)
%o A186366 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 */
%o A186366 (Sage) # uses[bell_matrix from A264428]
%o A186366 # Adds a column 1,0,0,0, ... at the left side of the triangle.
%o A186366 bell_matrix(lambda n: A000111(n), 10) # _Peter Luschny_, Jan 18 2016
%Y A186366 Cf. A186367. Diagonals: A000111, A211602, A212258, A212259.
%Y A186366 Cf. A248120.
%Y A186366 T(2n,n) gives A344445.
%Y A186366 T(n^2,n) gives A344532.
%K A186366 nonn,tabl
%O A186366 1,5
%A A186366 _Emeric Deutsch_, Feb 28 2011