A028417 -id:A028417 - cp's OEIS frontend

A180191 Number of permutations of [n] having at least one succession. A succession of a permutation p is a position i such that p(i+1)-p(i) = 1.

0, 1, 3, 13, 67, 411, 2921, 23633, 214551, 2160343, 23897269, 288102189, 3760013027, 52816397219, 794536751217, 12744659120521, 217140271564591, 3916221952414383, 74539067188152941, 1493136645424092773, 31400620285465593339, 691708660911435955579

Offset: 1

Emeric Deutsch, Sep 07 2010

nonn

a(n) = A180190(n,1).
a(n+2) = p(n+2) where p(x) is the unique degree-n polynomial such that p(k) = k! for k = 1, ..., n+1. - Michael Somos, Jan 05 2012
From Jon Perry, Jan 04 2013: (Start)
Number of permutations of {1,...,n-1,n+1} with at least one indexed point p(k)=k with 1<=k<=n. Note that this means p(k)=n+1 is never an indexed point as kFor n>1, a(n) is the number of permutations of [n+1] that have a fixed point and contain 12; for example the a(3)=3 such permutations of {1,2,3,4} are 1234, 1243, and 3124.
(End)
For n > 0: row sums of triangle A116853. - Reinhard Zumkeller, Aug 31 2014

			x^2 + 3*x^3 + 13*x^4 + 67*x^5 + 411*x^6 + 2921*x^7 + 23633*x^8 + ...
a(3) = 3 because we have 123, 312, and 231; the permutations 132, 213, and 321 have no successions.
a(4) = 13 since p(x) = (3*x^2 - 7*x + 6) / 2 interpolates p(1) = 1, p(2) = 2, p(3) = 6, and p(4) = 13. - _Michael Somos_, Jan 05 2012

Alois P. Heinz, Table of n, a(n) for n = 1..200
Uriel Feige, Tighter bounds for online bipartite matching, 2018.

Cf. A000142, A000166, A000255, A002467, A028417, A180190.
Cf. A116853, A276975.
Column k=1 of A306234, A306461, and of A324362(n-1).

a180191 n = if n == 1 then 0 else sum $ a116853_row (n - 1)
-- Reinhard Zumkeller, Aug 31 2014

d[0] := 1: for n to 50 do d[n] := n*d[n-1]+(-1)^n end do: seq(factorial(n)-d[n]-d[n-1], n = 1 .. 22);

f[n_] := Sum[ -(-1)^k (n - k)! Binomial[n - 1, k], {k, 1, n}]; Array[f, 20] (* Robert G. Wilson v, Oct 16 2010 *)

{a(n) = if( n<2, 0, n--; subst( polinterpolate( vector( n, k, k!)), x, n+1))} /* Michael Somos, Jan 05 2012 */

a(n) = n! - d(n) - d(n-1), where d(j) = A000166(j) are the derangement numbers.
a(n) = n! - A000255(n-1) = A002467(n) - A000166(n-1). - Jon Perry, Jan 05 2013
a(n) = (n-1)! [x^(n-1)] (1-exp(-x))/(1-x)^2. - Alois P. Heinz, Feb 23 2019

A322383 Number T(n,k) of entries in the k-th cycles of all permutations of [n] when cycles are ordered by increasing lengths (and increasing smallest elements); triangle T(n,k), n>=1, 1<=k<=n, read by rows.

Original entry on oeis.org

1, 3, 1, 10, 7, 1, 45, 37, 13, 1, 236, 241, 101, 21, 1, 1505, 1661, 896, 226, 31, 1, 10914, 13301, 7967, 2612, 442, 43, 1, 90601, 117209, 78205, 29261, 6441, 785, 57, 1, 837304, 1150297, 827521, 346453, 88909, 14065, 1297, 73, 1, 8610129, 12314329, 9507454, 4338214, 1253104, 234646, 28006, 2026, 91, 1

Offset: 1

Alois P. Heinz, Dec 05 2018

			The 6 permutations of {1,2,3} are:
  (1)     (2)   (3)
  (1)     (2,3)
  (2)     (1,3)
  (3)     (1,2)
  (1,2,3)
  (1,3,2)
