A000255 -id:A000255 - cp's OEIS frontend

A176732 a(n) = (n+5)a(n-1) + (n-1)a(n-2), a(-1)=0, a(0)=1.

1, 6, 43, 356, 3333, 34754, 398959, 4996032, 67741129, 988344062, 15434831091, 256840738076, 4536075689293, 84731451264186, 1668866557980343, 34563571477305464, 750867999393119889, 17072113130285524982, 405423357986250112699, 10037458628015142154452, 258639509502117306002581

Offset: 0

Wolfdieter Lang, Jul 14 2010

a(n) enumerates the possibilities for distributing n beads, n>=1, labeled differently from 1 to n, over a set of (unordered) necklaces, excluding necklaces with exactly one bead, and k=6 indistinguishable, ordered, fixed cords, each allowed to have any number of beads. Beadless necklaces as well as beadless cords contribute a factor 1 in the counting, e.g., a(0):= 1*1 =1. See A000255 for the description of a fixed cord with beads. This produces for a(n) the exponential (aka binomial) convolution of the subfactorial sequence {A000166(n)} and the sequence {A001725(n+5) = (n+5)!/5!}. See the necklaces and cords problem comment in A000153. Therefore the recurrence with inputs holds. This comment derives from a family of recurrences found by Malin Sjodahl for a combinatorial problem for certain quark and gluon diagrams (Feb 27 2010).

			Necklaces and 6 cords problem. For n=4 one considers the following weak 2-part compositions of 4: (4,0), (3,1), (2,2), and (0,4), where (1,3) does not appear because there are no necklaces with 1 bead. These compositions contribute respectively !4*1,binomial(4,3)*!3*c6(1), (binomial(4,2)*2)*c6(2), and 1*c6(4) with the subfactorials !n:=A000166(n) (see the necklace comment there) and the c6(n):=A001725(n+5) numbers for the pure 6-cord problem (see the remark on the e.g.f. for the k-cord problem in A000153; here for k=6: 1/(1-x)^6). This adds up as 9 + 4*2*6 + (6*1)*42 + 3024 = 3333 = a(4).

Cf. A000153, A000261, A001909, A001910 (necklaces and k=5 cords), A176732.

a := n -> hypergeom([-n,7],[],1)*(-1)^n:
seq(simplify(a(n)),n=0..9); # Peter Luschny, Apr 25 2015

Rest[RecurrenceTable[{a[0]==1,a[-1]==0,a[n]==(n+5)a[n-1]+(n-1)a[n-2]},a,{n,20}]] (* Harvey P. Dale, Oct 01 2012 *)

E.g.f. (exp(-x)/(1-x))*(1/(1-x)^6) = exp(-x)/(1-x)^7, equivalent to the recurrence.
a(n) = A086764(n+6,6).
a(n) = A090010(n), n>0. - R. J. Mathar, Jul 22 2010
a(n) = (-1)^n*hypergeom([-n,7],[],1). - Peter Luschny, Apr 25 2015

A176733 a(n) = (n+6)a(n-1) + (n-1)a(n-2), a(-1)=0, a(0)=1.

Original entry on oeis.org

1, 7, 57, 527, 5441, 61959, 770713, 10391023, 150869313, 2346167879, 38896509881, 684702346767, 12752503850497, 250514001320647, 5176062576469401, 112204510124346479, 2546140161382663553, 60356495873790805383, 1491840283714484609593, 38382424018590349736719

Offset: 0

Wolfdieter Lang, Jul 14 2010

a(n) enumerates the possibilities for distributing n beads, n>=1, labeled differently from 1 to n, over a set of (unordered) necklaces, excluding necklaces with exactly one bead, and k=7 indistinguishable, ordered, fixed cords, each allowed to have any number of beads. Beadless necklaces as well as beadless cords contribute a factor 1 in the counting, e.g., a(0):= 1*1 =1. See A000255 for the description of a fixed cord with beads. This produces for a(n) the exponential (aka binomial) convolution of the subfactorial sequence {A000166(n)} and the sequence {A001730(n+6) = (n+6)!/6!}. See the necklaces and cords problem comment in A000153. Therefore the recurrence with inputs holds. This comment derives from a family of recurrences found by Malin Sjodahl for a combinatorial problem for certain quark and gluon diagrams (Feb 27 2010).

			Necklaces and 7 cords problem. For n=4 one considers the following weak 2-part compositions of 4: (4,0), (3,1), (2,2), and (0,4), where (1,3) does not appear because there are no necklaces with 1 bead. These compositions contribute respectively !4*1,binomial(4,3)*!3*c7(1), (binomial(4,2)*!2)*c7(2), and 1*c7(4) with the subfactorials !n:=A000166(n) (see the necklace comment there) and the c7(n):=A001730(n+6) numbers for the pure 7-cord problem (see the remark on the e.g.f. for the k-cord problem in A000153; here for k=7: 1/(1-x)^7). This adds up as 9 + 4*2*7 + (6*1)*56 + 5040 = 5441 = a(4).

