cp's OEIS Frontend

This is a front-end for the Online Encyclopedia of Integer Sequences, made by Christian Perfect. The idea is to provide OEIS entries in non-ancient HTML, and then to think about how they're presented visually. The source code is on GitHub.

A008279 Triangle T(n,k) = n!/(n-k)! (0 <= k <= n) read by rows, giving number of permutations of n things k at a time.

Original entry on oeis.org

1, 1, 1, 1, 2, 2, 1, 3, 6, 6, 1, 4, 12, 24, 24, 1, 5, 20, 60, 120, 120, 1, 6, 30, 120, 360, 720, 720, 1, 7, 42, 210, 840, 2520, 5040, 5040, 1, 8, 56, 336, 1680, 6720, 20160, 40320, 40320, 1, 9, 72, 504, 3024, 15120, 60480, 181440, 362880, 362880
Offset: 0

Views

Author

N. J. A. Sloane

Keywords

Comments

Also called permutation coefficients.
Also falling factorials triangle A068424 with column a(n,0)=1 and row a(0,1)=1 otherwise a(0,k)=0, added. - Wolfdieter Lang, Nov 07 2003
The higher-order exponential integrals E(x,m,n) are defined in A163931; for information about the asymptotic expansion of E(x,m=1,n) see A130534. The asymptotic expansions for n = 1, 2, 3, 4, ..., lead to the right hand columns of the triangle given above. - Johannes W. Meijer, Oct 16 2009
The number of injective functions from a set of size k to a set of size n. - Dennis P. Walsh, Feb 10 2011
The number of functions f from {1,2,...,k} to {1,2,...,n} that satisfy f(x) >= x for all x in {1,2,...,k}. - Dennis P. Walsh, Apr 20 2011
T(n,k) = A181511(n,k) for k=1..n-1. - Reinhard Zumkeller, Nov 18 2012
The e.g.f.s enumerating the faces of the permutohedra / permutahedra, Perm(s,t;x) = [e^(sx)-1]/[s-t(e^(sx)-1)], (cf. A090582 and A019538) and the stellahedra / stellohedra, St(s,t;x) = [s e^((s+t)x)]/[s-t(e^(sx)-1)], (cf. A248727) given in Toric Topology satisfy exp[u*d/dt] St(s,t;x) = St(s,u+t;x) = [e^(ux)/(1-u*Perm(s,t;x))]*St(s,t;x), where e^(ux)/(1-uy) is a bivariate e.g.f. for the row polynomials of this entry and A094587. Equivalently, d/dt St = (x+Perm)*St and d/dt Perm = Perm^2, or d/dt log(St) = x + Perm and d/dt log(Perm) = Perm. - Tom Copeland, Nov 14 2016
T(n, k)/n! are the coefficients of the n-th exponential Taylor polynomial, or truncated exponentials, which was proved to be irreducible by Schur. See Coleman link. - Michel Marcus, Feb 24 2020
Given a generic choice of k+2 residues, T(n, k) is the number of meromorphic differentials on the Riemann sphere having a zero of order n and these prescribed residues at its k+2 poles. - Quentin Gendron, Jan 16 2025

Examples

			Triangle begins:
  1;
  1,  1;
  1,  2,  2;
  1,  3,  6,   6;
  1,  4, 12,  24,   24;
  1,  5, 20,  60,  120,   120;
  1,  6, 30, 120,  360,   720,    720;
  1,  7, 42, 210,  840,  2520,   5040,   5040;
  1,  8, 56, 336, 1680,  6720,  20160,  40320,   40320;
  1,  9, 72, 504, 3024, 15120,  60480, 181440,  362880,  362880;
  1, 10, 90, 720, 5040, 30240, 151200, 604800, 1814400, 3628800, 3628800;
  ...
For example, T(4,2)=12 since there are 12 injective functions f:{1,2}->{1,2,3,4}. There are 4 choices for f(1) and then, since f is injective, 3 remaining choices for f(2), giving us 12 ways to construct an injective function. - _Dennis P. Walsh_, Feb 10 2011
For example, T(5,3)=60 since there are 60 functions f:{1,2,3}->{1,2,3,4,5} with f(x) >= x. There are 5 choices for f(1), 4 choices for f(2), and 3 choices for f(3), giving us 60 ways to construct such a function. - _Dennis P. Walsh_, Apr 30 2011

References

  • CRC Standard Mathematical Tables and Formulae, 30th ed., 1996, p. 176; 31st ed., p. 215, Section 3.3.11.1.
  • Maple V Reference Manual, p. 490, numbperm(n,k).

Links

Crossrefs

Row sums give A000522.
Cf. A001497, A001498, A136572.
T(n,0)=A000012, T(n,1)=A000027, T(n+1,2)=A002378, T(n,3)=A007531, T(n,4)=A052762, and T(n,n)=A000142.
Cf. A019538, A090582, A094587, A248727.