so there are 10 elements in the first cycles, 7 in the second cycles and only 1 in the third cycles.
Triangle T(n,k) begins:
      1;
      3,      1;
     10,      7,     1;
     45,     37,    13,     1;
    236,    241,   101,    21,    1;
   1505,   1661,   896,   226,   31,   1;
  10914,  13301,  7967,  2612,  442,  43,  1;
  90601, 117209, 78205, 29261, 6441, 785, 57, 1;
  ...

Alois P. Heinz, Rows n = 1..141, flattened
Andrew V. Sills, Integer Partitions Probability Distributions, arXiv:1912.05306 [math.CO], 2019.
Wikipedia, Permutation

Columns k=1-10 give: A028417, A332906, A332907, A332908, A332909, A332910, A332911, A332912, A332913, A332914.
Row sums give A001563.
Cf. A185105, A322384.

b:= proc(n, l) option remember; `if`(n=0, add(l[i]*
      x^i, i=1..nops(l)), add(binomial(n-1, j-1)*
      b(n-j, sort([l[], j]))*(j-1)!, j=1..n))
    end:
T:= n-> (p-> (seq(coeff(p, x, i), i=1..n)))(b(n, [])):
seq(T(n), n=1..12);

b[n_, l_] := b[n, l] = If[n == 0, l.x^Range[Length[l]], Sum[Binomial[n - 1, j - 1] b[n - j, Sort[Append[l, j]]] (j - 1)!, {j, 1, n}]];
T[n_] := Rest @ CoefficientList[b[n, {}], x];
Array[T, 12] // Flatten (* Jean-François Alcover, Mar 03 2020, after Alois P. Heinz *)

A145877 Triangle read by rows: T(n,k) is the number of permutations of [n] for which the shortest cycle length is k (1<=k<=n).

Original entry on oeis.org

1, 1, 1, 4, 0, 2, 15, 3, 0, 6, 76, 20, 0, 0, 24, 455, 105, 40, 0, 0, 120, 3186, 714, 420, 0, 0, 0, 720, 25487, 5845, 2688, 1260, 0, 0, 0, 5040, 229384, 52632, 22400, 18144, 0, 0, 0, 0, 40320, 2293839, 525105, 223200, 151200, 72576, 0, 0, 0, 0, 362880, 25232230

Offset: 1

Emeric Deutsch, Oct 27 2008

Row sums are the factorials (A000142).
Sum(T(n,k), k=2..n) = A000166(n) (the derangement numbers).
T(n,1) = A002467(n).
T(n,n) = (n-1)! (A000142).
Sum(k*T(n,k),k=1..n) = A028417(n).
For the statistic "length of the longest cycle", see A126074.

			T(4,2)=3 because we have 3412=(13)(24), 2143=(12)(34) and 4321=(14)(23).
Triangle starts:
      1;
      1,    1;
      4,    0,    2;
     15,    3,    0,    6;
     76,   20,    0,    0, 24;
    455,  105,   40,    0,  0, 120;
   3186,  714,  420,    0,  0,   0, 720;
  25487, 5845, 2688, 1260,  0,   0,   0, 5040;
  ...

Alois P. Heinz, Rows n = 1..141, flattened
Steven Finch, Permute, Graph, Map, Derange, arXiv:2111.05720 [math.CO], 2021.
D. Panario and B. Richmond, Exact largest and smallest size of components, Algorithmica, 31 (2001), 413-432.

Cf. A000142, A000166, A002467, A028417, A126074.

T(2n,n) gives A110468(n-1) (for n>0). - Alois P. Heinz, Apr 21 2017

F:=proc(k) options operator, arrow: (1-exp(-x^k/k))*exp(-(sum(x^j/j, j = 1 .. k-1)))/(1-x) end proc: for k to 16 do g[k]:= series(F(k),x=0,16) end do: T:= proc(n,k) options operator, arrow: factorial(n)*coeff(g[k],x,n) end proc: for n to 11 do seq(T(n,k),k=1..n) end do; # yields sequence in triangular form

