|
| |
|
|
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.
|
|
87
| |
|
|
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
(list; table; graph; refs; listen; history; 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
Contribution from Johannes W. Meijer (meijgia(AT)hotmail.com), Oct 16 2009: (Start)
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.
(End)
The number of injective functions from a set of size k to a set of size n. [From Dennis 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}. [From Dennis Walsh, April 20 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
| T. D. Noe, Rows n=0..100 of triangle, flattened
W. Lang, On generalizations of Stirling number triangles, J. Integer Seqs., Vol. 3 (2000), #00.2.4.
Dennis Walsh, Notes on no-less functions
|
|
|
FORMULA
| E.g.f.: sum T(n,k) x^n/n! y^k = exp(x)/(1-x*y). - Vladeta Jovovic (vladeta(AT)eunet.rs), Aug 19 2002
Equals A007318 * A136572 - Gary W. Adamson (qntmpkt(AT)yahoo.com), 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 (se16(AT)btinternet.com), 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}. - Frank Adams-Watters (FrankTAW(AT)Netscape.net), 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 (qntmpkt(AT)yahoo.com), 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). [From Paul Barry (pbarry(AT)wit.ie), Feb 11 2009]
T(n,k)=sum(binomial(k,j)*T(x,j)*T(y,k-j),j=0..k) for x+y=n. [From Dennis Walsh, Feb 10 2011]
E.g.f (with k fixed): x^k*exp(x) [From Dennis Walsh, April 20 2011]
G.f. (with k fixed): k!x^k/(1-x)^(k+1) [From Dennis Walsh, April 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. [From Dennis 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. [From Dennis Walsh, April 30 2011]
|
|
|
MAPLE
| with(combstruct):for n from 0 to 10 do seq(count(Permutation(n), size=m), m = 0 .. n) od; - Zerinvary Lajos (zerinvarylajos(AT)yahoo.com), Dec 16 2007
seq(seq(n!/(n-k)!, k=0..n), n=0..10); [From Dennis Walsh, April 20 2011]
|
|
|
MATHEMATICA
| Table[CoefficientList[Series[(1 + x)^m, {x, 0, 20}], x]* Table[n!, {n, 0, m}], {m, 0, 10}] // Grid [From Geoffrey Critzer (critzer.geoffrey(AT)usd443.org), Mar 16 2010]
|
|
|
PROG
| (PARI) T(n, k)=if(k<0|k>n, 0, n!/(n-k)!)
(PARI) T(n, k)=local(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)))
|
|
|
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 * A056043 A187005 A158497
Adjacent sequences: A008276 A008277 A008278 * A008280 A008281 A008282
|
|
|
KEYWORD
| nonn,tabl,nice,easy,core
|
|
|
AUTHOR
| N. J. A. Sloane (njas(AT)research.att.com).
|
| |
|
|
