A186754 -id:A186754 - cp's OEIS frontend

A186755 Number of permutations of {1,2,...,n} having no increasing cycles. 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)

1, 0, 0, 1, 5, 23, 129, 894, 7202, 65085, 651263, 7161713, 85922825, 1116946192, 15637356864, 234562319757, 3753007054781, 63801128569995, 1148420035784849, 21819978138955622, 436399552962252082, 9164390639379582121, 201616594791853840063

Offset: 0

Emeric Deutsch, Feb 26 2011

nonn

a(n) = A186754(n,0).

			a(4)=5 because we have (1432), (1342), (1423), (1243), and (1324).
a(5)=23 counts all cyclic permutations of {1,2,3,4,5}, except (12345).

Alois P. Heinz, Table of n, a(n) for n = 0..450

Cf. A186754, A186756, A186757, A186758, A186759, A186760.

g := exp(1-exp(z))/(1-z): gser := series(g, z = 0, 25): seq(factorial(n)*coeff(gser, z, n), n = 0 .. 22);
# second Maple program:
a:= proc(n) option remember; `if`(n=0, 1, add(
      a(n-j)*binomial(n-1, j-1)*((j-1)!-1), j=1..n))
    end:
seq(a(n), n=0..25);  # Alois P. Heinz, Apr 13 2017

With[{nn=30},CoefficientList[Series[Exp[1-Exp[x]]/(1-x),{x,0,nn}],x] Range[0,nn]!] (* Harvey P. Dale, May 23 2016 *)

E.g.f.: exp(1-exp(z))/(1-z).

a(n) ~ n! * exp(1-exp(1)) = 0.179374... * n!. - Vaclav Kotesovec, Mar 17 2014

A186758 Number of permutations of {1,2,...,n} with no increasing cycles of length >=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)

Original entry on oeis.org

1, 1, 1, 2, 10, 59, 363, 2491, 19661, 176536, 1767540, 19460671, 233578585, 3036411429, 42507793209, 637606959466, 10201702712738, 173429224591607, 3121728583605435, 59312852905363623, 1186257030934984061, 24911396924131631880, 548050726738352726108

Offset: 0

Emeric Deutsch, Feb 26 2011

nonn

a(n) = A186757(n,0).

			a(3)=2 because we have (1)(2)(3) and (132).
a(4)=10 because we have (1)(2)(34), (1)(243), (132)(4), (142)(3), (143)(2), and the 5 cyclic permutations of {1,2,3,4} different from (1234).

Alois P. Heinz, Table of n, a(n) for n = 0..450

Cf. A186754, A186755, A186756, A186757, A186759, A186760.

g := exp(1+z-exp(z))/(1-z): gser := series(g, z = 0, 25): seq(factorial(n)*coeff(gser, z, n), n = 0 .. 22);
# second Maple program:
a:= proc(n) option remember; `if`(n=0, 1, add(a(n-j)*
      binomial(n-1, j-1)*((j-1)!-`if`(j=1, 0, 1)), j=1..n))
    end:
seq(a(n), n=0..25);  # Alois P. Heinz, Apr 13 2017

CoefficientList[Series[E^(1+x-E^x)/(1-x), {x, 0, 20}], x]* Range[0, 20]! (* Vaclav Kotesovec, Oct 05 2013 *)

E.g.f.: exp(1+z-exp(z))/(1-z).
a(n) ~ n! * exp(2-exp(1)). - Vaclav Kotesovec, Oct 05 2013
a(n) = Sum_{k=0..1} A186754(n,k). - Alois P. Heinz, Dec 02 2021

A186756 Triangle read by rows: T(n,k) is the number of permutations of {1,2,...,n} having k nonincreasing cycles (0<=k<=floor(n/3)). 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) < ... .

Original entry on oeis.org

1, 1, 2, 5, 1, 15, 9, 52, 68, 203, 507, 10, 877, 3918, 245, 4140, 32057, 4123, 21147, 280700, 60753, 280, 115975, 2645611, 853914, 13300, 678570, 26917867, 11923428, 396935, 4213597, 295934526, 169127222, 9710855, 15400, 27644437, 3513447546, 2469452843, 215274774, 1201200

Offset: 0

Emeric Deutsch, Feb 26 2011

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

			T(3,0) = 5 because we have (1)(2)(3), (1)(23), (12)(3), (13)(2), and (123).
T(3,1) = 1 because we have (132).
T(4,1) = 9 because we have (1)(243), (1432), (142)(3), (132)(4), (1342), (1423), (1243), (143)(2), and (1324).
Triangle starts:
    1;
    1;
    2;
    5,   1;
   15,   9;
   52,  68;
  203, 507, 10;

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

