login
This site is supported by donations to The OEIS Foundation.

 

Logo


Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
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. 95
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 (list; table; graph; refs; listen; history; text; internal format)
OFFSET

0,5

COMMENTS

Also called permutation coefficients.

Also falling factorials triangle A068424 with column a(n,0)=1 and row a(0,1)=1 else a(0,k)=0, added. - Wolfdieter Lang, Nov 07 2003

The higher order exponential integrals E(x,m,n) are defined in A163931 and 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

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

T. D. Noe, Rows n=0..100 of triangle, flattened

J. Fernando Barbero G., Jesús Salas, Eduardo J. S. Villaseñor, Bivariate Generating Functions for a Class of Linear Recurrences. I. General Structure, arXiv:1307.2010 [math.CO], 2013-2014.

R. L. Graham, D. E. Knuth, and O. Patashnik, Concrete Mathematics: A Foundation for Computer Science, 2nd ed. Reading, MA: Addison-Wesley, 1994.

Germain Kreweras, Une dualité élémentaire souvent utile dans les problèmes combinatoires, Mathématiques et Sciences Humaines 3 (1963): 31-41.

W. Lang, On generalizations of Stirling number triangles, J. Integer Seqs., Vol. 3 (2000), #00.2.4.

T. S. Motzkin, Sorting numbers for cylinders and other classification numbers, in Combinatorics, Proc. Symp. Pure Math. 19, AMS, 1971, pp. 167-176. [Annotated, scanned copy]

OEIS Wiki, Sorting numbers

Dennis Walsh, Notes on no-less functions

Eric Weisstein's World of Mathematics, Falling Factorial

Index entries for "core" sequences

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 else 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

E.g.f (with k fixed): x^k*exp(x). - Dennis P. Walsh, Apr 20 2011

G.f. (with k fixed): k!x^k/(1-x)^(k+1). - Dennis P. Walsh, Apr 20 2011

EXAMPLE

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

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 *)

PROG

(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 */

(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

(Sage)

for n in range(8): [falling_factorial(n, k) for k in (0..n)] # Peter Luschny, Mar 26 2015

(MAGMA) / As triangle / [[Factorial(n)/Factorial(n-k): k in [0..n]]: n in [0.. 15]]; // Vincenzo Librandi, Oct 11 2015

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.

Sequence in context: A082037 A163649 A110858 * A239572 A056043 A187005

Adjacent sequences:  A008276 A008277 A008278 * A008280 A008281 A008282

KEYWORD

nonn,tabl,nice,easy,core,changed

AUTHOR

N. J. A. Sloane

STATUS

approved

Lookup | Welcome | Wiki | Register | Music | Plot 2 | Demos | Index | Browse | More | WebCam
Contribute new seq. or comment | Format | Transforms | Superseeker | Recent | More pages
The OEIS Community | Maintained by The OEIS Foundation Inc.

License Agreements, Terms of Use, Privacy Policy .

Last modified August 27 02:35 EDT 2016. Contains 275901 sequences.