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!)
A186757 Triangle read by rows: T(n,k) is the number of permutations of {1,2,...,n} having k increasing cycles of length >=2 (0<=k<= n/2). A cycle (b(1), b(2), ...) is said to be increasing if, when written with its smallest element in the first position, it satisfies b(1) < b(2) < b(3) < ... . 7
1, 1, 1, 1, 2, 4, 10, 11, 3, 59, 36, 25, 363, 212, 130, 15, 2491, 1688, 651, 210, 19661, 14317, 4487, 1750, 105, 176536, 129076, 42435, 12628, 2205, 1767540, 1277159, 451626, 104755, 26775, 945, 19460671, 13974236, 5068723, 1120570, 264880, 27720 (list; graph; refs; listen; history; text; internal format)
OFFSET

0,5

COMMENTS

Row n contains 1 + floor(n/2) entries.

Sum of entries in row n is n!.

T(n,0) = A186758(n).

Sum_{k>=0}k*T(n,k) = A056542(n).

LINKS

Alois P. Heinz, Rows n = 0..200, flattened

FORMULA

E.g.f.: G(t,z) = exp((t-1)(exp(z)-1-z))/(1-z).

The 4-variate e.g.f. H(u,v,w,z) of the permutations of {1,2,...,n} with respect to size (marked by z), number of fixed points (marked by u), number of increasing cycles of length >=2 (marked by v), and number of nonincreasing cycles (marked by w) is given by H(u,v,w,z)=exp(uz+v(exp(z)-1-z)+w(1-exp(z))/(1-z)^w. Remark: the nonincreasing cycles are necessarily of length >=3. We have: G(t,z)=H(1,t,1,z).

EXAMPLE

T(3,0)=2 because we have (1)(2)(3) and (132).

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

Triangle starts:

    1;

    1;

    1,   1;

    2,   4;

   10,  11,   3;

   59,  36,  25;

  363, 212, 130, 15;

MAPLE

b:= proc(n) option remember; expand(

      `if`(n=0, 1, add(b(n-i)*binomial(n-1, i-1)*

      `if`(i>1, (x+(i-1)!-1), 1), i=1..n)))

    end:

T:= n-> (p-> seq(coeff(p, x, i), i=0..degree(p)))(b(n)):

seq(T(n), n=0..12);  # Alois P. Heinz, Mar 19 2017

MATHEMATICA

b[n_] := b[n] = Expand[If[n == 0, 1, Sum[b[n-i]*Binomial[n-1, i-1]*If[i > 1, (x + (i - 1)! - 1), 1], {i, 1, n}]]];

T[n_] := Function[p, Table[Coefficient[p, x, i], {i, 0, Exponent[p, x]}]][ b[n]];

Table[T[n], {n, 0, 12}] // Flatten (* Jean-Fran├žois Alcover, May 03 2017, after Alois P. Heinz *)

CROSSREFS

Cf. A056542, A186754, A186755, A186756, A186758, A186759, A186760.

Sequence in context: A320150 A056376 A185372 * A184876 A243622 A178713

Adjacent sequences:  A186754 A186755 A186756 * A186758 A186759 A186760

KEYWORD

nonn,tabf

AUTHOR

Emeric Deutsch, Feb 26 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 April 6 18:45 EDT 2020. Contains 333286 sequences. (Running on oeis4.)