Rest[Transpose[Table[Range[0, 16]! CoefficientList[
      Series[(Exp[x^n/n] -1) (Exp[-Sum[x^k/k, {k, 1, n}]]/(1 - x)), {x, 0, 16}],x], {n, 1, 8}]]] // Grid (* Geoffrey Critzer, Mar 04 2011 *)

E.g.f. for column k is (1-exp(-x^k/k))*exp( -sum(j=1..k-1, x^j/j ) ) / (1-x). - Vladeta Jovovic

A028418 Sum over all n! permutations of n letters of maximum cycle length.

Original entry on oeis.org

1, 3, 13, 67, 411, 2911, 23563, 213543, 2149927, 23759791, 286370151, 3734929903, 52455166063, 788704078527, 12648867695311, 215433088624351, 3884791172487903, 73919882720901823, 1480542628345939807, 31128584449987511871, 685635398619169059391

Offset: 1

Joe Keane (jgk(AT)jgk.org)

nonn

Sum the n-permutations having at least 1 cycle of length >= i for all i >= 1. A000142 + A033312 + A066052 + A202364 + ... The summation is precisely that indicated in the title since each permutation whose longest cycle = i is counted i times. - Geoffrey Critzer, Jan 09 2013

S. W. Golomb, Shift-Register Sequences, Holden-Day, San Francisco, 1967, p. 183.
R. Sedgewick and P. Flajolet, Analysis of Algorithms, Addison Wesley, 1996, page 358.

Alois P. Heinz, Table of n, a(n) for n = 1..450 (first 142 terms from Thomas Dybdahl Ahle)
Ph. Flajolet and A. Odlyzko, Singularity analysis of generating functions, p. 22.

Cf. A006128, A028417, A060014, A126074.

Column k=1 of A322384.

b:= proc(n, m) option remember; `if`(n=0, m, add((j-1)!*
      b(n-j, max(m,j))*binomial(n-1, j-1), j=1..n))
    end:
a:= n-> b(n, 0):
seq(a(n), n=1..25);  # Alois P. Heinz, May 14 2016

kmax = 19; gf[x_] = Sum[ 1/(1-x) - 1/(E^((x^(1+k)*Hypergeometric2F1[1+k, 1, 2+k, x])/ (1+k))*(1-x)), {k, 0, kmax}];
a[n_] := n!*Coefficient[Series[gf[x], {x, 0, kmax}], x^n]; Array[a, kmax]
(* Jean-François Alcover, Jun 22 2011, after e.g.f. *)
a[ n_] := If[ n < 1, 0, 1 + Total @ Apply[ Max, Map[ Length, First /@ PermutationCycles /@ Drop[ Permutations @ Range @ n, 1], {2}], 1]]; (* Michael Somos, Aug 19 2018 *)

E.g.f.: Sum_{k>=0} (1/(1-x) - exp(Sum_{j=1..k} x^j/j)).
a(n) = f(n, 0, n, n!) where f(L, r, n, m) = m*r if r >= l, otherwise Sum_{k=0..L-1} (f(k, max(L-k,r), n-1, m/n) + (n-L)*f(L, r, n-1, m/n)). - Thomas Dybdahl Ahle, Aug 15 2011
a(n) = Sum_{k=1..n} k * A126074(n,k). - Alois P. Heinz, May 17 2016

More terms from Vladeta Jovovic, Sep 19 2002

More terms from Thomas Dybdahl Ahle, Aug 15 2011

A097147 Total sum of minimum block sizes in all partitions of n-set.

Original entry on oeis.org

1, 3, 7, 21, 66, 258, 1079, 4987, 25195, 136723, 789438, 4863268, 31693715, 217331845, 1564583770, 11795630861, 92833623206, 760811482322, 6479991883525, 57256139503047, 523919025038279, 4956976879724565, 48424420955966635, 487810283307069696

Offset: 1

Vladeta Jovovic, Jul 27 2004

Alois P. Heinz, Table of n, a(n) for n = 1..576

Cf. A028417, A028418, A046746, A006128, A097145, A097146, A097148.

Column k=1 of A319298.