Cf. A000110, A121633, A186754, A186755, A186757, A186758, A186759, A186760.

G := exp((1-t)*(exp(z)-1))/(1-z)^t: Gser := simplify(series(G, z = 0, 16)): for n from 0 to 13 do P[n] := sort(expand(factorial(n)*coeff(Gser, z, n))) end do: for n from 0 to 13 do seq(coeff(P[n], t, j), j = 0 .. floor((1/3)*n)) end do; # yields sequence in triangular form
# second Maple program:
b:= proc(n) option remember; expand(`if`(n=0, 1, add(
      (1+x*(i!-1))*b(n-i-1)*binomial(n-1, i), i=0..n-1)))
    end:
T:= n-> (p-> seq(coeff(p, x, i), i=0..degree(p)))(b(n)):
seq(T(n), n=0..15);  # Alois P. Heinz, Sep 26 2016

b[n_] := b[n] = Expand[If[n==0, 1, Sum[(1+x*(i!-1))*b[n-i-1]*Binomial[n-1, i], {i, 0, n-1}]]]; T[n_] := Function [p, Table[Coefficient[p, x, i], {i, 0, Exponent[p, x]}]][b[n]]; Table[T[n], {n, 0, 15}] // Flatten (* Jean-François Alcover, Nov 28 2016 after Alois P. Heinz *)

E.g.f.: G(t,z) = exp((1-t)*(exp(z)-1))/(1-z)^t.
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(u*z+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,1,t,z).
Sum_{k=0..n} T(n,k) = n!.
T(n,0) = A000110(n) (the Bell numbers).
Sum_{k=0..n} k*T(n,k) = A121633(n).

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

Original entry on oeis.org

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

Offset: 0

Emeric Deutsch, Feb 26 2011

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

			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;

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

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

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

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

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

A186759 Triangle read by rows: T(n,k) is the number of permutations of {1,2,...,n} having k cycles that are either nonincreasing or of length 1 (0<=k<=n). 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) < ... .

Original entry on oeis.org

1, 0, 1, 1, 0, 1, 1, 4, 0, 1, 4, 9, 10, 0, 1, 11, 53, 35, 20, 0, 1, 41, 280, 268, 95, 35, 0, 1, 162, 1804, 1904, 903, 210, 56, 0, 1, 715, 12971, 15727, 8008, 2408, 406, 84, 0, 1, 3425, 104600, 142533, 80323, 25662, 5502, 714, 120, 0, 1, 17722, 936370, 1418444, 871575, 303385, 68712, 11256, 1170, 165, 0, 1

Offset: 0

Emeric Deutsch, Feb 26 2011

			T(3,1) = 4 because we have (1)(23), (12)(3), (13)(2), and (132).
T(4,4) = 1 because we have (1)(2)(3)(4).
Triangle starts:
   1;
   0,  1;
   1,  0,  1;
   1,  4,  0,  1;
   4,  9, 10,  0, 1;
  11, 53, 35, 20, 0, 1;

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

Cf. A000296, A186754, A186755, A186756, A186757, A186758, A186760.