Programs

  • Haskell
    a008279 n k = a008279_tabl !! n !! k
a008279_row n = a008279_tabl !! n
a008279_tabl = iterate f [1] where
   f xs = zipWith (+) ([0] ++ zipWith (*) xs [1..]) (xs ++ [0])
-- Reinhard Zumkeller, Dec 15 2013, Nov 18 2012
  • Magma
    /* As triangle */ [[Factorial(n)/Factorial(n-k): k in [0..n]]: n in [0.. 15]]; // Vincenzo Librandi, Oct 11 2015
  • Maple
    with(combstruct): for n from 0 to 10 do seq(count(Permutation(n),size=m), m = 0 .. n) od; # Zerinvary Lajos, Dec 16 2007
seq(seq(n!/(n-k)!,k=0..n),n=0..10); # Dennis P. Walsh, Apr 20 2011
seq(print(seq(pochhammer(n-k+1,k),k=0..n)),n=0..6); # Peter Luschny, Mar 26 2015
  • Mathematica
    Table[CoefficientList[Series[(1 + x)^m, {x, 0, 20}], x]* Table[n!, {n, 0, m}], {m, 0, 10}] // Grid (* Geoffrey Critzer, Mar 16 2010 *)
Table[ Pochhammer[n - k + 1, k], {n, 0, 9}, {k, 0, n}] // Flatten (* or *)
Table[ FactorialPower[n, k], {n, 0, 9}, {k, 0, n}] // Flatten  (* Jean-François Alcover, Jul 18 2013, updated Jan 28 2016 *)
  • PARI
    {T(n, k) = if( k<0 || k>n, 0, n!/(n-k)!)}; /* Michael Somos, Nov 14 2002 */
  • PARI
    {T(n, k) = my(A, p); if( k<0 || k>n, 0, if( n==0, 1, A = matrix(n, n, i, j, x + (i==j)); polcoeff( sum(i=1, n!, if( p = numtoperm(n, i), prod(j=1, n, A[j, p[j]]))), k)))}; /* Michael Somos, Mar 05 2004 */
  • Python
    from math import factorial, isqrt, comb
def A008279(n): return factorial(a:=(m:=isqrt(k:=n+1<<1))-(k<=m*(m+1)))//factorial(a-n+comb(a+1,2)) # Chai Wah Wu, Nov 13 2024
  • Sage
    for n in range(8): [falling_factorial(n,k) for k in (0..n)] # Peter Luschny, Mar 26 2015

Formula

E.g.f.: Sum T(n,k) x^n/n! y^k = exp(x)/(1-x*y). - Vladeta Jovovic, Aug 19 2002
Equals A007318 * A136572. - Gary W. Adamson, Jan 07 2008
T(n, k) = n*T(n-1, k-1) = k*T(n-1, k-1)+T(n-1, k) = n*T(n-1, k)/(n-k) = (n-k+1)*T(n, k-1). - Henry Bottomley, Mar 29 2001
T(n, k) = n!/(n-k)! if n >= k >= 0, otherwise 0.
G.f. for k-th column k!*x^k/(1-x)^(k+1), k >= 0.
E.g.f. for n-th row (1+x)^n, n >= 0.
Sum T(n, k)x^k = permanent of n X n matrix a_ij = (x+1 if i=j, x otherwise). - Michael Somos, Mar 05 2004
Ramanujan psi_1(k, x) polynomials evaluated at n+1. - Ralf Stephan, Apr 16 2004
E.g.f.: Sum T(n,k) x^n/n! y^k/k! = e^{x+xy}. - Franklin T. Adams-Watters, Feb 07 2006
The triangle is the binomial transform of an infinite matrix with (1, 1, 2, 6, 24, ...) in the main diagonal and the rest zeros. - Gary W. Adamson, Nov 20 2006
G.f.: 1/(1-x-xy/(1-xy/(1-x-2xy/(1-2xy/(1-x-3xy/(1-3xy/(1-x-4xy/(1-4xy/(1-... (continued fraction). - Paul Barry, Feb 11 2009
T(n,k) = Sum_{j=0..k} binomial(k,j)*T(x,j)*T(y,k-j) for x+y = n. - Dennis P. Walsh, Feb 10 2011
From Dennis P. Walsh, Apr 20 2011: (Start)
E.g.f (with k fixed): x^k*exp(x).
G.f. (with k fixed): k!*x^k/(1-x)^(k+1). (End)
For n >= 2 and m >= 2, Sum_{k=0..m-2} S2(n, k+2)*T(m-2, k) = Sum_{p=0..n-2} m^p. S2(n,k) are the Stirling numbers of the second kind A008277. - Tony Foster III, Jul 23 2019

Started in 1964 by Neil J. A. Sloane | Maintained by The OEIS Foundation Inc.

Content is available under The OEIS End-User License Agreement.