Robert Israel, Table of n, a(n) for n = 0..442

Cf. A176732 (necklaces and k=6 cords).

f:= proc(n) option remember; (n+6)*procname(n-1) + (n-1)*procname(n-2) end proc:
f(-1):= 0: f(0):= 1:
map(f, [$0..30]); # Robert Israel, Dec 01 2024

Table[(-1)^n HypergeometricPFQ[{8, -n}, {}, 1], {n, 0, 20}] (* Benedict W. J. Irwin, May 29 2016 *)

E.g.f. (exp(-x)/(1-x))*(1/(1-x)^7) = exp(-x)/(1-x)^8, equivalent to the given recurrence.
a(n) = A086764(n+7,7).
a(n) = (-1)^n*2F0(8,-n;;1). - Benedict W. J. Irwin, May 29 2016

A189281 Number of permutations p of 1,2,...,n satisfying p(i+2) - p(i) <> 2 for all 1 <= i <= n-2.

Original entry on oeis.org

1, 1, 2, 5, 18, 75, 410, 2729, 20906, 181499, 1763490, 18943701, 222822578, 2847624899, 39282739034, 581701775369, 9202313110506, 154873904848803, 2762800622799362, 52071171437696453, 1033855049655584786, 21567640717569135515

Offset: 0

Vaclav Kotesovec, Apr 19 2011

nonn

a(n) is also the number of ways to place n nonattacking pieces rook + semi-leaper (2,2) on an n X n chessboard.
Comments from Vaclav Kotesovec, Mar 05 2022: (Start)
The original submission had keyword hard because of the following running times (in 2012):
a(33) 39 hours
a(34) 78 hours
a(35) 147 hours
The conjectured recurrence would imply the asymptotic expansion for a(n)/n! ~
(1 + 3/n + 2/n^2 + 1/n^3 + 0/n^4 + 3/n^5 + 26/n^6 + 101/n^7 + 124/n^8 - 1409/n^9 - 13266/n^10)/e.
This exactly matches the formula from 2011. In addition, all coefficients are integers. It is highly probable that recurrence is correct.
(End)
There are good reasons to believe the conjecture is correct. (It has the expected form.)  The problem is one of counting Hamiltonian cycles in the complement of some simple graph. There is a method for counting these efficiently (although I have not implemented in code). Similar to A242522 / A229430. - Andrew Howroyd, Mar 06 2022
See also Manuel Kauers's comments below. Since the four new terms took weeks of computation, the keyword "hard" continues to be justified. - N. J. A. Sloane, Mar 06 2022
a(40)-a(300) were computed using an independent solution (dynamic programming, O(N^4) per term), and the conjectured recurrence was further confirmed to be correct up to n=300. Consequently, the keyword "hard" is removed. - Rintaro Matsuo, Oct 18 2022

