Displaying 1-10 of 71 results found.
Tribonacci equivalent of mousetrap sequence ( A002467).
+20
1
1, 1, 1, 9, 44, 270, 1938, 15764, 143776, 1453302, 16128420, 194980478, 2550746400, 35904118874, 541097840528, 8693290587030, 148324680742912, 2678504175897990, 51039398650102776, 1023458322628129882
COMMENTS
The mousetrap sequence ( A002467) can be defined in a Fibonacci-like way as: a(0) = a(1) = 1; for n>1 a(n) = n*(a(n-1)+a(n-2)). The current sequence is thus the tribonacci equivalent of that.
FORMULA
a(0) = a(1) = a(2) = 1; for n>2 a(n) = n*(a(n-1)+a(n-2)+a(n-3)).
MATHEMATICA
RecurrenceTable[{a[0]==a[1]==a[2]==1, a[n]==n(a[n-1]+a[n-2]+a[n-3])}, a, {n, 20}] (* Harvey P. Dale, Dec 25 2018 *)
0, 0, 3, 14, 75, 454, 3185, 25486, 229383, 2293838, 25232229, 302786758, 3936227867, 55107190150, 826607852265, 13225725636254, 224837335816335, 4047072044694046, 76894368849186893, 1537887376983737878
COMMENTS
n divides a(n) and a(n+2) for odd n. 2 divides a(n) for even n. - Alexander Adamchuk, Jan 11 2008
LINKS
E. W. Weisstein's World of Mathematics, Mousetrap.
MATHEMATICA
Denominator[k=1; NestList[1+1/(k++ #1)&, 1, 50]] - 1 (* Alexander Adamchuk, Jan 11 2008 *)
Triangle read by rows. Convolution triangle of A002467 (number of permutations with fixed points).
+20
0
1, 0, 1, 0, 1, 1, 0, 4, 2, 1, 0, 15, 9, 3, 1, 0, 76, 38, 15, 4, 1, 0, 455, 198, 70, 22, 5, 1, 0, 3186, 1182, 378, 112, 30, 6, 1, 0, 25487, 8115, 2274, 629, 165, 39, 7, 1, 0, 229384, 63266, 15439, 3840, 965, 230, 49, 8, 1, 0, 2293839, 554656, 117921, 25966, 6006, 1401, 308, 60, 9, 1
EXAMPLE
[0] 1;
[1] 0, 1;
[2] 0, 1, 1;
[3] 0, 4, 2, 1;
[4] 0, 15, 9, 3, 1;
[5] 0, 76, 38, 15, 4, 1;
[6] 0, 455, 198, 70, 22, 5, 1;
[7] 0, 3186, 1182, 378, 112, 30, 6, 1;
[8] 0, 25487, 8115, 2274, 629, 165, 39, 7, 1;
[9] 0, 229384, 63266, 15439, 3840, 965, 230, 49, 8, 1;
MAPLE
# Uses function PMatrix from A357368. PMatrix(10, n -> simplify(GAMMA(n+1) - GAMMA(n+1, -1)*exp(-1)));
Subfactorial or rencontres numbers, or derangements: number of permutations of n elements with no fixed points.
(Formerly M1937 N0766)
+10
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
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
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)
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 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 maximal number of totally mixed Nash equilibria in games of n players, each with 2 pure options. - Raimundas Vidunas, Jan 22 2014 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
R. K. Guy and R. J. Nowakowski, Mousetrap, Preprint, Feb 10 1993. [Annotated scanned copy] Eric Weisstein's World of Mathematics, Edge Cover. Eric Weisstein's World of Mathematics, Matching.
FORMULA
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).
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) = 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) = ((-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 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 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[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 *) RecurrenceTable[{a[n] == n*a[n - 1] + (-1)^n, a[0] == 1}, a, {n, 0, 23}] (* Ray Chandler, Jul 30 2015 *) 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 */ (Python) See Hobson link.
(Maxima)
s[0]:1$
s[n]:=n*s[n-1]+(-1)^n$
(Haskell)
a000166 n = a000166_list !! n
a000166_list = 1 : 0 : zipWith (*) [1..]
(zipWith (+) a000166_list $ tail a000166_list)
(Python)
for n in range(10*2):
x, m = x*n + m, -m
(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. Cf. A101560, A101559, A000110, A101033, A101032, A000204, A100492, A099731, A000045, A094216, A094638, A000108.
Number of n-stacks with strictly receding walls, or the number of Type A partitions of n in the sense of Auluck (1951).
(Formerly M0644 N0238)
+10
60
1, 1, 1, 1, 2, 3, 5, 7, 10, 14, 19, 26, 35, 47, 62, 82, 107, 139, 179, 230, 293, 372, 470, 591, 740, 924, 1148, 1422, 1756, 2161, 2651, 3244, 3957, 4815, 5844, 7075, 8545, 10299, 12383, 14859, 17794, 21267, 25368, 30207, 35902, 42600, 50462, 59678, 70465, 83079, 97800, 114967, 134956, 158205, 185209, 216546, 252859
COMMENTS
Number of smooth weakly unimodal compositions of n into positive parts such that the first and last part are 1 (smooth means that successive parts differ by at most one), see example. Dropping the requirement for unimodality gives A186085. - Joerg Arndt, Dec 09 2012 Number of weakly unimodal compositions of n where the maximal part m appears at least m times, see example. - Joerg Arndt, Jun 11 2013 Also weakly unimodal compositions of n with first part 1, maximal up-step 1, and no consecutive up-steps; see example. The smooth weakly unimodal compositions are recovered by shifting all rows above the bottom row to the left by one position with respect to the next lower row. - Joerg Arndt, Mar 30 2014 It would seem from Stanley that he regards a(0)=0 for this sequence and A001523. - Michael Somos, Feb 22 2015 Also the number of odd-length compositions of n with alternating parts strictly decreasing. These are finite odd-length sequences q of positive integers summing to n such that q(i) > q(i+2) for all possible i. The even-length version is A064428. For example, the a(1) = 1 through a(9) = 14 compositions are: (1) (2) (3) (4) (5) (6) (7) (8) (9)
(211) (221) (231) (241) (251) (261)
(311) (312) (322) (332) (342)
(321) (331) (341) (351)
(411) (412) (413) (423)
(421) (422) (432)
(511) (431) (441)
(512) (513)
(521) (522)
(611) (531)
(612)
(621)
(711)
(32211)
(End)
In the Ferrers diagram of a partition x of n, count the dots in each diagonal parallel to the main diagonal (starting at the top-right, say). The result diag(x) is a smooth weakly unimodal composition of n into positive parts such that the first and last part are 1. For example, diag(5541) = 11233221. The function diag is many-to-one; the size of its codomain as a set is a(n). If diag(x) = diag(y), each hook of x can be slid by the same amount past the main diagonal to get y. For example, diag(5541) = diag(44331). - George Beck, Sep 26 2021 Conjecture: Also the number of integer partitions y of n with a fixed point y(i) = i. These partitions are ranked by A352827. The conjecture is stated at A238395, but Resta tells me he may not have had a proof. The a(1) = 1 through a(8) = 10 partitions are: (1) (11) (111) (22) (32) (42) (52) (62)
(1111) (221) (222) (322) (422)
(11111) (321) (421) (521)
(2211) (2221) (2222)
(111111) (3211) (3221)
(22111) (4211)
(1111111) (22211)
(32111)
(221111)
(11111111)
Note that these are not the same partitions (compare A352827 to A352874), only the same count (apparently). (End)
The above conjecture is true. See Section 4 of the Blecher-Knopfmacher paper in the Links section. - Jeremy Lovejoy, Sep 26 2022
REFERENCES
G. E. Andrews, The reasonable and unreasonable effectiveness of number theory in statistical mechanics, pp. 21-34 of S. A. Burr, ed., The Unreasonable Effectiveness of Number Theory, Proc. Sympos. Appl. Math., 46 (1992). Amer. Math. Soc.
G. E. Andrews, Three-quadrant Ferrers graphs, Indian J. Math., 42 (No. 1, 2000), 1-7.
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).
R. P. Stanley, Enumerative Combinatorics, Cambridge, Vol. 1, 1999; see section 2.5 on page 76.
LINKS
E. M. Wright, Stacks, III, Quart. J. Math. Oxford, 23 (1972), 153-158.
FORMULA
G.f.: 1 + ( Sum_{k>=1} -(-1)^k * x^(k*(k+1)/2) ) / ( Product_{k>=1} 1-x^k ).
G.f.: 1 + ( Sum_{n>=1} q^(n^2) / ( Product_{k=1..n-1} 1-q^k )^2 * (1-q^n) ) ). - Joerg Arndt, Dec 09 2012 a(n) ~ exp(Pi*sqrt(2*n/3)) / (8*sqrt(3)*n) [Auluck, 1951]. - Vaclav Kotesovec, Sep 26 2016
EXAMPLE
For a(6)=5 we have the following stacks:
.x... ..x.. ...x. .xx.
xxxxx xxxxx xxxxx xxxx xxxxxx
.
There are a(9) = 14 smooth weakly unimodal compositions of 9:
01: [ 1 1 1 1 1 1 1 1 1 ]
02: [ 1 1 1 1 1 1 2 1 ]
03: [ 1 1 1 1 1 2 1 1 ]
04: [ 1 1 1 1 2 1 1 1 ]
05: [ 1 1 1 1 2 2 1 ]
06: [ 1 1 1 2 1 1 1 1 ]
07: [ 1 1 1 2 2 1 1 ]
08: [ 1 1 2 1 1 1 1 1 ]
09: [ 1 1 2 2 1 1 1 ]
10: [ 1 1 2 2 2 1 ]
11: [ 1 2 1 1 1 1 1 1 ]
12: [ 1 2 2 1 1 1 1 ]
13: [ 1 2 2 2 1 1 ]
14: [ 1 2 3 2 1 ]
(End)
There are a(9) = 14 weakly unimodal compositions of 9 where the maximal part m appears at least m times:
01: [ 1 1 1 1 1 1 1 1 1 ]
02: [ 1 1 1 1 1 2 2 ]
03: [ 1 1 1 1 2 2 1 ]
04: [ 1 1 1 2 2 1 1 ]
05: [ 1 1 1 2 2 2 ]
06: [ 1 1 2 2 1 1 1 ]
07: [ 1 1 2 2 2 1 ]
08: [ 1 2 2 1 1 1 1 ]
09: [ 1 2 2 2 1 1 ]
10: [ 1 2 2 2 2 ]
11: [ 2 2 1 1 1 1 1 ]
12: [ 2 2 2 1 1 1 ]
13: [ 2 2 2 2 1 ]
14: [ 3 3 3 ]
(End)
There are a(9) = 14 compositions of 9 with first part 1, maximal up-step 1, and no consecutive up-steps:
01: [ 1 1 1 1 1 1 1 1 1 ]
02: [ 1 1 1 1 1 1 1 2 ]
03: [ 1 1 1 1 1 1 2 1 ]
04: [ 1 1 1 1 1 2 1 1 ]
05: [ 1 1 1 1 1 2 2 ]
06: [ 1 1 1 1 2 1 1 1 ]
07: [ 1 1 1 1 2 2 1 ]
08: [ 1 1 1 2 1 1 1 1 ]
09: [ 1 1 1 2 2 1 1 ]
10: [ 1 1 1 2 2 2 ]
11: [ 1 1 2 1 1 1 1 1 ]
12: [ 1 1 2 2 1 1 1 ]
13: [ 1 1 2 2 2 1 ]
14: [ 1 1 2 2 3 ]
(End)
G.f. = 1 + x + x^2 + x^3 + 2*x^4 + 3*x^5 + 5*x^6 + 7*x^7 + 10*x^8 + 14*x^9 + ...
MAPLE
b:= proc(n, i, t) option remember; `if`(n<=0, `if`(i=1, 1, 0),
`if`(n<0 or i<1, 0, b(n-i, i, t)+b(n-(i-1), i-1, false)+
`if`(t, b(n-(i+1), i+1, t), 0)))
end:
a:= n-> b(n-1, 1, true):
# second Maple program:
local r, a;
a := 0 ;
if n = 0 then
return 1 ;
end if;
for r from 1 do
if r*(r+1) > 2*n then
return a;
else
a := a-(-1)^r*combinat[numbpart](n-r*(r+1)/2) ;
end if;
end do:
MATHEMATICA
max = 50; f[x_] := 1 + Sum[-(-1)^k*x^(k*(k+1)/2), {k, 1, max}] / Product[(1-x^k), {k, 1, max}]; CoefficientList[ Series[ f[x], {x, 0, max}], x] (* Jean-François Alcover, Dec 27 2011, after g.f. *) b[n_, i_, t_] := b[n, i, t] = If[n <= 0, If[i == 1, 1, 0], If[n<0 || i<1, 0, b[n-i, i, t] + b[n - (i-1), i-1, False] + If[t, b[n - (i+1), i+1, t], 0]]]; a[n_] := b[n-1, 1, True]; Table[a[n], {n, 0, 70}] (* Jean-François Alcover, Dec 01 2015, after Alois P. Heinz *) Flatten[{1, Table[Sum[(-1)^(j-1)*PartitionsP[n-j*((j+1)/2)], {j, 1, Floor[(Sqrt[8*n + 1] - 1)/2]}], {n, 1, 60}]}] (* Vaclav Kotesovec, Sep 26 2016 *) ici[q_]:=And@@Table[q[[i]]>q[[i+2]], {i, Length[q]-2}];
Table[If[n==0, 1, Length[Select[Join@@Permutations/@Select[IntegerPartitions[n], OddQ@*Length], ici]]], {n, 0, 15}] (* Gus Wiseman, Mar 30 2021 *)
PROG
(PARI) {a(n) = if( n<1, n==0, polcoeff( sum(k=1, (sqrt(1+8*n) - 1)\2, -(-1)^k * x^((k + k^2)/2)) / eta(x + x * O(x^n)), n))}; /* Michael Somos, Jul 22 2003 */ (PARI) N=66; q='q+O('q^N);
Vec( 1 + sum(n=1, N, q^(n^2)/(prod(k=1, n-1, 1-q^k)^2*(1-q^n)) ) ) \\ Joerg Arndt, Dec 09 2012 (Sage)
if n < 4: return 1
return (number_of_partitions(n) - [p.crank() for p in Partitions(n)].count(0))/2
CROSSREFS
Conjectured to be column k = 1 of A352833. These partitions (positive crank) are ranked by A352874. A064391 counts partitions by crank.
A257989 gives the crank of the partition with Heinz number n.
Number of partitions of n with nonnegative crank.
+10
44
1, 0, 1, 2, 3, 4, 6, 8, 12, 16, 23, 30, 42, 54, 73, 94, 124, 158, 206, 260, 334, 420, 532, 664, 835, 1034, 1288, 1588, 1962, 2404, 2953, 3598, 4392, 5328, 6466, 7808, 9432, 11338, 13632, 16326, 19544, 23316, 27806, 33054, 39273, 46534, 55096, 65076, 76808
COMMENTS
For a partition p, let l(p) = largest part of p, w(p) = number of 1's in p, m(p) = number of parts of p larger than w(p). The crank of p is given by l(p) if w(p) = 0, otherwise m(p)-w(p).
Also the number of even-length compositions of n with alternating parts strictly decreasing, or properly 2-colored partitions (proper = no equal parts of the same color) with the same number of parts of each color, or ordered pairs of strict partitions of the same length with total n. The odd-length case is A001522, and there are a total of A000041 compositions with alternating parts strictly decreasing (see A342528 for a bijective proof). The a(2) = 1 through a(7) = 8 ordered pairs of strict partitions of the same length are: (1)(1) (1)(2) (1)(3) (1)(4) (1)(5) (1)(6)
(2)(1) (2)(2) (2)(3) (2)(4) (2)(5)
(3)(1) (3)(2) (3)(3) (3)(4)
(4)(1) (4)(2) (4)(3)
(5)(1) (5)(2)
(21)(21) (6)(1)
(21)(31)
(31)(21)
Conjecture: Also the number of integer partitions y of n without a fixed point y(i) = i, ranked by A352826. This is stated at A238394, but Resta tells me he may not have had a proof. The a(2) = 1 through a(7) = 8 partitions without a fixed point are: (2) (3) (4) (5) (6) (7)
(21) (31) (41) (33) (43)
(211) (311) (51) (61)
(2111) (411) (331)
(3111) (511)
(21111) (4111)
(31111)
(211111)
The version for compositions is A238351. A238352 counts reversed partitions by fixed points, rank statistic A352822.
A238394 counts reversed partitions without a fixed point, ranked by A352830.
A238395 counts reversed partitions with a fixed point, ranked by A352872. (End)
The above conjecture is true. See Section 4 of the Blecher-Knopfmacher paper in the Links section. - Jeremy Lovejoy, Sep 26 2022
REFERENCES
B. C. Berndt, Ramanujan's Notebooks Part III, Springer-Verlag, see p. 18 Entry 9 Corollary (i).
G. E. Andrews, B. C. Berndt, Ramanujan's Lost Notebook Part I, Springer, see p. 169 Entry 6.7.1.
FORMULA
G.f.: (Sum_{k>=0} (-1)^k * x^(k(k+1)/2)) / (Product_{k>0} 1-x^k). - Michael Somos, Jul 28 2003 G.f.: Sum_{i>=0} x^(i*(i+1)) / (Product_{j=1..i} 1-x^j )^2. - Jon Perry, Jul 18 2004 G.f.: (Sum_{i>=0} x^i / (Product_{j=1..i} 1-x^j)^2 ) * (Product_{k>0} 1-x^k). - Li Han, May 23 2020
EXAMPLE
G.f. = 1 + x^2 + 2*x^3 + 3*x^4 + 4*x^5 + 6*x^6 + 8*x^7 + 12*x^8 + 16*x^9 + 23*x^10 + ... - Michael Somos, Jan 15 2018 The a(0) = 1 through a(8) = 12 partitions with nonnegative crank:
() . (2) (3) (4) (5) (6) (7) (8)
(21) (22) (32) (33) (43) (44)
(31) (41) (42) (52) (53)
(221) (51) (61) (62)
(222) (322) (71)
(321) (331) (332)
(421) (422)
(2221) (431)
(521)
(2222)
(3221)
(3311)
(End)
MATHEMATICA
a[ n_] := If[ n < 0, 0, SeriesCoefficient[ Sum[ (-1)^k x^(k (k + 1)/2) , {k, 0, (Sqrt[1 + 8 n] - 1)/2}] / QPochhammer[ x], {x, 0, n}]]; (* Michael Somos, Jan 15 2018 *) a[ n_] := If[ n < 0, 0, SeriesCoefficient[ Sum[ x^(k (k + 1)) / QPochhammer[ x, x, k]^2 , {k, 0, (Sqrt[1 + 4 n] - 1)/2}], {x, 0, n}]]; (* Michael Somos, Jan 15 2018 *) ck[y_]:=With[{w=Count[y, 1]}, If[w==0, If[y=={}, 0, Max@@y], Count[y, _?(#>w&)]-w]]; Table[Length[Select[IntegerPartitions[n], ck[#]>=0&]], {n, 0, 30}] (* Gus Wiseman, Mar 30 2021 *) ici[q_]:=And@@Table[q[[i]]>q[[i+2]], {i, Length[q]-2}];
Table[Length[Select[Join@@Permutations/@Select[IntegerPartitions[n], EvenQ@*Length], ici]], {n, 0, 15}] (* Gus Wiseman, Mar 30 2021 *)
PROG
(PARI) {a(n) = if( n<0, 0, polcoeff( sum(k=0, (sqrtint(1 + 8*n) -1)\2, (-1)^k * x^((k+k^2)/2)) / eta( x + x * O(x^n)), n))}; /* Michael Somos, Jul 28 2003 */
CROSSREFS
These are the row-sums of the right (or left) half of A064391, inclusive. These partitions are ranked by A352873. A034008 counts even-length compositions.
A224958 counts compositions w/ alternating parts unequal (even: A342532).
A257989 gives the crank of the partition with Heinz number n.
A342527 counts compositions w/ alternating parts equal (even: A065608).
A342528 = compositions w/ alternating parts weakly decr. (even: A114921).
a(n) = n*a(n-1) + 1, a(0) = 0.
(Formerly M2858 N1149)
+10
43
0, 1, 3, 10, 41, 206, 1237, 8660, 69281, 623530, 6235301, 68588312, 823059745, 10699776686, 149796873605, 2246953104076, 35951249665217, 611171244308690, 11001082397556421, 209020565553572000, 4180411311071440001, 87788637532500240022
COMMENTS
This sequence shares divisibility properties with A000522; each of the primes in A072456 divide only a finite number of terms of this sequence. - T. D. Noe, Jul 07 2005 Sum of the lengths of the first runs in all permutations of [n]. Example: a(3)=10 because the lengths of the first runs in the permutation (123),(13)2,(3)12,(2)13,(23)1 and (3)21 are 3,2,1,1,2 and 1, respectively (first runs are enclosed between parentheses). Number of cells in the last columns of all deco polyominoes of height n. A deco polyomino is a directed column-convex polyomino in which the height, measured along the diagonal, is attained only in the last column. a(n) = Sum_{k=1..n} k* A092582(n,k). - Emeric Deutsch, Aug 16 2006 Starting with offset 1 = eigensequence of an infinite lower triangular matrix with (1, 2, 3, ...) as the right border, (1, 1, 1, ...) as the left border, and the rest zeros. - Gary W. Adamson, Apr 27 2009 if s(n) is a sequence defined as s(0) = x, s(n) = n*s(n-1)+k, n > 0 then s(n) = n!*x + a(n)*k. - Gary Detlefs, Feb 20 2010 Number of arrangements of proper subsets of n distinct objects, i.e., arrangements which are not permutations (where the empty set is considered a proper subset of any nonempty set); see example. - Daniel Forgues, Apr 23 2011 For n >= 0, A002627(n+1) is the sequence of sums of Pascal-like triangle with one side 1,1,..., and the other side A000522. - Vladimir Shevelev, Feb 06 2012 a(n) is the number of quasilinear weak orderings on {1,...,n}. - J. Devillet, Dec 22 2017
REFERENCES
D. Singh, The numbers L(m,n) and their relations with prepared Bernoulli and Eulerian numbers, Math. Student, 20 (1952), 66-70.
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).
FORMULA
a(n) = n! * Sum_{k=1..n} 1/k!.
E.g.f.: (exp(x)-1)/(1-x). - Mario Catalani (mario.catalani(AT)unito.it), Feb 06 2003
a(m) = Integral_{s=0..oo} ((1+s)^m - s^m)*exp(-s) = GAMMA(m+1,1) * exp(1) - GAMMA(m+1). - Stephen Crowley, Jul 24 2009 E.g.f.: Q(0)/(1-x), where Q(k)= 1 + (x-1)*k!/(1 - x/(x + (x-1)*(k+1)!/Q(k+1))); (continued fraction). (End)
E.g.f.: x/(1-x)*E(0)/2, where E(k)= 1 + 1/(1 - x/(x + (k+2)/E(k+1))); (continued fraction). - Sergei N. Gladkovskii, Jun 01 2013 1/(e - 1) = 1 - 1!/(1*3) - 2!/(3*10) - 3!/(10*41) - 4!/(41*206) - ... (see A056542 and A185108). - Peter Bala, Oct 09 2013 Conjecture: a(n) + (-n-1)*a(n-1) + (n-1)*a(n-2) = 0. - R. J. Mathar, Feb 16 2014 The e.g.f. f(x) = (exp(x)-1)/(1-x) satisfies the differential equation: (1-x)*f'(x) - (2-x)*f(x) + 1, from which we can obtain the recurrence:
a(n+1) = a(n) + n! + Sum_{k=1..n} (n!/k!)*a(k). The above conjectured recurrence can be obtained from the original recurrence or from the differential equation satisfied by f(x). - Emanuele Munarini, Jun 20 2014
EXAMPLE
[a(0), a(1), ...] = GAMMA(m+1,1)*exp(1) - GAMMA(m+1) = [exp(-1)*exp(1)-1, 2*exp(-1)*exp(1)-1, 5*exp(-1)*exp(1)-2, 16*exp(-1)*exp(1)-6, 65*exp(-1)*exp(1)-24, 326*exp(-1)*exp(1)-120, ...]. - Stephen Crowley, Jul 24 2009 n=0: {}: #{} = 0
n=1: {1}: #{()} = 1
n=2: {1,2}: #{(),(1),(2)} = 3
n=3: {1,2,3}: #{(),(1),(2),(3),(1,2),(2,1),(1,3),(3,1),(2,3),(3,2)} = 10
(End)
x + 3*x^2 + 10*x^3 + 41*x^4 + 206*x^5 + 1237*x^6 + 8660*x^7 + 69281*x^8 + ...
MAPLE
add( (n-j)!*binomial(n, j), j=1..n) ;
end proc:
MATHEMATICA
RecurrenceTable[{a[0]==0, a[n]==n*a[n-1]+1}, a, {n, 30}] (* Harvey P. Dale, Mar 29 2015 *)
PROG
(PARI) a(n)= n!*sum(k=1, n, 1/k!); \\ Joerg Arndt, Apr 24 2011 (Haskell)
a002627 n = a002627_list !! n
a002627_list = 0 : map (+ 1) (zipWith (*) [1..] a002627_list)
(Maxima) makelist(sum(n!/k!, k, 1, n), n, 0, 40); /* Emanuele Munarini, Jun 20 2014 */ (Magma) I:=[1]; [0] cat [n le 1 select I[n] else n*Self(n-1)+1:n in [1..21]]; // Marius A. Burtea, Aug 07 2019
CROSSREFS
Conjectured to give records in A130147.
Triangular array formed from successive differences of factorial numbers.
+10
27
1, 1, 0, 2, 1, 1, 6, 4, 3, 2, 24, 18, 14, 11, 9, 120, 96, 78, 64, 53, 44, 720, 600, 504, 426, 362, 309, 265, 5040, 4320, 3720, 3216, 2790, 2428, 2119, 1854, 40320, 35280, 30960, 27240, 24024, 21234, 18806, 16687, 14833, 362880, 322560
COMMENTS
Number of permutations of 1,2,...,k,n+1,n+2,...,2n-k that have no agreements with 1,...,n. For example, consider 1234 and 1256, then n=4 and k=2, so T(4,2)=14. Compare A000255 for the case k=1. - Jon Perry, Jan 23 2004 T(n-1,k-1) is the number of non-derangements of {1,2,...,n} having smallest fixed point equal to k. Example: T(3,1)=4 because we have 4213, 4231, 3214, and 3241 (the permutations of {1,2,3,4} having smallest fixed equal to 2).
Row sums give the number of non-derangement permutations of {1,2,...,n} ( A002467). Closely related to A134830, where each row has an extra term (see the Charalambides reference). (End)
T(n,k) is the number of permutations of {1..n} that don't fix the points 1..k. - Robert FERREOL, Aug 04 2016
REFERENCES
Ch. A. Charalambides, Enumerative Combinatorics, Chapman & Hall/CRC, Boca Raton, Florida, 2002, p. 176, Table 5.3. [From Emeric Deutsch, Apr 21 2009]
FORMULA
t(n, k) = t(n, k-1) - t(n-1, k-1) = t(n, k+1) - t(n-1, k) = n*t(n-1, k) + k*t(n-2, k-1) = (n-1)*t(n-1, k-1) + (k-1)*t(n-2, k-2) = A060475(n, k)*(n-k)!. - Henry Bottomley, Mar 16 2001 T(n, k) = Sum_{j>=0} (-1)^j * binomial(k, j)*(n-j)!. - Philippe Deléham, May 29 2005 T(n,k) = Sum_{j=0..n-k} d(n-j)*binomial(n-k,j), where d(i)= A000166(i) are the derangement numbers. - Emeric Deutsch, Jul 17 2009 T(n, k) = n!*hypergeom([-k], [-n], -1). - Peter Luschny, Jul 28 2024
EXAMPLE
Triangle begins:
1;
1, 0;
2, 1, 1;
6, 4, 3, 2;
24, 18, 14, 11, 9;
120, 96, 78, 64, 53, 44;
...
The left-hand column is the factorial numbers ( A000142). The other numbers in the row are calculated by subtracting the numbers in the previous row. For example, row 4 is 6, 4, 3, 2, so row 5 is 4! = 24, 24 - 6 = 18, 18 - 4 = 14, 14 - 3 = 11, 11 - 2 = 9. - Michael B. Porter, Aug 05 2016
MAPLE
d[0] := 1: for n to 15 do d[n] := n*d[n-1]+(-1)^n end do: T := proc (n, k) if k <= n then sum(binomial(n-k, j)*d[n-j], j = 0 .. n-k) else 0 end if end proc: for n from 0 to 9 do seq(T(n, k), k = 0 .. n) end do; # yields sequence in triangular form - Emeric Deutsch, Jul 17 2009 # second Maple program:
T:= proc(n, k) option remember;
`if`(k=0, n!, T(n, k-1)-T(n-1, k-1))
end:
MATHEMATICA
t[n_, k_] = Sum[(-1)^j*Binomial[k, j]*(n-j)!, {j, 0, n}]; Flatten[Table[t[n, k], {n, 0, 9}, {k, 0, n}]][[1 ;; 47]] (* Jean-François Alcover, May 17 2011, after Philippe Deléham *) T[n_, k_] := n! Hypergeometric1F1[-k, -n, -1];
Table[T[n, k], {n, 0, 7}, {k, 0, n}] // Flatten (* Peter Luschny, Jul 28 2024 *)
PROG
(Haskell)
a047920 n k = a047920_tabl !! n !! k
a047920_row n = a047920_tabl !! n
a047920_tabl = map fst $ iterate e ([1], 1) where
e (row, n) = (scanl (-) (n * head row) row, n + 1)
(PARI) row(n) = vector(n+1, k, k--; sum(j=0, n, (-1)^j * binomial(k, j)*(n-j)!)); \\ Michel Marcus, Sep 04 2021
CROSSREFS
See A068106 for another version of this triangle.
Euler's difference table: triangle read by rows, formed by starting with factorial numbers ( A000142) and repeatedly taking differences. T(n,n) = n!, T(n,k) = T(n,k+1) - T(n-1,k).
+10
23
1, 0, 1, 1, 1, 2, 2, 3, 4, 6, 9, 11, 14, 18, 24, 44, 53, 64, 78, 96, 120, 265, 309, 362, 426, 504, 600, 720, 1854, 2119, 2428, 2790, 3216, 3720, 4320, 5040, 14833, 16687, 18806, 21234, 24024, 27240, 30960, 35280, 40320, 133496, 148329, 165016, 183822, 205056, 229080, 256320, 287280, 322560, 362880
COMMENTS
Triangle T(n,k) (n >= 1, 1 <= k <= n) giving number of ways of winning with (n-k+1)st card in the generalized "Game of Thirteen" with n cards.
T(n-1,k-1) is the number of non-derangements of {1,2,...,n} having largest fixed point equal to k. Example: T(3,1)=3 because we have 1243, 4213, and 3241.
(End)
LINKS
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.
FORMULA
T(n, k) = Sum_{j>= 0} (-1)^j*binomial(n-k, j)*(n-j)!. - Philippe Deléham, May 29 2005 T(n,k) = Sum_{j=0..k} d(n-j)*binomial(k, j), where d(i) = A000166(i) are the derangement numbers. Sum_{k=0..n} (k+1)*T(n,k) = A000166(n+2) (the derangement numbers). (End) T(n, k) = n!*hypergeom([k-n], [-n], -1). - Peter Luschny, Oct 05 2017 D-finite recurrence for columns: T(n,k) = n*T(n-1,k) + (n-k)*T(n-2,k). - Georg Fischer, Aug 13 2022
EXAMPLE
Triangle begins:
[0] 1;
[1] 0, 1;
[2] 1, 1, 2;
[3] 2, 3, 4, 6;
[4] 9, 11, 14, 18, 24;
[5] 44, 53, 64, 78, 96, 120;
[6] 265, 309, 362, 426, 504, 600, 720;
[7] 1854, 2119, 2428, 2790, 3216, 3720, 4320, 5040.
MAPLE
d[0] := 1: for n to 15 do d[n] := n*d[n-1]+(-1)^n end do: T := proc (n, k) if k <= n then sum(binomial(k, j)*d[n-j], j = 0 .. k) else 0 end if end proc: for n from 0 to 9 do seq(T(n, k), k = 0 .. n) end do; # yields sequence in triangular form; Emeric Deutsch, Jul 18 2009
MATHEMATICA
t[n_, k_] := Sum[(-1)^j*Binomial[n-k, j]*(n-j)!, {j, 0, n}]; Flatten[ Table[ t[n, k], {n, 0, 9}, {k, 0, n}]] (* Jean-François Alcover, Feb 21 2012, after Philippe Deléham *) T[n_, k_] := n! HypergeometricPFQ[{k-n}, {-n}, -1];
Table[T[n, k], {n, 0, 9}, {k, 0, n}] // Flatten (* Peter Luschny, Oct 05 2017 *)
PROG
(Haskell)
a068106 n k = a068106_tabl !! n !! k
a068106_row n = a068106_tabl !! n
a068106_tabl = map reverse a047920_tabl
CROSSREFS
Diagonals give A000142, A001563, A001564, A001565, A001688, A001689, A023043, A023044, A023045, A023046, A023047 (factorials and k-th differences, k=1..10). Columns k=0..10 give A000166, A000255, A055790, A277609, A277563, A280425, A280920, A284204, A284205, A284206, A284207.
EXTENSIONS
More terms from Antonio G. Astudillo (afg_astudillo(AT)lycos.com), Apr 01 2003
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.
+10
22
0, 1, 3, 13, 67, 411, 2921, 23633, 214551, 2160343, 23897269, 288102189, 3760013027, 52816397219, 794536751217, 12744659120521, 217140271564591, 3916221952414383, 74539067188152941, 1493136645424092773, 31400620285465593339, 691708660911435955579
COMMENTS
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 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 k<n+1. Permutations of {1,2,4} with an indexed point p(k)=k are 124, 142 and 421, so a(3)=3.
For 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)
FORMULA
a(n) = n! - d(n) - d(n-1), where d(j) = A000166(j) are the derangement numbers. a(n) = (n-1)! [x^(n-1)] (1-exp(-x))/(1-x)^2. - Alois P. Heinz, Feb 23 2019
EXAMPLE
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
MAPLE
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);
MATHEMATICA
f[n_] := Sum[ -(-1)^k (n - k)! Binomial[n - 1, k], {k, 1, n}]; Array[f, 20] (* Robert G. Wilson v, Oct 16 2010 *)
PROG
(PARI) {a(n) = if( n<2, 0, n--; subst( polinterpolate( vector( n, k, k!)), x, n+1))} /* Michael Somos, Jan 05 2012 */ (Haskell)
a180191 n = if n == 1 then 0 else sum $ a116853_row (n - 1)
Search completed in 0.052 seconds
| 