G := exp((1-t)*(exp(z)-1-z))/(1-z)^t: Gser := simplify(series(G, z = 0, 13)): for n from 0 to 10 do P[n] := sort(expand(factorial(n)*coeff(Gser, z, n))) end do: for n from 0 to 10 do seq(coeff(P[n], t, j), j = 0 .. n) end do; # yields sequence in triangular form
# second Maple program:
b:= proc(n) option remember; expand(
      `if`(n=0, 1, add(b(n-i)*binomial(n-1, i-1)*
      `if`(i=1, x, 1+x*((i-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..10);  # Alois P. Heinz, Sep 25 2016

b[n_] := b[n] = Expand[If[n == 0, 1, Sum[b[n-i]*Binomial[n-1, i-1]*If[i == 1, x, 1+x*((i-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, 10}] // Flatten (* Jean-François Alcover, Nov 28 2016 after Alois P. Heinz *)

E.g.f.: G(t,z) = exp((1-t)*(exp(z)-1-z))/(1-z)^t.
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(u*z+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(t,1,t,z).
Sum_{k=0..n} T(n,k) = n!.
T(n,0) = A000296(n).
Sum_{k=0..n} k*T(n,k) = A186760(n).

A186760 Number of cycles that are either nonincreasing or of length 1 in all permutations of {1,2,...,n}. 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)

Original entry on oeis.org

0, 1, 2, 7, 33, 188, 1247, 9448, 80623, 765926, 8022139, 91872328, 1142384735, 15330003154, 220847064955, 3399884265524, 55705822616383, 967921774366510, 17778279366693179, 344189681672898400, 7005438733866799999, 149547115419379439978, 3341127481398057119515

Offset: 0

Emeric Deutsch, Feb 26 2011

nonn

a(n) = Sum(A186759(n,k), k=0..n).

			a(3) = 7 because in (1)(2)(3), (1)(23), (12)(3), (13)(2), (123), and (132) we have a total of 3 + 1 + 1 + 1 + 0 + 1 = 7 cycles that are either of length 1 or nonincreasing.

Alois P. Heinz, Table of n, a(n) for n = 0..300

Cf. A186754, A186755, A186756, A186757, A186758, A186759.

g := (1+z-exp(z)-ln(1-z))/(1-z): gser := series(g, z = 0, 25): seq(factorial(n)*coeff(gser, z, n), n = 0 .. 22);

CoefficientList[Series[(1+x-E^x-Log[1-x])/(1-x), {x, 0, 20}], x]* Range[0, 20]! (* Vaclav Kotesovec, Oct 08 2013 *)

E.g.f.: (1+z-exp(z)-log(1-z))/(1-z).
a(n) ~ n! * (log(n) + gamma + 2 - exp(1)), where gamma is the Euler-Mascheroni constant (A001620). - Vaclav Kotesovec, Oct 08 2013
D-finite with recurrence a(n) +(-2*n-1)*a(n-1) +(n^2+2*n-4)*a(n-2) +(-2*n^2+6*n-3)*a(n-3) +((n-3)^2)*a(n-4)=0. - R. J. Mathar, Jul 26 2022

A349788 Number of permutations of [n] having exactly one increasing cycle.

Original entry on oeis.org

0, 1, 1, 1, 5, 36, 234, 1597, 12459, 111451, 1116277, 12298958, 147655760, 1919465237, 26870436345, 403044639709, 6448695657957, 109628096021612, 1973308547820586, 37492874766408001, 749857477972731979, 15747006284752049759, 346434131946498886045

Offset: 0

Alois P. Heinz, Nov 30 2021

nonn

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

Exponential convolution of A000587 with A002627.

			a(4) = 5: (1)(243), (143)(2), (142)(3), (132)(4), (1234).

Alois P. Heinz, Table of n, a(n) for n = 0..450
Wikipedia, Permutation

Column k=1 of A186754.

Cf. A000587, A002627, A131719, A186755, A186758.

b:= proc(n) option remember; series(`if`(n=0, 1, add((x+
     (j-1)!-1)*binomial(n-1, j-1)*b(n-j), j=1..n)), x, 2)
    end:
a:= n-> coeff(b(n), x, 1):
seq(a(n), n=0..23);

b[n_] := b[n] = Series[If[n == 0, 1, Sum[(x+
     (j-1)!-1)*Binomial[n-1, j-1]*b[n-j], {j, 1, n}]], {x, 0, 2}];
a[n_] := Coefficient[b[n], x, 1];
Table[a[n], {n, 0, 23}] (* Jean-François Alcover, Apr 15 2022, after Alois P. Heinz *)

E.g.f.: exp(1-exp(x))*(exp(x)-1)/(1-x).
a(n) = A186758(n) - A186755(n).
a(n) = Sum_{j=0..n} binomial(n,j)*A000587(j)*A002627(n-j).
a(n) mod 2 = A131719(n).
a(n) ~ (exp(1) - 1) * exp(1 - exp(1)) * n!. - Vaclav Kotesovec, Dec 05 2021

cp's OEIS Frontend

A186755 Number of permutations of {1,2,...,n} having no increasing cycles. 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)

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Maple

Mathematica

Formula

A186758 Number of permutations of {1,2,...,n} with no increasing cycles of length >=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)

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Maple

Mathematica

Formula

A186756 Triangle read by rows: T(n,k) is the number of permutations of {1,2,...,n} having k nonincreasing cycles (0<=k<=floor(n/3)). 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) < ... .

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Maple

Mathematica

Formula

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

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Maple

Mathematica

Formula

Views

Author

Keywords

Examples

Links

Crossrefs

Programs

Maple

Mathematica

Formula

A186760 Number of cycles that are either nonincreasing or of length 1 in all permutations of {1,2,...,n}. 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)

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Maple

Mathematica

Formula

A349788 Number of permutations of [n] having exactly one increasing cycle.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs