OFFSET
0,5
KEYWORD
dead
STATUS
approved
The OEIS is supported by the many generous donors to the OEIS Foundation.
0, 0, 1, 0, 6, 20, 135, 924, 7420, 66744, 667485, 7342280, 88107426, 1145396460, 16035550531, 240533257860, 3848532125880, 65425046139824, 1177650830516985, 22375365779822544, 447507315596451070, 9397653627525472260, 206748379805560389951, 4755212735527888968620
Subfactorial or rencontres numbers, or derangements: number of permutations of n elements with no fixed points.
(Formerly M1937 N0766)
(Formerly M1937 N0766)
+10
526
526
1, 0, 1, 2, 9, 44, 265, 1854, 14833, 133496, 1334961, 14684570, 176214841, 2290792932, 32071101049, 481066515734, 7697064251745, 130850092279664, 2355301661033953, 44750731559645106, 895014631192902121, 18795307255050944540, 413496759611120779881, 9510425471055777937262
OFFSET
0,4
COMMENTS
Euler not only gives the first ten or so terms of the sequence, he also proves both recurrences a(n) = (n-1)*(a(n-1) + a(n-2)) and a(n) = n*a(n-1) + (-1)^n.
a(n) is the permanent of the matrix with 0 on the diagonal and 1 elsewhere. - Yuval Dekel, Nov 01 2003
a(n) is the number of desarrangements of length n. A desarrangement of length n is a permutation p of {1,2,...,n} for which the smallest of all the ascents of p (taken to be n if there are no ascents) is even. Example: a(3) = 2 because we have 213 and 312 (smallest ascents at i = 2). See the J. Désarménien link and the Bona reference (p. 118). - Emeric Deutsch, Dec 28 2007
a(n) is the number of deco polyominoes of height n and having in the last column an even number of cells. A deco polyomino is a directed column-convex polyomino in which the height, measured along the diagonal, is attained only in the last column. - Emeric Deutsch, Dec 28 2007
Attributed to Nicholas Bernoulli in connection with a probability problem that he presented. See Problem #15, p. 494, in "History of Mathematics" by David M. Burton, 6th edition. - Mohammad K. Azarian, Feb 25 2008
a(n) is the number of permutations p of {1,2,...,n} with p(1)!=1 and having no right-to-left minima in consecutive positions. Example a(3) = 2 because we have 231 and 321. - Emeric Deutsch, Mar 12 2008
a(n) is the number of permutations p of {1,2,...,n} with p(n)! = n and having no left to right maxima in consecutive positions. Example a(3) = 2 because we have 312 and 321. - Emeric Deutsch, Mar 12 2008
Number of wedged (n-1)-spheres in the homotopy type of the Boolean complex of the complete graph K_n. - Bridget Tenner, Jun 04 2008
The only prime number in the sequence is 2. - Howard Berman (howard_berman(AT)hotmail.com), Nov 08 2008
From Emeric Deutsch, Apr 02 2009: (Start)
a(n) is the number of permutations of {1,2,...,n} having exactly one small ascent. A small ascent in a permutation (p_1,p_2,...,p_n) is a position i such that p_{i+1} - p_i = 1. (Example: a(3) = 2 because we have 312 and 231; see the Charalambides reference, pp. 176-180.) [See also David, Kendall and Barton, p. 263. - N. J. A. Sloane, Apr 11 2014]
a(n) is the number of permutations of {1,2,...,n} having exactly one small descent. A small descent in a permutation (p_1,p_2,...,p_n) is a position i such that p_i - p_{i+1} = 1. (Example: a(3)=2 because we have 132 and 213.) (End)
For n > 2, a(n) + a(n-1) = A000255(n-1); where A000255 = (1, 1, 3, 11, 53, ...). - Gary W. Adamson, Apr 16 2009
Connection to A002469 (game of mousetrap with n cards): A002469(n) = (n-2)*A000255(n-1) + A000166(n). (Cf. triangle A159610.) - Gary W. Adamson, Apr 17 2009
From Emeric Deutsch, Jul 18 2009: (Start)
a(n) is the sum of the values of the largest fixed points of all non-derangements of length n-1. Example: a(4)=9 because the non-derangements of length 3 are 123, 132, 213, and 321, having largest fixed points 3, 1, 3, and 2, respectively.
a(n) is the number of non-derangements of length n+1 for which the difference between the largest and smallest fixed point is 2. Example: a(3) = 2 because we have 1'43'2 and 32'14'; a(4) = 9 because we have 1'23'54, 1'43'52, 1'53'24, 52'34'1, 52'14'3, 32'54'1, 213'45', 243'15', and 413'25' (the extreme fixed points are marked).
(End)
a(n), n >= 1, is also the number of unordered necklaces with n beads, labeled differently from 1 to n, where each necklace has >= 2 beads. This produces the M2 multinomial formula involving partitions without part 1 given below. Because M2(p) counts the permutations with cycle structure given by partition p, this formula gives the number of permutations without fixed points (no 1-cycles), i.e., the derangements, hence the subfactorials with their recurrence relation and inputs. Each necklace with no beads is assumed to contribute a factor 1 in the counting, hence a(0)=1. 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). - Wolfdieter Lang, Jun 01 2010
From Emeric Deutsch, Sep 06 2010: (Start)
a(n) is the number of permutations of {1,2,...,n, n+1} starting with 1 and having no successions. A succession in a permutation (p_1,p_2,...,p_n) is a position i such that p_{i+1} - p_i = 1. Example: a(3)=2 because we have 1324 and 1432.
a(n) is the number of permutations of {1,2,...,n} that do not start with 1 and have no successions. A succession in a permutation (p_1,p_2,...,p_n) is a position i such that p_{i+1} - p_i = 1. Example: a(3)=2 because we have 213 and 321.
(End)
Increasing colored 1-2 trees with choice of two colors for the rightmost branch of nonleave except on the leftmost path, there is no vertex of outdegree one on the leftmost path. - Wenjin Woan, May 23 2011
a(n) is the number of zeros in n-th row of the triangle in A170942, n > 0. - Reinhard Zumkeller, Mar 29 2012
a(n) is the maximal number of totally mixed Nash equilibria in games of n players, each with 2 pure options. - Raimundas Vidunas, Jan 22 2014
Convolution of sequence A135799 with the sequence generated by 1+x^2/(2*x+1). - Thomas Baruchel, Jan 08 2016
The number of interior lattice points of the subpolytope of the n-dimensional permutohedron whose vertices correspond to permutations avoiding 132 and 312. - Robert Davis, Oct 05 2016
Consider n circles of different radii, where each circle is either put inside some bigger circle or contains a smaller circle inside it (no common points are allowed). Then a(n) gives the number of such combinations. - Anton Zakharov, Oct 12 2016
If we partition the permutations of [n+1] in A000240 according to their starting digit, we will get (n+1) equinumerous classes each of size a(n), i.e., A000240(n+1) = (n+1)*a(n), hence a(n) is the size of each class of permutations of [n+1] in A000240. For example, for n = 4 we have 45 = 5*9. - Enrique Navarrete, Jan 10 2017
Call d_n1 the permutations of [n] that have the substring n1 but no substring in {12,23,...,(n-1)n}. If we partition them according to their starting digit, we will get (n-1) equinumerous classes each of size A000166(n-2) (the class starting with the digit 1 is empty since we must have the substring n1). Hence d_n1 = (n-1)*A000166(n-2) and A000166(n-2) is the size of each nonempty class in d_n1. For example, d_71 = 6*44 = 264, so there are 264 permutations in d_71 distributed in 6 nonempty classes of size A000166(5) = 44. (To get permutations in d_n1 recursively from more basic ones see the link "Forbidden Patterns" below.) - Enrique Navarrete, Jan 15 2017
Also the number of maximum matchings and minimum edge covers in the n-crown graph. - Eric W. Weisstein, Jun 14 and Dec 24 2017
The sequence a(n) taken modulo a positive integer k is periodic with exact period dividing k when k is even and dividing 2*k when k is odd. This follows from the congruence a(n+k) = (-1)^k*a(n) (mod k) for all n and k, which in turn is easily proved by induction making use of the recurrence a(n) = n*a(n-1) + (-1)^n. - Peter Bala, Nov 21 2017
a(n) is the number of distinct possible solutions for a directed, no self loop containing graph (not necessarily connected) that has n vertices, and each vertex has an in- and out-degree of exactly 1. - Patrik Holopainen, Sep 18 2018
a(n) is the dimension of the kernel of the random-to-top and random-to-random shuffling operators over a collection of n objects (in a vector space of size n!), as noticed by M. Wachs and V. Reiner. See the Reiner, Saliola and Welker reference below. - Nadia Lafreniere, Jul 18 2019
a(n) is the number of distinct permutations for a Secret Santa gift exchange with n participants. - Patrik Holopainen, Dec 30 2019
a(2*n+1) is even. More generally, a(m*n+1) is divisible by m*n, which follows from a(n+1) = n*(a(n) + a(n-1)) = n*A000255(n-1) for n >= 1. a(2*n) is odd; in fact, a(2*n) == 1 (mod 8). Other divisibility properties include a(6*n) == 1 (mod 24), a(9*n+4) == a(9*n+7) == 0 (mod 9), a(10*n) == 1 (mod 40), a(11*n+5) == 0 (mod 11) and a(13*n+8 ) == 0 (mod 13). - Peter Bala, Apr 05 2022
REFERENCES
U. Abel, Some new identities for derangement numbers, Fib. Q., 56:4 (2018), 313-318.
M. Bona, Combinatorics of Permutations, Chapman & Hall/CRC, Boca Raton, Florida, 2004.
Miklos Bona, editor, Handbook of Enumerative Combinatorics, CRC Press, 2015, page 32.
R. A. Brualdi and H. J. Ryser: Combinatorial Matrix Theory, 1992, Section 7.2, p. 202.
Ch. A. Charalambides, Enumerative Combinatorics, Chapman & Hall/CRC, Boca Raton, Florida, 2002.
L. Comtet, Advanced Combinatorics, Reidel, 1974, p. 182.
Florence Nightingale David and D. E. Barton, Combinatorial Chance. Hafner, NY, 1962, p. 168.
Florence Nightingale David, Maurice George Kendall, and D. E. Barton, Symmetric Function and Allied Tables, Cambridge, 1966, p. 263, Table 7.5.1, row 1.
P. R. de Montmort, On the Game of Thirteen (1713), reprinted in Annotated Readings in the History of Statistics, ed. H. A. David and A. W. F. Edwards, Springer-Verlag, 2001, pp. 25-29.
J. M. de Saint-Martin, "Le problème des rencontres" in Quadrature, No. 61, pp. 14-19, 2006, EDP-Sciences Les Ulis (France).
H. Doerrie, 100 Great Problems of Elementary Mathematics, Dover, NY, 1965, p. 19.
Leonhart Euler, Solution quaestionis curiosae ex doctrina combinationum, Mémoires Académie sciences St. Pétersburg 3 (1809/1810), 57-64; also E738 in his Collected Works, series I, volume 7, pages 435-440.
J. M. Gandhi, On logarithmic numbers, Math. Student, 31 (1963), 73-83.
A. Hald, A History of Probability and Statistics and Their Applications Before 1750, Wiley, NY, 1990 (Chapter 19).
Irving Kaplansky, John Riordan, The problème des ménages. Scripta Math. 12 (1946), 113-124. See Eq(1).
Arnold Kaufmann, "Introduction à la combinatorique en vue des applications." Dunod, Paris, 1968. See p. 92.
Florian Kerschbaum and Orestis Terzidis, Filtering for Private Collaborative Benchmarking, in Emerging Trends in Information and Communication Security, Lecture Notes in Computer Science, Volume 3995/2006.
E. Lozansky and C. Rousseau, Winning Solutions, Springer, 1996; see p. 152.
P. A. MacMahon, Combinatory Analysis, 2 vols., Chelsea, NY, 1960, see p. 102.
M. S. Petković, "Non-attacking rooks", Famous Puzzles of Great Mathematicians, pp. 265-268, Amer. Math. Soc.(AMS), 2009.
V. Reiner, F. Saliola, and V. Welker. Spectra of Symmetrized Shuffling Operators, Memoirs of the American Mathematical Society, vol. 228, Amer. Math. Soc., Providence, RI, 2014, pp. 1-121. See section VI.9.
J. Riordan, An Introduction to Combinatorial Analysis, Wiley, 1958, p. 65.
H. J. Ryser, Combinatorial Mathematics. Mathematical Association of America, Carus Mathematical Monograph 14, 1963, p. 23.
T. Simpson, Permutations with unique fixed and reflected points. Ars Combin. 39 (1995), 97-108.
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).
David Wells, The Penguin Dictionary of Curious and Interesting Numbers. Penguin Books, NY, 1986, Revised edition 1987. See p. 122.
D. B. West, Combinatorial Mathematics, Cambridge, 2021, p. 82.
H. S. Wilf, Generatingfunctionology, Academic Press, NY, 1990, p. 147, Eq. 5.2.9 (q=1).
LINKS
Seiichi Manyama, Table of n, a(n) for n = 0..450 (terms 0..200 from T. D. Noe)
Christian Aebi and Grant Cairns, Generalizations of Wilson's Theorem for Double-, Hyper-, Sub-and Superfactorials, The American Mathematical Monthly 122.5 (2015): 433-443.
Joerg Arndt, Generating Random Permutations, PhD thesis, Australian National University, Canberra, Australia, (2010).
Joerg Arndt, Matters Computational (The Fxtbook), p. 280.
Etor Arza, Aritz Perez, Ekhine Irurozki, and Josu Ceberio, Kernels of Mallows Models under the Hamming Distance for solving the Quadratic Assignment Problem, arXiv:1910.08800 [stat.ML], 2019.
Roland Bacher, Counting Packings of Generic Subsets in Finite Groups, Electr. J. Combinatorics, 19 (2012), #P7.
Roland Bacher and P. De La Harpe, Conjugacy growth series of some infinitely generated groups, arXiv:1603.07943 [math.GR], 2016.
B. Balof and H. Jenne, Tilings, Continued Fractions, Derangements, Scramblings, and e, Journal of Integer Sequences, 17 (2014), #14.2.7.
V. Baltic, On the number of certain types of strongly restricted permutations, Appl. An. Disc. Math. 4 (2010), 119-135; Doi:10.2298/AADM1000008B.
E. Barcucci, A. Del Lungo, and R. Pinzani, "Deco" polyominoes, permutations and random generation, Theoretical Computer Science, 159, 1996, 29-42.
D. Barsky, Analyse p-adique et suites classiques de nombres, Sem. Loth. Comb. B05b (1981) 1-21.
Arthur T. Benjamin and Joel Ornstein, A bijective proof of a derangement recurrence, Fibonacci Quart., 55(5):28-29, 2017.
H. Bergeron, E. M. F. Curado, J. P. Gazeau, and L. M. C. S. Rodrigues, A note about combinatorial sequences and Incomplete Gamma function, arXiv preprint arXiv: 1309.6910 [math.CO], 2013.
Natasha Blitvić and Einar Steingrímsson, Permutations, moments, measures, arXiv:2001.00280 [math.CO], 2020.
Stefano Capparelli, Margherita Maria Ferrari, Emanuele Munarini, and Norma Zagaglia Salvi, A Generalization of the "Problème des Rencontres", J. Int. Seq. 21 (2018), #18.2.8.
Lapo Cioni and Luca Ferrari, Preimages under the Queuesort algorithm, arXiv preprint arXiv:2102.07628 [math.CO], 2021; Discrete Math., 344 (2021), #112561.
P. Cvitanovic, Group theory for Feynman diagrams in non-Abelian gauge theories, Phys. Rev. D14 (1976), 1536-1553.
S. K. Das and N. Deo, Rencontres graphs: a family of bipartite graphs, Fib. Quart., Vol. 25, No. 3, August 1987, 250-262.
R. Davis and B. Sagan, Pattern-Avoiding Polytopes, arXiv preprint arxiv:1609.01782 [math.CO], 2016.
J. Désarménien, Une autre interprétation du nombre de dérangements, Sem. Loth. Comb. B08b (1982) 11-16.
Emeric Deutsch and S. Elizalde, The largest and the smallest fixed points of permutations, arXiv:0904.2792 [math.CO], 2009.
R. M. Dickau, Derangement diagrams.
Tomislav Došlic and Darko Veljan, Logarithmic behavior of some combinatorial sequences, Discrete Math. 308 (2008), no. 11, 2182--2212. MR2404544 (2009j:05019).
P. Duchon and R. Duvignau, A new generation tree for permutations, FPSAC 2014, Chicago, USA; Discrete Mathematics and Theoretical Computer Science (DMTCS) Proceedings, 2014, 679-690.
J. East and R. D. Gray, Idempotent generators in finite partition monoids and related semigroups, arXiv preprint arXiv:1404.2359 [math.GR], 2014.
Sergi Elizalde, A simple bijective proof of a familiar derangement recurrence, arXiv:2005.11312 [math.CO], 2020.
Uriel Feige, Tighter bounds for online bipartite matching, 2018.
Philip Feinsilver and John McSorley, Zeons, Permanents, the Johnson Scheme, and Generalized Derangements, International Journal of Combinatorics, Volume 2011, Article ID 539030, 29 pages.
FindStat - Combinatorial Statistic Finder, The number of fixed points of a permutation.
H. Fripertinger, The Rencontre Numbers. [Broken link]
Hannah Fry and Brady Haran, The Problems with Secret Santa, Numberphile video (2016).
Jason Fulman and Robert Guralnick, Derangements in simple and primitive groups, arXiv:math/0208022 [math.GR], 2002.
J. M. Gandhi, On logarithmic numbers, Math. Student, 31 (1963), 73-83. [Annotated scanned copy]
Zbigniew Gołębiewski and Mateusz Klimczak, Protection Number of Recursive Trees, 2019 Proceedings of the Sixteenth Workshop on Analytic Algorithmics and Combinatorics (ANALCO).
O. Gonzalez, C. Beltran, and I. Santamaria, On the Number of Interference Alignment Solutions for the K-User MIMO Channel with Constant Coefficients, arXiv preprint arXiv:1301.6196 [cs.IT], 2013.
G. Gordon and E. McMahon, Moving faces to other places: facet derangements, Amer. Math. Monthly, 117 (2010), 865-88.
R. K. Guy and R. J. Nowakowski, Mousetrap, Preprint, Feb 10 1993. [Annotated scanned copy]
Amihay Hanany, Vishnu Jejjala, Sanjaye Ramgoolam, and Rak-Kyeong Seong, Consistency and Derangements in Brane Tilings, arXiv:1512.09013 [hep-th], 2015.
Mehdi Hassani, Derangements and Applications, Journal of Integer Sequences, Vol. 6 (2003), #03.1.2.
M. Hassani, Counting and computing by e, arXiv:math/0606613 [math.CO], 2006.
Nick Hobson, Python program.
Q.-H. Hou, Z.-W. Sun and H.-M. Wen, On monotonicity of some combinatorial sequences, arXiv:1208.3903 [math.CO], 2012-2014.
INRIA Algorithms Project, Encyclopedia of Combinatorial Structures 21.
E. Irurozki, B. Calvo, and J. A. Lozano, Sampling and learning the Mallows and Weighted Mallows models under the Hamming distance, 2014.
Ekhine Irurozki, B. Calvo, and J. A. Lozano, PerMallows: An R Package for Mallows and Generalized Mallows Models, Journal of Statistical Software, August 2016, Volume 71, Issue 12. doi: 10.18637/jss.v071.i12.
Milan Janjic, Determinants and Recurrence Sequences, Journal of Integer Sequences, 2012, Article 12.3.5.
Shirali Kadyrov and Farukh Mashurov, Generalized continued fraction expansions for Pi and E, arXiv:1912.03214 [math.NT], 2019.
I. Kaplansky and J. Riordan, The problème des ménages, Scripta Math. 12, (1946), 113-124. [Scan of annotated copy]
Vaclav Kotesovec, Non-attacking chess pieces, 6ed, 2013, p. 220.
A. R. Kräuter, Über die Permanente gewisser zirkulärer Matrizen..., Séminaire Lotharingien de Combinatoire, B11b (1984), 11 pp.
J. W. Layman, The Hankel Transform and Some of its Properties, J. Integer Sequences, 4 (2001), #01.1.5.
Les Tablettes du Chercheur, 52. Combinaisons, pp. 10-11, Dec 01 1890.
Rui-Li Liu and Feng-Zhen Zhao, New Sufficient Conditions for Log-Balancedness, With Applications to Combinatorial Sequences, J. Int. Seq., Vol. 21 (2018), Article 18.5.7.
E. Lucas, Théorie des nombres (annotated scans of a few selected pages).
T. Mansour and M. Shattuck, Counting permutations by the number of successors within cycles, Discr. Math., 339 (2016), 1368-1376.
Richard J. Martin and Michael J. Kearney, Integral representation of certain combinatorial recurrences, Combinatorica: 35:3 (2015), 309-315.
Ivica Martinjak and Dajana Stanić, A Short Combinatorial Proof of Derangement Identity, arXiv:1711.04537 [math.CO], 2017.
R. D. McKelvey and A. McLennan, The maximal number of regular totally mixed Nash equilibria, J. Economic Theory, 72:411--425, 1997.
J. R. G. Mendonça, On the uniform generation of random derangements, arXiv:1809.04571 [stat.CO], 2018.
Romeo Mestrovic, Variations of Kurepa's left factorial hypothesis, arXiv preprint arXiv:1312.7037 [math.NT], 2013.
Emanuele Munarini, q-Derangement Identities, J. Int. Seq., Vol. 23 (2020), Article 20.3.8.
Emanuele Munarini, Two-Parameter Identities for q-Appell Polynomials, Journal of Integer Sequences, Vol. 26 (2023), Article 23.3.1.
Enrique Navarrete, Forbidden Patterns and the Alternating Derangement Sequence, arXiv:1610.01987 [math.CO], 2016.
Andrew O'Desky and David Harry Richman, Derangements and the p-adic incomplete gamma function, arXiv:2012.04615 [math.NT], 2020.
R. Ondrejka, The first 100 exact subfactorials (Review), Math. Comp., 21 (1967), 502.
Hyungju Park, An Asymptotic Formula for the Number of Stabilized-Interval-Free Permutations, J. Int. Seq. (2023) Vol. 26, Art. 23.9.3.
P. Peart and W.-J. Woan, Generating Functions via Hankel and Stieltjes Matrices, J. Integer Seqs., Vol. 3 (2000), #00.2.1.
Alexsandar Petojevic, The Function vM_m(s; a; z) and Some Well-Known Sequences, Journal of Integer Sequences, Vol. 5 (2002), Article 02.1.7.
Simon Plouffe, Exact formulas for integer sequences.
K. Ragnarsson and B. E. Tenner, Homotopy type of the Boolean complex of a Coxeter system, Adv. Math. 222 (2009), 409-430.
J. B. Remmel, A note on a recursion for the number of derangements, European J. Combin., 4(4):371-374, 1983.
John Riordan, Letter to N. J. A. Sloane, Sep 26 1980 with notes on the 1973 Handbook of Integer Sequences. Note that the sequences are identified by their N-numbers, not their A-numbers.
M. Rumney and E. J. F. Primrose, A sequence connected with the subfactorial sequence, Note 3207, Math. Gaz. 52 (1968), 381-382.
M. Rumney and E. J. F. Primrose, A sequence connected with the subfactorial sequence, Note 3207, Math. Gaz. 52 (1968), 381-382. [Annotated scanned copy]
E. Sandifer, How Euler Did It, Derangements.
M. Shattuck, Combinatorial proofs of some Bell number formulas, arXiv preprint arXiv:1401.6588 [math.CO], 2014.
T. Simpson, Permutations with unique fixed and reflected points, Preprint. (Annotated scanned copy)
Michael Z. Spivey and Laura L. Steil, The k-Binomial Transforms and the Hankel Transform, Journal of Integer Sequences, Vol. 9 (2006), Article 06.1.1.
R. J. Stones, S. Lin, X. Liu, and G. Wang, On Computing the Number of Latin Rectangles, Graphs and Combinatorics (2016) 32:1187-1202; DOI 10.1007/s00373-015-1643-1.
Xinyu Sun, New Lower Bound On The Number of Ternary Square-Free Words, J. Integer Seqs., Vol. 6, 2003.
L. Takacs, The Problem of Coincidences, Archive for History of Exact Sciences, Volume 21, No. 3, Sept. 1980. pp. 229-244, paragraph 3.
R. Vidunas, MacMahon's master theorem and totally mixed Nash equilibria, arXiv:1401.5400 [math.CO], 2014, see (7).
G. Villemin's Almanach of Numbers, Sous-factorielle.
Chenying Wang, Piotr Miska, and István Mezo, The r-derangement numbers, Discrete Mathematics 340.7 (2017): 1681-1692.
Yi Wang and Bao-Xuan Zhu, Proofs of some conjectures on monotonicity of number-theoretic and combinatorial sequences, arXiv preprint arXiv:1303.5595 [math.CO], 2013.
Eric Weisstein's World of Mathematics, Crown Graph.
Eric Weisstein's World of Mathematics, Derangement.
Eric Weisstein's World of Mathematics, Edge Cover.
Eric Weisstein's World of Mathematics, Exponential Distribution.
Eric Weisstein's World of Mathematics, Matching.
Eric Weisstein's World of Mathematics, Maximum Independent Edge Set.
Eric Weisstein's World of Mathematics, Rooks Problem.
Eric Weisstein's World of Mathematics, Subfactorial.
Wikipedia, Derangement.
Wikipedia, Rencontres numbers.
Herbert S. Wilf, A bijection in the theory of derangements, Mathematics Magazine, 57(1):37-40, 1984.
H. S. Wilf, Generatingfunctionology, 2nd edn., Academic Press, NY, 1994, p. 176, Eq. 5.2.9 (q=1).
E. M. Wright, Arithmetical properties of Euler's rencontre number, J. London Math. Soc., (2) (1971/1972), 437-442.
D. Zeilberger, Automatic Enumeration of Generalized Menage Numbers, arXiv preprint arXiv:1401.1089 [math.CO], 2014.
OEIS Wiki, Derangement numbers.
OEIS Wiki, Rencontres numbers.
FORMULA
a(n) = A008290(n,0).
a(n) + A003048(n+1) = 2*n!. - D. G. Rogers, Aug 26 2006
a(n) = {(n-1)!/exp(1)}, n > 1, where {x} is the nearest integer function. - Simon Plouffe, March 1993 [This uses offset 1, see below for the version with offset 0. - Charles R Greathouse IV, Jan 25 2012]
a(0) = 1, a(n) = round(n!/e) = floor(n!/e + 1/2) for n > 0.
a(n) = n!*Sum_{k=0..n} (-1)^k/k!.
D-finite with recurrence a(n) = (n-1)*(a(n-1) + a(n-2)), n > 0.
a(n) = n*a(n-1) + (-1)^n.
E.g.f.: exp(-x)/(1-x).
a(n) = Sum_{k=0..n} binomial(n, k)*(-1)^(n-k)*k! = Sum_{k=0..n} (-1)^(n-k)*n!/(n-k)!. - Paul Barry, Aug 26 2004
The e.g.f. y(x) satisfies y' = x*y/(1-x).
Inverse binomial transform of A000142. - Ross La Haye, Sep 21 2004
In Maple notation, representation as n-th moment of a positive function on [-1, infinity]: a(n)= int( x^n*exp(-x-1), x=-1..infinity ), n=0, 1... . a(n) is the Hamburger moment of the function exp(-1-x)*Heaviside(x+1). - Karol A. Penson, Jan 21 2005
a(n) = A001120(n) - n!. - Philippe Deléham, Sep 04 2005
a(n) = Integral_{x=0..oo} (x-1)^n*exp(-x) dx. - Gerald McGarvey, Oct 14 2006
a(n) = Sum_{k=2,4,...} T(n,k), where T(n,k) = A092582(n,k) = k*n!/(k+1)! for 1 <= k < n and T(n,n)=1. - Emeric Deutsch, Feb 23 2008
a(n) = n!/e + (-1)^n*(1/(n+2 - 1/(n+3 - 2/(n+4 - 3/(n+5 - ...))))). Asymptotic result (Ramanujan): (-1)^n*(a(n) - n!/e) ~ 1/n - 2/n^2 + 5/n^3 - 15/n^4 + ..., where the sequence [1,2,5,15,...] is the sequence of Bell numbers A000110. - Peter Bala, Jul 14 2008
From William Vaughn (wvaughn(AT)cvs.rochester.edu), Apr 13 2009: (Start)
a(n) = Integral_{p=0..1} (log(1/(1-p)) - 1)^n dp.
Proof: Using the substitutions 1=log(e) and y = e(1-p) the above integral can be converted to ((-1)^n/e) Integral_{y=0..e} (log(y))^n dy.
From CRC Integral tables we find the antiderivative of (log(y))^n is (-1)^n n! Sum_{k=0..n} (-1)^k y(log(y))^k / k!.
Using the fact that e(log(e))^r = e for any r >= 0 and 0(log(0))^r = 0 for any r >= 0 the integral becomes n! * Sum_{k=0..n} (-1)^k / k!, which is line 9 of the Formula section. (End)
a(n) = exp(-1)*Gamma(n+1,-1) (incomplete Gamma function). - Mark van Hoeij, Nov 11 2009
G.f.: 1/(1-x^2/(1-2x-4x^2/(1-4x-9x^2/(1-6x-16x^2/(1-8x-25x^2/(1-... (continued fraction). - Paul Barry, Nov 27 2009
a(n) = Sum_{p in Pano1(n)} M2(p), n >= 1, with Pano1(n) the set of partitions without part 1, and the multinomial M2 numbers. See the characteristic array for partitions without part 1 given by A145573 in Abramowitz-Stegun (A-S) order, with A002865(n) the total number of such partitions. The M2 numbers are given for each partition in A-St order by the array A036039. - Wolfdieter Lang, Jun 01 2010
a(n) = row sum of A008306(n), n > 1. - Gary Detlefs, Jul 14 2010
a(n) = ((-1)^n)*(n-1)*hypergeom([-n+2, 2], [], 1), n>=1; 1 for n=0. - Wolfdieter Lang, Aug 16 2010
a(n) = (-1)^n * hypergeom([ -n, 1], [], 1), n>=1; 1 for n=0. From the binomial convolution due to the e.g.f. - Wolfdieter Lang, Aug 26 2010
Integral_{x=0..1} x^n*exp(x) = (-1)^n*(a(n)*e - n!).
O.g.f.: Sum_{n>=0} n^n*x^n/(1 + (n+1)*x)^(n+1). - Paul D. Hanna, Oct 06 2011
G.f.: hypergeom([1,1],[],x/(x+1))/(x+1). - Mark van Hoeij, Nov 07 2011
From Sergei N. Gladkovskii, Nov 25 2011, Jul 05 2012, Sep 23 2012, Oct 13 2012, Mar 09 2013, Mar 10 2013, Oct 18 2013: (Start)
Continued fractions:
In general, e.g.f. (1+a*x)/exp(b*x) = U(0) with U(k) = 1 + a*x/(1-b/(b-a*(k+1)/U(k+1))). For a=-1, b=-1: exp(-x)/(1-x) = 1/U(0).
E.g.f.: (1-x/(U(0)+x))/(1-x), where U(k) = k+1 - x + (k+1)*x/U(k+1).
E.g.f.: 1/Q(0) where Q(k) = 1 - x/(1 - 1/(1 - (k+1)/Q(k+1))).
G.f.: 1/U(0) where U(k) = 1 + x - x*(k+1)/(1 - x*(k+1)/U(k+1)).
G.f.: Q(0)/(1+x) where Q(k) = 1 + (2*k+1)*x/((1+x)-2*x*(1+x)*(k+1)/(2*x*(k+1)+(1+x)/ Q(k+1))).
G.f.: 1/Q(0) where Q(k) = 1 - 2*k*x - x^2*(k + 1)^2/Q(k+1).
G.f.: T(0) where T(k) = 1 - x^2*(k+1)^2/(x^2*(k+1)^2-(1-2*x*k)*(1-2*x-2*x*k)/T(k+1)). (End)
0 = a(n)*(a(n+1) + a(n+2) - a(n+3)) + a(n+1)*(a(n+1) + 2*a(n+2) - a(n+3)) + a(n+2)*a(n+2) if n>=0. - Michael Somos, Jan 25 2014
a(n) = Sum_{k = 0..n} (-1)^(n-k)*binomial(n,k)*(k + x)^k*(k + x + 1)^(n-k) = Sum_{k = 0..n} (-1)^(n-k)*binomial(n,k)*(k + x)^(n-k)*(k + x - 1)^k, for arbitrary x. - Peter Bala, Feb 19 2017
From Peter Luschny, Jun 20 2017: (Start)
a(n) = Sum_{j=0..n} Sum_{k=0..n} binomial(-j-1, -n-1)*abs(Stirling1(j, k)).
a(n) = Sum_{k=0..n} (-1)^(n-k)*Pochhammer(n-k+1, k) (cf. A008279). (End)
a(n) = n! - Sum_{j=0..n-1} binomial(n,j) * a(j). - Alois P. Heinz, Jan 23 2019
Sum_{n>=2} 1/a(n) = A281682. - Amiram Eldar, Nov 09 2020
a(n) = KummerU(-n, -n, -1). - Peter Luschny, May 10 2022
a(n) = (-1)^n*Sum_{k=0..n} Bell(k)*Stirling1(n+1, k+1). - Mélika Tebni, Jul 05 2022
EXAMPLE
a(2) = 1, a(3) = 2 and a(4) = 9 since the possibilities are {BA}, {BCA, CAB} and {BADC, BCDA, BDAC, CADB, CDAB, CDBA, DABC, DCAB, DCBA}. - Henry Bottomley, Jan 17 2001
The Boolean complex of the complete graph K_4 is homotopy equivalent to the wedge of 9 3-spheres.
Necklace problem for n = 6: partitions without part 1 and M2 numbers for n = 6: there are A002865(6) = 4 such partitions, namely (6), (2,4), (3^2) and (2^3) in A-St order with the M2 numbers 5!, 90, 40 and 15, respectively, adding up to 265 = a(6). This corresponds to 1 necklace with 6 beads, two necklaces with 2 and 4 beads respectively, two necklaces with 3 beads each and three necklaces with 2 beads each. - Wolfdieter Lang, Jun 01 2010
G.f. = 1 + x^2 + 9*x^3 + 44*x^4 + 265*x^5 + 1854*x^6 + 14833*x^7 + 133496*x^8 + ...
MAPLE
A000166 := proc(n) option remember; if n<=1 then 1-n else (n-1)*(procname(n-1)+procname(n-2)); fi; end;
a:=n->n!*sum((-1)^k/k!, k=0..n): seq(a(n), n=0..21); # Zerinvary Lajos, May 17 2007
ZL1:=[S, {S=Set(Cycle(Z, card>1))}, labeled]: seq(count(ZL1, size=n), n=0..21); # Zerinvary Lajos, Sep 26 2007
with (combstruct):a:=proc(m) [ZL, {ZL=Set(Cycle(Z, card>=m))}, labeled]; end: A000166:=a(2):seq(count(A000166, size=n), n=0..21); # Zerinvary Lajos, Oct 02 2007
Z := (x, m)->m!^2*sum(x^j/((m-j)!^2), j=0..m): R := (x, n, m)->Z(x, m)^n: f := (t, n, m)->sum(coeff(R(x, n, m), x, j)*(t-1)^j*(n*m-j)!, j=0..n*m): seq(f(0, n, 1), n=0..21); # Zerinvary Lajos, Jan 22 2008
a:=proc(n) if `mod`(n, 2)=1 then sum(2*k*factorial(n)/factorial(2*k+1), k=1.. floor((1/2)*n)) else 1+sum(2*k*factorial(n)/factorial(2*k+1), k=1..floor((1/2)*n)-1) end if end proc: seq(a(n), n=0..20); # Emeric Deutsch, Feb 23 2008
G(x):=2*exp(-x)/(1-x): f[0]:=G(x): for n from 1 to 26 do f[n]:=diff(f[n-1], x) od: x:=0: seq(f[n]/2, n=0..21); # Zerinvary Lajos, Apr 03 2009
seq(simplify(KummerU(-n, -n, -1)), n = 0..23); # Peter Luschny, May 10 2022
MATHEMATICA
a[0] = 1; a[n_] := n*a[n - 1] + (-1)^n; a /@ Range[0, 21] (* Robert G. Wilson v *)
a[0] = 1; a[1] = 0; a[n_] := Round[n!/E] /; n >= 1 (* Michael Taktikos, May 26 2006 *)
Range[0, 20]! CoefficientList[ Series[ Exp[ -x]/(1 - x), {x, 0, 20}], x]
dr[{n_, a1_, a2_}]:={n+1, a2, n(a1+a2)}; Transpose[NestList[dr, {0, 0, 1}, 30]][[3]] (* Harvey P. Dale, Feb 23 2013 *)
a[n_] := (-1)^n HypergeometricPFQ[{- n, 1}, {}, 1]; (* Michael Somos, Jun 01 2013 *)
a[n_] := n! SeriesCoefficient[Exp[-x] /(1 - x), {x, 0, n}]; (* Michael Somos, Jun 01 2013 *)
Table[Subfactorial[n], {n, 0, 21}] (* Jean-François Alcover, Jan 10 2014 *)
RecurrenceTable[{a[n] == n*a[n - 1] + (-1)^n, a[0] == 1}, a, {n, 0, 23}] (* Ray Chandler, Jul 30 2015 *)
Subfactorial[Range[0, 20]] (* Eric W. Weisstein, Dec 31 2017 *)
nxt[{n_, a_}]:={n+1, a(n+1)+(-1)^(n+1)}; NestList[nxt, {0, 1}, 25][[All, 2]] (* Harvey P. Dale, Jun 01 2019 *)
PROG
(PARI) {a(n) = if( n<1, 1, n * a(n-1) + (-1)^n)}; /* Michael Somos, Mar 24 2003 */
(PARI) {a(n) = n! * polcoeff( exp(-x + x * O(x^n)) / (1 - x), n)}; /* Michael Somos, Mar 24 2003 */
(PARI) {a(n)=polcoeff(sum(m=0, n, m^m*x^m/(1+(m+1)*x+x*O(x^n))^(m+1)), n)} /* Paul D. Hanna */
(PARI) A000166=n->n!*sum(k=0, n, (-1)^k/k!) \\ M. F. Hasler, Jan 26 2012
(PARI) a(n)=if(n, round(n!/exp(1)), 1) \\ Charles R Greathouse IV, Jun 17 2012
(Python) See Hobson link.
(Maxima)
s[0]:1$
s[n]:=n*s[n-1]+(-1)^n$
makelist(s[n], n, 0, 12); /* Emanuele Munarini, Mar 01 2011 */
(Haskell)
a000166 n = a000166_list !! n
a000166_list = 1 : 0 : zipWith (*) [1..]
(zipWith (+) a000166_list $ tail a000166_list)
-- Reinhard Zumkeller, Dec 09 2012
(Python)
A000166_list, m, x = [], 1, 1
for n in range(10*2):
x, m = x*n + m, -m
A000166_list.append(x) # Chai Wah Wu, Nov 03 2014
(Magma) I:=[0, 1]; [1] cat [n le 2 select I[n] else (n-1)*(Self(n-1)+Self(n-2)): n in [1..30]]; // Vincenzo Librandi, Jan 07 2016
CROSSREFS
Cf. A000142, A002467, A003221, A000522, A000240, A000387, A000449, A000475, A129135, A092582, A000255, A002469, A159610, A068985, A068996, A047865, A038205, A008279, A281682.
A001120 has a similar recurrence.
KEYWORD
core,nonn,easy,nice
AUTHOR
EXTENSIONS
Minor edits by M. F. Hasler, Jan 16 2017
STATUS
approved
Triangle T(n,k) of rencontres numbers (number of permutations of n elements with k fixed points).
+10
115
115
1, 0, 1, 1, 0, 1, 2, 3, 0, 1, 9, 8, 6, 0, 1, 44, 45, 20, 10, 0, 1, 265, 264, 135, 40, 15, 0, 1, 1854, 1855, 924, 315, 70, 21, 0, 1, 14833, 14832, 7420, 2464, 630, 112, 28, 0, 1, 133496, 133497, 66744, 22260, 5544, 1134, 168, 36, 0, 1, 1334961, 1334960, 667485, 222480, 55650, 11088, 1890, 240, 45, 0, 1
OFFSET
0,7
COMMENTS
This is a binomial convolution triangle (Sheffer triangle) of the Appell type: (exp(-x)/(1-x),x), i.e., the e.g.f. of column k is (exp(-x)/(1-x))*(x^k/k!). See the e.g.f. given by V. Jovovic below. - Wolfdieter Lang, Jan 21 2008
The formula T(n,k) = binomial(n,k)*A000166(n-k), with the derangements numbers (subfactorials) A000166 (see also the Charalambides reference) shows the Appell type of this triangle. - Wolfdieter Lang, Jan 21 2008
T(n,k) is the number of permutations of {1,2,...,n} having k pairs of consecutive right-to-left minima (0 is considered a right-to-left minimum for each permutation). Example: T(4,2)=6 because we have 1243, 1423, 4123, 1324, 3124 and 2134; for example, 1324 has right-to-left minima in positions 0-1,3-4 and 2134 has right-to-left minima in positions 0,2-3-4, the consecutive ones being joined by "-". - Emeric Deutsch, Mar 29 2008
T is an example of the group of matrices outlined in the table in A132382--the associated matrix for the sequence aC(0,1). - Tom Copeland, Sep 10 2008
A refinement of this triangle is given by A036039. - Tom Copeland, Nov 06 2012
This triangle equals (A211229(2*n,2*k)) n,k >= 0. - Peter Bala, Dec 17 2014
REFERENCES
Ch. A. Charalambides, Enumerative Combinatorics, Chapman & Hall/CRC, Boca Raton, Florida, 2002, p. 173, Table 5.2 (without row n=0 and column k=0).
R. L. Graham, D. E. Knuth and O. Patashnik, Concrete Mathematics. Addison-Wesley, Reading, MA, 1990, p. 194.
Arnold Kaufmann, Introduction à la combinatorique en vue des applications, Dunod, Paris, 1968. See p. 92.
J. Riordan, An Introduction to Combinatorial Analysis, Wiley, 1958, p. 65.
LINKS
Alois P. Heinz, Rows n = 0..150, flattened (first 51 rows from T. D. Noe)
Taha Akbari, Prove using combinatorics Sum_{k=0..n} (k-1)^2 D_n(k)=n!, Mathematics Stack Exchange, Jun 06 2017
Paul Barry, General Eulerian Polynomials as Moments Using Exponential Riordan Arrays, Journal of Integer Sequences, 16 (2013), #13.9.6.
Stefano Capparelli, Margherita Maria Ferrari, Emanuele Munarini, and Norma Zagaglia Salvi, A Generalization of the "Problème des Rencontres", J. Int. Seq. 21 (2018), #18.2.8.
Bhadrachalam Chitturi and Krishnaveni K S, Adjacencies in Permutations, arXiv preprint arXiv:1601.04469 [cs.DM], 2016. See Table 1.
S. K. Das and N. Deo, Rencontres graphs: a family of bipartite graphs, Fib. Quart., Vol. 25, No. 3, August 1987, 250-262.
Robert W. Donley Jr, Binomial arrays and generalized Vandermonde identities, arXiv:1905.01525 [math.CO], 2019.
FindStat - Combinatorial Statistic Finder, The number of adjacencies of a permutation, 0 appended, The number of fixed points of a permutation
I. Kaplansky, Symbolic solution of certain problems in permutations, Bull. Amer. Math. Soc., 50 (1944), 906-914.
J. Liese and J. Remmel, Q-analogues of the number of permutations with k-excedances, PU. M. A. Vol. 21 (2010), No. 2, pp. 285-320 (see E_{n,0}(x) in Table 1 p. 291).
L. Takacs, On the "problème des ménages", Discr. Math. 36 (3) (1981) 289-297, Table 2.
Wikipedia, Rencontres numbers.
FORMULA
T(n, k) = T(n-1, k)*n + binomial(n, k)*(-1)^(n-k) = T(n, k-1)/k + binomial(n, k)*(-1)^(n-k)/(n-k+1) = T(n-1, k-1)*n/k = T(n-k, 0)*binomial(n, k) = A000166(n-k)*binomial(n,k) [with T(0, 0) = 1]; so T(n, n) = 1, T(n, n-1) = 0, T(n, n-2) = n*(n-1)/2 for n >= 0.
Sum_{k=0..n} T(n, k) = Sum_{k=0..n} k * T(n, k) = n! for all n > 0, n, k integers. - Wouter Meeussen, May 29 2001
From Vladeta Jovovic, Aug 12 2002: (Start)
O.g.f. for k-th column: (1/k!)*Sum_{i>=k} i!*x^i/(1+x)^(i+1).
O.g.f. for k-th row: k!*Sum_{i=0..k} (-1)^i/i!*(1-x)^i. (End)
E.g.f.: exp((y-1)*x)/(1-x). - Vladeta Jovovic, Aug 18 2002
E.g.f. for number of permutations with exactly k fixed points is x^k/(k!*exp(x)*(1-x)). - Vladeta Jovovic, Aug 25 2002
Sum_{k=0..n} T(n, k)*x^k is the permanent of the n X n matrix with x's on the diagonal and 1's elsewhere; for x = 0, 1, 2, 3, 4, 5, 6 see A000166, A000142, A000522, A010842, A053486, A053487, A080954. - Philippe Deléham, Dec 12 2003; for x = 1+i see A009551 and A009102. - John M. Campbell, Oct 11 2011
T(n, k) = Sum_{j=0..n} A008290(n, j)*k^(n-j) is the permanent of the n X n matrix with 1's on the diagonal and k's elsewhere; for k = 0, 1, 2 see A000012, A000142, A000354. - Philippe Deléham, Dec 13 2003
T(n,k) = Sum_{j=0..n} (-1)^(j-k)*binomial(j,k)*n!/j!. - Paul Barry, May 25 2006
T(n,k) = (n!/k!)*Sum_{j=0..n-k} ((-1)^j)/j!, 0 <= k <= n. From the Appell type of the triangle and the subfactorial formula.
T(n,0) = n*Sum_{j=0..n-1} (j/(j+1))*T(n-1,j), T(0,0)=1. From the z-sequence of this Sheffer triangle z(j)=j/(j+1) with e.g.f. (1-exp(x)*(1-x))/x. See the W. Lang link under A006232 for Sheffer a- and z-sequences. - Wolfdieter Lang, Jan 21 2008
T(n,k) = (n/k)*T(n-1,k-1) for k >= 1. See above. From the a-sequence of this Sheffer triangle a(0)=1, a(n)=0, n >= 1 with e.g.f. 1. See the W. Lang link under A006232 for Sheffer a- and z-sequences. - Wolfdieter Lang, Jan 21 2008
From Henk P. J. van Wijk, Oct 29 2012: (Start)
T(n,k) = T(n-1,k)*(n-1-k) + T(n-1,k+1)*(k+1) for k=0 and
T(n,k) = T(n-1,k-1) + T(n-1,k)*(n-1-k) + T(n-1,k+1)*(k+1) for k>=1.
(End)
T(n,k) = A098825(n,n-k). - Reinhard Zumkeller, Dec 16 2013
Sum_{k=0..n} k^2 * T(n, k) = 2*n! if n > 1. - Michael Somos, Jun 06 2017
From Tom Copeland, Jul 26 2017: (Start)
The lowering and raising operators of this Appell sequence of polynomials P(n,x) are L = d/dx and R = x + d/dL log[exp(-L)/(1-L)] = x-1 + 1/(1-L) = x + L + L^2 - ... such that L P(n,x) = n P(n-1,x) and R P(n,x) = P(n+1,x).
P(n,x) = (1-L)^(-1) exp(-L) x^n = (1+L+L^2+...)(x-1)^n = n! Sum_{k=0..n} (x-1)^k / k!.
The polynomials of this pair P_n(x) and Q_n(x) are umbral compositional inverses; i.e., P_n(Q.(x)) = x^n = Q_n(P.(x)), where, e.g., (Q.(x))^n = Q_n(x).
For more on the infinitesimal generator, noted by Bala below, see A238385. (End)
Sum_{k=0..n} k^m * T(n,k) = A000110(m)*n! if n >= m. - Zhujun Zhang, May 24 2019
Sum_{k=0..n} (k+1) * T(n,k) = A098558(n). - Alois P. Heinz, Mar 11 2022
From Alois P. Heinz, May 20 2023: (Start)
Sum_{k=0..n} (-1)^k * T(n,k) = A000023(n).
Sum_{k=0..n} (-1)^k * k * T(n,k) = A335111(n). (End)
EXAMPLE
exp((y-1)*x)/(1-x) = 1 + y*x + (1/2!)*(1+y^2)*x^2 + (1/3!)*(2 + 3*y + y^3)*x^3 + (1/4!)*(9 + 8*y + 6*y^2 + y^4)*x^4 + (1/5!)*(44 + 45*y + 20*y^2 + 10*y^3 + y^5)*x^5 + ...
Triangle begins:
1
0 1
1 0 1
2 3 0 1
9 8 6 0 1
44 45 20 10 0 1
265 264 135 40 15 0 1
1854 1855 924 315 70 21 0 1
14833 14832 7420 2464 630 112 28 0 1
133496 133497 66744 22260 5544 1134 168 36 0 1
...
From Peter Bala, Feb 13 2017: (Start)
The infinitesimal generator has integer entries given by binomial(n,k)*(n-k-1)! for n >= 2 and 0 <= k <= n-2 and begins
0
0 0
1 0 0
2 3 0 0
6 8 6 0 0
24 30 20 10 0 0
...
MAPLE
T:= proc(n, k) T(n, k):= `if`(k=0, `if`(n<2, 1-n, (n-1)*
(T(n-1, 0)+T(n-2, 0))), binomial(n, k)*T(n-k, 0))
end:
seq(seq(T(n, k), k=0..n), n=0..12); # Alois P. Heinz, Mar 15 2013
MATHEMATICA
a[0] = 1; a[1] = 0; a[n_] := Round[n!/E] /; n >= 1 size = 8; Table[Binomial[n, k]a[n - k], {n, 0, size}, {k, 0, n}] // TableForm (* Harlan J. Brothers, Mar 19 2007 *)
T[n_, k_] := Subfactorial[n-k]*Binomial[n, k]; Table[T[n, k], {n, 0, 10}, {k, 0, n}] // Flatten (* Jean-François Alcover, Jul 12 2017 *)
T[n_, k_] := If[n<1, Boole[n==0 && k==0], T[n, k] = T[n-1, k-1] + T[n-1, k]*(n-1-k) + T[n-1, k+1]*(k+1)]; (* Michael Somos, Sep 13 2024 *)
PROG
(PARI) {T(n, k) = if(k<0 || k>n, 0, n!/k! * sum(i=0, n-k, (-1)^i/i!))}; /* Michael Somos, Apr 26 2000 */
(Haskell)
a008290 n k = a008290_tabl !! n !! k
a008290_row n = a008290_tabl !! n
a008290_tabl = map reverse a098825_tabl
-- Reinhard Zumkeller, Dec 16 2013
CROSSREFS
KEYWORD
AUTHOR
EXTENSIONS
Comments and more terms from Michael Somos, Apr 26 2000 and Christian G. Bower, Apr 26 2000
STATUS
approved
Rencontres numbers: number of permutations of [n] with exactly one fixed point.
(Formerly M2763 N1111)
(Formerly M2763 N1111)
+10
37
37
1, 0, 3, 8, 45, 264, 1855, 14832, 133497, 1334960, 14684571, 176214840, 2290792933, 32071101048, 481066515735, 7697064251744, 130850092279665, 2355301661033952, 44750731559645107, 895014631192902120, 18795307255050944541, 413496759611120779880
OFFSET
1,3
COMMENTS
a(n) is also the number of permutations of [n] having no circular succession. A circular succession in a permutation p of [n] is either a pair p(i), p(i+1), where p(i+1)=p(i)+1 or the pair p(n), p(1) if p(1)=p(n)+1. a(4)=8 because we have 1324, 1432, 4132, 2143, 2413, 3214, 3241, and 4321. - Emeric Deutsch, Sep 06 2010
a(n) is also the number of permutations of [n] having no substring in {12, 23, ..., (n-1)n, n1}. For example, a(4) = 8 since we have 1324, 1432, 4213, 2143, 2431, 3214, 3142, 4321 (different from permutations having no circular succession). - Enrique Navarrete, Oct 07 2016
a(n-1) is also the number of permutations of [n] that allow the substring n1 in the set of permutations of [n] having no substring in {12, 23, ..., (n-1)n}. For example, for n=5 the 8 permutations in S5 having no substring in {12,23,34,45} that allow the substring 51 are {51324,51432,25143,24351,35142,32514,42513,43251} (see link). - Enrique Navarrete, Jan 11 2017
From Enrique Navarrete, Mar 25 2017: (Start)
Let D(n,k) be the set of permutations on [n] that for fixed k, 0 < k < n, avoid substrings j(j+k) for 1 <= j <= n - k, and avoid substrings j(j+k) (mod n) for n-k < j <= n. Then the number of permutations in D(n,k) with k relative prime to n, n>=2, is given by a(n). For example, the forbidden substrings in D(4,3) are {14;21,32,43} (the forbidden substrings (mod 4) are written after the semicolon and lie below the diagonal in the chessboard below):
1 2 3 4
1 |_|_|_|x|
2 |x|_|_|_|
3 |_|x|_|_|
4 |_|_|x|_|
_
Then since 4 and 3 are relatively prime, a(4)=8, and the permutations in D(4,3) are 1234, 1342, 2341, 2413, 3124, 3412, 4123, 4231.
For another example, the forbidden substrings in D(8,5) are {16,27,38;41, 52,63,74,85} and the number of permutations in D(8,5) is a(8)=14832 (see the "K-Shift Forbidden Substrings" link).
(End)
REFERENCES
Kaufmann, Arnold. "Introduction à la combinatorique en vue des applications." Dunod, Paris, 1968. See p. 92.
J. Riordan, An Introduction to Combinatorial Analysis, Wiley, 1958, p. 65.
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).
N. Ya. Vilenkin, Combinatorics, p. 56, eq.(13), F_n = a(n). Academic Press, 1971.
LINKS
T. D. Noe, Table of n, a(n) for n=1..100
Bhadrachalam Chitturi and Krishnaveni K S, Adjacencies in Permutations, arXiv preprint arXiv:1601.04469 [cs.DM], 2016.
S. K. Das and N. Deo, Rencontres graphs: a family of bipartite graphs, Fib. Quart., Vol. 25, No. 3, August 1987, 250-262.
FindStat - Combinatorial Statistic Finder, The number of fixed points of a permutation
I. Kaplansky, Symbolic solution of certain problems in permutations, Bull. Amer. Math. Soc., 50 (1944), 906-914.
Enrique Navarrete, Forbidden Patterns and the Alternating Derangement Sequence, arXiv:1610.01987 [math.CO], 2016.
Enrique Navarrete, Generalized K-Shift Forbidden Substrings in Permutations, arXiv:1610.06217 [math.CO], 2016.
S. M. Tanny, Permutations and successions, J. Combinatorial Theory, Series A, 21 (1976), 196-202.
FORMULA
E.g.f.: x*exp(-x)/(1-x). [Corrected by Vaclav Kotesovec, Sep 26 2012]
a(n) = Sum_{k=0..n-1} (-1)^k*n!/k!.
a(n) = A180188(n,0). - Emeric Deutsch, Sep 06 2010
E.g.f.: x*A(x) where A(x) is the e.g.f. for A000166. - Geoffrey Critzer, Jan 14 2012
a(n) = n*a(n-1) - (-1)^n*n = A000166(n) - (-1)^n = n*A000166(n-1) = A000387(n+1)*2/(n+1) = A000449(n+2)*6/((n+1)*(n+2)).
a(n) = n*floor(((n-1)!+1)/e), n > 1. - Gary Detlefs, Jul 13 2010
Limit_{n->infinity} n!/a(n) = e = 2.71828...
a(n) = (n-1)*(a(n-1)+a(n-2)) + (-1)^(n-1), n>=2. - Enrique Navarrete, Oct 07 2016
O.g.f.: Sum_{k>=1} k!*x^k/(1 + x)^(k+1). - Ilya Gutkovskiy, Apr 13 2017
a(n) = (-1)^(n-1)*n*hypergeom([1,1-n], [], 1). - Peter Luschny, May 09 2017
EXAMPLE
a(3) = 3 because the permutations of {1,2,3} with exactly one fixed point are the transpositions (1 2), (1 3) and (2 3).
a(4) = 8 because for each element x of {1,2,3,4} there are exactly two permutations which leave only x invariant, namely the two circular permutations of the three remaining numbers, one being the inverse (and the square) of the other. - M. F. Hasler, Jan 16 2017
MAPLE
G(x):=exp(-x)/(1-x)*x: f[0]:=G(x): for n from 1 to 26 do f[n]:=diff(f[n-1], x) od: x:=0: seq(f[n], n=1..22); # Zerinvary Lajos, Apr 03 2009
A000240 := proc(n)
n!*add((-1)^k/k!, k=0..n-1) ;
end proc: # R. J. Mathar, Jul 09 2012
a := n -> (-1)^(n-1)*n*hypergeom([1, 1-n], [], 1):
seq(simplify(a(n)), n=1..22); # Peter Luschny, May 09 2017
MATHEMATICA
Table[Subfactorial[n]-(-1)^n, {n, 1, 25}] (* Zerinvary Lajos, Jul 10 2009, updated for offset 1 by Jean-François Alcover, Jan 10 2014 *)
Table[n!*Sum[(-1)^k/k!, {k, 0, n-1}], {n, 1, 25}] (* Vaclav Kotesovec, Sep 26 2012 *)
Table[n!*SeriesCoefficient[x*E^(-x)/(1-x), {x, 0, n}], {n, 1, 25}] (* Vaclav Kotesovec, Sep 26 2012 *)
PROG
(Python)
a = 0
for i in range(1, 51):
a = (a - (-1)**i)*i
print(a, end=', ') # Alex Ratushnyak, Apr 20 2012
(PARI) x='x+O('x^66); Vec( serlaplace(x*exp(-x)/(1-x)) ) \\ Joerg Arndt, Feb 19 2014
(PARI) a(n, p=vector(n, i, i), s=x->!x)=sum(k=1, n!, #select(s, numtoperm(n, k)-p)==1) \\ For illustrative purpose. #select(...) is almost twice as fast as {p=numtoperm(n, k); sum(i=1, n, p[i]==i)}. - M. F. Hasler, Jan 16 2017
CROSSREFS
KEYWORD
nonn,easy,nice
AUTHOR
STATUS
approved
Triangle of rencontres numbers.
+10
26
26
1, 2, 3, 9, 8, 6, 44, 45, 20, 10, 265, 264, 135, 40, 15, 1854, 1855, 924, 315, 70, 21, 14833, 14832, 7420, 2464, 630, 112, 28, 133496, 133497, 66744, 22260, 5544, 1134, 168, 36, 1334961, 1334960, 667485, 222480, 55650, 11088, 1890, 240, 45, 14684570
OFFSET
2,2
COMMENTS
T(n,k) = number of permutations of n elements with k fixed points.
T(n,n-1)=0 and T(n,n)=1 are omitted from the array. - Geoffrey Critzer, Nov 28 2011.
REFERENCES
R. L. Graham, D. E. Knuth and O. Patashnik, Concrete Mathematics. Addison-Wesley, Reading, MA, 1990, p. 194.
Kaufmann, Arnold. "Introduction a la combinatorique en vue des applications." Dunod, Paris, 1968. See p. 92.
J. Riordan, An Introduction to Combinatorial Analysis, Wiley, 1958, p. 65.
LINKS
T. D. Noe, Rows n=2..50, flattened
FindStat - Combinatorial Statistic Finder, The number of fixed points of a permutation
I. Kaplansky, Symbolic solution of certain problems in permutations, Bull. Amer. Math. Soc., 50 (1944), 906-914.
FORMULA
E.g.f. for column k: (x^k/k!)(exp(-x)/(1-x)). - Geoffrey Critzer, Nov 28 2011
Row generating polynomials appear to be given by -1 + sum {k = 0..n} (-1)^(n+k)*C(n,k)*(1+k*x)^(n-k)*(2+(k-1)*x)^k. - Peter Bala, Dec 29 2011
EXAMPLE
Triangle begins:
1
2 3
9 8 6
44 45 20 10
265 264 135 40 15
1854 1855 924 315 70 21
14833 14832 7420 2464 630 112 28
133496 133497 66744 22260 5544 1134 168 36
...
MAPLE
T:= proc(n, k) T(n, k):= `if`(k=0, `if`(n<2, 1-n, (n-1)*
(T(n-1, 0)+T(n-2, 0))), binomial(n, k)*T(n-k, 0))
end:
seq(seq(T(n, k), k=0..n-2), n=2..12); # Alois P. Heinz, Mar 17 2013
MATHEMATICA
Prepend[Flatten[f[list_]:=Select[list, #>1&]; Map[f, Drop[Transpose[Table[d = Exp[-x]/(1 - x); Range[0, 10]! CoefficientList[Series[d x^k/k!, {x, 0, 10}], x], {k, 0, 8}]], 3]]], 1] (* Geoffrey Critzer, Nov 28 2011 *)
PROG
(PARI) T(n, k)= if(k<0 || k>n, 0, n!/k!*sum(i=0, n-k, (-1)^i/i!))
CROSSREFS
KEYWORD
AUTHOR
EXTENSIONS
Comments and more terms from Michael Somos, Apr 26 2000
STATUS
approved
a(n) = n*(-1)^n.
+10
21
21
0, -1, 2, -3, 4, -5, 6, -7, 8, -9, 10, -11, 12, -13, 14, -15, 16, -17, 18, -19, 20, -21, 22, -23, 24, -25, 26, -27, 28, -29, 30, -31, 32, -33, 34, -35, 36, -37, 38, -39, 40, -41, 42, -43, 44, -45, 46, -47, 48, -49, 50, -51, 52, -53, 54, -55, 56, -57, 58, -59, 60, -61, 62, -63, 64, -65
OFFSET
0,3
COMMENTS
a(n) is the determinant of the (n+1) X (n+1) matrix with 0's in the main diagonal and 1's elsewhere. - Franz Vrabec, Dec 01 2007
Sum_{n>0} 1/a(n) = -log(2). - Jaume Oliver Lafont, Feb 24 2009
Pisano period lengths: 1, 2, 6, 4, 10, 6, 14, 8, 18, 10, 22, 12, 26, 14, 30, 16, 34, 18, 38, 20, ... (is this A066043?). - R. J. Mathar, Aug 10 2012
a(n) is the determinant of the (n+1) X (n+1) matrix whose i-th row, j-th column entry is the value of the cubic residue symbol ((j-i)/p) where p is a prime of the form 3k+2 and n < p. - Ryan Wood, Nov 09 2017
a(n-1) is the difference in the number of even minus odd parity derangements (permutations with no fixed points) in symmetric group S_n. - Julian Hatfield Iacoponi, Aug 01 2024
LINKS
Vincenzo Librandi, Table of n, a(n) for n = 0..2000
Tanya Khovanova, Recursive Sequences
László Németh, The trinomial transform triangle, J. Int. Seqs., Vol. 21 (2018), Article 18.7.3. Also arXiv:1807.07109 [math.NT], 2018.
Index entries for linear recurrences with constant coefficients, signature (-2,-1).
FORMULA
G.f.: -x/(1+x)^2.
E.g.f: -x*exp(-x).
a(n) = -2*a(n-1) - a(n-2) for n >= 2. - Jaume Oliver Lafont, Feb 24 2009
MATHEMATICA
Array[# (-1)^# &, 66, 0] (* Michael De Vlieger, Nov 18 2017 *)
Table[If[EvenQ[n], n, -n], {n, 0, 70}] (* Harvey P. Dale, Jan 17 2022 *)
PROG
(Magma) [n*(-1)^n: n in [0..80]]; // Vincenzo Librandi, Jun 08 2011
(PARI) a(n)=n*(-1)^n \\ Charles R Greathouse IV, Dec 07 2011
(Haskell)
a038608 n = n * (-1) ^ n
a038608_list = [0, -1] ++ map negate
(zipWith (+) a038608_list (map (* 2) $ tail a038608_list))
-- Reinhard Zumkeller, Nov 24 2012
(Python)
def A038608(n): return -n if n&1 else n # Chai Wah Wu, Nov 14 2022
KEYWORD
sign,easy
AUTHOR
Vasiliy Danilov (danilovv(AT)usa.net), Jul 1998
EXTENSIONS
Edited by Frank Ellermann, Jan 28 2002
STATUS
approved
Take the permutations of lengths 1, 2, 3, ... arranged lexicographically, and replace each permutation with the number of its fixed points.
+10
19
19
1, 2, 0, 3, 1, 1, 0, 0, 1, 4, 2, 2, 1, 1, 2, 2, 0, 1, 0, 0, 1, 1, 0, 2, 1, 0, 0, 0, 1, 1, 2, 0, 0, 5, 3, 3, 2, 2, 3, 3, 1, 2, 1, 1, 2, 2, 1, 3, 2, 1, 1, 1, 2, 2, 3, 1, 1, 3, 1, 1, 0, 0, 1, 2, 0, 1, 0, 0, 1, 1, 0, 2, 1, 0, 0, 0, 1, 1, 2, 0, 0, 2, 0, 1, 0, 0, 1, 3, 1, 2, 1, 1, 2, 1, 0, 1, 0, 0, 0, 0, 1, 0, 1, 0, 0
OFFSET
1,2
COMMENTS
Length of n-th row = sum of n-th row = n!; number of zeros in n-th row = A000166(n); number of positive terms in n-th row = A002467(n). [Reinhard Zumkeller, Mar 29 2012]
LINKS
Reinhard Zumkeller, Rows n=1..7 of triangle, flattened
FindStat - Combinatorial Statistic Finder, The number of fixed points of a permutation
EXAMPLE
123,132,213,231,312,321 (corresponding to 3rd row of triangle A030298) have respectively 3,1,1,0,0,1 fixed points.
PROG
(Haskell)
import Data.List (permutations, sort)
a170942 n k = a170942_tabf !! (n-1) (k-1)
a170942_row n = map fps $ sort $ permutations [1..n] where
fps perm = sum $ map fromEnum $ zipWith (==) perm [1..n]
a170942_tabf = map a170942_row [1..]
-- Reinhard Zumkeller, Mar 29 2012
CROSSREFS
KEYWORD
nonn,tabf
AUTHOR
Neven Juric (neven.juric(AT)apis-it.hr) and N. J. A. Sloane, Feb 23 2010
EXTENSIONS
a(36)-a(105) from John W. Layman, Feb 23 2010
Keyword tabf added by Reinhard Zumkeller, Mar 29 2012
STATUS
approved
Number of even permutations of length n with no fixed points.
(Formerly M0922)
(Formerly M0922)
+10
11
11
OFFSET
0,4
REFERENCES
N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).
LINKS
Vincenzo Librandi, Table of n, a(n) for n = 0..100
Bashir Ali and A. Umar, Some combinatorial properties of the alternating group, Southeast Asian Bulletin Math. 32 (2008), 823-830. [From Abdullahi Umar, Oct 09 2008]
L. Carlitz and R. A. Scoville, Problem E2354, Amer. Math. Monthly, 79 (1972), 394.
G. Gordon and E. McMahon, Moving faces to other places: facet derangements, Amer. Math. Monthly, 117 (2010), 865-88.
G. Gordon and E. McMahon, Moving faces to other places: facet derangements, arXiv:0906.4253 [math.CO], 2009.
Karen Meagher, Peter Sin, All 2-transitive groups have the EKR-module property, arXiv:1911.11252 [math.CO], 2019.
Piotr Miska, Arithmetic Properties of the Sequence of Derangements and its Generalizations, arXiv:1508.01987 [math.NT], 2015. (see Chapter 5 p. 44)
J. M. Thomas, The number of even and odd absolute permutations of n letters, Bull. Amer. Math. Soc. 31 (1925), 303-304.
FORMULA
a(n) = (A000166(n)-(-1)^n*(n-1))/2.
From Abdullahi Umar, Oct 09 2008: (Start)
a(n) = (n!/2)*sum(((-1)^i)/i!, i=0..n-2)+((-1)^(n-1))*(n-1) for n>1, a(0)=1, a(1)=0.
a(n) = (n-1)*(a(n-1)+a(n-2))+((-1)^(n-1))*(n-1) for n>1, a(0)=1, a(1)=0.
a(n) = n*a(n-1)+((-1)^(n-1))*(n-2)*(n+1)/2 for n>0, a(0)=1.
E.g.f.: (1-x^2/2)*exp(-x)/(1-x). (End)
MAPLE
A003221 := n -> ((-1)^n*hypergeom([-n, 1], [], 1)-(-1)^n*(n-1))/2:
seq(simplify(A003221(n)), n=0..22); # Peter Luschny, May 09 2017
MATHEMATICA
a[n_] := (Round[n!/E] - (-1)^n*(n - 1))/2; a[0] = 1; Table[a[n], {n, 0, 22}] (* Jean-François Alcover, Dec 13 2011, after Simon Plouffe *)
Range[0, 25]! CoefficientList[Series[(1 - x^2 / 2) E^(-x) / (1 - x), {x, 0, 25}], x] (* Vincenzo Librandi, Aug 11 2015 *)
PROG
(Python)
from __future__ import division
A003221_list, m, x = [], -1, 0
for n in range(10*2):
....x, m = x*n + m*(n*(n-1)//2-1), -m
....A003221_list.append(x) # Chai Wah Wu, Nov 03 2014
(PARI) a(n) = ( n!*sum(r=2, n, (-1)^r/r!) + (-1)^(n-1)*(n-1))/2; \\ Michel Marcus, Apr 22 2016
KEYWORD
nonn,easy,nice
AUTHOR
EXTENSIONS
Typo in second formula fixed by Josh Swanson, Nov 10 2013
STATUS
approved
Regard triangle of rencontres numbers (see A008290) as infinite matrix, compute inverse, read by rows.
+10
11
11
1, 0, 1, -1, 0, 1, -2, -3, 0, 1, -3, -8, -6, 0, 1, -4, -15, -20, -10, 0, 1, -5, -24, -45, -40, -15, 0, 1, -6, -35, -84, -105, -70, -21, 0, 1, -7, -48, -140, -224, -210, -112, -28, 0, 1, -8, -63, -216, -420, -504, -378, -168, -36, 0, 1, -9, -80, -315, -720
OFFSET
0,7
COMMENTS
The n-th row consists of coefficients of the characteristic polynomial of the adjacency matrix of the complete n-graph.
Triangle of coefficients of det(M(n)) where M(n) is the n X n matrix m(i,j)=x if i=j, m(i,j)=i/j otherwise. - Benoit Cloitre, Feb 01 2003
T is an example of the group of matrices outlined in the table in A132382--the associated matrix for rB(0,1). The e.g.f. for the row polynomials is exp(x*t) * exp(x) *(1-x). T(n,k) = Binomial(n,k)* s(n-k) where s = (1,0,-1,-2,-3,...) with an e.g.f. of exp(x)*(1-x) which is the reciprocal of the e.g.f. of A000166. - Tom Copeland, Sep 10 2008
Row sums are: {1, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, ...}. - Roger L. Bagula, Feb 20 2009
T is related to an operational calculus connecting an infinitesimal generator for fractional integro-derivatives with the values of the Riemann zeta function at positive integers (see MathOverflow links). - Tom Copeland, Nov 02 2012
The submatrix below the null subdiagonal is signed and row reversed A127717. The submatrix below the diagonal is A074909(n,k)s(n-k) where s(n)= -n, i.e., multiply the n-th diagonal by -n. A074909 and its reverse A135278 have several combinatorial interpretations. - Tom Copeland, Nov 04 2012
T(n,k) is the difference between the number of even (A145224) and odd (A145225) permutations (of an n-set) with exactly k fixed points. - Julian Hatfield Iacoponi, Aug 08 2024
REFERENCES
Norman Biggs, Algebraic Graph Theory, 2nd ed. Cambridge University Press, 1993. p. 17.
J. Riordan, An Introduction to Combinatorial Analysis, Wiley, 1958, p.184 problem 3.
LINKS
M. Bhargava, K. Kedlaya, and L. Ng, Solutions to the 66th William Lowell Putnam Mathematical Competition Saturday, Dec 03 2005
FORMULA
G.f.: (x-n+1)*(x+1)^(n-1) = Sum_(k=0..n) T(n,k) x^k.
T(n, k) = (1-n+k)*binomial(n, k).
k-th column has o.g.f. x^k(1-(k+2)x)/(1-x)^(k+2). k-th row gives coefficients of (x-k)(x+1)^k. - Paul Barry, Jan 25 2004
T(n,k) = Coefficientslist[Det[Table[If[i == j, x, 1], {i, 1, n}, {k, 1, n}],x]. - Roger L. Bagula, Feb 20 2009
From Peter Bala, Aug 08 2011: (Start)
Given a permutation p belonging to the symmetric group S_n, let fix(p) be the number of fixed points of p and sign(p) its parity. The row polynomials R(n,x) have a combinatorial interpretation as R(n,x) = (-1)^n*Sum_{permutations p in S_n} sign(p)*(-x)^(fix(p)). An example is given below.
Note: The polynomials P(n,x) = Sum_{permutations p in S_n} x^(fix(p)) are the row polynomials of the rencontres numbers A008290. The integral results Integral_{x = 0..n} R(n,x) dx = n/(n+1) = Integral_{x = 0..-1} R(n,x) dx lead to the identities Sum_{p in S_n} sign(p)*(-n)^(1 + fix(p))/(1 + fix(p)) = (-1)^(n+1)*n/(n+1) = Sum_{p in S_n} sign(p)/(1 + fix(p)). The latter equality was Problem B6 in the 66th William Lowell Putnam Mathematical Competition 2005. (End)
From Tom Copeland, Jul 26 2017: (Start)
The e.g.f. in Copeland's 2008 comment implies this entry is an Appell sequence of polynomials P(n,x) with lowering and raising operators L = d/dx and R = x + d/dL log[exp(L)(1-L)] = x+1 - 1/(1-L) = x - L - L^2 - ... such that L P(n,x) = n P(n-1,x) and R P(n,x) = P(n+1,x).
P(n,x) = (1-L) exp(L) x^n = (1-L) (x+1)^n = (x+1)^n - n (x+1)^(n-1) = (x+1-n)(x+1)^(n-1) = (x+s.)^n umbrally, where (s.)^n = s_n = P(n,0).
The polynomials of this pair P_n(x) and Q_n(x) are umbral compositional inverses; i.e., P_n(Q.(x)) = x^n = Q_n(P.(x)), where, e.g., (Q.(x))^n = Q_n(x).
The exponential infinitesimal generator (infinigen) of this entry is the negated infinigen of A008290, the matrix (M) noted by Bala, related to A238363. Then e^M = [the lower triangular A008290], and e^(-M) = [the lower triangular A055137]. For more on the infinigens, see A238385. (End)
From the row g.f.s corresponding to Bagula's matrix example below, the n-th row polynomial has a zero of multiplicity n-1 at x = 1 and a zero at x = -n+1. Since this is an Appell sequence dP_n(x)/dx = n P_{n-1}(x), the critical points of P_n(x) have the same abscissas as the zeros of P_{n-1}(x); therefore, x = 1 is an inflection point for the polynomials of degree > 2 with P_n(1) = 0, and the one local extremum of P_n has the abscissa x = -n + 2 with the value (-n+1)^{n-1}, signed values of A000312. - Tom Copeland, Nov 15 2019
From Julian Hatfield Iacoponi, Aug 08 2024: (Start)
EXAMPLE
1; 0,1; -1,0,1; -2,-3,0,1; -3,-8,-6,0,1; ...
(Bagula's matrix has a different sign convention from the list.)
From Roger L. Bagula, Feb 20 2009: (Start)
{ 1},
{ 0, 1},
{-1, 0, 1},
{ 2, -3, 0, 1},
{-3, 8, -6, 0, 1},
{ 4, -15, 20, -10, 0, 1},
{-5, 24, -45, 40, -15, 0, 1},
{ 6, -35, 84, -105, 70, -21, 0, 1},
{-7, 48, -140, 224, -210, 112, -28, 0, 1},
{ 8, -63, 216, -420, 504, -378, 168, -36, 0, 1},
{-9, 80, -315, 720, -1050, 1008, -630, 240, -45, 0, 1}
(End)
R(3,x) = (-1)^3*Sum_{permutations p in S_3} sign(p)*(-x)^(fix(p)).
p | fix(p) | sign(p) | (-1)^3*sign(p)*(-x)^fix(p)
========+========+=========+===========================
(123) | 3 | +1 | x^3
(132) | 1 | -1 | -x
(213) | 1 | -1 | -x
(231) | 0 | +1 | -1
(312) | 0 | +1 | -1
(321) | 1 | -1 | -x
========+========+=========+===========================
| R(3,x) = x^3 - 3*x - 2
- Peter Bala, Aug 08 2011
MATHEMATICA
M[n_] := Table[If[i == j, x, 1], {i, 1, n}, {j, 1, n}]; a = Join[{{1}}, Flatten[Table[CoefficientList[Det[M[n]], x], {n, 1, 10}]]] (* Roger L. Bagula, Feb 20 2009 *)
t[n_, k_] := (k-n+1)*Binomial[n, k]; Table[t[n, k], {n, 0, 10}, {k, 0, n}] // Flatten (* Jean-François Alcover, Nov 29 2013, after Pari *)
PROG
(PARI) T(n, k)=(1-n+k)*if(k<0 || k>n, 0, n!/k!/(n-k)!)
CROSSREFS
KEYWORD
sign,tabl
AUTHOR
Christian G. Bower, Apr 25 2000
EXTENSIONS
Additional comments from Michael Somos, Jul 04 2002
STATUS
approved
Number of permutations of n elements with an even number of fixed points.
+10
7
7
1, 0, 2, 2, 16, 64, 416, 2848, 22912, 205952, 2060032, 22659328, 271913984, 3534877696, 49488295936, 742324422656, 11877190795264, 201912243453952, 3634420382302208, 69053987263479808, 1381079745270120448, 29002674650671480832, 638058842314774675456
OFFSET
0,3
COMMENTS
Let d(n) be the number of derangements of n elements (sequence A000166) then a(n) has the recursion: a(n) = d(n) + C(n,2)*d(n-2) + C(n,4)*d(n-4) + C(n,6)*d(n-6)... = A000166(n) + A000387(n) + A000475(n) + C(n,6)*d(n-6)... The E.g.f. for a(n) is: cosh(x) * exp(-x)/(1-x) and the asymptotic expression for a(n) is: a(n) ~ n! * (1 + 1/e^2)/2 i.e., as n goes to infinity the fraction of permutations that has an even number of fixed points is about (1 + 1/e^2)/2 = 0.567667...
LINKS
G. C. Greubel, Table of n, a(n) for n = 0..445
FORMULA
a(n) = Sum_{k=0..[n/2]} Sum_{l=0..(n-2*k)} (-1)^l * n!/((2*k)! * l!).
More generally, e.g.f. for number of degree-n permutations with an even number of k-cycles is cosh(x^k/k)*exp(-x^k/k)/(1-x). - Vladeta Jovovic, Jan 31 2006
E.g.f.: 1/(1-x)/(x*E(0)+1), where E(k) = 1 - x^2/( x^2 + (2*k+1)*(2*k+3)/E(k+1) ); (continued fraction ). - Sergei N. Gladkovskii, Dec 29 2013
MATHEMATICA
nn = 20; d = Exp[-x]/(1 - x); Range[0, nn]! CoefficientList[Series[Cosh[x] d, {x, 0, nn}], x] (* Geoffrey Critzer, Jan 14 2012 *)
Table[Sum[Sum[(-1)^j * n!/(j!*(2*k)!), {j, 0, n - 2*k}], {k, 0, Floor[n/2]}], {n, 0, 50}] (* G. C. Greubel, Aug 21 2017 *)
PROG
(PARI) for(n=0, 50, print1(sum(k=0, n\2, sum(j=0, n-2*k, (-1)^j*n!/(j!*(2*k)!))), ", ")) \\ G. C. Greubel, Aug 21 2017
CROSSREFS
KEYWORD
nonn
AUTHOR
Ahmed Fares (ahmedfares(AT)my-deja.com), Jul 04 2001
EXTENSIONS
More terms from Vladeta Jovovic, Jul 05 2001
STATUS
approved
Search completed in 0.033 seconds
Lookup
Welcome
Wiki
Register
Music
Plot 2
Demos
Index
WebCam
Contribute
Format
Style Sheet
Transforms
Superseeker
Recents
Maintained by The OEIS Foundation Inc.
Last modified October 21 08:27 EDT 2024. Contains 376969 sequences.