g:= proc(n, i, p) option remember; `if`(n=0, (i+1)*p!,
      `if`(i<1, 0, add(g(n-i*j, i-1, p+j*i)/j!/i!^j, j=0..n/i)))
    end:
a:= n-> g(n$2, 0):
seq(a(n), n=1..30);  # Alois P. Heinz, Mar 06 2015

Drop[Apply[Plus,Table[nn=25;Range[0,nn]!CoefficientList[Series[Exp[Sum[ x^i/i!,{i,n,nn}]]-1,{x,0,nn}],x],{n,1,nn}]],1]  (* Geoffrey Critzer, Jan 10 2013 *)
g[n_, i_, p_] := g[n, i, p] = If[n == 0, (i+1)*p!, If[i<1, 0,
     Sum[g[n-i*j, i-1, p+j*i]/j!/i!^j, {j, 0, n/i}]]];
a[n_] := g[n, n, 0];
Array[a, 30] (* Jean-François Alcover, Aug 24 2021, after Alois P. Heinz *)

E.g.f.: Sum_{k>0} (-1+exp(Sum_{j>=k} x^j/j!)).

More terms from Max Alekseyev, Apr 29 2010

A097148 Total sum of maximum block sizes in all partitions of n-set.

Original entry on oeis.org

1, 3, 10, 35, 136, 577, 2682, 13435, 72310, 414761, 2524666, 16239115, 109976478, 781672543, 5814797281, 45155050875, 365223239372, 3070422740989, 26780417126048, 241927307839731, 2260138776632752, 21805163768404127, 216970086170175575, 2224040977932468379

Offset: 1

Vladeta Jovovic, Jul 27 2004

Let M be the infinite lower triangular matrix given by A080510 and v the column vector [1,2,3,...] then M*v=A097148 (this sequence, as column vector). - Gary W. Adamson, Feb 24 2011

Alois P. Heinz, Table of n, a(n) for n = 1..576

Cf. A028417, A028418, A046746, A006128, A097145-A097147.
Cf. A080510.
Column k=1 of A319375.

b:= proc(n, m) option remember; `if`(n=0, m, add(
      b(n-j, max(j, m))*binomial(n-1, j-1), j=1..n))
    end:
a:= n-> b(n, 0):
seq(a(n), n=1..24);  # Alois P. Heinz, Mar 02 2020, revised May 08 2024

Drop[ Range[0, 22]! CoefficientList[ Series[ Sum[E^(E^x - 1) - E^Sum[x^j/j!, {j, 1, k}], {k, 0, 22}], {x, 0, 22}], x], 1] (* Robert G. Wilson v, Aug 05 2004 *)

E.g.f.: Sum_{k>=0} (exp(exp(x)-1)-exp(Sum_{j=1..k} x^j/j!)).

More terms from Robert G. Wilson v, Aug 05 2004

A097145 Total sum of minimum list sizes in all sets of lists of n-set, cf. A000262.

Original entry on oeis.org

0, 1, 5, 25, 157, 1101, 9211, 85513, 900033, 10402633, 133059331, 1836961941, 27619253113, 444584808253, 7678546353843, 140944884572521, 2751833492404321, 56691826303303953, 1233793951629951043, 28191548364561422173, 676190806704598883241

Offset: 0

Vladeta Jovovic, Jul 27 2004

			For n=4 we have 73 sets of lists (cf. A000262): (1234) (24 ways), (123)(4) (6*4 ways), (12)(34) (3*4 ways), (12)(3)(4) (6*2 ways), (1)(2)(3)(4) (1 way); so a(n)= 24*4+24*1+12*2+12*1+1*1 = 157.

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

Cf. A000262, A028417, A028418, A046746, A006128, A097146-A097148.

b:= proc(n, m) option remember; `if`(n=0, m, add(j!*
      b(n-j, min(m, j))*binomial(n-1, j-1), j=1..n))
    end:
a:= n-> `if`(n=0, 0, b(n, infinity)):
seq(a(n), n=0..25);  # Alois P. Heinz, May 10 2016