Rintaro Matsuo, Table of n, a(n) for n = 0..300 (terms 0..35 from Vaclav Kotesovec, terms 36..39 from Christoph Koutschan, computed using a parallelization of Kotesovec's Mathematica program)
Robert Dougherty-Bliss, Experimental Methods in Number Theory and Combinatorics, Ph. D. Dissertation, Rutgers Univ. (2024). See p. 4.
Manuel Kauers, Comments on the Conjectured Recurrence for A189281.
Manuel Kauers and Christoph Koutschan, Guessing with Little Data, arXiv:2202.07966 [cs.SC], 2022.
Vaclav Kotesovec, Non-attacking chess pieces, 6ed, 2013, p. 644.
Vaclav Kotesovec, Mathematica program for this sequence.
Rintaro Matsuo, O(n^4) code to calculate a(n)
George Spahn and Doron Zeilberger, Counting Permutations Where The Difference Between Entries Located r Places Apart Can never be s (For any given positive integers r and s), arXiv:2211.02550 [math.CO], 2022.

Cf. A000255, A002464, A055790, A110128.

Asymptotics: a(n)/n! ~ (1 + 3/n + 2/n^2)/e.
Conjectured recurrence of degree 11 and order 8: (262711*n + 1387742*n^2 - 824875*n^3 - 1855253*n^4 - 111530*n^5 + 680983*n^6 + 364242*n^7 + 84992*n^8 + 10332*n^9 + 640*n^10 + 16*n^11)*a(n) + (-1050844*n - 9705192*n^2 - 7414683*n^3 + 3536494*n^4 + 6459004*n^5 + 3326393*n^6 + 903534*n^7 + 144684*n^8 + 13756*n^9 + 720*n^10 + 16*n^11)*a(n+1) + (3492344 - 2212342*n - 8507169*n^2 - 11544227*n^3 - 12034116*n^4 - 8216995*n^5 - 3442049*n^6 - 890050*n^7 - 142300*n^8 - 13660*n^9 - 720*n^10 - 16*n^11)*a(n+2) + (19817984 + 45323852*n + 825228*n^2 - 57004661*n^3 - 57059306*n^4 - 28077270*n^5 - 8398637*n^6 - 1631510*n^7 - 207980*n^8 - 16828*n^9 - 784*n^10 - 16*n^11)*a(n+3) + (9586160 + 6680237*n - 13772613*n^2 - 27689586*n^3 - 22162455*n^4 - 9855085*n^5 - 2629562*n^6 - 427656*n^7 - 41332*n^8 - 2176*n^9 - 48*n^10)*a(n+4) + (22192864 + 44710768*n - 2924668*n^2 - 52385912*n^3 - 45161616*n^4 - 18784740*n^5 - 4549208*n^6 - 674256*n^7 - 60400*n^8 - 3008*n^9 - 64*n^10)*a(n+5) + (557152 - 2032472*n - 2937392*n^2 - 1594200*n^3 - 517688*n^4 - 122032*n^5 - 19856*n^6 - 1792*n^7 - 64*n^8)*a(n+6) + (3786960 + 7105324*n - 1191064*n^2 - 8059160*n^3 - 5938996*n^4 - 2073752*n^5 - 402736*n^6 - 44528*n^7 - 2624*n^8 - 64*n^9)*a(n+7) + (-598208 - 943004*n + 414196*n^2 + 1213772*n^3 + 728648*n^4 + 203584*n^5 + 29616*n^6 + 2176*n^7 + 64*n^8)*a(n+8) = 0. This recurrence correctly predicted the four new terms in the b-file. - Christoph Koutschan, Feb 19 2022
Comment from N. J. A. Sloane, Mar 12 2022: (Start)
The preceding conjectured recurrence is equivalent to the following, which has degree 3 and order 13, and was obtained by Doron Zeilberger and then reformatted by Manuel Kauers (it uses Mathematica syntax):
Conjecture: ((-1 + n)^2*n*a[n])/4 + (n*(-16 + 38*n + 11*n^2)*a[1 + n])/16 +
(3/2 + (139*n)/16 + (29*n^2)/8 + (3*n^3)/16)*a[2 + n] +
(-21/4 - (51*n)/4 - (79*n^2)/16 - (5*n^3)/8)*a[3 + n] +
(-15/2 - n/8 + (5*n^2)/4 + n^3/8)*a[4 + n] +
(603/4 + (307*n)/4 + (49*n^2)/4 + (11*n^3)/16)*a[5 + n] +
(-41 - (533*n)/16 - (49*n^2)/8 - (5*n^3)/16)*a[6 + n] +
(-911/2 - 161*n - (303*n^2)/16 - (3*n^3)/4)*a[7 + n] +
(-363 - (417*n)/4 - (37*n^2)/4 - n^3/4)*a[8 + n] +
(-993/4 - 53*n - (11*n^2)/4)*a[9 + n] + (-130 - (93*n)/4 - n^2)*a[10 + n] +
(-71/4 - 2*n)*a[11 + n] + (-10 - n)*a[12 + n] + a[13 + n] == 0.
(End)
From Mark van Hoeij, Jul 25 2012: (Start)
A compact way to write the order 13 recurrence is as follows:
Let b(n) = a(n+3) + a(n+2) + (n/2+2)*a(n+1) + (n-1)*a(n)/2
and c(n) = b(n+4) + (n/2+2)*b(n+2) - b(n+1)/2 + (1-n)*b(n)/2;
then c(n+6) - (n+11)*c(n+5) - (2*n+75/4)*c(n+4) + (3-n)*c(n+3)/4 - c(n+2)/2 - (7*n+22)*c(n+1)/4-n*c(n) = 0. (End)

A207821 Number of permutations of [n] that either have a fixed point or a succession, but not both.

Original entry on oeis.org

0, 1, 0, 5, 12, 69, 370, 2609, 20552, 183249, 1817794, 19867793, 237126320, 3068483277, 42788761294, 639619513669, 10202914060472, 172984071549421, 3106257794721534, 58892020126278457, 1175554242034515780, 24643158882899363129, 541279064964716455230, 12431122899361840993737, 297944099946417376956220, 7439329384072966947792437

Offset: 0

Jon Perry, Jan 10 2013

nonn

A succession of a permutation p is the appearance of [k,k+1], e.g. in 23541, 23 is a succession.

			a(4) = 12 because we have 1324, 1432, 2341, 2431, 3214, 3241, 3412, 3421, 4123, 4132, 4213 and 4312.

Max Alekseyev, Table of n, a(n) for n = 0..30

Cf. A000166, A002467, A180191, A201452, A207819.

A207821(n)=my(p,c);sum(k=1,n!,p=numtoperm(n,k);c=(p[1]==1);for(j=2,n,p[j]==j & c<=0 & !c++ & break; p[j]-1==p[j-1] & c>=0 & !c-- & break); c!=0) \\ M. F. Hasler, Jan 13 2013

a(n) = A209325(n) + A209326(n) = A000166(n) + A000255(n-1) - 2*A209322(n) = 2*A207819(n) - A180191(n) - A002467(n). - Max Alekseyev, Apr 03 2025

Values a(1) to a(10) double-checked by M. F. Hasler, Jan 13 2013
Inserted a(0) and a(11)-a(13) from Alois P. Heinz, Jan 18 2013
a(14)-a(20) from Alois P. Heinz, Jul 05 2021
Terms a(21) onward from Max Alekseyev, Apr 03 2025

A384891 Number of permutations of {1..n} with all distinct lengths of maximal runs (increasing by 1).

Original entry on oeis.org

1, 1, 1, 3, 3, 5, 23, 25, 43, 63, 345, 365, 665, 949, 1513, 8175, 9003, 15929, 23399, 36949, 51043, 293715, 314697, 570353, 826817, 1318201, 1810393, 2766099, 14180139, 15600413, 27707879, 40501321, 63981955, 88599903, 134362569, 181491125, 923029217

Offset: 0

Gus Wiseman, Jun 19 2025

nonn

			The permutation (1,2,6,7,8,9,3,4,5) has maximal runs ((1,2),(6,7,8,9),(3,4,5)), with lengths (2,4,3), so is counted under a(9).
The a(0) = 1 through a(7) = 25 permutations:
  ()  (1)  (12)  (123)  (1234)  (12345)  (123456)  (1234567)
                 (231)  (2341)  (23451)  (123564)  (1234675)
                 (312)  (4123)  (34512)  (123645)  (1234756)
                                (45123)  (124563)  (1245673)
                                (51234)  (126345)  (1273456)
                                         (145623)  (1456723)
                                         (156234)  (1672345)
                                         (231456)  (2314567)
                                         (234156)  (2345167)
                                         (234561)  (2345671)
                                         (312456)  (3124567)
                                         (345126)  (3456127)
                                         (345612)  (3456712)
                                         (412356)  (4567123)
                                         (451236)  (4567231)
                                         (456231)  (4567312)
                                         (456312)  (5123467)
                                         (561234)  (5612347)
                                         (562341)  (5671234)
                                         (564123)  (6712345)
                                         (612345)  (6723451)
                                         (634512)  (6751234)
                                         (645123)  (7123456)
                                                   (7345612)
                                                   (7561234)

Christian Sievers, Table of n, a(n) for n = 0..5000

Counting by number of maximal anti-runs gives A010027, for runs A123513.
For subsets instead of permutations we have A384175, complement A384176.
For partitions we have A384884 (anti-runs A384885), strict A384178 (anti-runs A384880).
For equal instead of distinct lengths we have A384892.
For anti-runs instead of runs we have A384907.
A000041 counts integer partitions, strict A000009.
A034839 counts subsets by number of maximal runs, for strict partitions A116674.
A098859 counts Wilf partitions (distinct multiplicities), complement A336866.
A356606 counts strict partitions without a neighborless part, complement A356607.
A384893 counts subsets by number of maximal anti-runs, for partitions A268193, A384905.
Cf. A000255, A044813, A072574, A242882, A287170, A325324, A325325, A328592, A329739, A351202, A384177, A384886.

Table[Length[Select[Permutations[Range[n]],UnsameQ@@Length/@Split[#,#2==#1+1&]&]],{n,0,10}]

lista(n)=my(b(n)=sum(i=0,n-1,(-1)^i*(n-i)!*binomial(n-1,i)), d=floor(sqrt(2*n)), p=prod(i=1,n,1+x*y^i,1+O(y*y^n)*((1-x^(n+1))/(1-x))+O(x*x^d))); Vec(1+sum(i=1,d,i!*b(i)*polcoef(p,i))) \\ Christian Sievers, Jun 22 2025

a(n) = Sum_{k=1..n} ( T(n,k) * A000255(k-1) ) for n>=1, where T(n,k) is the number of compositions of n into k distinct parts (cf. A072574). - Christian Sievers, Jun 22 2025

a(11) and beyond from Christian Sievers, Jun 22 2025

A384892 Number of permutations of {1..n} with all equal lengths of maximal runs (increasing by 1).

Original entry on oeis.org

1, 1, 2, 4, 13, 54, 314, 2120, 16700, 148333, 1468512, 16019532, 190899736, 2467007774, 34361896102, 513137616840, 8178130784179, 138547156531410, 2486151753462260, 47106033220679060, 939765362754015750, 19690321886243848784, 432292066866187743954

Offset: 0

Gus Wiseman, Jun 19 2025

nonn

			The permutation (1,2,5,6,3,4,7,8) has maximal runs ((1,2),(5,6),(3,4),(7,8)), with lengths (2,2,2,2), so is counted under a(8).
The a(0) = 1 through a(4) = 13 permutations:
  ()  (1)  (12)  (123)  (1234)
           (21)  (132)  (1324)
                 (213)  (1432)
                 (321)  (2143)
                        (2413)
                        (2431)
                        (3142)
                        (3214)
                        (3241)
                        (3412)
                        (4132)
                        (4213)
                        (4321)

Christian Sievers, Table of n, a(n) for n = 0..450

For subsets instead of permutations we have A243815, for anti-runs A384889.
For strict partitions and distinct lengths we have A384178, anti-runs A384880.
For integer partitions and distinct lengths we have A384884, anti-runs A384885.
For distinct lengths we have A384891, for anti-runs A384907.
For partitions we have A384904, strict A384886.
A010027 counts permutations by maximal anti-runs, for runs A123513.
A034839 counts subsets by number of maximal runs, for strict partitions A116674.
A098859 counts Wilf partitions (distinct multiplicities), complement A336866.
A384893 counts subsets by number of maximal anti-runs, for partitions A268193, A384905.
Cf. A000255, A044813, A047993, A242882, A325325, A329739, A351202, A384175, A384176, A384177.

Table[Length[Select[Permutations[Range[n]],SameQ@@Length/@Split[#,#2==#1+1&]&]],{n,0,10}]

a(n)=if(n,sumdiv(n,d,sum(i=0,d-1,(-1)^i*(d-i)!*binomial(d-1,i))),1) \\ Christian Sievers, Jun 22 2025

a(n) = Sum_{d|n} A000255(d-1). - Christian Sievers, Jun 22 2025

a(11) and beyond from Christian Sievers, Jun 22 2025

A001260 Number of permutations of length n with 4 consecutive ascending pairs.

Original entry on oeis.org

0, 0, 0, 0, 1, 5, 45, 385, 3710, 38934, 444990, 5506710, 73422855, 1049946755, 16035550531, 260577696015, 4489954146860, 81781307674780, 1570201107355980, 31698434854748604, 671260973394676605, 14879618243581997745

Offset: 1

N. J. A. Sloane

nonn

F. N. David, M. G. Kendall and D. E. Barton, Symmetric Function and Allied Tables, Cambridge, 1966, p. 263.
N. J. A. Sloane, A Handbook of Integer Sequences, Academic Press, 1973 (includes this sequence).
N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).

Vincenzo Librandi, Table of n, a(n) for n = 1..200

Cf. A010027, A000255, A000166, A000274, A000313, A001261.

A diagonal in triangle A010027.

a:=n->sum((n+2)!*sum((-1)^k/k!/4!, j=1..n), k=0..n): seq(a(n), n=2..19); # Zerinvary Lajos, May 25 2007
series(hypergeom([2, 5],[],x/(x+1))/(x+1)^5,x=0,30); # Mark van Hoeij, Nov 07 2011

Drop[CoefficientList[Series[x^4/4! Exp[-x]/(1 - x)^2, {x, 0, 20}], x] Range[0, 20]!, 4] (* Vaclav Kotesovec, Mar 26 2014 *)

(n-1)*a(n) = (n+3)*(a(n-1)*n + a(n-2)*n - a(n-1) + 2*a(n-2)).
E.g.f.: (for offset 4): (x^4/4!)*exp(-x)/(1-x)^2. - Vladeta Jovovic, Jan 03 2003
G.f.: (for offset 0): hypergeom([2, 5],[],x/(x+1))/(x+1)^5. - Mark van Hoeij, Nov 07 2011
Recurrence (for offset 5): (n-5)*a(n) = (n-5)*(n-1)*a(n-1) + (n-2)*(n-1)*a(n-2). - Vaclav Kotesovec, Mar 26 2014
a(n) ~ n! * exp(-1)/24. - Vaclav Kotesovec, Mar 26 2014

More terms from Vladeta Jovovic, Jan 03 2003

Name clarified and offset changed by N. J. A. Sloane, Apr 12 2014

A076731 Table T(n,k) giving number of ways of obtaining exactly 0 correct answers on an (n,k)-matching problem (1 <= k <= n).

Original entry on oeis.org

0, 1, 1, 2, 3, 2, 3, 7, 11, 9, 4, 13, 32, 53, 44, 5, 21, 71, 181, 309, 265, 6, 31, 134, 465, 1214, 2119, 1854, 7, 43, 227, 1001, 3539, 9403, 16687, 14833, 8, 57, 356, 1909, 8544, 30637, 82508, 148329, 133496, 9, 73, 527, 3333, 18089, 81901, 296967, 808393

Offset: 1

Mohammad K. Azarian, Oct 28 2002

Hanson et al. define the (n,k)-matching problem in the following realistic way. A matching question on an exam has k questions with n possible answers to choose from, each question having a unique answer. If a student guesses the answers at random, using each answer at most once, what is the probability of obtaining r of the k correct answers?
The T(n,k) represent the number of ways of obtaining exactly zero correct answers, i.e., r=0, given k questions and n possible answers, 1 <= k <= n.
T(n,k) is the number of injections from [1,...,k] into [1,...,n] with no fixed points. - David Bevan, Apr 29 2013

			0; 1,1; 2,3,2; 3,7,11,9; ...
Formatted as a square array:
0 1 2 3 4 5 6 7 8
1 3 7 13 21 31 43 57 which equals A002061
2 11 32 71 134 227 356 which equals A094792
9 53 181 465 1001 1909 which equals A094793
44 309 1214 3539 8544 which equals A094794
265 2119 9403 30637 which equals A023043
1854 16687 82508 which equals A023044
14833 148329 which equals A023045
Columns give A000255 A000153 A000261 A001909 A001910
Formatted as a triangular array (mirror image of A086764):
0
1 1
2 3 2
3 7 11 9
4 13 32 53 44
5 21 71 181 309 265
6 31 134 465 1214 2119 1854
7 43 227 1001 3539 9403 16687 14833
8 57 356 1909 8544 30637 82508 148329 133496

D. Hanson, K. Seyffarth and J. H. Weston, Matchings, Derangements, Rencontres, Mathematics Magazine, Vol. 56, No. 4, September 1983.
StackExchange, How many injective functions f:[1,...,m]->[1,...,n] have no fixed point?

Cf. A076732, A086764.

Similar to A060475.

A076731 := proc(n,k): (1/(n-k)!)*A061312(n-1,k-1) end: A061312:=proc(n,k): add(((-1)^j)*binomial(k+1,j)*(n+1-j)!, j=0..k+1) end: for n from 1 to 7 do seq(A076731(n,k), k=1..n) od; seq(seq(A076731(n,k), k=1..n), n=1..9); # Johannes W. Meijer, Jul 27 2011

t[n_,k_] := k!(n - k)! SeriesCoefficient[Exp[z(1-u+u^2z)/(1-z u)]/(1-z u), {z,0,n}, {u,0,k}]; Table[t[n,k], {n,9}, {k,n}] //TableForm (* David Bevan, Apr 29 2013 *)
t[n_, k_] := Pochhammer[n-k+1, k]*Hypergeometric1F1[-k, -n, -1]; Table[t[n, k], {n, 1, 10}, {k, 1, n}] // Flatten (* Jean-François Alcover, Nov 29 2013 *)

T(n,k) = F(n,k)*Sum{((-1)^j)*C(k, j)*(n-j)! (j=0 to k)}, where F(n,k) = 1/(n-k)! for 1 <= k <= n.
From Johannes W. Meijer, Jul 27 2011: (Start)
T(n,k) = (n-1)*T(n-1,k-1) + (k-1)*T(n-2,k-2) with T(n,1) = (n-1) and T(n,n) = A000166(n) [Hanson et al.]
T(n,k) = (1/(n-k)!)*A061312(n-1,k-1)
sum(T(n,k), k=1..n) = A193464(n); row sums. (End)
T(n,k) = k!(n-k)![z^n*u^k]J(z,u) where J(z,u) = exp(z(1-u+z*u^2)/(1-z*u))/(1-z*u) is the exponential generating function of labeled digraphs consisting just of directed paths and oriented cycles (of length at least 2), z marking the vertices and u the edges; [z^n*u^k]J(z,u) is the coefficient of z^n*u^k in J(z,u). - David Bevan, Apr 29 2013

Additional comments from Zerinvary Lajos, Mar 30 2006

A136123 Triangle read by rows: T(n,k) is the number of permutations of {1,2,...,n} having k maximal strings of increasing consecutive integers (0<=k<=floor(n/2)).

Original entry on oeis.org

1, 1, 1, 1, 3, 3, 11, 12, 1, 53, 56, 11, 309, 321, 87, 3, 2119, 2175, 693, 53, 16687, 17008, 5934, 680, 11, 148329, 150504, 55674, 8064, 309, 1468457, 1485465, 572650, 96370, 5805, 53, 16019531, 16170035, 6429470, 1200070, 95575, 2119

Offset: 0

Emeric Deutsch and Vladeta Jovovic, Dec 17 2007

Row n has 1+floor(n/2) terms. Row sums are the factorials (A000142). Column 0 yields A000255. Column 1 yields A001277. Column 2 yields A001278. Column 3 yields A001279. Column 4 yields A001280. Sum(k*T(n,k),k>=0)=(n-2)!*(n^2 - 3n + 3)=A001564(n-2).

			T(3,0)=3 because we have 132, 213 and 321; T(6,3)=3 because we have 125634, 341256, 563412.
Triangle starts:
    1;
    1;
    1,   1;
    3,   3;
   11,  12,  1;
   53,  56, 11;
  309, 321, 87, 3;
  ...

F. N. David, M. G. Kendall and D. E. Barton, Symmetric Function and Allied Tables, Cambridge, 1966, p. 264, Table 7.6.1.

Cf. A000142, A000255, A001277, A001278, A001279, A001280, A001564, A010029 (rows reversed).

G:=Sum(factorial(n)*(((1-t)*x^2-x)/((1-t)*x^2-1))^n, n=0..infinity): Gser:= simplify(series(G,x=0,13)): for n from 0 to 11 do P[n]:=sort(coeff(Gser,x,n)) end do: for n from 0 to 11 do seq(coeff(P[n],t,j),j=0..floor((1/2)*n)) end do; # yields sequence in triangular form
# alternative
A136123 := proc(n,k)
    add( x^i*( ((1-y)*x-1)/((1-y)*x^2-1) )^i*i!,i=0..n+1) ;
    coeftayl(%,x=0,n) ;
    coeftayl(%,y=0,k) ;
end proc:
seq(seq( A136123(n,k),k=0..floor(n/2)),n=0..12) ; # R. J. Mathar, Jul 01 2022

T[n_, k_] := Sum[x^i*(((1-y)*x-1)/((1-y)*x^2-1))^i*i!, {i, 0, n+1}] //
   SeriesCoefficient[#, {x, 0, n}]& //
   SeriesCoefficient[#, {y, 0, k}]&;
Table[Table[T[n, k], {k, 0, Floor[n/2]}], {n, 0, 12}] // Flatten (* Jean-François Alcover, May 09 2023, after R. J. Mathar *)

G.f.: G(x,t) = Sum_{n>=0} n!*(((1-t)*x^2 - x)/((1-t)*x^2-1))^n. - Vladeta Jovovic

A184182 Triangle read by rows: T(n,k) is the number of permutations of {1,2,...,n} whose longest block is of length k (0<=k<=n).

Original entry on oeis.org

1, 0, 1, 0, 1, 1, 0, 3, 2, 1, 0, 11, 10, 2, 1, 0, 53, 53, 11, 2, 1, 0, 309, 334, 63, 11, 2, 1, 0, 2119, 2428, 415, 64, 11, 2, 1, 0, 16687, 20009, 3121, 425, 64, 11, 2, 1, 0, 148329, 184440, 26402, 3205, 426, 64, 11, 2, 1, 0, 1468457, 1881050, 248429, 27145, 3215, 426, 64, 11, 2, 1

Offset: 0

Emeric Deutsch, Feb 13 2011

A block of a permutation is a maximal sequence of consecutive integers which appear in consecutive positions. For example, the permutation 5412367 has 4 blocks: 5, 4, 123, and 67. Its longest block has length 3.

			T(3,1) = 3 because we have 132, 213, and 321.
T(4,3) = 2 because we have 4123 and 2341.
Triangle starts:
  1;
  0,   1;
  0,   1,   1;
  0,   3,   2,  1;
  0,  11,  10,  2,  1;
  0,  53,  53, 11,  2, 1;
  0, 309, 334, 63, 11, 2, 1;
  ...

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

Columns k=0..3 give A000007, A000255(n-1), A370390, A370392.
Cf. A000166, A184180.
Row sums are A000142.

d[-1]:= 0: d[0] := 1: for n to 40 do d[n] := n*d[n-1]+(-1)^n end do: b := proc (n, m, k) options operator, arrow: coeff(add(t^j, j = 1 .. k)^m, t, n) end proc: T := proc (n, k) options operator, arrow: add(b(n, m, k)*(d[m]+d[m-1]), m = 0 .. n)-add(b(n, m, k-1)*(d[m]+d[m-1]), m = 1 .. n) end proc: for n from 0 to 11 do seq(T(n, k), k = 0 .. n) end do; # yields sequence in triangular form

b[n_, m_, k_] := Module[{t}, Coefficient[Total[t^Range[k]]^m, t, n]];
T[n_, k_] := If[n == 0, 1, Module[{d = Subfactorial}, Sum[(b[n, m, k] - b[n, m, k-1])*(d[m]+d[m-1]), {m, 1, n}]]];
Table[T[n, k], {n, 0, 10}, {k, 0, n}] // Flatten (* Jean-François Alcover, Aug 06 2024 *)

T(n,k) = Sum_{m=1..n} (b(n,m,k)-b(n,m,k-1))*(d(m)+d(m-1)), where b(n,m,k) = coefficient of t^n in (t+t^2+...+t^k)^m and d(j) = A000166(j) are the derangement numbers.
T(n,1) = A000255(n-1) for n>=1.
Sum_{k=1..n} T(n,k) = n! (row sums).

Row n=0 and column k=0 added by Alois P. Heinz, Feb 17 2024

cp's OEIS Frontend

A176732 a(n) = (n+5)*a(n-1) + (n-1)*a(n-2), a(-1)=0, a(0)=1.

Views

Author

Keywords

Comments

Examples

Crossrefs

Programs

Maple

Mathematica

Formula

A176733 a(n) = (n+6)*a(n-1) + (n-1)*a(n-2), a(-1)=0, a(0)=1.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Maple

Mathematica

Formula

A189281 Number of permutations p of 1,2,...,n satisfying p(i+2) - p(i) <> 2 for all 1 <= i <= n-2.

Views

Author

Keywords

Comments

Links

Crossrefs

Formula

A207821 Number of permutations of [n] that either have a fixed point or a succession, but not both.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

PARI

Formula

Extensions

A384891 Number of permutations of {1..n} with all distinct lengths of maximal runs (increasing by 1).

Views

Author

Keywords

Examples

Links

Crossrefs

Programs

Mathematica

PARI

Formula

Extensions

A384892 Number of permutations of {1..n} with all equal lengths of maximal runs (increasing by 1).

Views

Author

Keywords

Examples

Links

Crossrefs

Programs

Mathematica

PARI

Formula

Extensions

A001260 Number of permutations of length n with 4 consecutive ascending pairs.

Views

Author

Keywords

References

Links

Crossrefs

Programs

Maple

Mathematica

Formula

Extensions

A176732 a(n) = (n+5)a(n-1) + (n-1)a(n-2), a(-1)=0, a(0)=1.

A176733 a(n) = (n+6)a(n-1) + (n-1)a(n-2), a(-1)=0, a(0)=1.