b[n_, m_] := b[n, m] = If[n==0, m, Sum[j!*b[n-j, Min[m, j]]*Binomial[n-1, j - 1], {j, 1, n}]]; a[n_] := If[n==0, 0, b[n, Infinity]]; Table[a[n], {n, 0, 25}] (* Jean-François Alcover, Feb 18 2017, after Alois P. Heinz *)

E.g.f.: Sum_{k>0} (exp(x^k/(1-x))-1).

More terms from Max Alekseyev, Jul 04 2009

a(0)=0 prepended by Alois P. Heinz, May 10 2016

A232193 Numerators of the expected value of the length of a random cycle in a random n-permutation.

Original entry on oeis.org

1, 3, 23, 55, 1901, 4277, 198721, 16083, 14097247, 4325321, 2132509567, 4527766399, 13064406523627, 905730205, 13325653738373, 362555126427073, 14845854129333883, 57424625956493833, 333374427829017307697, 922050973293317, 236387355420350878139797

Offset: 1

Geoffrey Critzer, Nov 20 2013

In this experiment we randomly select (uniform distribution) an n-permutation and then randomly select one of the cycles from that permutation. Cf. A102928/A175441 which gives the expected cycle length when we simply randomly select a cycle.

			Expectations for n=1,... are 1/1, 3/2, 23/12, 55/24, 1901/720, 4277/1440, 198721/60480, 16083/4480, ... = A232193/A232248
For n=3 there are 6 permutations.  We have probability 1/6 of selecting (1)(2)(3) and the cycle size is 1.  We have probability 3/6 of selecting a permutation with cycle type (1)(23) and (on average) the cycle length is 3/2.  We have probability 2/6 of selecting a permutation of the form (123) and the cycle size is 3.  1/6*1 + 3/6*3/2 + 2/6*3 = 23/12.

Alois P. Heinz, Table of n, a(n) for n = 1..250

Denominators are A232248.
Cf. A028417(n)/n! the expected value of the length of the shortest cycle in a random n-permutation.
Cf. A028418(n)/n! the expected value of the length of the longest cycle in a random n-permutation.

with(combinat):
b:= proc(n, i) option remember; `if`(n=0, 1, `if`(i<1, 0,
      expand(add(multinomial(n, n-i*j, i$j)/j!*(i-1)!^j
      *b(n-i*j, i-1) *x^j, j=0..n/i))))
    end:
a:= n->numer((p->add(coeff(p, x, i)/i, i=1..n))(b(n$2))/(n-1)!):
seq(a(n), n=1..30);  # Alois P. Heinz, Nov 21 2013
# second Maple program:
a:= n-> numer(add(abs(combinat[stirling1](n, i))/i, i=1..n)/(n-1)!):
seq(a(n), n=1..30);  # Alois P. Heinz, Nov 23 2013

Table[Numerator[Total[Map[Total[#]!/Product[#[[i]],{i,1,Length[#]}]/Apply[Times,Table[Count[#,k]!,{k,1,Max[#]}]]/(Total[#]-1)!/Length[#]&,Partitions[n]]]],{n,1,25}]

a(n) = Numerator( 1/(n-1)! * Sum_{i=1..n} A132393(n,i)/i ). - Alois P. Heinz, Nov 23 2013

a(n) = numerator(Sum_{k=0..n} A002657(k)/A091137(k)) (conjectured). - Michel Marcus, Jul 19 2019

A097146 Total sum of maximum list sizes in all sets of lists of n-set, cf. A000262.

Original entry on oeis.org

0, 1, 5, 31, 217, 1781, 16501, 172915, 1998641, 25468777, 352751941, 5292123431, 85297925065, 1472161501981, 27039872306357, 527253067633531, 10865963240550241, 236088078855319505, 5390956470528548101, 129102989125943058607, 3234053809095307670201, 84596120521251178630981, 2305894874979300173268085

Offset: 0

Vladeta Jovovic, Jul 27 2004

			For n=4 we have 73 sets of lists (cf. A000262): (1234) (24 ways), (123)(4) (6*4 ways), (12)(34) (3*4 ways), (12)(3)(4) (6*2 ways), (1)(2)(3)(4) (1 way); so a(4)= 24*4+24*3+12*2+12*2+1*1 = 217.

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

Cf. A028417, A028418, A046746, A006128, A097145, A097147, A097148.

b:= proc(n, m) option remember; `if`(n=0, m, add(j!*
      b(n-j, max(m, j))*binomial(n-1, j-1), j=1..n))
    end:
a:= n-> b(n, 0):
seq(a(n), n=0..25);  # Alois P. Heinz, May 10 2016

b[n_, m_] := b[n, m] = If[n == 0, m, Sum[j! b[n-j, Max[m, j]] Binomial[n-1, j-1], {j, 1, n}]];
a[n_] := b[n, 0];
a /@ Range[0, 25] (* Jean-François Alcover, Nov 05 2020, after Alois P. Heinz *)

N=50; x='x+O('x^N);
egf=exp(x/(1-x))*sum(k=1,N, (1-exp(x^k/(x-1))) );
Vec( serlaplace(egf) ) /* show terms */

E.g.f.: exp(x/(1-x))*Sum_{k>0} (1-exp(x^k/(x-1))).

a(0)=0 prepended by Alois P. Heinz, May 10 2016

A208231 Sum of the minimum cycle length over all functions f:{1,2,...,n}->{1,2,...,n} (endofunctions).

Original entry on oeis.org

0, 1, 5, 37, 373, 4761, 73601, 1336609, 27888281, 657386305, 17276807089, 500876786301, 15879053677697, 546470462226313, 20288935994319929, 808320431258439121, 34397370632215764001, 1557106493482564625793, 74713970491718324746529, 3787792171563440619543133, 202314171910557294992453009

Offset: 0

Geoffrey Critzer, Jan 10 2013

nonn

Sum of the number of endofunctions whose cycle lengths are >=i for all i >=1. A000312 + A065440 + A134362 + A208230 + ...

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

Cf. A000169, A028417, A000312, A065440, A134362, A208230, A208248, A290932.

b:= proc(n, m) option remember; `if`(n=0, m, add((j-1)!*
      b(n-j, min(m, j))*binomial(n-1, j-1), j=1..n))
    end:
a:= n-> add(b(j$2)*n^(n-j)*binomial(n-1, j-1), j=0..n):
seq(a(n), n=0..25);  # Alois P. Heinz, May 20 2016

nn=20;t=Sum[n^(n-1)x^n/n!,{n,1,nn}];Apply[Plus,Table[Range[0,nn]!CoefficientList[Series[Exp[Sum[t^i/i,{i,n,nn}]]-1,{x,0,nn}],x],{n,1,nn}]]

E.g.f.: A(T(x)) = Sum_{k>=1} exp( Sum_{i>=k} T(x)^i/i) - 1 where A(x) is the e.g.f. for A028417 and T(x) is the e.g.f. for A000169.

Showing 1-10 of 10 results.

cp's OEIS Frontend

A180191 Number of permutations of [n] having at least one succession. A succession of a permutation p is a position i such that p(i+1)-p(i) = 1.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Haskell

Maple

Mathematica

PARI

Formula

A322383 Number T(n,k) of entries in the k-th cycles of all permutations of [n] when cycles are ordered by increasing lengths (and increasing smallest elements); triangle T(n,k), n>=1, 1<=k<=n, read by rows.

Views

Author

Keywords

Examples

Links

Crossrefs

Programs

Maple

Mathematica

A145877 Triangle read by rows: T(n,k) is the number of permutations of [n] for which the shortest cycle length is k (1<=k<=n).

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Maple

Mathematica

Formula

A028418 Sum over all n! permutations of n letters of maximum cycle length.

Views

Author

Keywords

Comments

References

Links

Crossrefs

Programs

Maple

Mathematica

Formula

Extensions

A097147 Total sum of minimum block sizes in all partitions of n-set.

Views

Author

Keywords

Links

Crossrefs

Programs

Maple

Mathematica

Formula

Extensions

A097148 Total sum of maximum block sizes in all partitions of n-set.

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Maple

Mathematica

Formula

Extensions

A097145 Total sum of minimum list sizes in all sets of lists of n-set, cf. A000262.

Views

Author

Keywords

Examples

Links

Crossrefs