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.

Showing 1-10 of 21 results. Next

A238385 Shifted lower triangular matrix A238363 with a main diagonal of ones.

Original entry on oeis.org

1, 1, 1, -1, 2, 1, 2, -3, 3, 1, -6, 8, -6, 4, 1, 24, -30, 20, -10, 5, 1, -120, 144, -90, 40, -15, 6, 1, 720, -840, 504, -210, 70, -21, 7, 1, -5040, 5760, -3360, 1344, -420, 112, -28, 8, 1, 40320, -45360, 25920, -10080, 3024, -756, 168, -36, 9, 1, -362880, 403200, -226800, 86400, -25200, 6048, -1260, 240, -45, 10, 1
Offset: 0

Views

Author

Tom Copeland, Feb 25 2014

Keywords

Comments

Shift A238363 and add a main diagonal of ones to obtain this array. The row polynomials form a special Sheffer sequence of polynomials, an Appell sequence.

Examples

			The triangle a(n,k) begins:
n\k       0       1        2      3       4     5      6    7   8   9 10 ...
0:        1
1:        1       1
2:       -1       2        1
3:        2      -3        3      1
4:       -6       8       -6      4       1
5:       24     -30       20    -10       5     1
6:     -120     144      -90     40     -15     6      1
7:      720    -840      504   -210      70   -21      7    1
8:    -5040    5760    -3360   1344    -420   112    -28    8   1
9:    40320  -45360    25920 -10080    3024  -756    168  -36   9   1
10: -362880  403200  -226800  86400  -25200  6048  -1260  240 -45  10  1
... formatted by _Wolfdieter Lang_, Mar 09 2014
----------------------------------------------------------------------------

Crossrefs

Cf. A002741, A007318, A008275, A008277, A008290, A048993, A055137, A074909, A132440, A238363.

Formula

a(n,k) = (-1)^(n+k-1)*n!/((n-k)*k!) for k
Along the n-th diagonal (n>0) Diag(n,k) = a(n+k,k) = (-1)^(n-1)(n-1)! * A007318(n+k,k).
E.g.f.: (log(1+t)+1)*exp(x*t).
E.g.f. for inverse: exp(x*t)/(log(1+t)+1).
The lowering/annihilation and raising/creation operators for the row polynomials are L=D=d/dx and R=x+1/[(1+D)(1+log(1+D))], i.e., L p(n,x)= n*p(n-1,x) and R p(n,x)= p(n+1,x).
E.g.f. of row sums: (log(1+t)+1)*exp(t). Cf. |row sums-1|=|A002741|.
E.g.f. of unsigned row sums: (-log(1-t)+1)*exp(t). Cf. A002104 + 1.
Let dP = A132440, the infinitesimal generator for the Pascal matrix, I, the identity matrix, and T, this entry's lower triangular matrix, then exp(T-I)=I+dP, i.e., T=I+log(I+dP). Also, ((T-I)n)^n=0, where (T-I)_n denotes the n X n submatrix, i.e., (T-I)_n is nilpotent of order n. - _Tom Copeland, Mar 02 2014
Dividing each subdiagonal by its first element (-1)^(n-1)*(n-1)! yields Pascal's triangle A007318. This is equivalent to multiplying the e.g.f. by exp(t)/(log(1+t)+1). - Tom Copeland, Apr 16 2014
From Tom Copeland, Apr 25 2014: (Start)
A) T = [St1]*[dP]*[St2] + I = [padded A008275]*A132440*A048993 + I
B) = [St1]*[dP]*[St1]^(-1) + I
C) = [St2]^(-1)*[dP]*[St2] + I
D) = [St2]^(-1)*[dP]*[St1]^(-1) + I,
where [St1]=padded A008275 just as [St2]=A048993=padded A008277 and I=identity matrix. Cf. A074909. (End)
From Tom Copeland, Jul 26 2017: (Start)
p_n(x) = (1 + log(1+D)) x^n = (1 + D - D^2/2 + D^3/3- ...) x^n = x^n + n! * Sum_(k=1,..,n) (-1)^(k+1) (1/k) x^(n-k)/(n-k)!.
Unsigned T with the first two diagonals nulled gives an exponential infinitesimal generator M (infinigen) for the rencontres numbers A008290, and negated M gives the infinigen for A055137; i.e., with M = |T| - I - dP = -log(I-dP)-dP, then e^M = e^(-dP) / (I-dP) = lower triangular A008290, and e^(-M) = e^dP (I-dP) = A007318 * (I-dP) = lower triangular A055137. The matrix formulation is consistent with the operator relations e^(-D) / (1-D) x^n = n-th row polynomial of A008290 and e^D (1-D) x^n = n-th row polynomial of A055137. (End)

A000217 Triangular numbers: a(n) = binomial(n+1,2) = n*(n+1)/2 = 0 + 1 + 2 + ... + n.

Original entry on oeis.org

0, 1, 3, 6, 10, 15, 21, 28, 36, 45, 55, 66, 78, 91, 105, 120, 136, 153, 171, 190, 210, 231, 253, 276, 300, 325, 351, 378, 406, 435, 465, 496, 528, 561, 595, 630, 666, 703, 741, 780, 820, 861, 903, 946, 990, 1035, 1081, 1128, 1176, 1225, 1275, 1326, 1378, 1431
Offset: 0

Views

Author

N. J. A. Sloane

Keywords

Comments

Also referred to as T(n) or C(n+1, 2) or binomial(n+1, 2) (preferred).
Also generalized hexagonal numbers: n*(2*n-1), n=0, +-1, +-2, +-3, ... Generalized k-gonal numbers are second k-gonal numbers and positive terms of k-gonal numbers interleaved, k >= 5. In this case k = 6. - Omar E. Pol, Sep 13 2011 and Aug 04 2012
Number of edges in complete graph of order n+1, K_{n+1}.
Number of legal ways to insert a pair of parentheses in a string of n letters. E.g., there are 6 ways for three letters: (a)bc, (ab)c, (abc), a(b)c, a(bc), ab(c). Proof: there are C(n+2,2) ways to choose where the parentheses might go, but n + 1 of them are illegal because the parentheses are adjacent. Cf. A002415.
For n >= 1, a(n) is also the genus of a nonsingular curve of degree n+2, such as the Fermat curve x^(n+2) + y^(n+2) = 1. - Ahmed Fares (ahmedfares(AT)my_deja.com), Feb 21 2001
From Harnack's theorem (1876), the number of branches of a nonsingular curve of order n is bounded by a(n-1)+1, and the bound can be achieved. See also A152947. - Benoit Cloitre, Aug 29 2002. Corrected by Robert McLachlan, Aug 19 2024
Number of tiles in the set of double-n dominoes. - Scott A. Brown, Sep 24 2002
Number of ways a chain of n non-identical links can be broken up. This is based on a similar problem in the field of proteomics: the number of ways a peptide of n amino acid residues can be broken up in a mass spectrometer. In general, each amino acid has a different mass, so AB and BC would have different masses. - James A. Raymond, Apr 08 2003
Triangular numbers - odd numbers = shifted triangular numbers; 1, 3, 6, 10, 15, 21, ... - 1, 3, 5, 7, 9, 11, ... = 0, 0, 1, 3, 6, 10, ... - Xavier Acloque, Oct 31 2003 [Corrected by Derek Orr, May 05 2015]
Centered polygonal numbers are the result of [number of sides * A000217 + 1]. E.g., centered pentagonal numbers (1,6,16,31,...) = 5 * (0,1,3,6,...) + 1. Centered heptagonal numbers (1,8,22,43,...) = 7 * (0,1,3,6,...) + 1. - Xavier Acloque, Oct 31 2003
Maximum number of lines formed by the intersection of n+1 planes. - Ron R. King, Mar 29 2004
Number of permutations of [n] which avoid the pattern 132 and have exactly 1 descent. - Mike Zabrocki, Aug 26 2004
Number of ternary words of length n-1 with subwords (0,1), (0,2) and (1,2) not allowed. - Olivier Gérard, Aug 28 2012
Number of ways two different numbers can be selected from the set {0,1,2,...,n} without repetition, or, number of ways two different numbers can be selected from the set {1,2,...,n} with repetition.
Conjecturally, 1, 6, 120 are the only numbers that are both triangular and factorial. - Christopher M. Tomaszewski (cmt1288(AT)comcast.net), Mar 30 2005
Binomial transform is {0, 1, 5, 18, 56, 160, 432, ...}, A001793 with one leading zero. - Philippe Deléham, Aug 02 2005
Each pair of neighboring terms adds to a perfect square. - Zak Seidov, Mar 21 2006
Number of transpositions in the symmetric group of n+1 letters, i.e., the number of permutations that leave all but two elements fixed. - Geoffrey Critzer, Jun 23 2006
With rho(n):=exp(i*2*Pi/n) (an n-th root of 1) one has, for n >= 1, rho(n)^a(n) = (-1)^(n+1). Just use the triviality a(2*k+1) == 0 (mod (2*k+1)) and a(2*k) == k (mod (2*k)).
a(n) is the number of terms in the expansion of (a_1 + a_2 + a_3)^(n-1). - Sergio Falcon, Feb 12 2007
a(n+1) is the number of terms in the complete homogeneous symmetric polynomial of degree n in 2 variables. - Richard Barnes, Sep 06 2017
The number of distinct handshakes in a room with n+1 people. - Mohammad K. Azarian, Apr 12 2007 [corrected, Joerg Arndt, Jan 18 2016]
Equal to the rank (minimal cardinality of a generating set) of the semigroup PT_n\S_n, where PT_n and S_n denote the partial transformation semigroup and symmetric group on [n]. - James East, May 03 2007
a(n) gives the total number of triangles found when cevians are drawn from a single vertex on a triangle to the side opposite that vertex, where n = the number of cevians drawn+1. For instance, with 1 cevian drawn, n = 1+1 = 2 and a(n)= 2*(2+1)/2 = 3 so there is a total of 3 triangles in the figure. If 2 cevians are drawn from one point to the opposite side, then n = 1+2 = 3 and a(n) = 3*(3+1)/2 = 6 so there is a total of 6 triangles in the figure. - Noah Priluck (npriluck(AT)gmail.com), Apr 30 2007
For n >= 1, a(n) is the number of ways in which n-1 can be written as a sum of three nonnegative integers if representations differing in the order of the terms are considered to be different. In other words, for n >= 1, a(n) is the number of nonnegative integral solutions of the equation x + y + z = n-1. - Amarnath Murthy, Apr 22 2001 (edited by Robert A. Beeler)
a(n) is the number of levels with energy n + 3/2 (in units of h*f0, with Planck's constant h and the oscillator frequency f0) of the three-dimensional isotropic harmonic quantum oscillator. See the comment by A. Murthy above: n = n1 + n2 + n3 with positive integers and ordered. Proof from the o.g.f. See the A. Messiah reference. - Wolfdieter Lang, Jun 29 2007
From Hieronymus Fischer, Aug 06 2007: (Start)
Numbers m >= 0 such that round(sqrt(2m+1)) - round(sqrt(2m)) = 1.
Numbers m >= 0 such that ceiling(2*sqrt(2m+1)) - 1 = 1 + floor(2*sqrt(2m)).
Numbers m >= 0 such that fract(sqrt(2m+1)) > 1/2 and fract(sqrt(2m)) < 1/2, where fract(x) is the fractional part of x (i.e., x - floor(x), x >= 0). (End)
If Y and Z are 3-blocks of an n-set X, then, for n >= 6, a(n-1) is the number of (n-2)-subsets of X intersecting both Y and Z. - Milan Janjic, Nov 09 2007
Equals row sums of triangle A143320, n > 0. - Gary W. Adamson, Aug 07 2008
a(n) is also an even perfect number in A000396 iff n is a Mersenne prime A000668. - Omar E. Pol, Sep 05 2008. Unnecessary assumption removed and clarified by Rick L. Shepherd, Apr 14 2025
Equals row sums of triangle A152204. - Gary W. Adamson, Nov 29 2008
The number of matches played in a round robin tournament: n*(n-1)/2 gives the number of matches needed for n players. Everyone plays against everyone else exactly once. - Georg Wrede (georg(AT)iki.fi), Dec 18 2008
-a(n+1) = E(2)*binomial(n+2,2) (n >= 0) where E(n) are the Euler numbers in the enumeration A122045. Viewed this way, a(n) is the special case k=2 in the sequence of diagonals in the triangle A153641. - Peter Luschny, Jan 06 2009
Equivalent to the first differences of successive tetrahedral numbers. See A000292. - Jeremy Cahill (jcahill(AT)inbox.com), Apr 15 2009
The general formula for alternating sums of powers is in terms of the Swiss-Knife polynomials P(n,x) A153641 2^(-n-1)(P(n,1)-(-1)^k P(n,2k+1)). Thus a(k) = |2^(-3)(P(2,1)-(-1)^k P(2,2k+1))|. - Peter Luschny, Jul 12 2009
a(n) is the smallest number > a(n-1) such that gcd(n,a(n)) = gcd(n,a(n-1)). If n is odd this gcd is n; if n is even it is n/2. - Franklin T. Adams-Watters, Aug 06 2009
Partial sums of A001477. - Juri-Stepan Gerasimov, Jan 25 2010. [A-number corrected by Omar E. Pol, Jun 05 2012]
The numbers along the right edge of Floyd's triangle are 1, 3, 6, 10, 15, .... - Paul Muljadi, Jan 25 2010
From Charlie Marion, Dec 03 2010: (Start)
More generally, a(2k+1) == j*(2j-1) (mod 2k+2j+1) and
a(2k) == [-k + 2j*(j-1)] (mod 2k+2j).
Column sums of:
1 3 5 7 9 ...
1 3 5 ...
1 ...
...............
---------------
1 3 6 10 15 ...
Sum_{n>=1} 1/a(n)^2 = 4*Pi^2/3-12 = 12 less than the volume of a sphere with radius Pi^(1/3).
(End)
A004201(a(n)) = A000290(n); A004202(a(n)) = A002378(n). - Reinhard Zumkeller, Feb 12 2011
1/a(n+1), n >= 0, has e.g.f. -2*(1+x-exp(x))/x^2, and o.g.f. 2*(x+(1-x)*log(1-x))/x^2 (see the Stephen Crowley formula line). -1/(2*a(n+1)) is the z-sequence for the Sheffer triangle of the coefficients of the Bernoulli polynomials A196838/A196839. - Wolfdieter Lang, Oct 26 2011
From Charlie Marion, Feb 23 2012: (Start)
a(n) + a(A002315(k)*n + A001108(k+1)) = (A001653(k+1)*n + A001109(k+1))^2. For k=0 we obtain a(n) + a(n+1) = (n+1)^2 (identity added by N. J. A. Sloane on Feb 19 2004).
a(n) + a(A002315(k)*n - A055997(k+1)) = (A001653(k+1)*n - A001109(k))^2.
(End)
Plot the three points (0,0), (a(n), a(n+1)), (a(n+1), a(n+2)) to form a triangle. The area will be a(n+1)/2. - J. M. Bergot, May 04 2012
The sum of four consecutive triangular numbers, beginning with a(n)=n*(n+1)/2, minus 2 is 2*(n+2)^2. a(n)*a(n+2)/2 = a(a(n+1)-1). - J. M. Bergot, May 17 2012
(a(n)*a(n+3) - a(n+1)*a(n+2))*(a(n+1)*a(n+4) - a(n+2)*a(n+3))/8 = a((n^2+5*n+4)/2). - J. M. Bergot, May 18 2012
a(n)*a(n+1) + a(n+2)*a(n+3) + 3 = a(n^2 + 4*n + 6). - J. M. Bergot, May 22 2012
In general, a(n)*a(n+1) + a(n+k)*a(n+k+1) + a(k-1)*a(k) = a(n^2 + (k+2)*n + k*(k+1)). - Charlie Marion, Sep 11 2012
a(n)*a(n+3) + a(n+1)*a(n+2) = a(n^2 + 4*n + 2). - J. M. Bergot, May 22 2012
In general, a(n)*a(n+k) + a(n+1)*a(n+k-1) = a(n^2 + (k+1)*n + k-1). - Charlie Marion, Sep 11 2012
a(n)*a(n+2) + a(n+1)*a(n+3) = a(n^2 + 4*n + 3). - J. M. Bergot, May 22 2012
Three points (a(n),a(n+1)), (a(n+1),a(n)) and (a(n+2),a(n+3)) form a triangle with area 4*a(n+1). - J. M. Bergot, May 23 2012
a(n) + a(n+k) = (n+k)^2 - (k^2 + (2n-1)*k -2n)/2. For k=1 we obtain a(n) + a(n+1) = (n+1)^2 (see below). - Charlie Marion, Oct 02 2012
In n-space we can define a(n-1) nontrivial orthogonal projections. For example, in 3-space there are a(2)=3 (namely point onto line, point onto plane, line onto plane). - Douglas Latimer, Dec 17 2012
From James East, Jan 08 2013: (Start)
For n >= 1, a(n) is equal to the rank (minimal cardinality of a generating set) and idempotent rank (minimal cardinality of an idempotent generating set) of the semigroup P_n\S_n, where P_n and S_n denote the partition monoid and symmetric group on [n].
For n >= 3, a(n-1) is equal to the rank and idempotent rank of the semigroup T_n\S_n, where T_n and S_n denote the full transformation semigroup and symmetric group on [n].
(End)
For n >= 3, a(n) is equal to the rank and idempotent rank of the semigroup PT_n\S_n, where PT_n and S_n denote the partial transformation semigroup and symmetric group on [n]. - James East, Jan 15 2013
Conjecture: For n > 0, there is always a prime between A000217(n) and A000217(n+1). Sequence A065383 has the first 1000 of these primes. - Ivan N. Ianakiev, Mar 11 2013
The formula, a(n)*a(n+4k+2)/2 + a(k) = a(a(n+2k+1) - (k^2+(k+1)^2)), is a generalization of the formula a(n)*a(n+2)/2 = a(a(n+1)-1) in Bergot's comment dated May 17 2012. - Charlie Marion, Mar 28 2013
The series Sum_{k>=1} 1/a(k) = 2, given in a formula below by Jon Perry, Jul 13 2003, has partial sums 2*n/(n+1) (telescopic sum) = A022998(n)/A026741(n+1). - Wolfdieter Lang, Apr 09 2013
For odd m = 2k+1, we have the recurrence a(m*n + k) = m^2*a(n) + a(k). Corollary: If number T is in the sequence then so is 9*T+1. - Lekraj Beedassy, May 29 2013
Euler, in Section 87 of the Opera Postuma, shows that whenever T is a triangular number then 9*T + 1, 25*T + 3, 49*T + 6 and 81*T + 10 are also triangular numbers. In general, if T is a triangular number then (2*k + 1)^2*T + k*(k + 1)/2 is also a triangular number. - Peter Bala, Jan 05 2015
Using 1/b and 1/(b+2) will give a Pythagorean triangle with sides 2*b + 2, b^2 + 2*b, and b^2 + 2*b + 2. Set b=n-1 to give a triangle with sides of lengths 2*n,n^2-1, and n^2 + 1. One-fourth the perimeter = a(n) for n > 1. - J. M. Bergot, Jul 24 2013
a(n) = A028896(n)/6, where A028896(n) = s(n) - s(n-1) are the first differences of s(n) = n^3 + 3*n^2 + 2*n - 8. s(n) can be interpreted as the sum of the 12 edge lengths plus the sum of the 6 face areas plus the volume of an n X (n-1) X (n-2) rectangular prism. - J. M. Bergot, Aug 13 2013
Dimension of orthogonal group O(n+1). - Eric M. Schmidt, Sep 08 2013
Number of positive roots in the root system of type A_n (for n > 0). - Tom Edgar, Nov 05 2013
A formula for the r-th successive summation of k, for k = 1 to n, is binomial(n+r,r+1) [H. W. Gould]. - Gary Detlefs, Jan 02 2014
Also the alternating row sums of A095831. Also the alternating row sums of A055461, for n >= 1. - Omar E. Pol, Jan 26 2014
For n >= 3, a(n-2) is the number of permutations of 1,2,...,n with the distribution of up (1) - down (0) elements 0...011 (n-3 zeros), or, the same, a(n-2) is up-down coefficient {n,3} (see comment in A060351). - Vladimir Shevelev, Feb 14 2014
a(n) is the dimension of the vector space of symmetric n X n matrices. - Derek Orr, Mar 29 2014
Non-vanishing subdiagonal of A132440^2/2, aside from the initial zero. First subdiagonal of unsigned A238363. Cf. A130534 for relations to colored forests, disposition of flags on flagpoles, and colorings of the vertices of complete graphs. - Tom Copeland, Apr 05 2014
The number of Sidon subsets of {1,...,n+1} of size 2. - Carl Najafi, Apr 27 2014
Number of factors in the definition of the Vandermonde determinant V(x_1,x_2,...,x_n) = Product_{1 <= i < k <= n} x_i - x_k. - Tom Copeland, Apr 27 2014
Number of weak compositions of n into three parts. - Robert A. Beeler, May 20 2014
Suppose a bag contains a(n) red marbles and a(n+1) blue marbles, where a(n), a(n+1) are consecutive triangular numbers. Then, for n > 0, the probability of choosing two marbles at random and getting two red or two blue is 1/2. In general, for k > 2, let b(0) = 0, b(1) = 1 and, for n > 1, b(n) = (k-1)*b(n-1) - b(n-2) + 1. Suppose, for n > 0, a bag contains b(n) red marbles and b(n+1) blue marbles. Then the probability of choosing two marbles at random and getting two red or two blue is (k-1)/(k+1). See also A027941, A061278, A089817, A053142, A092521. - Charlie Marion, Nov 03 2014
Let O(n) be the oblong number n(n+1) = A002378 and S(n) the square number n^2 = A000290(n). Then a(4n) = O(3n) - O(n), a(4n+1) = S(3n+1) - S(n), a(4n+2) = S(3n+2) - S(n+1) and a(4n+3) = O(3n+2) - O(n). - Charlie Marion, Feb 21 2015
Consider the partition of the natural numbers into parts from the set S=(1,2,3,...,n). The length (order) of the signature of the resulting sequence is given by the triangular numbers. E.g., for n=10, the signature length is 55. - David Neil McGrath, May 05 2015
a(n) counts the partitions of (n-1) unlabeled objects into three (3) parts (labeled a,b,c), e.g., a(5)=15 for (n-1)=4. These are (aaaa),(bbbb),(cccc),(aaab),(aaac),(aabb),(aacc),(aabc),(abbc),(abcc),(abbb),(accc),(bbcc),(bccc),(bbbc). - David Neil McGrath, May 21 2015
Conjecture: the sequence is the genus/deficiency of the sinusoidal spirals of index n which are algebraic curves. The value 0 corresponds to the case of the Bernoulli Lemniscate n=2. So the formula conjectured is (n-1)(n-2)/2. - Wolfgang Tintemann, Aug 02 2015
Conjecture: Let m be any positive integer. Then, for each n = 1,2,3,... the set {Sum_{k=s..t} 1/k^m: 1 <= s <= t <= n} has cardinality a(n) = n*(n+1)/2; in other words, all the sums Sum_{k=s..t} 1/k^m with 1 <= s <= t are pairwise distinct. (I have checked this conjecture via a computer and found no counterexample.) - Zhi-Wei Sun, Sep 09 2015
The Pisano period lengths of reading the sequence modulo m seem to be A022998(m). - R. J. Mathar, Nov 29 2015
For n >= 1, a(n) is the number of compositions of n+4 into n parts avoiding the part 2. - Milan Janjic, Jan 07 2016
In this sequence only 3 is prime. - Fabian Kopp, Jan 09 2016
Suppose you are playing Bulgarian Solitaire (see A242424 and Chamberland's and Gardner's books) and, for n > 0, you are starting with a single pile of a(n) cards. Then the number of operations needed to reach the fixed state {n, n-1,...,1} is a(n-1). For example, {6}->{5,1}->{4,2}->{3,2,1}. - Charlie Marion, Jan 14 2016
Numbers k such that 8k + 1 is a square. - Juri-Stepan Gerasimov, Apr 09 2016
Every perfect cube is the difference of the squares of two consecutive triangular numbers. 1^2-0^2 = 1^3, 3^2-1^2 = 2^3, 6^2-3^2 = 3^3. - Miquel Cerda, Jun 26 2016
For n > 1, a(n) = tau_n(k*) where tau_n(k) is the number of ordered n-factorizations of k and k* is the square of a prime. For example, tau_3(4) = tau_3(9) = tau_3(25) = tau_3(49) = 6 (see A007425) since the number of divisors of 4, 9, 25, and 49's divisors is 6, and a(3) = 6. - Melvin Peralta, Aug 29 2016
In an (n+1)-dimensional hypercube, number of two-dimensional faces congruent with a vertex (see also A001788). - Stanislav Sykora, Oct 23 2016
Generalizations of the familiar formulas, a(n) + a(n+1) = (n+1)^2 (Feb 19 2004) and a(n)^2 + a(n+1)^2 = a((n+1)^2) (Nov 22 2006), follow: a(n) + a(n+2k-1) + 4a(k-1) = (n+k)^2 + 6a(k-1) and a(n)^2 + a(n+2k-1)^2 + (4a(k-1))^2 + 3a(k-1) = a((n+k)^2 + 6a(k-1)). - Charlie Marion, Nov 27 2016
a(n) is also the greatest possible number of diagonals in a polyhedron with n+4 vertices. - Vladimir Letsko, Dec 19 2016
For n > 0, 2^5 * (binomial(n+1,2))^2 represents the first integer in a sum of 2*(2*n + 1)^2 consecutive integers that equals (2*n + 1)^6. - Patrick J. McNab, Dec 25 2016
Does not satisfy Benford's law (cf. Ross, 2012). - N. J. A. Sloane, Feb 12 2017
Number of ordered triples (a,b,c) of positive integers not larger than n such that a+b+c = 2n+1. - Aviel Livay, Feb 13 2017
Number of inequivalent tetrahedral face colorings using at most n colors so that no color appears only once. - David Nacin, Feb 22 2017
Also the Wiener index of the complete graph K_{n+1}. - Eric W. Weisstein, Sep 07 2017
Number of intersections between the Bernstein polynomials of degree n. - Eric Desbiaux, Apr 01 2018
a(n) is the area of a triangle with vertices at (1,1), (n+1,n+2), and ((n+1)^2, (n+2)^2). - Art Baker, Dec 06 2018
For n > 0, a(n) is the smallest k > 0 such that n divides numerator of (1/a(1) + 1/a(2) + ... + 1/a(n-1) + 1/k). It should be noted that 1/1 + 1/3 + 1/6 + ... + 2/(n(n+1)) = 2n/(n+1). - Thomas Ordowski, Aug 04 2019
Upper bound of the number of lines in an n-homogeneous supersolvable line arrangement (see Theorem 1.1 in Dimca). - Stefano Spezia, Oct 04 2019
For n > 0, a(n+1) is the number of lattice points on a triangular grid with side length n. - Wesley Ivan Hurt, Aug 12 2020
From Michael Chu, May 04 2022: (Start)
Maximum number of distinct nonempty substrings of a string of length n.
Maximum cardinality of the sumset A+A, where A is a set of n numbers. (End)
a(n) is the number of parking functions of size n avoiding the patterns 123, 132, and 312. - Lara Pudwell, Apr 10 2023
Suppose two rows, each consisting of n evenly spaced dots, are drawn in parallel. Suppose we bijectively draw lines between the dots of the two rows. For n >= 1, a(n - 1) is the maximal possible number of intersections between the lines. Equivalently, the maximal number of inversions in a permutation of [n]. - Sela Fried, Apr 18 2023
The following equation complements the generalization in Bala's Comment (Jan 05 2015). (2k + 1)^2*a(n) + a(k) = a((2k + 1)*n + k). - Charlie Marion, Aug 28 2023
a(n) + a(n+k) + a(k-1) + (k-1)*n = (n+k)^2. For k = 1, we have a(n) + a(n+1) = (n+1)^2. - Charlie Marion, Nov 17 2023
a(n+1)/3 is the expected number of steps to escape from a linear row of n positions starting at a random location and randomly performing steps -1 or +1 with equal probability. - Hugo Pfoertner, Jul 22 2025
a(n+1) is the number of nonnegative integer solutions to p + q + r = n. By Sylvester's law of inertia, it is also the number of congruence classes of real symmetric n-by-n matrices or equivalently, the number of symmetric bilinear forms on a real n-dimensional vector space. - Paawan Jethva, Jul 24 2025

Examples

			G.f.: x + 3*x^2 + 6*x^3 + 10*x^4 + 15*x^5 + 21*x^6 + 28*x^7 + 36*x^8 + 45*x^9 + ...
When n=3, a(3) = 4*3/2 = 6.
Example(a(4)=10): ABCD where A, B, C and D are different links in a chain or different amino acids in a peptide possible fragments: A, B, C, D, AB, ABC, ABCD, BC, BCD, CD = 10.
a(2): hollyhock leaves on the Tokugawa Mon, a(4): points in Pythagorean tetractys, a(5): object balls in eight-ball billiards. - _Bradley Klee_, Aug 24 2015
From _Gus Wiseman_, Oct 28 2020: (Start)
The a(1) = 1 through a(5) = 15 ordered triples of positive integers summing to n + 2 [Beeler, McGrath above] are the following. These compositions are ranked by A014311.
  (111)  (112)  (113)  (114)  (115)
         (121)  (122)  (123)  (124)
         (211)  (131)  (132)  (133)
                (212)  (141)  (142)
                (221)  (213)  (151)
                (311)  (222)  (214)
                       (231)  (223)
                       (312)  (232)
                       (321)  (241)
                       (411)  (313)
                              (322)
                              (331)
                              (412)
                              (421)
                              (511)
The unordered version is A001399(n-3) = A069905(n), with Heinz numbers A014612.
The strict case is A001399(n-6)*6, ranked by A337453.
The unordered strict case is A001399(n-6), with Heinz numbers A007304.
(End)

References

  • M. Abramowitz and I. A. Stegun, eds., Handbook of Mathematical Functions, National Bureau of Standards Applied Math. Series 55, 1964 (and various reprintings), p. 828.
  • C. Alsina and R. B. Nelson, Charming Proofs: A Journey into Elegant Mathematics, MAA, 2010. See Chapter 1.
  • T. M. Apostol, Introduction to Analytic Number Theory, Springer-Verlag, 1976, page 2.
  • A. H. Beiler, Recreations in the Theory of Numbers, Dover, NY, 1964, p. 189.
  • A. T. Benjamin and J. J. Quinn, Proofs that really count: the art of combinatorial proof, M.A.A. 2003, p. 109ff.
  • Marc Chamberland, Single Digits: In Praise of Small Numbers, Chapter 3, The Number Three, p. 72, Princeton University Press, 2015.
  • L. Comtet, Advanced Combinatorics, Reidel, 1974, p. 155.
  • John H. Conway and Richard K. Guy, The Book of Numbers, New York: Springer-Verlag, 1996. See pp. 33, 38, 40, 70.
  • J. M. De Koninck and A. Mercier, 1001 Problèmes en Théorie Classique des Nombres, Problème 309 pp 46-196, Ellipses, Paris, 2004
  • E. Deza and M. M. Deza, Figurate numbers, World Scientific Publishing (2012), page 6.
  • L. E. Dickson, History of the Theory of Numbers. Carnegie Institute Public. 256, Washington, DC, Vol. 1, 1919; Vol. 2, 1920; Vol. 3, 1923, see vol. 2, p. 1.
  • Martin Gardner, Colossal Book of Mathematics, Chapter 34, Bulgarian Solitaire and Other Seemingly Endless Tasks, pp. 455-467, W. W. Norton & Company, 2001.
  • James Gleick, The Information: A History, A Theory, A Flood, Pantheon, 2011. [On page 82 mentions a table of the first 19999 triangular numbers published by E. de Joncort in 1762.]
  • Jan Gullberg, Mathematics from the Birth of Numbers, W. W. Norton & Co., NY & London, 1997, §4.6 Mathematical Proof and §8.6 Figurate Numbers, pp. 158-159, 289-290.
  • Cay S. Horstmann, Scala for the Impatient. Upper Saddle River, New Jersey: Addison-Wesley (2012): 171.
  • Elemer Labos, On the number of RGB-colors we can distinguish. Partition Spectra. Lecture at 7th Hungarian Conference on Biometry and Biomathematics. Budapest. Jul 06 2005.
  • A. Messiah, Quantum Mechanics, Vol.1, North Holland, Amsterdam, 1965, p. 457.
  • J. C. P. Miller, editor, Table of Binomial Coefficients. Royal Society Mathematical Tables, Vol. 3, Cambridge Univ. Press, 1954.
  • Alfred S. Posamentier, Math Charmers, Tantalizing Tidbits for the Mind, Prometheus Books, NY, 2003, pages 52-53, 129-132, 274.
  • 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).
  • James J. Tattersall, Elementary Number Theory in Nine Chapters, Cambridge University Press, 1999, pages 2-6, 13.
  • T. Trotter, Some Identities for the Triangular Numbers, Journal of Recreational Mathematics, Spring 1973, 6(2).
  • D. Wells, The Penguin Dictionary of Curious and Interesting Numbers, pp. 91-93 Penguin Books 1987.

Links

Crossrefs

The figurate numbers, with parameter k as in the second Python program: A001477 (k=0), this sequence (k=1), A000290 (k=2), A000326 (k=3), A000384 (k=4), A000566 (k=5), A000567 (k=6), A001106 (k=7), A001107 (k=8).
Cf. A000096, A000124, A000292, A000330, A000396, A000668, A001082, A001788, A002024, A002378, A002415, A003056 (inverse function), A004526, A006011, A007318, A008953, A008954, A010054 (characteristic function), A028347, A036666, A046092, A051942, A055998, A055999, A056000, A056115, A056119, A056121, A056126, A062717, A087475, A101859, A109613, A143320, A210569, A245031, A245300, A060544, A016754.
a(n) = A110449(n, 0).
a(n) = A110555(n+2, 2).
A diagonal of A008291.
Column 2 of A195152.
Numbers of the form n*t(n+k,h)-(n+k)*t(n,h), where t(i,h) = i*(i+2*h+1)/2 for any h (for A000217 is k=1): A005563, A067728, A140091, A140681, A212331.
Boustrophedon transforms: A000718, A000746.
Iterations: A007501 (start=2), A013589 (start=4), A050542 (start=5), A050548 (start=7), A050536 (start=8), A050909 (start=9).
Cf. A002817 (doubly triangular numbers), A075528 (solutions of a(n)=a(m)/2).
Cf. A104712 (first column, starting with a(1)).
Some generalized k-gonal numbers are A001318 (k=5), this sequence (k=6), A085787 (k=7), etc.
A001399(n-3) = A069905(n) = A211540(n+2) counts 3-part partitions.
A001399(n-6) = A069905(n-3) = A211540(n-1) counts 3-part strict partitions.
A011782 counts compositions of any length.
A337461 counts pairwise coprime triples, with unordered version A307719.
Cf. A000212, A001840, A007304, A156040, A220377, A337483, A337604.
Cf. A099174, A130534, A132440, A238363.

Programs

  • Haskell
    a000217 n = a000217_list !! n
a000217_list = scanl1 (+) [0..] -- Reinhard Zumkeller, Sep 23 2011
  • J
    a000217=: *-:@>: NB. Stephen Makdisi, May 02 2018
  • Magma
    [n*(n+1)/2: n in [0..60]]; // Bruno Berselli, Jul 11 2014
  • Magma
    [n: n in [0..1500] | IsSquare(8*n+1)]; // Juri-Stepan Gerasimov, Apr 09 2016
  • Maple
    A000217 := proc(n) n*(n+1)/2; end;
istriangular:=proc(n) local t1; t1:=floor(sqrt(2*n)); if n = t1*(t1+1)/2 then return true else return false; end if; end proc; # N. J. A. Sloane, May 25 2008
ZL := [S, {S=Prod(B, B, B), B=Set(Z, 1 <= card)}, unlabeled]:
seq(combstruct[count](ZL, size=n), n=2..55); # Zerinvary Lajos, Mar 24 2007
isA000217 := proc(n)
    issqr(1+8*n) ;
end proc: # R. J. Mathar, Nov 29 2015 [This is the recipe Leonhard Euler proposes in chapter VII of his "Vollständige Anleitung zur Algebra", 1765. Peter Luschny, Sep 02 2022]
  • Mathematica
    Array[ #*(# - 1)/2 &, 54] (* Zerinvary Lajos, Jul 10 2009 *)
FoldList[#1 + #2 &, 0, Range@ 50] (* Robert G. Wilson v, Feb 02 2011 *)
Accumulate[Range[0,70]] (* Harvey P. Dale, Sep 09 2012 *)
CoefficientList[Series[x / (1 - x)^3, {x, 0, 50}], x] (* Vincenzo Librandi, Jul 30 2014 *)
(* For Mathematica 10.4+ *) Table[PolygonalNumber[n], {n, 0, 53}] (* Arkadiusz Wesolowski, Aug 27 2016 *)
LinearRecurrence[{3, -3, 1}, {0, 1, 3}, 54] (* Robert G. Wilson v, Dec 04 2016 *)
(* The following Mathematica program, courtesy of Steven J. Miller, is useful for testing if a sequence is Benford. To test a different sequence only one line needs to be changed. This strongly suggests that the triangular numbers are not Benford, since the second and third columns of the output disagree. - N. J. A. Sloane, Feb 12 2017 *)
fd[x_] := Floor[10^Mod[Log[10, x], 1]]
benfordtest[num_] := Module[{},
   For[d = 1, d <= 9, d++, digit[d] = 0];
   For[n = 1, n <= num, n++,
    {
     d = fd[n(n+1)/2];
     If[d != 0, digit[d] = digit[d] + 1];
     }];
   For[d = 1, d <= 9, d++, digit[d] = 1.0 digit[d]/num];
   For[d = 1, d <= 9, d++,
    Print[d, " ", 100.0 digit[d], " ", 100.0 Log[10, (d + 1)/d]]];
   ];
benfordtest[20000]
Table[Length[Join@@Permutations/@IntegerPartitions[n,{3}]],{n,0,15}] (* Gus Wiseman, Oct 28 2020 *)
  • PARI
    A000217(n) = n * (n + 1) / 2;
  • PARI
    is_A000217(n)=n*2==(1+n=sqrtint(2*n))*n \\ M. F. Hasler, May 24 2012
  • PARI
    is(n)=ispolygonal(n,3) \\ Charles R Greathouse IV, Feb 28 2014
  • PARI
    list(lim)=my(v=List(),n,t); while((t=n*n++/2)<=lim,listput(v,t)); Vec(v) \\ Charles R Greathouse IV, Jun 18 2021
  • Python
    for n in range(0,60): print(n*(n+1)//2, end=', ') # Stefano Spezia, Dec 06 2018
  • Python
    # Intended to compute the initial segment of the sequence, not
# isolated terms. If in the iteration the line "x, y = x + y + 1, y + 1"
# is replaced by "x, y = x + y + k, y + k" then the figurate numbers are obtained,
# for k = 0 (natural A001477), k = 1 (triangular), k = 2 (squares), k = 3 (pentagonal), k = 4 (hexagonal), k = 5 (heptagonal), k = 6 (octagonal), etc.
def aList():
    x, y = 1, 1
    yield 0
    while True:
        yield x
        x, y = x + y + 1, y + 1
A000217 = aList()
print([next(A000217) for i in range(54)]) # Peter Luschny, Aug 03 2019
  • SageMath
    [n*(n+1)/2 for n in (0..60)] # Bruno Berselli, Jul 11 2014
  • Scala
    (1 to 53).scanLeft(0)( + ) // Horstmann (2012), p. 171
  • Scheme
    (define (A000217 n) (/ (* n (+ n 1)) 2)) ;; Antti Karttunen, Jul 08 2017

Formula

G.f.: x/(1-x)^3. - Simon Plouffe in his 1992 dissertation
E.g.f.: exp(x)*(x+x^2/2).
a(n) = a(-1-n).
a(n) + a(n-1)*a(n+1) = a(n)^2. - Terrel Trotter, Jr., Apr 08 2002
a(n) = (-1)^n*Sum_{k=1..n} (-1)^k*k^2. - Benoit Cloitre, Aug 29 2002
a(n+1) = ((n+2)/n)*a(n), Sum_{n>=1} 1/a(n) = 2. - Jon Perry, Jul 13 2003
For n > 0, a(n) = A001109(n) - Sum_{k=0..n-1} (2*k+1)*A001652(n-1-k); e.g., 10 = 204 - (1*119 + 3*20 + 5*3 + 7*0). - Charlie Marion, Jul 18 2003
With interpolated zeros, this is n*(n+2)*(1+(-1)^n)/16. - Benoit Cloitre, Aug 19 2003
a(n+1) is the determinant of the n X n symmetric Pascal matrix M_(i, j) = binomial(i+j+1, i). - Benoit Cloitre, Aug 19 2003
a(n) = ((n+1)^3 - n^3 - 1)/6. - Xavier Acloque, Oct 24 2003
a(n) = a(n-1) + (1 + sqrt(1 + 8*a(n-1)))/2. This recursive relation is inverted when taking the negative branch of the square root, i.e., a(n) is transformed into a(n-1) rather than a(n+1). - Carl R. White, Nov 04 2003
a(n) = Sum_{k=1..n} phi(k)*floor(n/k) = Sum_{k=1..n} A000010(k)*A010766(n, k) (R. Dedekind). - Vladeta Jovovic, Feb 05 2004
a(n) + a(n+1) = (n+1)^2. - N. J. A. Sloane, Feb 19 2004
a(n) = a(n-2) + 2*n - 1. - Paul Barry, Jul 17 2004
a(n) = sqrt(Sum_{i=1..n} Sum_{j=1..n} (i*j)) = sqrt(A000537(n)). - Alexander Adamchuk, Oct 24 2004
a(n) = sqrt(sqrt(Sum_{i=1..n} Sum_{j=1..n} (i*j)^3)) = (Sum_{i=1..n} Sum_{j=1..n} Sum_{k=1..n} (i*j*k)^3)^(1/6). - Alexander Adamchuk, Oct 26 2004
a(n) == 1 (mod n+2) if n is odd and a(n) == n/2+2 (mod n+2) if n is even. - Jon Perry, Dec 16 2004
a(0) = 0, a(1) = 1, a(n) = 2*a(n-1) - a(n-2) + 1. - Miklos Kristof, Mar 09 2005
a(n) = a(n-1) + n. - Zak Seidov, Mar 06 2005
a(n) = A108299(n+3,4) = -A108299(n+4,5). - Reinhard Zumkeller, Jun 01 2005
a(n) = A111808(n,2) for n > 1. - Reinhard Zumkeller, Aug 17 2005
a(n)*a(n+1) = A006011(n+1) = (n+1)^2*(n^2+2)/4 = 3*A002415(n+1) = 1/2*a(n^2+2*n). a(n-1)*a(n) = (1/2)*a(n^2-1). - Alexander Adamchuk, Apr 13 2006 [Corrected and edited by Charlie Marion, Nov 26 2010]
a(n) = floor((2*n+1)^2/8). - Paul Barry, May 29 2006
For positive n, we have a(8*a(n))/a(n) = 4*(2*n+1)^2 = (4*n+2)^2, i.e., a(A033996(n))/a(n) = 4*A016754(n) = (A016825(n))^2 = A016826(n). - Lekraj Beedassy, Jul 29 2006
a(n)^2 + a(n+1)^2 = a((n+1)^2) [R B Nelsen, Math Mag 70 (2) (1997), p. 130]. - R. J. Mathar, Nov 22 2006
a(n) = A126890(n,0). - Reinhard Zumkeller, Dec 30 2006
a(n)*a(n+k)+a(n+1)*a(n+1+k) = a((n+1)*(n+1+k)). Generalizes previous formula dated Nov 22 2006 [and comments by J. M. Bergot dated May 22 2012]. - Charlie Marion, Feb 04 2011
(sqrt(8*a(n)+1)-1)/2 = n. - David W. Cantrell (DWCantrell(AT)sigmaxi.net), Feb 26 2007
a(n) = A023896(n) + A067392(n). - Lekraj Beedassy, Mar 02 2007
Sum_{k=0..n} a(k)*A039599(n,k) = A002457(n-1), for n >= 1. - Philippe Deléham, Jun 10 2007
8*a(n)^3 + a(n)^2 = Y(n)^2, where Y(n) = n*(n+1)*(2*n+1)/2 = 3*A000330(n). - Mohamed Bouhamida, Nov 06 2007 [Edited by Derek Orr, May 05 2015]
A general formula for polygonal numbers is P(k,n) = (k-2)*(n-1)n/2 + n = n + (k-2)*A000217(n-1), for n >= 1, k >= 3. - Omar E. Pol, Apr 28 2008 and Mar 31 2013
a(3*n) = A081266(n), a(4*n) = A033585(n), a(5*n) = A144312(n), a(6*n) = A144314(n). - Reinhard Zumkeller, Sep 17 2008
a(n) = A022264(n) - A049450(n). - Reinhard Zumkeller, Oct 09 2008
If we define f(n,i,a) = Sum_{j=0..k-1} (binomial(n,k)*Stirling1(n-k,i)*Product_{j=0..k-1} (-a-j)), then a(n) = -f(n,n-1,1), for n >= 1. - Milan Janjic, Dec 20 2008
4*a(x) + 4*a(y) + 1 = (x+y+1)^2 + (x-y)^2. - Vladimir Shevelev, Jan 21 2009
a(n) = A000124(n-1) + n-1 for n >= 2. a(n) = A000124(n) - 1. - Jaroslav Krizek, Jun 16 2009
An exponential generating function for the inverse of this sequence is given by Sum_{m>=0} ((Pochhammer(1, m)*Pochhammer(1, m))*x^m/(Pochhammer(3, m)*factorial(m))) = ((2-2*x)*log(1-x)+2*x)/x^2, the n-th derivative of which has a closed form which must be evaluated by taking the limit as x->0. A000217(n+1) = (lim_{x->0} d^n/dx^n (((2-2*x)*log(1-x)+2*x)/x^2))^-1 = (lim_{x->0} (2*Gamma(n)*(-1/x)^n*(n*(x/(-1+x))^n*(-x+1+n)*LerchPhi(x/(-1+x), 1, n) + (-1+x)*(n+1)*(x/(-1+x))^n + n*(log(1-x)+log(-1/(-1+x)))*(-x+1+n))/x^2))^-1. - Stephen Crowley, Jun 28 2009
a(n) = A034856(n+1) - A005408(n) = A005843(n) + A000124(n) - A005408(n). - Jaroslav Krizek, Sep 05 2009
a(A006894(n)) = a(A072638(n-1)+1) = A072638(n) = A006894(n+1)-1 for n >= 1. For n=4, a(11) = 66. - Jaroslav Krizek, Sep 12 2009
With offset 1, a(n) = floor(n^3/(n+1))/2. - Gary Detlefs, Feb 14 2010
a(n) = 4*a(floor(n/2)) + (-1)^(n+1)*floor((n+1)/2). - Bruno Berselli, May 23 2010
a(n) = 3*a(n-1) - 3*a(n-2) + a(n-3); a(0)=0, a(1)=1. - Mark Dols, Aug 20 2010
From Charlie Marion, Oct 15 2010: (Start)
a(n) + 2*a(n-1) + a(n-2) = n^2 + (n-1)^2; and
a(n) + 3*a(n-1) + 3*a(n-2) + a(n-3) = n^2 + 2*(n-1)^2 + (n-2)^2.
In general, for n >= m > 2, Sum_{k=0..m} binomial(m,m-k)*a(n-k) = Sum_{k=0..m-1} binomial(m-1,m-1-k)*(n-k)^2.
a(n) - 2*a(n-1) + a(n-2) = 1, a(n) - 3*a(n-1) + 3*a(n-2) - a(n-3) = 0 and a(n) - 4*a(n-1) + 6*a(n-2) - 4*(a-3) + a(n-4) = 0.
In general, for n >= m > 2, Sum_{k=0..m} (-1)^k*binomial(m,m-k)*a(n-k) = 0.
(End)
a(n) = sqrt(A000537(n)). - Zak Seidov, Dec 07 2010
For n > 0, a(n) = 1/(Integral_{x=0..Pi/2} 4*(sin(x))^(2*n-1)*(cos(x))^3). - Francesco Daddi, Aug 02 2011
a(n) = A110654(n)*A008619(n). - Reinhard Zumkeller, Aug 24 2011
a(2*k-1) = A000384(k), a(2*k) = A014105(k), k > 0. - Omar E. Pol, Sep 13 2011
a(n) = A026741(n)*A026741(n+1). - Charles R Greathouse IV, Apr 01 2012
a(n) + a(a(n)) + 1 = a(a(n)+1). - J. M. Bergot, Apr 27 2012
a(n) = -s(n+1,n), where s(n,k) are the Stirling numbers of the first kind, A048994. - Mircea Merca, May 03 2012
a(n)*a(n+1) = a(Sum_{m=1..n} A005408(m))/2, for n >= 1. For example, if n=8, then a(8)*a(9) = a(80)/2 = 1620. - Ivan N. Ianakiev, May 27 2012
a(n) = A002378(n)/2 = (A001318(n) + A085787(n))/2. - Omar E. Pol, Jan 11 2013
G.f.: x * (1 + 3x + 6x^2 + ...) = x * Product_{j>=0} (1+x^(2^j))^3 = x * A(x) * A(x^2) * A(x^4) * ..., where A(x) = (1 + 3x + 3x^2 + x^3). - Gary W. Adamson, Jun 26 2012
G.f.: G(0) where G(k) = 1 + (2*k+3)*x/(2*k+1 - x*(k+2)*(2*k+1)/(x*(k+2) + (k+1)/G(k+1))); (continued fraction, 3rd kind, 3-step). - Sergei N. Gladkovskii, Nov 23 2012
a(n) = A002088(n) + A063985(n). - Reinhard Zumkeller, Jan 21 2013
G.f.: x + 3*x^2/(Q(0)-3*x) where Q(k) = 1 + k*(x+1) + 3*x - x*(k+1)*(k+4)/Q(k+1); (continued fraction). - Sergei N. Gladkovskii, Mar 14 2013
a(n) + a(n+1) + a(n+2) + a(n+3) + n = a(2*n+4). - Ivan N. Ianakiev, Mar 16 2013
a(n) + a(n+1) + ... + a(n+8) + 6*n = a(3*n+15). - Charlie Marion, Mar 18 2013
a(n) + a(n+1) + ... + a(n+20) + 2*n^2 + 57*n = a(5*n+55). - Charlie Marion, Mar 18 2013
3*a(n) + a(n-1) = a(2*n), for n > 0. - Ivan N. Ianakiev, Apr 05 2013
In general, a(k*n) = (2*k-1)*a(n) + a((k-1)*n-1). - Charlie Marion, Apr 20 2015
Also, a(k*n) = a(k)*a(n) + a(k-1)*a(n-1). - Robert Israel, Apr 20 2015
a(n+1) = det(binomial(i+2,j+1), 1 <= i,j <= n). - Mircea Merca, Apr 06 2013
a(n) = floor(n/2) + ceiling(n^2/2) = n - floor(n/2) + floor(n^2/2). - Wesley Ivan Hurt, Jun 15 2013
a(n) = floor((n+1)/(exp(2/(n+1))-1)). - Richard R. Forberg, Jun 22 2013
Sum_{n>=1} a(n)/n! = 3*exp(1)/2 by the e.g.f. Also see A067764 regarding ratios calculated this way for binomial coefficients in general. - Richard R. Forberg, Jul 15 2013
Sum_{n>=1} (-1)^(n+1)/a(n) = 4*log(2) - 2 = 0.7725887... . - Richard R. Forberg, Aug 11 2014
2/(Sum_{n>=m} 1/a(n)) = m, for m > 0. - Richard R. Forberg, Aug 12 2014
A228474(a(n))=n; A248952(a(n))=0; A248953(a(n))=a(n); A248961(a(n))=A000330(n). - Reinhard Zumkeller, Oct 20 2014
a(a(n)-1) + a(a(n+2)-1) + 1 = A000124(n+1)^2. - Charlie Marion, Nov 04 2014
a(n) = 2*A000292(n) - A000330(n). - Luciano Ancora, Mar 14 2015
a(n) = A007494(n-1) + A099392(n) for n > 0. - Bui Quang Tuan, Mar 27 2015
Sum_{k=0..n} k*a(k+1) = a(A000096(n+1)). - Charlie Marion, Jul 15 2015
Let O(n) be the oblong number n(n+1) = A002378(n) and S(n) the square number n^2 = A000290(n). Then a(n) + a(n+2k) = O(n+k) + S(k) and a(n) + a(n+2k+1) = S(n+k+1) + O(k). - Charlie Marion, Jul 16 2015
A generalization of the Nov 22 2006 formula, a(n)^2 + a(n+1)^2 = a((n+1)^2), follows. Let T(k,n) = a(n) + k. Then for all k, T(k,n)^2 + T(k,n+1)^2 = T(k,(n+1)^2 + 2*k) - 2*k. - Charlie Marion, Dec 10 2015
a(n)^2 + a(n+1)^2 = a(a(n) + a(n+1)). Deducible from N. J. A. Sloane's a(n) + a(n+1) = (n+1)^2 and R. B. Nelson's a(n)^2 + a(n+1)^2 = a((n+1)^2). - Ben Paul Thurston, Dec 28 2015
Dirichlet g.f.: (zeta(s-2) + zeta(s-1))/2. - Ilya Gutkovskiy, Jun 26 2016
a(n)^2 - a(n-1)^2 = n^3. - Miquel Cerda, Jun 29 2016
a(n) = A080851(0,n-1). - R. J. Mathar, Jul 28 2016
a(n) = A000290(n-1) - A034856(n-4). - Peter M. Chema, Sep 25 2016
a(n)^2 + a(n+3)^2 + 19 = a(n^2 + 4*n + 10). - Charlie Marion, Nov 23 2016
2*a(n)^2 + a(n) = a(n^2+n). - Charlie Marion, Nov 29 2016
G.f.: x/(1-x)^3 = (x * r(x) * r(x^3) * r(x^9) * r(x^27) * ...), where r(x) = (1 + x + x^2)^3 = (1 + 3*x + 6*x^2 + 7*x^3 + 6*x^4 + 3*x^5 + x^6). - Gary W. Adamson, Dec 03 2016
a(n) = sum of the elements of inverse of matrix Q(n), where Q(n) has elements q_i,j = 1/(1-4*(i-j)^2). So if e = appropriately sized vector consisting of 1's, then a(n) = e'.Q(n)^-1.e. - Michael Yukish, Mar 20 2017
a(n) = Sum_{k=1..n} ((2*k-1)!!*(2*n-2*k-1)!!)/((2*k-2)!!*(2*n-2*k)!!). - Michael Yukish, Mar 20 2017
Sum_{i=0..k-1} a(n+i) = (3*k*n^2 + 3*n*k^2 + k^3 - k)/6. - Christopher Hohl, Feb 23 2019
a(n) = A060544(n + 1) - A016754(n). - Ralf Steiner, Nov 09 2019
a(n) == 0 (mod n) iff n is odd (see De Koninck reference). - Bernard Schott, Jan 10 2020
8*a(k)*a(n) + ((a(k)-1)*n + a(k))^2 = ((a(k)+1)*n + a(k))^2. This formula reduces to the well-known formula, 8*a(n) + 1 = (2*n+1)^2, when k = 1. - Charlie Marion, Jul 23 2020
a(k)*a(n) = Sum_{i = 0..k-1} (-1)^i*a((k-i)*(n-i)). - Charlie Marion, Dec 04 2020
From Amiram Eldar, Jan 20 2021: (Start)
Product_{n>=1} (1 + 1/a(n)) = cosh(sqrt(7)*Pi/2)/(2*Pi).
Product_{n>=2} (1 - 1/a(n)) = 1/3. (End)
a(n) = Sum_{k=1..2*n-1} (-1)^(k+1)*a(k)*a(2*n-k). For example, for n = 4, 1*28 - 3*21 + 6*15 - 10*10 + 15*6 - 21*3 + 28*1 = 10. - Charlie Marion, Mar 23 2022
2*a(n) = A000384(n) - n^2 + 2*n. In general, if P(k,n) = the n-th k-gonal number, then (j+1)*a(n) = P(5 + j, n) - n^2 + (j+1)*n. More generally, (j+1)*P(k,n) = P(2*k + (k-2)*(j-1),n) - n^2 + (j+1)*n. - Charlie Marion, Mar 14 2023
a(n) = A109613(n) * A004526(n+1). - Torlach Rush, Nov 10 2023
a(n) = (1/6)* Sum_{k = 0..3*n} (-1)^(n+k+1) * k*(k + 1) * binomial(3*n+k, 2*k). - Peter Bala, Nov 03 2024
From Peter Bala, Jul 05 2025: (Start)
The following series telescope: for k >= 0,
Sum_{n >= 1} a(n)*a(n+2)*...*a(n+2*k)/(a(n+1)*a(n+3)*...*a(n+2*k+3)) = 1/(2*k + 3);
Sum_{n >= 1} a(n+1)*a(n+3)*...*a(n+2*k+1)/(a(n)*a(n+2)*...*a(n+2*k+2)) = 2/(2*k + 3) * Sum_{i = 1..2*k+3} 1/i. (End)

Extensions

Edited by Derek Orr, May 05 2015

A007318 Pascal's triangle read by rows: C(n,k) = binomial(n,k) = n!/(k!*(n-k)!), 0 <= k <= n.

Original entry on oeis.org

1, 1, 1, 1, 2, 1, 1, 3, 3, 1, 1, 4, 6, 4, 1, 1, 5, 10, 10, 5, 1, 1, 6, 15, 20, 15, 6, 1, 1, 7, 21, 35, 35, 21, 7, 1, 1, 8, 28, 56, 70, 56, 28, 8, 1, 1, 9, 36, 84, 126, 126, 84, 36, 9, 1, 1, 10, 45, 120, 210, 252, 210, 120, 45, 10, 1, 1, 11, 55, 165, 330, 462, 462, 330, 165, 55, 11, 1
Offset: 0

Views

Author

N. J. A. Sloane and Mira Bernstein, Apr 28 1994

Keywords

Comments

A. W. F. Edwards writes: "It [the triangle] was first written down long before 1654, the year in which Blaise Pascal wrote his Traité du triangle arithmétique, but it was this work that brought together all the different aspects of the numbers for the first time. In it Pascal developed the properties of the number as a piece of pure mathematics ... and then, in a series of appendices, showed how these properties were relevant to the study of the figurate numbers, to the theory of combinations, to the expansion of binomial expressions, and to the solution of an important problem in the theory of probability." (A. W. F. Edwards, Pascal's Arithmetical Triangle, Johns Hopkins University Press (2002), p. xiii)
Edwards reports that the naming of the triangle after Pascal was done first by Montmort in 1708 as the "Table de M. Pascal pour les combinaisons" and then by De Moivre in 1730 as the "Triangulum Arithmeticum PASCALANIUM". (Edwards, p. xiv)
In China, Yang Hui in 1261 listed the coefficients of (a+b)^n up to n=6, crediting the expansion to Chia Hsein's Shih-so suan-shu circa 1100. Another prominent early use was in Chu Shih-Chieh's Precious Mirror of the Four Elements in 1303. (Edwards, p. 51)
In Persia, Al-Karaji discovered the binomial triangle "some time soon after 1007", and Al-Samawal published it in the Al-bahir some time before 1180. (Edwards, p. 52)
In India, Halayuda's commentary (circa 900) on Pingala's treatise on syllabic combinations (circa 200 B.C.E.) contains a clear description of the additive computation of the triangle. (Amulya Kumar Bag, Binomial Theorem in Ancient India, p. 72)
Also in India, the multiplicative formula for C(n,k) was known to Mahavira in 850 and restated by Bhaskara in 1150. (Edwards, p. 27)
In Italy, Tartaglia published the triangle in his General trattato (1556), and Cardano published it in his Opus novum (1570). (Edwards, p. 39, 44) - Russ Cox, Mar 29 2022
Also sometimes called Omar Khayyam's triangle.
Also sometimes called Yang Hui's triangle.
C(n,k) = number of k-element subsets of an n-element set.
Row n gives coefficients in expansion of (1+x)^n.
Binomial(n+k-1,n-1) is the number of ways of placing k indistinguishable balls into n boxes (the "bars and stars" argument - see Feller).
Binomial(n-1,k-1) is the number of compositions (ordered partitions) of n with k summands.
Binomial(n+k-1,k-1) is the number of weak compositions (ordered weak partitions) of n into exactly k summands. - Juergen Will, Jan 23 2016
Binomial(n,k) is the number of lattice paths from (0,0) to (n,k) using steps (1,0) and (1,1). - Joerg Arndt, Jul 01 2011
If thought of as an infinite lower triangular matrix, inverse begins:
+1
-1 +1
+1 -2 +1
-1 +3 -3 +1
+1 -4 +6 -4 +1
All 2^n palindromic binomial coefficients starting after the A006516(n)-th entry are odd. - Lekraj Beedassy, May 20 2003
Binomial(n+k-1,n-1) is the number of standard tableaux of shape (n,1^k). - Emeric Deutsch, May 13 2004
Can be viewed as an array, read by antidiagonals, where the entries in the first row and column are all 1's and A(i,j) = A(i-1,j) + A(i,j-1) for all other entries. The determinant of each of its n X n subarrays starting at (0,0) is 1. - Gerald McGarvey, Aug 17 2004
Also the lower triangular readout of the exponential of a matrix whose entry {j+1,j} equals j+1 (and all other entries are zero). - Joseph Biberstine (jrbibers(AT)indiana.edu), May 26 2006
Binomial(n-3,k-1) counts the permutations in S_n which have zero occurrences of the pattern 231 and one occurrence of the pattern 132 and k descents. Binomial(n-3,k-1) also counts the permutations in S_n which have zero occurrences of the pattern 231 and one occurrence of the pattern 213 and k descents. - David Hoek (david.hok(AT)telia.com), Feb 28 2007
Inverse of A130595 (as an infinite lower triangular matrix). - Philippe Deléham, Aug 21 2007
Consider integer lists LL of lists L of the form LL = [m#L] = [m#[k#2]] (where '#' means 'times') like LL(m=3,k=3) = [[2,2,2],[2,2,2],[2,2,2]]. The number of the integer list partitions of LL(m,k) is equal to binomial(m+k,k) if multiple partitions like [[1,1],[2],[2]] and [[2],[2],[1,1]] and [[2],[1,1],[2]] are counted only once. For the example, we find 4*5*6/3! = 20 = binomial(6,3). - Thomas Wieder, Oct 03 2007
The infinitesimal generator for Pascal's triangle and its inverse is A132440. - Tom Copeland, Nov 15 2007
Row n>=2 gives the number of k-digit (k>0) base n numbers with strictly decreasing digits; e.g., row 10 for A009995. Similarly, row n-1>=2 gives the number of k-digit (k>1) base n numbers with strictly increasing digits; see A009993 and compare A118629. - Rick L. Shepherd, Nov 25 2007
From Lee Naish (lee(AT)cs.mu.oz.au), Mar 07 2008: (Start)
Binomial(n+k-1, k) is the number of ways a sequence of length k can be partitioned into n subsequences (see the Naish link).
Binomial(n+k-1, k) is also the number of n- (or fewer) digit numbers written in radix at least k whose digits sum to k. For example, in decimal, there are binomial(3+3-1,3)=10 3-digit numbers whose digits sum to 3 (see A052217) and also binomial(4+2-1,2)=10 4-digit numbers whose digits sum to 2 (see A052216). This relationship can be used to generate the numbers of sequences A052216 to A052224 (and further sequences using radix greater than 10). (End)
From Milan Janjic, May 07 2008: (Start)
Denote by sigma_k(x_1,x_2,...,x_n) the elementary symmetric polynomials. Then:
Binomial(2n+1,2k+1) = sigma_{n-k}(x_1,x_2,...,x_n), where x_i = tan^2(i*Pi/(2n+1)), (i=1,2,...,n).
Binomial(2n,2k+1) = 2n*sigma_{n-1-k}(x_1,x_2,...,x_{n-1}), where x_i = tan^2(i*Pi/(2n)), (i=1,2,...,n-1).
Binomial(2n,2k) = sigma_{n-k}(x_1,x_2,...,x_n), where x_i = tan^2((2i-1)Pi/(4n)), (i=1,2,...,n).
Binomial(2n+1,2k) = (2n+1)sigma_{n-k}(x_1,x_2,...,x_n), where x_i = tan^2((2i-1)Pi/(4n+2)), (i=1,2,...,n). (End)
Given matrices R and S with R(n,k) = binomial(n,k)*r(n-k) and S(n,k) = binomial(n,k)*s(n-k), then R*S = T where T(n,k) = binomial(n,k)*[r(.)+s(.)]^(n-k), umbrally. And, the e.g.f.s for the row polynomials of R, S and T are, respectively, exp(x*t)*exp[r(.)*x], exp(x*t)*exp[s(.)*x] and exp(x*t)*exp[r(.)*x]*exp[s(.)*x] = exp{[t+r(.)+s(.)]*x}. The row polynomials are essentially Appell polynomials. See A132382 for an example. - Tom Copeland, Aug 21 2008
As the rectangle R(m,n) = binomial(m+n-2,m-1), the weight array W (defined generally at A144112) of R is essentially R itself, in the sense that if row 1 and column 1 of W=A144225 are deleted, the remaining array is R. - Clark Kimberling, Sep 15 2008
If A007318 = M as an infinite lower triangular matrix, M^n gives A130595, A023531, A007318, A038207, A027465, A038231, A038243, A038255, A027466, A038279, A038291, A038303, A038315, A038327, A133371, A147716, A027467 for n=-1,0,1,2,3,4,5,6,7,8,9,10,11,12,13,14,15 respectively. - Philippe Deléham, Nov 11 2008
The coefficients of the polynomials with e.g.f. exp(x*t)*(cosh(t)+sinh(t)). - Peter Luschny, Jul 09 2009
The triangle or chess sums, see A180662 for their definitions, link Pascal's triangle with twenty different sequences, see the crossrefs. All sums come in pairs due to the symmetrical nature of this triangle. The knight sums Kn14 - Kn110 have been added. It is remarkable that all knight sums are related to the Fibonacci numbers, i.e., A000045, but none of the others. - Johannes W. Meijer, Sep 22 2010
Binomial(n,k) is also the number of ways to distribute n+1 balls into k+1 urns so that each urn gets at least one ball. See example in the example section below. - Dennis P. Walsh, Jan 29 2011
Binomial(n,k) is the number of increasing functions from {1,...,k} to {1,...,n} since there are binomial(n,k) ways to choose the k distinct, ordered elements of the range from the codomain {1,...,n}. See example in the example section below. - Dennis P. Walsh, Apr 07 2011
Central binomial coefficients: T(2*n,n) = A000984(n), T(n, floor(n/2)) = A001405(n). - Reinhard Zumkeller, Nov 09 2011
Binomial(n,k) is the number of subsets of {1,...,n+1} with k+1 as median element. To see this, note that Sum_{j=0..min(k,n-k)}binomial(k,j)*binomial(n-k,j) = binomial(n,k). See example in Example section below. - Dennis P. Walsh, Dec 15 2011
This is the coordinator triangle for the lattice Z^n, see Conway-Sloane, 1997. - N. J. A. Sloane, Jan 17 2012
One of three infinite families of integral factorial ratio sequences of height 1 (see Bober, Theorem 1.2). The other two are A046521 and A068555. For real r >= 0, C_r(n,k) := floor(r*n)!/(floor(r*k)!*floor(r*(n-k))!) is integral. See A211226 for the case r = 1/2. - Peter Bala, Apr 10 2012
Define a finite triangle T(m,k) with n rows such that T(m,0) = 1 is the left column, T(m,m) = binomial(n-1,m) is the right column, and the other entries are T(m,k) = T(m-1,k-1) + T(m-1,k) as in Pascal's triangle. The sum of all entries in T (there are A000217(n) elements) is 3^(n-1). - J. M. Bergot, Oct 01 2012
The lower triangular Pascal matrix serves as a representation of the operator exp(RLR) in a basis composed of a sequence of polynomials p_n(x) characterized by ladder operators defined by R p_n(x) = p_(n+1)(x) and L p_n(x) = n p_(n-1)(x). See A132440, A218272, A218234, A097805, and A038207. The transposed and padded Pascal matrices can be associated to the special linear group SL2. - Tom Copeland, Oct 25 2012
See A193242. - Alexander R. Povolotsky, Feb 05 2013
A permutation p_1...p_n of the set {1,...,n} has a descent at position i if p_i > p_(i+1). Let S(n) denote the subset of permutations p_1...p_n of {1,...,n} such that p_(i+1) - p_i <= 1 for i = 1,...,n-1. Then binomial(n,k) gives the number of permutations in S(n+1) with k descents. Alternatively, binomial(n,k) gives the number of permutations in S(n+1) with k+1 increasing runs. - Peter Bala, Mar 24 2013
Sum_{n=>0} binomial(n,k)/n! = e/k!, where e = exp(1), while allowing n < k where binomial(n,k) = 0. Also Sum_{n>=0} binomial(n+k-1,k)/n! = e * A000262(k)/k!, and for k>=1 equals e * A067764(k)/A067653(k). - Richard R. Forberg, Jan 01 2014
The square n X n submatrix (first n rows and n columns) of the Pascal matrix P(x) defined in the formulas below when multiplying on the left the Vandermonde matrix V(x_1,...,x_n) (with ones in the first row) translates the matrix to V(x_1+x,...,x_n+x) while leaving the determinant invariant. - Tom Copeland, May 19 2014
For k>=2, n>=k, k/((k/(k-1) - Sum_{n=k..m} 1/binomial(n,k))) = m!/((m-k+1)!*(k-2)!). Note: k/(k-1) is the infinite sum. See A000217, A000292, A000332 for examples. - Richard R. Forberg, Aug 12 2014
Let G_(2n) be the subgroup of the symmetric group S_(2n) defined by G_(2n) = {p in S_(2n) | p(i) = i (mod n) for i = 1,2,...,2n}. G_(2n) has order 2^n. Binomial(n,k) gives the number of permutations in G_(2n) having n + k cycles. Cf. A130534 and A246117. - Peter Bala, Aug 15 2014
C(n,k) = the number of Dyck paths of semilength n+1, with k+1 "u"'s in odd numbered positions and k+1 returns to the x axis. Example: {U = u in odd position and = return to x axis} binomial(3,0)=1 (Uudududd); binomial(3,1)=3 [(Uududd_Ud_), (Ud_Uududd_), (Uudd_Uudd_)]; binomial(3,2)=3 [(Ud_Ud_Uudd_), (Uudd_Ud_Ud_), (Ud_Uudd_Ud_)]; binomial(3,3)=1 (Ud_Ud_Ud_Ud_). - Roger Ford, Nov 05 2014
From Daniel Forgues, Mar 12 2015: (Start)
The binomial coefficients binomial(n,k) give the number of individuals of the k-th generation after n population doublings. For each doubling of population, each individual's clone has its generation index incremented by 1, and thus goes to the next row. Just tally up each row from 0 to 2^n - 1 to get the binomial coefficients.
0 1 3 7 15
0: O | . | . . | . . . . | . . . . . . . . |
1: | O | O . | O . . . | O . . . . . . . |
2: | | O | O O . | O O . O . . . |
3: | | | O | O O O . |
4: | | | | O |
This is a fractal process: to get the pattern from 0 to 2^n - 1, append a shifted down (by one row) copy of the pattern from 0 to 2^(n-1) - 1 to the right of the pattern from 0 to 2^(n-1) - 1. (Inspired by the "binomial heap" data structure.)
Sequence of generation indices: 1's-counting sequence: number of 1's in binary expansion of n (or the binary weight of n) (see A000120):
{0, 1, 1, 2, 1, 2, 2, 3, 1, 2, 2, 3, 2, 3, 3, 4, ...}
Binary expansion of 0 to 15:
0 1 10 11 100 101 110 111 1000 1001 1010 1011 1100 1101 1111
(End)
A258993(n,k) = T(n+k,n-k), n > 0. - Reinhard Zumkeller, Jun 22 2015
T(n,k) is the number of set partitions w of [n+1] that avoid 1/2/3 with rb(w)=k. The same holds for ls(w)=k, where avoidance is in the sense of Klazar and ls,rb defined by Wachs and White.
Satisfies Benford's law [Diaconis, 1977] - N. J. A. Sloane, Feb 09 2017
Let {A(n)} be a set with exactly n identical elements, with {A(0)} being the empty set E. Let {A(n,k)} be the k-th iteration of {A(n)}, with {A(n,0)} = {A(n)}. {A(n,1)} = The set of all the subsets of A{(n)}, including {A(n)} and E. {A(n,k)} = The set of all subsets of {A(n,k-1)}, including all of the elements of {A(n,k-1)}. Let A(n,k) be the number of elements in {A(n,k)}. Then A(n,k) = C(n+k,k), with each successive iteration replicating the members of the k-th diagonal of Pascal's Triangle. See examples. - Gregory L. Simay, Aug 06 2018
Binomial(n-1,k) is also the number of permutations avoiding both 213 and 312 with k ascents. - Lara Pudwell, Dec 19 2018
Binomial(n-1,k) is also the number of permutations avoiding both 132 and 213 with k ascents. - Lara Pudwell, Dec 19 2018
Binomial(n,k) is the dimension of the k-th exterior power of a vector space of dimension n. - Stefano Spezia, Dec 22 2018
C(n,k-1) is the number of unoriented colorings of the facets (or vertices) of an n-dimensional simplex using exactly k colors. Each chiral pair is counted as one when enumerating unoriented arrangements. - Robert A. Russell, Oct 20 2020
From Dilcher and Stolarsky: "Two of the most ubiquitous objects in mathematics are the sequence of prime numbers and the binomial coefficients (and thus Pascal's triangle). A connection between the two is given by a well-known characterization of the prime numbers: Consider the entries in the k-th row of Pascal's triangle, without the initial and final entries. They are all divisible by k if and only if k is a prime." - Tom Copeland, May 17 2021
Named "Table de M. Pascal pour les combinaisons" by Pierre Remond de Montmort (1708) after the French mathematician, physicist and philosopher Blaise Pascal (1623-1662). - Amiram Eldar, Jun 11 2021
Consider the n-th diagonal of the triangle as a sequence b(n) with n starting at 0. From it form a new sequence by leaving the 0th term as is, and thereafter considering all compositions of n, taking the product of b(i) over the respective numbers i in each composition, adding terms corresponding to compositions with an even number of parts subtracting terms corresponding to compositions with an odd number of parts. Then the n-th row of the triangle is obtained, with every second term multiplied by -1, followed by infinitely many zeros. For sequences starting with 1, this operation is a special case of a self-inverse operation, and therefore the converse is true. - Thomas Anton, Jul 05 2021
C(n,k) is the number of vertices in an n-dimensional unit hypercube, at an L1 distance of k (or: with a shortest path of k 1d-edges) from a given vertex. - Eitan Y. Levine, May 01 2023
C(n+k-1,k-1) is the number of vertices at an L1 distance from a given vertex in an infinite-dimensional box, which has k sides of length 2^m for each m >= 0. Equivalently, given a set of tokens containing k distinguishable tokens with value 2^m for each m >= 0, C(n+k-1,k-1) is the number of subsets of tokens with a total value of n. - Eitan Y. Levine, Jun 11 2023
Numbers in the k-th column, i.e., numbers of the form C(n,k) for n >= k, are known as k-simplex numbers. - Pontus von Brömssen, Jun 26 2023
Let r(k) be the k-th row and c(k) the k-th column. Denote convolution by * and repeated convolution by ^. Then r(k)*r(m)=r(k+m) and c(k)*c(m)=c(k+m+1). This is because r(k) = r(1) ^ k and c(k) = c(0) ^ k+1. - Eitan Y. Levine, Jul 23 2023
Number of permutations of length n avoiding simultaneously the patterns 231 and 312(resp., 213 and 231; 213 and 312) with k descents (equivalently, with k ascents). An ascent (resp., descent) in a permutation a(1)a(2)...a(n) is position i such that a(i)a(i+1)). - Tian Han, Nov 25 2023
C(n,k) are generalized binomial coefficients of order m=0. Calculated by the formula C(n,k) = Sum_{i=0..n-k} binomial(n+1, n-k-i)*Stirling2(i+ m+ 1, i+1) *(-1)^i, where m = 0 for n>= 0, 0 <= k <= n. - Igor Victorovich Statsenko, Feb 26 2023
The Akiyama-Tanigawa algorithm applied to the diagonals, binomial(n+k,k), yields the powers of n. - Shel Kaphan, May 03 2024

Examples

			Triangle T(n,k) begins:
   n\k 0   1   2   3   4   5   6   7   8   9  10  11 ...
   0   1
   1   1   1
   2   1   2   1
   3   1   3   3   1
   4   1   4   6   4   1
   5   1   5  10  10   5   1
   6   1   6  15  20  15   6   1
   7   1   7  21  35  35  21   7   1
   8   1   8  28  56  70  56  28   8   1
   9   1   9  36  84 126 126  84  36   9   1
  10   1  10  45 120 210 252 210 120  45  10   1
  11   1  11  55 165 330 462 462 330 165  55  11   1
  ...
There are C(4,2)=6 ways to distribute 5 balls BBBBB, among 3 different urns, < > ( ) [ ], so that each urn gets at least one ball, namely, <BBB>(B)[B], <B>(BBB)[B], <B>(B)[BBB], <BB>(BB)[B], <BB>(B)[BB], and <B>(BB)[BB].
There are C(4,2)=6 increasing functions from {1,2} to {1,2,3,4}, namely, {(1,1),(2,2)},{(1,1),(2,3)}, {(1,1),(2,4)}, {(1,2),(2,3)}, {(1,2),(2,4)}, and {(1,3),(2,4)}. - _Dennis P. Walsh_, Apr 07 2011
There are C(4,2)=6 subsets of {1,2,3,4,5} with median element 3, namely, {3}, {1,3,4}, {1,3,5}, {2,3,4}, {2,3,5}, and {1,2,3,4,5}. - _Dennis P. Walsh_, Dec 15 2011
The successive k-iterations of {A(0)} = E are E;E;E;...; the corresponding number of elements are 1,1,1,... The successive k-iterations of {A(1)} = {a} are (omitting brackets) a;a,E; a,E,E;...; the corresponding number of elements are 1,2,3,... The successive k-iterations of {A(2)} = {a,a} are aa; aa,a,E; aa, a, E and a,E and E;...; the corresponding number of elements are 1,3,6,... - _Gregory L. Simay_, Aug 06 2018
Boas-Buck type recurrence for column k = 4: T(8, 4) = (5/4)*(1 + 5 + 15 + 35) = 70. See the Boas-Buck comment above. - _Wolfdieter Lang_, Nov 12 2018

References

  • M. Abramowitz and I. A. Stegun, eds., Handbook of Mathematical Functions, National Bureau of Standards Applied Math. Series 55, 1964 (and various reprintings), p. 828.
  • Amulya Kumar Bag, Binomial theorem in ancient India, Indian Journal of History of Science, vol. 1 (1966), pp. 68-74.
  • Arthur T. Benjamin and Jennifer Quinn, Proofs that really count: the art of combinatorial proof, M.A.A. 2003, p. 63ff.
  • Boris A. Bondarenko, Generalized Pascal Triangles and Pyramids (in Russian), FAN, Tashkent, 1990, ISBN 5-648-00738-8.
  • Louis Comtet, Advanced Combinatorics, Reidel, 1974, p. 306.
  • John H. Conway and Richard K. Guy, The Book of Numbers, New York: Springer-Verlag, 1996. See pp. 68-74.
  • Paul Curtz, Intégration numérique des systèmes différentiels à conditions initiales, Centre de Calcul Scientifique de l'Armement, Arcueil, 1969.
  • A. W. F. Edwards, Pascal's Arithmetical Triangle, 2002.
  • William Feller, An Introduction to Probability Theory and Its Application, Vol. 1, 2nd ed. New York: Wiley, p. 36, 1968.
  • Ronald L. Graham, Donald E. Knuth, and Oren Patashnik, Concrete Mathematics. Addison-Wesley, Reading, MA, 2nd. ed., 1994, p. 155.
  • Jan Gullberg, Mathematics from the Birth of Numbers, W. W. Norton & Co., NY & London, 1997, §4.4 Powers and Roots, pp. 140-141.
  • David Hök, Parvisa mönster i permutationer [Swedish], 2007.
  • Donald E. Knuth, The Art of Computer Programming, Vol. 1, 2nd ed., p. 52.
  • Sergei K. Lando, Lecture on Generating Functions, Amer. Math. Soc., Providence, R.I., 2003, pp. 60-61.
  • Blaise Pascal, Traité du triangle arithmétique, avec quelques autres petits traitez sur la mesme matière, Desprez, Paris, 1665.
  • Clifford A. Pickover, A Passion for Mathematics, Wiley, 2005; see p. 71.
  • Alfred S. Posamentier, Math Charmers, Tantalizing Tidbits for the Mind, Prometheus Books, NY, 2003, pages 271-275.
  • A. P. Prudnikov, Yu. A. Brychkov, and O. I. Marichev, "Integrals and Series", Volume 1: "Elementary Functions", Chapter 4: "Finite Sums", New York, Gordon and Breach Science Publishers, 1986-1992.
  • John Riordan, An Introduction to Combinatorial Analysis, Wiley, 1958, p. 6.
  • John Riordan, Combinatorial Identities, Wiley, 1968, p. 2.
  • Robert Sedgewick and Philippe Flajolet, An Introduction to the Analysis of Algorithms, Addison-Wesley, Reading, MA, 1996, p. 143.
  • N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).
  • Jerome Spanier and Keith B. Oldham, "Atlas of Functions", Hemisphere Publishing Corp., 1987, chapter 6, pages 43-52.
  • James J. Tattersall, Elementary Number Theory in Nine Chapters, Cambridge University Press, 1999, pages 13, 30-33.
  • David Wells, The Penguin Dictionary of Curious and Interesting Numbers, Penguin Books, 1987, pp. 115-118.
  • Douglas B. West, Combinatorial Mathematics, Cambridge, 2021, p. 25.

Links

Crossrefs

Equals differences between consecutive terms of A102363. - David G. Williams (davidwilliams(AT)Paxway.com), Jan 23 2006
Row sums give A000079 (powers of 2).
Cf. A083093 (triangle read mod 3), A214292 (first differences of rows).
Partial sums of rows give triangle A008949.
The triangle of the antidiagonals is A011973.
Infinite matrix squared: A038207, cubed: A027465.
Cf. A101164. If rows are sorted we get A061554 or A107430.
Another version: A108044.
Cf. A008277, A132311, A132312, A052216, A052217, A052218, A052219, A052220, A052221, A052222, A052223, A144225, A202750, A211226, A047999, A026729, A052553, A051920, A193242.
Triangle sums (see the comments): A000079 (Row1); A000007 (Row2); A000045 (Kn11 & Kn21); A000071 (Kn12 & Kn22); A001924 (Kn13 & Kn23); A014162 (Kn14 & Kn24); A014166 (Kn15 & Kn25); A053739 (Kn16 & Kn26); A053295 (Kn17 & Kn27); A053296 (Kn18 & Kn28); A053308 (Kn19 & Kn29); A053309 (Kn110 & Kn210); A001519 (Kn3 & Kn4); A011782 (Fi1 & Fi2); A000930 (Ca1 & Ca2); A052544 (Ca3 & Ca4); A003269 (Gi1 & Gi2); A055988 (Gi3 & Gi4); A034943 (Ze1 & Ze2); A005251 (Ze3 & Ze4). - Johannes W. Meijer, Sep 22 2010
Fibonacci-Pascal triangles: A027926, A036355, A037027, A074829, A105809, A109906, A111006, A114197, A162741, A228074, A228196, A228576.
Cf. A137948, A245334.
Cf. A085478, A258993.
Cf. A115940 (pandigital binomial coefficients C(m,k) with k>1).
Cf. (simplex colorings) A325002 (oriented), [k==n+1] (chiral), A325003 (achiral), A325000 (k or fewer colors), A325009 (orthotope facets, orthoplex vertices), A325017 (orthoplex facets, orthotope vertices).
Triangles of generalized binomial coefficients (n,k)_m (or generalized Pascal triangles) for m = 2..12: A001263, A056939, A056940, A056941, A142465, A142467, A142468, A174109, A342889, A342890, A342891.

Programs

  • Axiom
    -- (start)
)set expose add constructor OutputForm
pascal(0,n) == 1
pascal(n,n) == 1
pascal(i,j | 0 < i and i < j) == pascal(i-1,j-1) + pascal(i,j-1)
pascalRow(n) == [pascal(i,n) for i in 0..n]
displayRow(n) == output center blankSeparate pascalRow(n)
for i in 0..20 repeat displayRow i -- (end)
  • GAP
    Flat(List([0..12],n->List([0..n],k->Binomial(n,k)))); # Stefano Spezia, Dec 22 2018
  • Haskell
    a007318 n k = a007318_tabl !! n !! k
a007318_row n = a007318_tabl !! n
a007318_list = concat a007318_tabl
a007318_tabl = iterate (\row -> zipWith (+) ([0] ++ row) (row ++ [0])) [1]
-- Cf. http://www.haskell.org/haskellwiki/Blow_your_mind#Mathematical_sequences
-- Reinhard Zumkeller, Nov 09 2011, Oct 22 2010
  • Magma
    /* As triangle: */ [[Binomial(n, k): k in [0..n]]: n in [0.. 10]]; // Vincenzo Librandi, Jul 29 2015
  • Maple
    A007318 := (n,k)->binomial(n,k);
  • Mathematica
    Flatten[Table[Binomial[n, k], {n, 0, 11}, {k, 0, n}]] (* Robert G. Wilson v, Jan 19 2004 *)
Flatten[CoefficientList[CoefficientList[Series[1/(1 - x - x*y), {x, 0, 12}], x], y]] (* Mats Granvik, Jul 08 2014 *)
  • Maxima
    create_list(binomial(n,k),n,0,12,k,0,n); /* Emanuele Munarini, Mar 11 2011 */
  • PARI
    C(n,k)=binomial(n,k) \\ Charles R Greathouse IV, Jun 08 2011
  • Python
    # See Hobson link. Further programs:
from math import prod,factorial
def C(n,k): return prod(range(n,n-k,-1))//factorial(k) # M. F. Hasler, Dec 13 2019, updated Apr 29 2022, Feb 17 2023
  • Python
    from math import comb, isqrt
def A007318(n): return comb(r:=(m:=isqrt(k:=n+1<<1))-(k<=m*(m+1)),n-comb(r+1,2)) # Chai Wah Wu, Nov 11 2024
  • Sage
    def C(n,k): return Subsets(range(n), k).cardinality() # Ralf Stephan, Jan 21 2014

Formula

a(n, k) = C(n,k) = binomial(n, k).
C(n, k) = C(n-1, k) + C(n-1, k-1).
The triangle is symmetric: C(n,k) = C(n,n-k).
a(n+1, m) = a(n, m) + a(n, m-1), a(n, -1) := 0, a(n, m) := 0, n
C(n, k) = n!/(k!(n-k)!) if 0<=k<=n, otherwise 0.
C(n, k) = ((n-k+1)/k) * C(n, k-1) with C(n, 0) = 1. - Michael B. Porter, Mar 23 2025
G.f.: 1/(1-y-x*y) = Sum_(C(n, k)*x^k*y^n, n, k>=0)
G.f.: 1/(1-x-y) = Sum_(C(n+k, k)*x^k*y^n, n, k>=0).
G.f. for row n: (1+x)^n = Sum_{k=0..n} C(n, k)*x^k.
G.f. for column k: x^k/(1-x)^(k+1); [corrected by Werner Schulte, Jun 15 2022].
E.g.f.: A(x, y) = exp(x+x*y).
E.g.f. for column n: x^n*exp(x)/n!.
In general the m-th power of A007318 is given by: T(0, 0) = 1, T(n, k) = T(n-1, k-1) + m*T(n-1, k), where n is the row-index and k is the column; also T(n, k) = m^(n-k)*C(n, k).
Triangle T(n, k) read by rows; given by A000007 DELTA A000007, where DELTA is Deléham's operator defined in A084938.
Let P(n+1) = the number of integer partitions of (n+1); let p(i) = the number of parts of the i-th partition of (n+1); let d(i) = the number of different parts of the i-th partition of (n+1); let m(i, j) = multiplicity of the j-th part of the i-th partition of (n+1). Define the operator Sum_{i=1..P(n+1), p(i)=k+1} as the sum running from i=1 to i=P(n+1) but taking only partitions with p(i)=(k+1) parts into account. Define the operator Product_{j=1..d(i)} = product running from j=1 to j=d(i). Then C(n, k) = Sum_{p(i)=(k+1), i=1..P(n+1)} p(i)! / [Product_{j=1..d(i)} m(i, j)!]. E.g., C(5, 3) = 10 because n=6 has the following partitions with m=3 parts: (114), (123), (222). For their multiplicities one has: (114): 3!/(2!*1!) = 3; (123): 3!/(1!*1!*1!) = 6; (222): 3!/3! = 1. The sum is 3 + 6 + 1 = 10 = C(5, 3). - Thomas Wieder, Jun 03 2005
C(n, k) = Sum_{j=0..k} (-1)^j*C(n+1+j, k-j)*A000108(j). - Philippe Deléham, Oct 10 2005
G.f.: 1 + x*(1 + x) + x^3*(1 + x)^2 + x^6*(1 + x)^3 + ... . - Michael Somos, Sep 16 2006
Sum_{k=0..floor(n/2)} x^(n-k)*T(n-k,k) = A000007(n), A000045(n+1), A002605(n), A030195(n+1), A057087(n), A057088(n), A057089(n), A057090(n), A057091(n), A057092(n), A057093(n) for x = 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, respectively. Sum_{k=0..floor(n/2)} (-1)^k*x^(n-k)*T(n-k,k) = A000007(n), A010892(n), A009545(n+1), A057083(n), A001787(n+1), A030191(n), A030192(n), A030240(n), A057084(n), A057085(n+1), A057086(n), A084329(n+1) for x = 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 20, respectively. - Philippe Deléham, Sep 16 2006
C(n,k) <= A062758(n) for n > 1. - Reinhard Zumkeller, Mar 04 2008
C(t+p-1, t) = Sum_{i=0..t} C(i+p-2, i) = Sum_{i=1..p} C(i+t-2, t-1). A binomial number is the sum of its left parent and all its right ancestors, which equals the sum of its right parent and all its left ancestors. - Lee Naish (lee(AT)cs.mu.oz.au), Mar 07 2008
From Paul D. Hanna, Mar 24 2011: (Start)
Let A(x) = Sum_{n>=0} x^(n*(n+1)/2)*(1+x)^n be the g.f. of the flattened triangle:
A(x) = 1 + (x + x^2) + (x^3 + 2*x^4 + x^5) + (x^6 + 3*x^7 + 3*x^8 + x^9) + ...
then A(x) equals the series Sum_{n>=0} (1+x)^n*x^n*Product_{k=1..n} (1-(1+x)*x^(2*k-1))/(1-(1+x)*x^(2*k));
also, A(x) equals the continued fraction 1/(1- x*(1+x)/(1+ x*(1-x)*(1+x)/(1- x^3*(1+x)/(1+ x^2*(1-x^2)*(1+x)/(1- x^5*(1+x)/(1+ x^3*(1-x^3)*(1+x)/(1- x^7*(1+x)/(1+ x^4*(1-x^4)*(1+x)/(1- ...))))))))).
These formulas are due to (1) a q-series identity and (2) a partial elliptic theta function expression. (End)
For n > 0: T(n,k) = A029600(n,k) - A029635(n,k), 0 <= k <= n. - Reinhard Zumkeller, Apr 16 2012
Row n of the triangle is the result of applying the ConvOffs transform to the first n terms of the natural numbers (1, 2, 3, ..., n). See A001263 or A214281 for a definition of this transformation. - Gary W. Adamson, Jul 12 2012
From L. Edson Jeffery, Aug 02 2012: (Start)
Row n (n >= 0) of the triangle is given by the n-th antidiagonal of the infinite matrix P^n, where P = (p_{i,j}), i,j >= 0, is the production matrix
0, 1,
1, 0, 1,
0, 1, 0, 1,
0, 0, 1, 0, 1,
0, 0, 0, 1, 0, 1,
0, 0, 0, 0, 1, 0, 1,
0, 0, 0, 0, 0, 1, 0, 1,
0, 0, 0, 0, 0, 0, 1, 0, 1,
... (End)
Row n of the triangle is also given by the n+1 coefficients of the polynomial P_n(x) defined by the recurrence P_0(x) = 1, P_1(x) = x + 1, P_n(x) = x*P_{n-1}(x) + P_{n-2}(x), n > 1. - L. Edson Jeffery, Aug 12 2013
For a closed-form formula for arbitrary left and right borders of Pascal-like triangles see A228196. - Boris Putievskiy, Aug 18 2013
For a closed-form formula for generalized Pascal's triangle see A228576. - Boris Putievskiy, Sep 04 2013
(1+x)^n = Sum_{k=0..n} (-1)^(n-k)*binomial(n,k)*Sum_{i=0..k} k^(n-i)*binomial(k,i)*x^(n-i)/(n-i)!. - Vladimir Kruchinin, Oct 21 2013
E.g.f.: A(x,y) = exp(x+x*y) = 1 + (x+y*x)/( E(0)-(x+y*x)), where E(k) = 1 + (x+y*x)/(1 + (k+1)/E(k+1) ); (continued fraction). - Sergei N. Gladkovskii, Nov 08 2013
E.g.f.: E(0) -1, where E(k) = 2 + x*(1+y)/(2*k+1 - x*(1+y)/E(k+1) ); (continued fraction). - Sergei N. Gladkovskii, Dec 24 2013
G.f.: 1 + x*(1+x)*(1+x^2*(1+x)/(W(0)-x^2-x^3)), where W(k) = 1 + (1+x)*x^(k+2) - (1+x)*x^(k+3)/W(k+1); (continued fraction). - Sergei N. Gladkovskii, Dec 24 2013
Sum_{n>=0} C(n,k)/n! = e/k!, where e = exp(1), while allowing n < k where C(n,k) = 0. Also Sum_{n>=0} C(n+k-1,k)/n! = e * A000262(k)/k!, and for k>=1 equals e * A067764(k)/A067653(k). - Richard R. Forberg, Jan 01 2014
Sum_{n>=k} 1/C(n,k) = k/(k-1) for k>=1. - Richard R. Forberg, Feb 10 2014
From Tom Copeland, Apr 26 2014: (Start)
Multiply each n-th diagonal of the Pascal lower triangular matrix by x^n and designate the result by A007318(x) = P(x). Then with :xD:^n = x^n*(d/dx)^n and B(n,x), the Bell polynomials (A008277),
A) P(x)= exp(x*dP) = exp[x*(e^M-I)] = exp[M*B(.,x)] = (I+dP)^B(.,x)
with dP = A132440, M = A238385-I, and I = identity matrix, and
B) P(:xD:) = exp(dP:xD:) = exp[(e^M-I):xD:] = exp[M*B(.,:xD:)] = exp[M*xD] = (I+dP)^(xD) with action P(:xD:)g(x) = exp(dP:xD:)g(x) = g[(I+dP)*x] (cf. also A238363).
C) P(x)^y = P(y*x). P(2x) = A038207(x) = exp[M*B(.,2x)], the face vectors of the n-dim hypercubes.
D) P(x) = [St2]*exp(x*M)*[St1] = [St2]*(I+dP)^x*[St1]
E) = [St1]^(-1)*(I+dP)^x*[St1] = [St2]*(I+dP)^x*[St2]^(-1)
where [St1]=padded A008275 just as [St2]=A048993=padded A008277 and exp(x*M) = (I+dP)^x = Sum_{k>=0} C(x,k) dP^k. (End)
T(n,k) = A245334(n,k) / A137948(n,k), 0 <= k <= n. - Reinhard Zumkeller, Aug 31 2014
From Peter Bala, Dec 21 2014: (Start)
Recurrence equation: T(n,k) = T(n-1,k)*(n + k)/(n - k) - T(n-1,k-1) for n >= 2 and 1 <= k < n, with boundary conditions T(n,0) = T(n,n) = 1. Note, changing the minus sign in the recurrence to a plus sign gives a recurrence for the square of the binomial coefficients - see A008459.
There is a relation between the e.g.f.'s of the rows and the diagonals of the triangle, namely, exp(x) * e.g.f. for row n = e.g.f. for diagonal n. For example, for n = 3 we have exp(x)*(1 + 3*x + 3*x^2/2! + x^3/3!) = 1 + 4*x + 10*x^2/2! + 20*x^3/3! + 35*x^4/4! + .... This property holds more generally for the Riordan arrays of the form ( f(x), x/(1 - x) ), where f(x) is an o.g.f. of the form 1 + f_1*x + f_2*x^2 + .... See, for example, A055248 and A106516.
Let P denote the present triangle. For k = 0,1,2,... define P(k) to be the lower unit triangular block array
/I_k 0\
\ 0 P/ having the k X k identity matrix I_k as the upper left block; in particular, P(0) = P. The infinite product P(0)*P(1)*P(2)*..., which is clearly well-defined, is equal to the triangle of Stirling numbers of the second kind A008277. The infinite product in the reverse order, that is, ...*P(2)*P(1)*P(0), is equal to the triangle of Stirling cycle numbers A130534. (End)
C(a+b,c) = Sum_{k=0..a} C(a,k)*C(b,b-c+k). This is a generalization of equation 1 from section 4.2.5 of the Prudnikov et al. reference, for a=b=c=n: C(2*n,n) = Sum_{k=0..n} C(n,k)^2. See Links section for animation of new formula. - Hermann Stamm-Wilbrandt, Aug 26 2015
The row polynomials of the Pascal matrix P(n,x) = (1+x)^n are related to the Bernoulli polynomials Br(n,x) and their umbral compositional inverses Bv(n,x) by the umbral relation P(n,x) = (-Br(.,-Bv(.,x)))^n = (-1)^n Br(n,-Bv(.,x)), which translates into the matrix relation P = M * Br * M * Bv, where P is the Pascal matrix, M is the diagonal matrix diag(1,-1,1,-1,...), Br is the matrix for the coefficients of the Bernoulli polynomials, and Bv that for the umbral inverse polynomials defined umbrally by Br(n,Bv(.,x)) = x^n = Bv(n,Br(.,x)). Note M = M^(-1). - Tom Copeland, Sep 05 2015
1/(1-x)^k = (r(x) * r(x^2) * r(x^4) * ...) where r(x) = (1+x)^k. - Gary W. Adamson, Oct 17 2016
Boas-Buck type recurrence for column k for Riordan arrays (see the Aug 10 2017 remark in A046521, also for the reference) with the Boas-Buck sequence b(n) = {repeat(1)}. T(n, k) = ((k+1)/(n-k))*Sum_{j=k..n-1} T(j, k), for n >= 1, with T(n, n) = 1. This reduces, with T(n, k) = binomial(n, k), to a known binomial identity (e.g, Graham et al. p. 161). - Wolfdieter Lang, Nov 12 2018
C((p-1)/a, b) == (-1)^b * fact_a(a*b-a+1)/fact_a(a*b) (mod p), where fact_n denotes the n-th multifactorial, a divides p-1, and the denominator of the fraction on the right side of the equation represents the modular inverse. - Isaac Saffold, Jan 07 2019
C(n,k-1) = A325002(n,k) - [k==n+1] = (A325002(n,k) + A325003(n,k)) / 2 = [k==n+1] + A325003(n,k). - Robert A. Russell, Oct 20 2020
From Hermann Stamm-Wilbrandt, May 13 2021: (Start)
Binomial sums are Fibonacci numbers A000045:
Sum_{k=0..n} C(n + k, 2*k + 1) = F(2*n).
Sum_{k=0..n} C(n + k, 2*k) = F(2*n + 1). (End)
C(n,k) = Sum_{i=0..k} A000108(i) * C(n-2i-1, k-i), for 0 <= k <= floor(n/2)-1. - Tushar Bansal, May 17 2025

Extensions

Checked all links, deleted 8 that seemed lost forever and were probably not of great importance. - N. J. A. Sloane, May 08 2018

A008290 Triangle T(n,k) of rencontres numbers (number of permutations of n elements with k fixed points).

Original entry on oeis.org

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

Views

Author

N. J. A. Sloane

Keywords

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

Examples

			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
...
It is essentially A238363 (unsigned and omitting the main diagonal), A211603 (with different offset) and appears to be A092271, again without the main diagonal. (End)

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

Crossrefs

Mirror of triangle A098825.
Columns give A000166, A000240, A000387, A000449, A000475, A129135, A129136, A129149, A129153, A129217, A129218, A129238, A129255.
Cf. A055137, A008291, A098558.
Cf. A080955.
Cf. A000012, A000142 (row sums), A000354.
Cf. A170942. Sub-triangle of A211229.
Cf. A092271, A111492, A211603, A238363.
T(2n,n) gives A281262.
Cf. A000023, A133314, A238385, A320582, A335111.

Programs

  • 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
  • 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 *)
T[0, 0]:=1; T[n_, 0]:=T[n, 0]=n  T[n-1, 0]+(-1)^n; T[n_, k_]:=T[n, k]=n/k T[n-1, k-1];
Flatten@Table[T[n, k], {n, 0, 9}, {k, 0, n}] (* Oliver Seipel, Nov 26 2024 *)
  • 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 */

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 formalism of A133314 applies to the pair of entries A008290 and A055137.
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)
T(n,k) = A145224(n,k)+A145225(n,k), refined by even and odd perms. - R. J. Mathar, Jul 06 2023

Extensions

Comments and more terms from Michael Somos, Apr 26 2000 and Christian G. Bower, Apr 26 2000

A007290 a(n) = 2*binomial(n,3).

Original entry on oeis.org

0, 0, 0, 2, 8, 20, 40, 70, 112, 168, 240, 330, 440, 572, 728, 910, 1120, 1360, 1632, 1938, 2280, 2660, 3080, 3542, 4048, 4600, 5200, 5850, 6552, 7308, 8120, 8990, 9920, 10912, 11968, 13090, 14280, 15540, 16872, 18278, 19760, 21320, 22960, 24682, 26488, 28380, 30360, 32430, 34592, 36848, 39200
Offset: 0

Views

Author

N. J. A. Sloane, Simon Plouffe

Keywords

Comments

Number of acute triangles made from the vertices of a regular n-polygon when n is even (cf. A000330). - Sen-Peng Eu, Apr 05 2001
a(n+2) is (-1)*coefficient of X in Zagier's polynomial (n,n-1). - Benoit Cloitre, Oct 12 2002
Definite integrals of certain products of 2 derivatives of (orthogonal) Chebyshev polynomials of the 2nd kind are pi-multiple of this sequence. For even (p+q): Integrate[ D[ChebyshevU[p, x], x] D[ChebyshevU[q, x], x] (1 - x^2)^(1/2), {x,-1,1}] / Pi = a(n), where n=Min[p,q]. Example: a(3)=20 because Integrate[ D[ChebyshevU[3, x], x] D[ChebyshevU[5, x], x] (1 - x^2)^(1/2), {x,-1,1}]/Pi = 20 since 3=Min[3,5] and 3+5 is even. - Christoph Pacher (Christoph.Pacher(AT)arcs.ac.at), Dec 16 2004
If Y is a 2-subset of an n-set X then, for n>=3, a(n-1) is the number of 3-subsets and 4-subsets of X having exactly one element in common with Y. - Milan Janjic, Dec 28 2007
a(n) is also the number of proper colorings of the cycle graph Csub3 (also the complete graph Ksub3) when n colors are available. - Gary E. Stevens, Dec 28 2008
a(n) is the reverse Wiener index of the path graph with n vertices. See the Balaban et al. reference, p. 927.
For n > 1: a(n) = sum of (n-1)-th row of A141418. - Reinhard Zumkeller, Nov 18 2012
This is the sequence for nuclear magic numbers in an idealized spherical nucleus under the harmonic oscillator model. - Jess Tauber, May 20 2013
Shifted non-vanishing diagonal of A132440^3/3. Second subdiagonal of A238363 (without zeros). For n>0, a(n+2)=n*(n+1)*(n+2)/3. Cf. A130534 for relations to colored forests and disposition of flags on flagpoles. - Tom Copeland, Apr 05 2014
a(n) is the number of ordered rooted trees with n non-root nodes that have 2 leaves; see A108838. - Joerg Arndt, Aug 18 2014
Number of floating point multiplications in the factorization of an (n-1)X(n-1) real matrix by Gaussian elimination as e.g. implemented in LINPACK subroutines sgefa.f or dgefa.f. The number of additions is given by A000330. - Hugo Pfoertner, Mar 28 2018
a(n+1) = Max_{s in S_n} Sum_{k=1..n} (k - s(k))^2 where S_n is the symmetric group of permutations of [1..n]; this maximum is obtained with the permutation s = (1, n) (2, n-1) (3, n-2) ... (k, n-k+1). (see Protat reference). - Bernard Schott, Dec 26 2022

References

  • Luigi Berzolari, Allgemeine Theorie der Höheren Ebenen Algebraischen Kurven, Encyclopädie der Mathematischen Wissenschaften mit Einschluss ihrer Anwendungen. Band III_2. Heft 3, Leipzig: B. G. Teubner, 1906, p. 352.
  • Louis Comtet, Advanced Combinatorics, Reidel, 1974, p. 259.
  • Maurice Protat, Des Olympiades à l'Agrégation, un problème de maximum, Problème 36, p. 83, Ellipses, Paris 1997.
  • N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).

Links

Crossrefs

A diagonal of A059419. Partial sums of A002378.
A diagonal of A008291. Row 3 of A074650.
Cf. A000292, A051925, A145066, A145067, A145068, A210569.

Programs

  • Haskell
    a007290 n = if n < 3 then 0 else 2 * a007318 n 3  -- Reinhard Zumkeller, Nov 18 2012
  • Magma
    I:=[0, 0, 0, 2]; [n le 4 select I[n] else 4*Self(n-1)-6*Self(n-2)+4*Self(n-3)-Self(n-4): n in [1..45]]; // Vincenzo Librandi, Jun 19 2012
  • Maple
    A007290 := proc(n) 2*binomial(n,3) end proc:
  • Mathematica
    Table[Integrate[ D[ChebyshevU[n, x], x] D[ChebyshevU[n, x], x] (1 - x^2)^(1/2), {x, -1, 1}]/Pi, {n, 1, 20}] (* Pacher *)
LinearRecurrence[{4,-6,4,-1},{0,0,0,2},50] (* Vincenzo Librandi, Jun 19 2012 *)
  • PARI
    my(x='x+O('x^100)); concat([0, 0, 0], Vec(2*x^3/(1-x)^4)) \\ Altug Alkan, Nov 01 2015
  • PARI
    apply( {A007290(n)=binomial(n,3)*2}, [0..55]) \\ M. F. Hasler, Jul 02 2021

Formula

G.f.: 2*x^3/(1-x)^4.
a(n) = a(n-1)*n/(n-3) = a(n-1) + A002378(n-2) = 2*A000292(n-2) = Sum_{i=0..n-2} i*(i+1) = n*(n-1)*(n-2)/3. - Henry Bottomley, Jun 02 2000 [Formula corrected by R. J. Mathar, Dec 13 2010]
a(n) = A000217(n-2) + A000330(n-2), n>1. - Reinhard Zumkeller, Mar 20 2008
a(n+1) = A000330(n) - A000217(n), n>=0. - Zak Seidov, Aug 07 2010
a(n) = A033487(n-2) - A052149(n-1) for n>1. - Bruno Berselli, Dec 10 2010
a(n) = 4*a(n-1) - 6*a(n-2) + 4*a(n-3) - a(n-4). - Vincenzo Librandi, Jun 19 2012
a(n) = (2*n - 3*n^2 + n^3)/3. - T. D. Noe, May 20 2013
a(n+1) = A002412(n) - A000330(n) or "Hex Pyramidal" - "Square Pyramidal" (as can also be seen via above formula). - Richard R. Forberg, Aug 07 2013
Sum_{n>=3} 1/a(n) = 3/4. - Enrique Pérez Herrero, Nov 10 2013
E.g.f.: exp(x)*x^3/3. - Geoffrey Critzer, Nov 22 2015
a(n+2) = delta(-n) = -delta(n) for n >= 0, where delta is the p-derivation over the integers with respect to prime p = 3. - Danny Rorabaugh, Nov 10 2017
(a(n) + a(n+1))/2 = A000330(n-1). - Ezhilarasu Velayutham, Apr 05 2019
Sum_{n>=3} (-1)^(n+1)/a(n) = 6*log(2) - 15/4. - Amiram Eldar, Jan 09 2022
a(n) = Sum_{m=0..n-2} Sum_{k=0..n-2} abs(m-k). - Nicolas Bělohoubek, Nov 06 2022
From Bernard Schott, Jan 04 2023: (Start)
a(n) = 2 * A000292(n-2), for n >= 2.
a(n+1) = 2 *Sum_{k=1..floor(n/2)} (n-(2k-1))^2, for n >= 2. (End)

A130534 Triangle T(n,k), 0 <= k <= n, read by rows, giving coefficients of the polynomial (x+1)(x+2)...(x+n), expanded in increasing powers of x. T(n,k) is also the unsigned Stirling number |s(n+1, k+1)|, denoting the number of permutations on n+1 elements that contain exactly k+1 cycles.

Original entry on oeis.org

1, 1, 1, 2, 3, 1, 6, 11, 6, 1, 24, 50, 35, 10, 1, 120, 274, 225, 85, 15, 1, 720, 1764, 1624, 735, 175, 21, 1, 5040, 13068, 13132, 6769, 1960, 322, 28, 1, 40320, 109584, 118124, 67284, 22449, 4536, 546, 36, 1, 362880, 1026576, 1172700, 723680, 269325, 63273, 9450, 870, 45, 1
Offset: 0

Views

Author

Philippe Deléham, Aug 09 2007

Keywords

Comments

This triangle is an unsigned version of the triangle of Stirling numbers of the first kind, A008275, which is the main entry for these numbers. - N. J. A. Sloane, Jan 25 2011
Or, triangle T(n,k), 0 <= k <= n, read by rows given by [1,1,2,2,3,3,4,4,5,5,6,6,...] DELTA [1,0,1,0,1,0,1,0,1,0,1,0,...] where DELTA is the operator defined in A084938.
Reversal of A094638.
Equals A132393*A007318, as infinite lower triangular matrices. - Philippe Deléham, Nov 13 2007
From Johannes W. Meijer, Oct 07 2009: (Start)
The higher order exponential integrals E(x,m,n) are defined in A163931. The asymptotic expansion of the exponential integrals E(x,m=1,n) ~ (exp(-x)/x)*(1 - n/x + n*(n+1)/x^2 - n*(n+1)*(n+2)/x^3 + ...), see Abramowitz and Stegun. This formula follows from the general formula for the asymptotic expansion, see A163932. We rewrite E(x,m=1,n) ~ (exp(-x)/x)*(1 - n/x + (n^2+n)/x^2 - (2*n+3*n^2+n^3)/x^3 + (6*n+11*n^2+6*n^3+n^4)/x^3 - ...) and observe that the T(n,m) are the polynomials coefficients in the denominators. Looking at the a(n,m) formula of A028421, A163932 and A163934, and shifting the offset given above to 1, we can write T(n-1,m-1) = a(n,m) = (-1)^(n+m)*Stirling1(n,m), see the Maple program.
The asymptotic expansion leads for values of n from one to eleven to known sequences, see the cross-references. With these sequences one can form the triangles A008279 (right-hand columns) and A094587 (left-hand columns).
See A163936 for information about the o.g.f.s. of the right-hand columns of this triangle.
(End)
The number of elements greater than i to the left of i in a permutation gives the i-th element of the inversion vector. (Skiena-Pemmaraju 2003, p. 69.) T(n,k) is the number of n-permutations that have exactly k 0's in their inversion vector. See evidence in Mathematica code below. - Geoffrey Critzer, May 07 2010
T(n,k) counts the rooted trees with k+1 trunks in forests of "naturally grown" rooted trees with n+2 nodes. This corresponds to sums of coefficients of iterated derivatives representing vectors, Lie derivatives, or infinitesimal generators for flow fields and formal group laws. Cf. links in A139605. - Tom Copeland, Mar 23 2014
A refinement is A036039. - Tom Copeland, Mar 30 2014
From Tom Copeland, Apr 05 2014: (Start)
With initial n=1 and row polynomials of T as p(n,x)=x(x+1)...(x+n-1), the powers of x correspond to the number of trunks of the rooted trees of the "naturally-grown" forest referred to above. With each trunk allowed m colors, p(n,m) gives the number of such non-plane colored trees for the forest with each tree having n+1 vertices.
p(2,m) = m + m^2 = A002378(m) = 2*A000217(m) = 2*(first subdiag of |A238363|).
p(3,m) = 2m + 3m^2 + m^3 = A007531(m+2) = 3*A007290(m+2) = 3*(second subdiag A238363).
p(4,m) = 6m + 11m^2 + 6m^3 + m^4 = A052762(m+3) = 4*A033487(m) = 4*(third subdiag).
From the Joni et al. link, p(n,m) also represents the disposition of n distinguishable flags on m distinguishable flagpoles.
The chromatic polynomial for the complete graph K_n is the falling factorial, which encodes the colorings of the n vertices of K_n and gives a shifted version of p(n,m).
E.g.f. for the row polynomials: (1-y)^(-x).
(End)
A relation to derivatives of the determinant |V(n)| of the n X n Vandermonde matrix V(n) in the indeterminates c(1) thru c(n):
|V(n)| = Product_{1<=jTom Copeland, Apr 10 2014
From Peter Bala, Jul 21 2014: (Start)
Let M denote the lower unit triangular array A094587 and for k = 0,1,2,... define M(k) to be the lower unit triangular block array
/I_k 0\
\ 0 M/
having the k X k identity matrix I_k as the upper left block; in particular, M(0) = M. Then the present triangle equals the infinite matrix product M(0)*M(1)*M(2)*... (which is clearly well defined). See the Example section. (End)
For the relation of this rising factorial to the moments of Viennot's Laguerre stories, see the Hetyei link, p. 4. - Tom Copeland, Oct 01 2015
Can also be seen as the Bell transform of n! without column 0 (and shifted enumeration). For the definition of the Bell transform see A264428. - Peter Luschny, Jan 27 2016

Examples

			Triangle  T(n,k) begins:
n\k         0        1        2       3       4      5      6     7    8  9 10
n=0:        1
n=1:        1        1
n=2:        2        3        1
n=3:        6       11        6       1
n=4:       24       50       35      10       1
n=5:      120      274      225      85      15      1
n=6:      720     1764     1624     735     175     21      1
n=7:     5040    13068    13132    6769    1960    322     28     1
n=8:    40320   109584   118124   67284   22449   4536    546    36    1
n=9:   362880  1026576  1172700  723680  269325  63273   9450   870   45  1
n=10: 3628800 10628640 12753576 8409500 3416930 902055 157773 18150 1320 55  1
[Reformatted and extended by _Wolfdieter Lang_, Feb 05 2013]
T(3,2) = 6 because there are 6 permutations of {1,2,3,4} that have exactly 2 0's in their inversion vector: {1, 2, 4, 3}, {1, 3, 2, 4}, {1, 3, 4, 2}, {2, 1, 3, 4},{2, 3, 1, 4}, {2, 3, 4, 1}. The respective inversion vectors are {0, 0, 1}, {0, 1, 0}, {0, 2, 0}, {1, 0, 0}, {2, 0, 0}, {3, 0, 0}. - _Geoffrey Critzer_, May 07 2010
T(3,1)=11 since there are exactly 11 permutations of {1,2,3,4} with exactly 2 cycles, namely, (1)(234), (1)(243), (2)(134), (2)(143), (3)(124), (3)(142), (4)(123), (4)(143), (12)(34), (13)(24), and (14)(23). - _Dennis P. Walsh_, Jan 25 2011
From _Peter Bala_, Jul 21 2014: (Start)
With the arrays M(k) as defined in the Comments section, the infinite product M(0*)M(1)*M(2)*... begins
  / 1          \/1        \/1        \      / 1           \
  | 1  1       ||0 1      ||0 1      |      | 1  1        |
  | 2  2  1    ||0 1 1    ||0 0 1    |... = | 2  3  1     |
  | 6  6  3 1  ||0 2 2 1  ||0 0 1 1  |      | 6 11  6  1  |
  |24 24 12 4 1||0 6 6 3 1||0 0 2 2 1|      |24 50 35 10 1|
  |...         ||...      ||...      |      |...          |
(End)

References

  • John H. Conway and Richard K. Guy, The Book of Numbers, New York: Springer-Verlag, 1996. See pp. 93-94.
  • Sriram Pemmaraju and Steven Skiena, Computational Discrete Mathematics, Cambridge University Press, 2003, pp. 69-71. [Geoffrey Critzer, May 07 2010]

Links

Crossrefs

See A008275, which is the main entry for these numbers; A094638 (reversed rows).
Diagonals: A000012 A000217 A000914 A001303 A000915 A053567 A112002 A191685. Columns A000142 A000254 A000399 A000454 A000482 A001233 A001234.
From Johannes W. Meijer, Oct 07 2009: (Start)
Row sums equal A000142.
The asymptotic expansions lead to A000142 (n=1), A000142(n=2; minus a(0)), A001710 (n=3), A001715 (n=4), A001720 (n=5), A001725 (n=6), A001730 (n=7), A049388 (n=8), A049389 (n=9), A049398 (n=10), A051431 (n=11), A008279 and A094587.
Cf. A163931 (E(x,m,n)), A028421 (m=2), A163932 (m=3), A163934 (m=4), A163936.
(End)
Cf. A136662.

Programs

  • Haskell
    a130534 n k = a130534_tabl !! n !! k
a130534_row n = a130534_tabl !! n
a130534_tabl = map (map abs) a008275_tabl
-- Reinhard Zumkeller, Mar 18 2013
  • Maple
    with(combinat): A130534 := proc(n,m): (-1)^(n+m)*stirling1(n+1,m+1) end proc: seq(seq(A130534(n,m), m=0..n), n=0..10); # Johannes W. Meijer, Oct 07 2009, revised Sep 11 2012
# The function BellMatrix is defined in A264428.
# Adds (1,0,0,0, ..) as column 0 (and shifts the enumeration).
BellMatrix(n -> n!, 9); # Peter Luschny, Jan 27 2016
  • Mathematica
    Table[Table[ Length[Select[Map[ToInversionVector, Permutations[m]], Count[ #, 0] == n &]], {n, 0, m - 1}], {m, 0, 8}] // Grid (* Geoffrey Critzer, May 07 2010 *)
rows = 10;
t = Range[0, rows]!;
T[n_, k_] := BellY[n, k, t];
Table[T[n, k], {n, 1, rows}, {k, 1, n}] // Flatten (* Jean-François Alcover, Jun 22 2018, after Peter Luschny *)

Formula

T(0,0) = 1, T(n,k) = 0 if k > n or if n < 0, T(n,k) = T(n-1,k-1) + n*T(n-1,k). T(n,0) = n! = A000142(n). T(2*n,n) = A129505(n+1). Sum_{k=0..n} T(n,k) = (n+1)! = A000142(n+1). Sum_{k=0..n} T(n,k)^2 = A047796(n+1). T(n,k) = |Stirling1(n+1,k+1)|, see A008275. (x+1)(x+2)...(x+n) = Sum_{k=0..n} T(n,k)*x^k. [Corrected by Arie Bos, Jul 11 2008]
Sum_{k=0..n} T(n,k)*x^k = A000007(n), A000142(n), A000142(n+1), A001710(n+2), A001715(n+3), A001720(n+4), A001725(n+5), A001730(n+6), A049388(n), A049389(n), A049398(n), A051431(n) for x = -1, 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, respectively. - Philippe Deléham, Nov 13 2007
For k=1..n, let A={a_1,a_2,...,a_k} denote a size-k subset of {1,2,...,n}. Then T(n,n-k) = Sum(Product_{i=1..k} a_i) where the sum is over all subsets A. For example, T(4,1)=50 since 1*2*3 + 1*2*4 + 1*3*4 + 2*3*4 = 50. - Dennis P. Walsh, Jan 25 2011
The preceding formula means T(n,k) = sigma_{n-k}(1,2,3,..,n) with the (n-k)-th elementary symmetric function sigma with the indeterminates chosen as 1,2,...,n. See the Oct 24 2011 comment in A094638 with sigma called there a. - Wolfdieter Lang, Feb 06 2013
From Gary W. Adamson, Jul 08 2011: (Start)
n-th row of the triangle = top row of M^n, where M is the production matrix:
1, 1;
1, 2, 1;
1, 3, 3, 1;
1, 4, 6, 4, 1;
... (End)
Exponential Riordan array [1/(1 - x), log(1/(1 - x))]. Recurrence: T(n+1,k+1) = Sum_{i=0..n-k} (n + 1)!/(n + 1 - i)!*T(n-i,k). - Peter Bala, Jul 21 2014

A074909 Running sum of Pascal's triangle (A007318), or beheaded Pascal's triangle read by beheaded rows.

Original entry on oeis.org

1, 1, 2, 1, 3, 3, 1, 4, 6, 4, 1, 5, 10, 10, 5, 1, 6, 15, 20, 15, 6, 1, 7, 21, 35, 35, 21, 7, 1, 8, 28, 56, 70, 56, 28, 8, 1, 9, 36, 84, 126, 126, 84, 36, 9, 1, 10, 45, 120, 210, 252, 210, 120, 45, 10, 1, 11, 55, 165, 330, 462, 462, 330, 165, 55, 11
Offset: 0

Views

Author

Wouter Meeussen, Oct 01 2002

Keywords

Comments

This sequence counts the "almost triangular" partitions of n. A partition is triangular if it is of the form 0+1+2+...+k. Examples: 3=0+1+2, 6=0+1+2+3. An "almost triangular" partition is a triangular partition with at most 1 added to each of the parts. Examples: 7 = 1+1+2+3 = 0+2+2+3 = 0+1+3+3 = 0+1+2+4. Thus a(7)=4. 8 = 1+2+2+3 = 1+1+3+3 = 1+1+2+4 = 0+2+3+3 = 0+2+2+4 = 0+1+3+4 so a(8)=6. - Moshe Shmuel Newman, Dec 19 2002
The "almost triangular" partitions are the ones cycled by the operation of "Bulgarian solitaire", as defined by Martin Gardner.
Start with A007318 - I (I = Identity matrix), then delete right border of zeros. - Gary W. Adamson, Jun 15 2007
Also the number of increasing acyclic functions from {1..n-k+1} to {1..n+2}. A function f is acyclic if for every subset B of the domain the image of B under f does not equal B. For example, T(3,1)=4 since there are exactly 4 increasing acyclic functions from {1,2,3} to {1,2,3,4,5}: f1={(1,2),(2,3),(3,4)}, f2={(1,2),(2,3),(3,5)}, f3={(1,2),(2,4),(3,5)} and f4={(1,3),(2,4),(4,5)}. - Dennis P. Walsh, Mar 14 2008
Second Bernoulli polynomials are (from A164555 instead of A027641) B2(n,x) = 1; 1/2, 1; 1/6, 1, 1; 0, 1/2, 3/2, 1; -1/30, 0, 1, 2, 1; 0, -1/6, 0, 5/3, 5/2, 1; ... . Then (B2(n,x)/A002260) = 1; 1/2, 1/2; 1/6, 1/2, 1/3; 0, 1/4, 1/2, 1/4; -1/30, 0, 1/3, 1/2, 1/5; 0, -1/12, 0, 5/12, 1/2, 1/6; ... . See (from Faulhaber 1631) Jacob Bernoulli Summae Potestatum (sum of powers) in A159688. Inverse polynomials are 1; -1, 2; 1, -3, 3; -1, 4, -6, 4; ... = A074909 with negative even diagonals. Reflected A053382/A053383 = reflected B(n,x) = RB(n,x) = 1; -1/2, 1; 1/6, -1, 1; 0, 1/2, -3/2, 1; ... . A074909 is inverse of RB(n,x)/A002260 = 1; -1/2, 1/2; 1/6, -1/2, 1/3; 0, 1/4, -1/2, 1/4; ... . - Paul Curtz, Jun 21 2010
A054143 is the fission of the polynomial sequence (p(n,x)) given by p(n,x) = x^n + x^(n-1) + ... + x + 1 by the polynomial sequence ((x+1)^n). See A193842 for the definition of fission. - Clark Kimberling, Aug 07 2011
Reversal of A135278. - Philippe Deléham, Feb 11 2012
For a closed-form formula for arbitrary left and right borders of Pascal-like triangles see A228196. - Boris Putievskiy, Aug 19 2013
For a closed-form formula for generalized Pascal's triangle see A228576. - Boris Putievskiy, Sep 09 2013
From A238363, the operator equation d/d(:xD:)f(xD)={exp[d/d(xD)]-1}f(xD) = f(xD+1)-f(xD) follows. Choosing f(x) = x^n and using :xD:^n/n! = binomial(xD,n) and (xD)^n = Bell(n,:xD:), the Bell polynomials of A008277, it follows that the lower triangular matrix [padded A074909]
A) = [St2]*[dP]*[St1] = A048993*A132440*[padded A008275]
B) = [St2]*[dP]*[St2]^(-1)
C) = [St1]^(-1)*[dP]*[St1],
where [St1]=padded A008275 just as [St2]=A048993=padded A008277 whereas [padded A074909]=A007318-I with I=identity matrix. - Tom Copeland, Apr 25 2014
T(n,k) generated by m-gon expansions in the case of odd m with "vertex to side" version or even m with "vertex to vertes" version. Refer to triangle expansions in A061777 and A101946 (and their companions for m-gons) which are "vertex to vertex" and "vertex to side" versions respectively. The label values at each iteration can be arranged as a triangle. Any m-gon can also be arranged as the same triangle with conditions: (i) m is odd and expansion is "vertex to side" version or (ii) m is even and expansion is "vertex to vertex" version. m*Sum_{i=1..k} T(n,k) gives the total label value at the n-th iteration. See also A247976. Vertex to vertex: A061777, A247618, A247619, A247620. Vertex to side: A101946, A247903, A247904, A247905. - Kival Ngaokrajang Sep 28 2014
From Tom Copeland, Nov 12 2014: (Start)
With P(n,x) = [(x+1)^(n+1)-x^(n+1)], the row polynomials of this entry, Up(n,x) = P(n,x)/(n+1) form an Appell sequence of polynomials that are the umbral compositional inverses of the Bernoulli polynomials B(n,x), i.e., B[n,Up(.,x)] = x^n = Up[n,B(.,x)] under umbral substitution, e.g., B(.,x)^n = B(n,x).
The e.g.f. for the Bernoulli polynomials is [t/(e^t - 1)] e^(x*t), and for Up(n,x) it's exp[Up(.,x)t] = [(e^t - 1)/t] e^(x*t).
Another g.f. is G(t,x) = log[(1-x*t)/(1-(1+x)*t)] = log[1 + t /(1 + -(1+x)t)] = t/(1-t*Up(.,x)) = Up(0,x)*t + Up(1,x)*t^2 + Up(2,x)*t^3 + ... = t + (1+2x)/2 t^2 + (1+3x+3x^2)/3 t^3 + (1+4x+6x^2+4x^3)/4 t^4 + ... = -log(1-t*P(.,x)), expressed umbrally.
The inverse, Ginv(t,x), in t of the g.f. may be found in A008292 from Copeland's list of formulas (Sep 2014) with a=(1+x) and b=x. This relates these two sets of polynomials to algebraic geometry, e.g., elliptic curves, trigonometric expansions, Chebyshev polynomials, and the combinatorics of permutahedra and their duals.
Ginv(t,x) = [e^((1+x)t) - e^(xt)] / [(1+x) * e^((1+x)t) - x * e^(xt)] = [e^(t/2) - e^(-t/2)] / [(1+x)e^(t/2) - x*e^(-t/2)] = (e^t - 1) / [1 + (1+x) (e^t - 1)] = t - (1 + 2 x) t^2/2! + (1 + 6 x + 6 x^2) t^3/3! - (1 + 14 x + 36 x^2 + 24 x^3) t^4/4! + ... = -exp[-Perm(.,x)t], where Perm(n,x) are the reverse face polynomials, or reverse f-vectors, for the permutahedra, i.e., the face polynomials for the duals of the permutahedra. Cf. A090582, A019538, A049019, A133314, A135278.
With L(t,x) = t/(1+t*x) with inverse L(t,-x) in t, and Cinv(t) = e^t - 1 with inverse C(t) = log(1 + t). Then Ginv(t,x) = L[Cinv(t),(1+x)] and G(t,x) = C[L[t,-(1+x)]]. Note L is the special linear fractional (Mobius) transformation.
Connections among the combinatorics of the permutahedra, simplices (cf. A135278), and the associahedra can be made through the Lagrange inversion formula (LIF) of A133437 applied to G(t,x) (cf. A111785 and the Schroeder paths A126216 also), and similarly for the LIF A134685 applied to Ginv(t,x) involving the simplicial Whitehouse complex, phylogenetic trees, and other structures. (See also the LIFs A145271 and A133932). (End)
R = x - exp[-[B(n+1)/(n+1)]D] = x - exp[zeta(-n)D] is the raising operator for this normalized sequence UP(n,x) = P(n,x) / (n+1), that is, R UP(n,x) = UP(n+1,x), where D = d/dx, zeta(-n) is the value of the Riemann zeta function evaluated at -n, and B(n) is the n-th Bernoulli number, or constant B(n,0) of the Bernoulli polynomials. The raising operator for the Bernoulli polynomials is then x + exp[-[B(n+1)/(n+1)]D]. [Note added Nov 25 2014: exp[zeta(-n)D] is abbreviation of exp(a.D) with (a.)^n = a_n = zeta(-n)]. - Tom Copeland, Nov 17 2014
The diagonals T(n, n-m), for n >= m, give the m-th iterated partial sum of the positive integers; that is A000027(n+1), A000217(n), A000292(n-1), A000332(n+1), A000389(n+1), A000579(n+1), A000580(n+1), A000581(n+1), A000582(n+1), ... . - Wolfdieter Lang, May 21 2015
The transpose gives the numerical coefficients of the Maurer-Cartan form matrix for the general linear group GL(n,1) (cf. Olver, but note that the formula at the bottom of p. 6 has an error--the 12 should be a 15). - Tom Copeland, Nov 05 2015
The left invariant Maurer-Cartan form polynomial on p. 7 of the Olver paper for the group GL^n(1) is essentially a binomial convolution of the row polynomials of this entry with those of A133314, or equivalently the row polynomials generated by the product of the e.g.f. of this entry with that of A133314, with some reindexing. - Tom Copeland, Jul 03 2018
From Tom Copeland, Jul 10 2018: (Start)
The first column of the inverse matrix is the sequence of Bernoulli numbers, which follows from the umbral definition of the Bernoulli polynomials (B.(0) + x)^n = B_n(x) evaluated at x = 1 and the relation B_n(0) = B_n(1) for n > 1 and -B_1(0) = 1/2 = B_1(1), so the Bernoulli numbers can be calculated using Cramer's rule acting on this entry's matrix and, therefore, from the ratios of volumes of parallelepipeds determined by the columns of this entry's square submatrices. - Tom Copeland, Jul 10 2018
Umbrally composing the row polynomials with B_n(x), the Bernoulli polynomials, gives (B.(x)+1)^(n+1) - (B.(x))^(n+1) = d[x^(n+1)]/dx = (n+1)*x^n, so multiplying this entry as a lower triangular matrix (LTM) by the LTM of the coefficients of the Bernoulli polynomials gives the diagonal matrix of the natural numbers. Then the inverse matrix of this entry has the elements B_(n,k)/(k+1), where B_(n,k) is the coefficient of x^k for B_n(x), and the e.g.f. (1/x) (e^(xt)-1)/(e^t-1). (End)

Examples

			T(4,2) = 0+0+1+3+6 = 10 = binomial(5, 2).
Triangle T(n,k) begins:
n\k 0  1  2   3   4   5   6   7   8   9 10 11
0:  1
1:  1  2
2:  1  3  3
3:  1  4  6   4
4:  1  5 10  10   5
5:  1  6 15  20  15   6
6:  1  7 21  35  35  21   7
7:  1  8 28  56  70  56  28   8
8:  1  9 36  84 126 126  84  36  9
9:  1 10 45 120 210 252 210 120 45   10
10: 1 11 55 165 330 462 462 330 165  55 11
11: 1 12 66 220 495 792 924 792 495 220 66 12
... Reformatted. - _Wolfdieter Lang_, Nov 04 2014
.
Can be seen as the square array A(n, k) = binomial(n + k + 1, n) read by descending antidiagonals. A(n, k) is the number of monotone nondecreasing functions f: {1,2,..,k} -> {1,2,..,n}. - _Peter Luschny_, Aug 25 2019
[0]  1,  1,   1,   1,    1,    1,     1,     1,     1, ... A000012
[1]  2,  3,   4,   5,    6,    7,     8,     9,    10, ... A000027
[2]  3,  6,  10,  15,   21,   28,    36,    45,    55, ... A000217
[3]  4, 10,  20,  35,   56,   84,   120,   165,   220, ... A000292
[4]  5, 15,  35,  70,  126,  210,   330,   495,   715, ... A000332
[5]  6, 21,  56, 126,  252,  462,   792,  1287,  2002, ... A000389
[6]  7, 28,  84, 210,  462,  924,  1716,  3003,  5005, ... A000579
[7]  8, 36, 120, 330,  792, 1716,  3432,  6435, 11440, ... A000580
[8]  9, 45, 165, 495, 1287, 3003,  6435, 12870, 24310, ... A000581
[9] 10, 55, 220, 715, 2002, 5005, 11440, 24310, 48620, ... A000582

Links

Crossrefs

Cf. A007318, A181971, A228196, A228576.
Row sums are A000225, diagonal sums are A052952.
The number of acyclic functions is A058127.
Cf. A008292, A090582, A019538, A049019, A133314, A135278, A133437, A111785, A126216, A134685, A133932, A248727, A033282, A134264.
Cf. A000027, A000217, A000292, A000332, A000389, A000579, A000580, A000581, A000582.
Cf. A325191.

Programs

  • GAP
    Flat(List([0..10],n->List([0..n],k->Binomial(n+1,k)))); # Muniru A Asiru, Jul 10 2018
  • Haskell
    a074909 n k = a074909_tabl !! n !! k
a074909_row n = a074909_tabl !! n
a074909_tabl = iterate
   (\row -> zipWith (+) ([0] ++ row) (row ++ [1])) [1]
-- Reinhard Zumkeller, Feb 25 2012
  • Magma
    /* As triangle */ [[Binomial(n+1,k): k in [0..n]]: n in [0.. 15]]; // Vincenzo Librandi, Jul 22 2018
  • Maple
    A074909 := proc(n,k)
    if k > n or k < 0 then
        0;
    else
        binomial(n+1,k) ;
    end if;
end proc: # Zerinvary Lajos, Nov 09 2006
  • Mathematica
    Flatten[Join[{1}, Table[Sum[Binomial[k, m], {k, 0, n}], {n, 0, 12}, {m, 0, n}] ]] (* or *) Flatten[Join[{1}, Table[Binomial[n, m], {n, 12}, {m, n}]]]
  • PARI
    print1(1);for(n=1,10,for(k=1,n,print1(", "binomial(n,k)))) \\ Charles R Greathouse IV, Mar 26 2013
  • Python
    from math import comb, isqrt
def A074909(n): return comb(r:=(m:=isqrt(k:=n+1<<1))+(k>m*(m+1)),n-comb(r,2)) # Chai Wah Wu, Nov 12 2024

Formula

T(n, k) = Sum_{i=0..n} C(i, n-k) = C(n+1, k).
Row n has g.f. (1+x)^(n+1)-x^(n+1).
E.g.f.: ((1+x)*e^t - x) e^(x*t). The row polynomials p_n(x) satisfy dp_n(x)/dx = (n+1)*p_(n-1)(x). - Tom Copeland, Jul 10 2018
T(n, k) = T(n-1, k-1) + T(n-1, k) for k: 0Reinhard Zumkeller, Apr 18 2005
T(n,k) = T(n-1,k) + 2*T(n-1,k-1) - T(n-2,k-1) - T(n-2,k-2), T(0,0)=1, T(1,0)=1, T(1,1)=2, T(n,k)=0 if k<0 or if k>n. - Philippe Deléham, Dec 27 2013
G.f. for column k (with leading zeros): x^(k-1)*(1/(1-x)^(k+1)-1), k >= 0. - Wolfdieter Lang, Nov 04 2014
Up(n, x+y) = (Up(.,x)+ y)^n = Sum_{k=0..n} binomial(n,k) Up(k,x)*y^(n-k), where Up(n,x) = ((x+1)^(n+1)-x^(n+1)) / (n+1) = P(n,x)/(n+1) with P(n,x) the n-th row polynomial of this entry. dUp(n,x)/dx = n * Up(n-1,x) and dP(n,x)/dx = (n+1)*P(n-1,x). - Tom Copeland, Nov 14 2014
The o.g.f. GF(x,t) = x / ((1-t*x)*(1-(1+t)x)) = x + (1+2t)*x^2 + (1+3t+3t^2)*x^3 + ... has the inverse GFinv(x,t) = (1+(1+2t)x-sqrt(1+(1+2t)*2x+x^2))/(2t(1+t)x) in x about 0, which generates the row polynomials (mod row signs) of A033282. The reciprocal of the o.g.f., i.e., x/GF(x,t), gives the free cumulants (1, -(1+2t) , t(1+t) , 0, 0, ...) associated with the moments defined by GFinv, and, in fact, these free cumulants generate these moments through the noncrossing partitions of A134264. The associated e.g.f. and relations to Grassmannians are described in A248727, whose polynomials are the basis for an Appell sequence of polynomials that are umbral compositional inverses of the Appell sequence formed from this entry's polynomials (distinct from the one described in the comments above, without the normalizing reciprocal). - Tom Copeland, Jan 07 2015
T(n, k) = (1/k!) * Sum_{i=0..k} Stirling1(k,i)*(n+1)^i, for 0<=k<=n. - Ridouane Oudra, Oct 23 2022

Extensions

I added an initial 1 at the suggestion of Paul Barry, which makes the triangle a little nicer but may mean that some of the formulas will now need adjusting. - N. J. A. Sloane, Feb 11 2003
Formula section edited, checked and corrected by Wolfdieter Lang, Nov 04 2014

A094587 Triangle of permutation coefficients arranged with 1's on the diagonal. Also, triangle of permutations on n letters with exactly k+1 cycles and with the first k+1 letters in separate cycles.

Original entry on oeis.org

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

Views

Author

Paul Barry, May 13 2004

Keywords

Comments

Also, table of Pochhammer sequences read by antidiagonals (see Rudolph-Lilith, 2015). - N. J. A. Sloane, Mar 31 2016
Reverse of A008279. Row sums are A000522. Diagonal sums are A003470. Rows of inverse matrix begin {1}, {-1,1}, {0,-2,1}, {0,0,-3,1}, {0,0,0,-4,1} ... The signed lower triangular matrix (-1)^(n+k)n!/k! has as row sums the signed rencontres numbers Sum_{k=0..n} (-1)^(n+k)n!/k!. (See A000166). It has matrix inverse 1 1,1 0,2,1 0,0,3,1 0,0,0,4,1,...
Exponential Riordan array [1/(1-x),x]; column k has e.g.f. x^k/(1-x). - Paul Barry, Mar 27 2007
From Tom Copeland, Nov 01 2007: (Start)
T is the umbral extension of n!*Lag[n,(.)!*Lag[.,x,-1],0] = (1-D)^(-1) x^n = (-1)^n * n! * Lag(n,x,-1-n) = Sum_{j=0..n} binomial(n,j) * j! * x^(n-j) = Sum_{j=0..n} (n!/j!) x^j. The inverse operator is A132013 with generalizations discussed in A132014.
b = T*a can be characterized several ways in terms of a(n) and b(n) or their o.g.f.'s A(x) and B(x).
1) b(n) = n! Lag[n,(.)!*Lag[.,a(.),-1],0], umbrally,
2) b(n) = (-1)^n n! Lag(n,a(.),-1-n)
3) b(n) = Sum_{j=0..n} (n!/j!) a(j)
4) B(x) = (1-xDx)^(-1) A(x), formally
5) B(x) = Sum_{j=0,1,...} (xDx)^j A(x)
6) B(x) = Sum_{j=0,1,...} x^j * D^j * x^j A(x)
7) B(x) = Sum_{j=0,1,...} j! * x^j * L(j,-:xD:,0) A(x) where Lag(n,x,m) are the Laguerre polynomials of order m, D the derivative w.r.t. x and (:xD:)^j = x^j * D^j. Truncating the operator series at the j = n term gives an o.g.f. for b(0) through b(n).
c = (0!,1!,2!,3!,4!,...) is the sequence associated to T under the list partition transform and the associated operations described in A133314 so T(n,k) = binomial(n,k)*c(n-k). The reciprocal sequence is d = (1,-1,0,0,0,...). (End)
From Peter Bala, Jul 10 2008: (Start)
This array is the particular case P(1,1) of the generalized Pascal triangle P(a,b), a lower unit triangular matrix, shown below:
n\k|0.....................1...............2.......3......4
----------------------------------------------------------
0..|1.....................................................
1..|a....................1................................
2..|a(a+b)...............2a..............1................
3..|a(a+b)(a+2b).........3a(a+b).........3a........1......
4..|a(a+b)(a+2b)(a+3b)...4a(a+b)(a+2b)...6a(a+b)...4a....1
...
The entries A(n,k) of this array satisfy the recursion A(n,k) = (a+b*(n-k-1))*A(n-1,k) + A(n-1,k-1), which reduces to the Pascal formula when a = 1, b = 0.
Various cases are recorded in the database, including: P(1,0) = Pascal's triangle A007318, P(2,0) = A038207, P(3,0) = A027465, P(2,1) = A132159, P(1,3) = A136215 and P(2,3) = A136216.
When b <> 0 the array P(a,b) has e.g.f. exp(x*y)/(1-b*y)^(a/b) = 1 + (a+x)*y + (a*(a+b)+2a*x+x^2)*y^2/2! + (a*(a+b)*(a+2b) + 3a*(a+b)*x + 3a*x^2+x^3)*y^3/3! + ...; the array P(a,0) has e.g.f. exp((x+a)*y).
We have the matrix identities P(a,b)*P(a',b) = P(a+a',b); P(a,b)^-1 = P(-a,b).
An analog of the binomial expansion for the row entries of P(a,b) has been proved by [Echi]. Introduce a (generally noncommutative and nonassociative) product ** on the ring of polynomials in two variables by defining F(x,y)**G(x,y) = F(x,y)G(x,y) + by^2*d/dy(G(x,y)).
Define the iterated product F^(n)(x,y) of a polynomial F(x,y) by setting F^(1) = F(x,y) and F^(n)(x,y) = F(x,y)**F^(n-1)(x,y) for n >= 2. Then (x+a*y)^(n) = x^n + C(n,1)*a*x^(n-1)*y + C(n,2)*a*(a+b)*x^(n-2)*y^2 + ... + C(n,n)*a*(a+b)*(a+2b)*...*(a+(n-1)b)*y^n. (End)
(n+1) * n-th row = reversal of triangle A068424: (1; 2,2; 6,6,3; ...) - Gary W. Adamson, May 03 2009
Let G(m, k, p) = (-p)^k*Product_{j=0..k-1}(j - m - 1/p) and T(n,k,p) = G(n-1,n-k,p) then T(n, k, 1) is this sequence, T(n, k, 2) = A112292(n, k) and T(n, k, 3) = A136214. - Peter Luschny, Jun 01 2009, revised Jun 18 2019
The higher order exponential integrals E(x,m,n) are defined in A163931. For a discussion of the asymptotic expansions of the E(x,m=1,n) ~ (exp(-x)/x)*(1 - n/x + (n^2+n)/x^2 - (2*n+3*n^2+n^3)/x^3 + (6*n+11*n^2+6*n^3+n^4)/x^3 - ...) see A130534. The asymptotic expansion of E(x,m=1,n) leads for n >= 1 to the left hand columns of the triangle given above. Triangle A165674 is generated by the asymptotic expansions of E(x,m=2,n). - Johannes W. Meijer, Oct 07 2009
T(n,k) = n!/k! = number of permutations of [n+1] with exactly k+1 cycles and with elements 1,2,...,k+1 in separate cycles. See link and example below. - Dennis P. Walsh, Jan 24 2011
T(n,k) is the number of n permutations that leave some size k subset of {1,2,...,n} fixed. Sum_{k=0..n}(-1)^k*T(n,k) = A000166(n) (the derangements). - Geoffrey Critzer, Dec 11 2011
T(n,k) = A162995(n-1,k-1), 2 <= k <= n; T(n,k) = A173333(n,k), 1 <= k <= n. - Reinhard Zumkeller, Jul 05 2012
The row polynomials form an Appell sequence. The matrix is a special case of a group of general matrices sketched in A132382. - Tom Copeland, Dec 03 2013
For interpretations in terms of colored necklaces, see A213936 and A173333. - Tom Copeland, Aug 18 2016
See A008279 for a relation of this entry to the e.g.f.s enumerating the faces of permutahedra and stellahedra. - Tom Copeland, Nov 14 2016
Also, T(n,k) is the number of ways to arrange n-k nonattacking rooks on the n X (n-k) chessboard. - Andrey Zabolotskiy, Dec 16 2016
The infinitesimal generator of this triangle is the generalized exponential Riordan array [-log(1-x), x] and equals the unsigned version of A238363. - Peter Bala, Feb 13 2017
Formulas for exponential and power series infinitesimal generators for this triangle T are given in Copeland's 2012 and 2014 formulas as T = unsigned exp[(I-A238385)] = 1/(I - A132440), where I is the identity matrix. - Tom Copeland, Jul 03 2017
If A(0) = 1/(1-x), and A(n) = d/dx(A(n-1)), then A(n) = n!/(1-x)^(n+1) = Sum_{k>=0} (n+k)!/k!*x^k = Sum_{k>=0} T(n+k, k)*x^k. - Michael Somos, Sep 19 2021

Examples

			Rows begin {1}, {1,1}, {2,2,1}, {6,6,3,1}, ...
For n=3 and k=1, T(3,1)=6 since there are exactly 6 permutations of {1,2,3,4} with exactly 2 cycles and with 1 and 2 in separate cycles. The permutations are (1)(2 3 4), (1)(2 4 3), (1 3)(2 4), (1 4)(2 3), (1 3 4)(2), and (1 4 3)(2). - _Dennis P. Walsh_, Jan 24 2011
Triangle begins:
     1,
     1,    1,
     2,    2,    1,
     6,    6,    3,    1,
    24,   24,   12,    4,    1,
   120,  120,   60,   20,    5,    1,
   720,  720,  360,  120,   30,    6,    1,
  5040, 5040, 2520,  840,  210,   42,    7,    1
The production matrix is:
      1,     1,
      1,     1,     1,
      2,     2,     1,    1,
      6,     6,     3,    1,    1,
     24,    24,    12,    4,    1,   1,
    120,   120,    60,   20,    5,   1,   1,
    720,   720,   360,  120,   30,   6,   1,   1,
   5040,  5040,  2520,  840,  210,  42,   7,   1,   1,
  40320, 40320, 20160, 6720, 1680, 336,  56,   8,   1,   1
which is the exponential Riordan array A094587, or [1/(1-x),x], with an extra superdiagonal of 1's.
Inverse begins:
   1,
  -1,  1,
   0, -2,  1,
   0,  0, -3,  1,
   0,  0,  0, -4,  1,
   0,  0,  0,  0, -5,  1,
   0,  0,  0,  0,  0, -6,  1,
   0,  0,  0,  0,  0,  0, -7,  1

Links

Crossrefs

Cf. A000166 (alt. row sums), A000522 (row sums).
Cf. A068424, A036039, A173333, A213936, A263916.
Cf. A000670, A008279, A021009, A048994, A132013, A132014, A132159, A132440, A133314, A218234, A235706, A238385.

Programs

  • Haskell
    a094587 n k = a094587_tabl !! n !! k
a094587_row n = a094587_tabl !! n
a094587_tabl = map fst $ iterate f ([1], 1)
   where f (row, i) = (map (* i) row ++ [1], i + 1)
-- Reinhard Zumkeller, Jul 04 2012
  • Maple
    T := proc(n, m): n!/m! end: seq(seq(T(n, m), m=0..n), n=0..9);  # Johannes W. Meijer, Oct 07 2009, revised Nov 25 2012
# Alternative: Note that if you leave out 'abs' you get A021009.
T := proc(n, k) option remember; if n = 0 and k = 0 then 1 elif k < 0 or k > n then 0 else abs((n + k)*T(n-1, k) - T(n-1, k-1)) fi end: #  Peter Luschny, Dec 30 2021
  • Mathematica
    Flatten[Table[Table[n!/k!, {k,0,n}], {n,0,10}]] (* Geoffrey Critzer, Dec 11 2011 *)
  • Sage
    def A094587_row(n): return (factorial(n)*exp(x).taylor(x,0,n)).list()
for n in (0..7): print(A094587_row(n)) # Peter Luschny, Sep 28 2017

Formula

T(n, k) = n!/k! if n >= k >= 0, otherwise 0.
T(n, k) = Sum_{i=k..n} |S1(n+1, i+1)*S2(i, k)| * (-1)^i, with S1, S2 the Stirling numbers.
T(n,k) = (n-k)*T(n-1,k) + T(n-1,k-1). E.g.f.: exp(x*y)/(1-y) = 1 + (1+x)*y + (2+2*x+x^2)*y^2/2! + (6+6*x+3*x^2+x^3)*y^3/3!+ ... . - Peter Bala, Jul 10 2008
A094587 = 1 / ((-1)*A129184 * A127648 + I), I = Identity matrix. - Gary W. Adamson, May 03 2009
From Johannes W. Meijer, Oct 07 2009: (Start)
The o.g.f. of right hand column k is Gf(z;k) = (k-1)!/(1-z)^k, k => 1.
The recurrence relations of the right hand columns lead to Pascal's triangle A007318. (End)
Let f(x) = (1/x)*exp(-x). The n-th row polynomial is R(n,x) = (-x)^n/f(x)*(d/dx)^n(f(x)), and satisfies the recurrence equation R(n+1,x) = (x+n+1)*R(n,x)-x*R'(n,x). Cf. A132159. - Peter Bala, Oct 28 2011
A padded shifted version of this lower triangular matrix with zeros in the first column and row except for a one in the diagonal position is given by integral(t=0 to t=infinity) exp[-t(I-P)] = 1/(I-P) = I + P^2 + P^3 + ... where P is the infinitesimal generator matrix A218234 and I the identity matrix. The non-padded version is given by P replaced by A132440. - Tom Copeland, Oct 25 2012
From Peter Bala, Aug 28 2013: (Start)
The row polynomials R(n,x) form a Sheffer sequence of polynomials with associated delta operator equal to d/dx. Thus d/dx(R(n,x)) = n*R(n-1,x). The Sheffer identity is R(n,x + y) = Sum_{k=0..n} binomial(n,k)*y^(n-k)*R(k,x).
Let P(n,x) = Product_{k=0..n-1} (x + k) denote the rising factorial polynomial sequence with the convention that P(0,x) = 1. Then this is triangle of connection constants when expressing the basis polynomials P(n,x + 1) in terms of the basis P(n,x). For example, row 3 is (6, 6, 3, 1) so P(3,x + 1) = (x + 1)*(x + 2)*(x + 3) = 6 + 6*x + 3*x*(x + 1) + x*(x + 1)*(x + 2). (End)
From Tom Copeland, Apr 21 & 26, and Aug 13 2014: (Start)
T-I = M = -A021009*A132440*A021009 with e.g.f. y*exp(x*y)/(1-y). Cf. A132440. Dividing the n-th row of M by n generates the (n-1)th row of T.
T = 1/(I - A132440) = {2*I - exp[(A238385-I)]}^(-1) = unsigned exp[(I-A238385)] = exp[A000670(.)*(A238385-I)] = , umbrally, where I = identity matrix.
The e.g.f. is exp(x*y)/(1-y), so the row polynomials form an Appell sequence with lowering operator d/dx and raising operator x + 1/(1-D).
With L(n,m,x)= Laguerre polynomials of order m, the row polynomials are (-1)^n*n!*L(n,-1-n,x) = (-1)^n*(-1!/(-1-n)!)*K(-n,-1-n+1,x) = n!* K(-n,-n,x) where K is Kummer's confluent hypergeometric function (as a limit of n+s as s tends to zero).
Operationally, (-1)^n*n!*L(n,-1-n,-:xD:) = (-1)^n*x^(n+1)*:Dx:^n*x^(-1-n) = (-1)^n*x*:xD:^n*x^(-1) = (-1)^n*n!*binomial(xD-1,n) = n!*K(-n,-n,-:xD:) where :AB:^n = A^n*B^n for any two operators. Cf. A235706 and A132159.
The n-th row of signed M has the coefficients of d[(-:xD:)^n]/d(:Dx:)= f[d/d(-:xD:)](-:xD:)^n with f(y)=y/(y-1), :Dx:^n= n!L(n,0,-:xD:), and (-:xD:)^n = n!L(n,0,:Dx:). M has the coefficients of [D/(1-D)]x^n. (End)
From Tom Copeland, Nov 18 2015: (Start)
Coefficients of the row polynomials of the e.g.f. Sum_{n>=0} P_n(b1,b2,..,bn;t) x^n/n! = e^(P.(..;t) x) = e^(xt) / (1-b.x) = (1 + b1 x + b2 x^2 + b3 x^3 + ...) e^(xt) = 1 + (b1 + t) x + (2 b2 + 2 b1 t + t^2) x^2/2! + (6 b3 + 6 b2 t + 3 b1 t^2 + t^3) x^3/3! + ... , with lowering operator L = d/dt, i.e., L P_n(..;t) = n * P_(n-1)(..;t), and raising operator R = t + d[log(1 + b1 D + b2 D^2 + ...)]/dD = t - Sum_{n>=1} F(n,b1,..,bn) D^(n-1), i.e., R P_n(..,;t) = P_(n+1)(..;t), where D = d/dt and F(n,b1,..,bn) are the Faber polynomials of A263916.
Also P_n(b1,..,bn;t) = CIP_n(t-F(1,b1),-F(2,b1,b2),..,-F(n,b1,..,bn)), the cycle index polynomials A036039.
(End)
The raising operator R = x + 1/(1-D) = x + 1 + D + D^2 + ... in matrix form acting on an o.g.f. (formal power series) is the transpose of the production matrix M below. The linear term x is the diagonal of ones after transposition. The other transposed diagonals come from D^m x^n = n! / (n-m)! x^(n-m). Then P(n,x) = (1,x,x^2,..) M^n (1,0,0,..)^T is a matrix representation of R P(n-1,x) = P(n,x). - Tom Copeland, Aug 17 2016
The row polynomials have e.g.f. e^(xt)/(1-t) = exp(t*q.(x)), umbrally. With p_n(x) the row polynomials of A132013, q_n(x) = v_n(p.(u.(x))), umbrally, where u_n(x) = (-1)^n v_n(-x) = (-1)^n Lah_n(x), the Lah polynomials with e.g.f. exp[x*t/(t-1)]. This has the matrix form [T] = [q] = [v]*[p]*[u]. Conversely, p_n(x) = u_n (q.(v.(x))). - Tom Copeland, Nov 10 2016
From the Appell sequence formalism, 1/(1-b.D) t^n = P_n(b1,b2,..,bn;t), the generalized row polynomials noted in the Nov 18 2015 formulas, consistent with the 2007 comments. - Tom Copeland, Nov 22 2016
From Peter Bala, Feb 18 2017: (Start)
G.f.: Sum_{n >= 1} (n*x)^(n-1)/(1 + (n - t)*x)^n = 1 + (1 + t)*x + (2 + 2*t + t^2)*x^2 + ....
n-th row polynomial R(n,t) = Sum_{k = 0..n} (-1)^(n-k)*binomial(n,k)*(x + k)^k*(x + k - t)^(n-k) = Sum_{k = 0..n} (-1)^(n-k)*binomial(n,k)*(x + k)^(n-k)*(x + k + t)^k, for arbitrary x. The particular case of the latter sum when x = 0 and t = 1 is identity 10.35 in Gould, Vol.4. (End)
Rodrigues-type formula for the row polynomials: R(n, x) = -exp(x)*Int(exp(-x)* x^n, x), for n >= 0. Recurrence: R(n, x) = x^n + n*R(n-1, x), for n >= 1, and R(0, x) = 1. d/dx(R(n, x)) = R(n, x) - x^n, for n >= 0 (compare with the formula from Peter Bala, Aug 28 2013). - Wolfdieter Lang, Dec 23 2019
T(n, k) = Sum_{i=0..n-k} A048994(n-k, i) * n^i for 0 <= k <= n. - Werner Schulte, Jul 26 2022

Extensions

Edited by Johannes W. Meijer, Oct 07 2009
New description from Dennis P. Walsh, Jan 24 2011

A135278 Triangle read by rows, giving the numbers T(n,m) = binomial(n+1, m+1); or, Pascal's triangle A007318 with its left-hand edge removed.

Original entry on oeis.org

1, 2, 1, 3, 3, 1, 4, 6, 4, 1, 5, 10, 10, 5, 1, 6, 15, 20, 15, 6, 1, 7, 21, 35, 35, 21, 7, 1, 8, 28, 56, 70, 56, 28, 8, 1, 9, 36, 84, 126, 126, 84, 36, 9, 1, 10, 45, 120, 210, 252, 210, 120, 45, 10, 1, 11, 55, 165, 330, 462, 462, 330, 165, 55, 11, 1, 12, 66, 220, 495, 792, 924, 792
Offset: 0

Views

Author

Zerinvary Lajos, Dec 02 2007

Keywords

Comments

T(n,m) is the number of m-faces of a regular n-simplex.
An n-simplex is the n-dimensional analog of a triangle. Specifically, a simplex is the convex hull of a set of (n + 1) affinely independent points in some Euclidean space of dimension n or higher, i.e., a set of points such that no m-plane contains more than (m + 1) of them. Such points are said to be in general position.
Reversing the rows gives A074909, which as a linear sequence is essentially the same as this.
From Tom Copeland, Dec 07 2007: (Start)
T(n,k) * (k+1)! = A068424. The comment on permuted words in A068424 shows that T is related to combinations of letters defined by connectivity of regular polytope simplexes.
If T is the diagonally-shifted Pascal matrix, binomial(n+m, k+m), for m=1, then T is a fundamental type of matrix that is discussed in A133314 and the following hold.
The infinitesimal matrix generator is given by A132681, so T = LM(1) of A132681 with inverse LM(-1).
With a(k) = (-x)^k / k!, T * a = [ Laguerre(n,x,1) ], a vector array with index n for the Laguerre polynomials of order 1. Other formulas for the action of T are given in A132681.
T(n,k) = (1/n!) (D_x)^n (D_t)^k Gf(x,t) evaluated at x=t=0 with Gf(x,t) = exp[ t * x/(1-x) ] / (1-x)^2.
[O.g.f. for T ] = 1 / { [ 1 - t * x/(1-x) ] * (1-x)^2 }. [ O.g.f. for row sums ] = 1 / { (1-x) * (1-2x) }, giving A000225 (without a leading zero) for the row sums. Alternating sign row sums are all 1. [Sign correction noted by Vincent J. Matsko, Jul 19 2015]
O.g.f. for row polynomials = [ (1+q)**(n+1) - 1 ] / [ (1+q) -1 ] = A(1,n+1,q) on page 15 of reference on Grassmann cells in A008292. (End)
Given matrices A and B with A(n,k) = T(n,k)*a(n-k) and B(n,k) = T(n,k)*b(n-k), then A*B = C where C(n,k) = T(n,k)*[a(.)+b(.)]^(n-k), umbrally. The e.g.f. for the row polynomials of A is {(a+t) exp[(a+t)x] - a exp(a x)}/t, umbrally. - Tom Copeland, Aug 21 2008
A007318*A097806 as infinite lower triangular matrices. - Philippe Deléham, Feb 08 2009
Riordan array (1/(1-x)^2, x/(1-x)). - Philippe Deléham, Feb 22 2012
The elements of the matrix inverse are T^(-1)(n,k)=(-1)^(n+k)*T(n,k). - R. J. Mathar, Mar 12 2013
Relation to K-theory: T acting on the column vector (-0,d,-d^2,d^3,...) generates the Euler classes for a hypersurface of degree d in CP^n. Cf. Dugger p. 168 and also A104712, A111492, and A238363. - Tom Copeland, Apr 11 2014
Number of walks of length p>0 between any two distinct vertices of the complete graph K_(n+2) is W(n+2,p)=(-1)^(p-1)*Sum_{k=0..p-1} T(p-1,k)*(-n-2)^k = ((n+1)^p - (-1)^p)/(n+2) = (-1)^(p-1)*Sum_{k=0..p-1} (-n-1)^k. This is equal to (-1)^(p-1)*Phi(p,-n-1), where Phi is the cyclotomic polynomial when p is an odd prime. For K_3, see A001045; for K_4, A015518; for K_5, A015521; for K_6, A015531; for K_7, A015540. - Tom Copeland, Apr 14 2014
Consider the transformation 1 + x + x^2 + x^3 + ... + x^n = A_0*(x-1)^0 + A_1*(x-1)^1 + A_2*(x-1)^2 + ... + A_n*(x-1)^n. This sequence gives A_0, ..., A_n as the entries in the n-th row of this triangle, starting at n = 0. - Derek Orr, Oct 14 2014
See A074909 for associations among this array, the Bernoulli polynomials and their umbral compositional inverses, and the face polynomials of permutahedra and their duals (cf. A019538). - Tom Copeland, Nov 14 2014
From Wolfdieter Lang, Dec 10 2015: (Start)
A(r, n) = T(n+r-2, r-1) = risefac(n,r)/r! = binomial(n+r-1, r), for n >= 1 and r >= 1, gives the array with the number of independent components of a symmetric tensors of rank r (number of indices) and dimension n (indices run from 1 to n). Here risefac(n, k) is the rising factorial.
As(r, n) = T(n+1, r+1) = fallfac(n, r)/r! = binomial(n, r), r >= 1 and n >= 1 (with the triangle entries T(n, k) = 0 for n < k) gives the array with the number of independent components of an antisymmetric tensor of rank r and dimension n. Here fallfac is the falling factorial. (End)
The h-vectors associated to these f-vectors are given by A000012 regarded as a lower triangular matrix. Read as bivariate polynomials, the h-polynomials are the complete homogeneous symmetric polynomials in two variables, found in the compositional inverse of an e.g.f. for A008292, the h-vectors of the permutahedra. - Tom Copeland, Jan 10 2017
For a correlation between the states of a quantum system and the combinatorics of the n-simplex, see Boya and Dixit. - Tom Copeland, Jul 24 2017

Examples

			The triangle T(n, k) begins:
   n\k  0  1   2   3   4   5   6   7   8  9 10 11 ...
   0:   1
   1:   2  1
   2:   3  3   1
   3:   4  6   4   1
   4:   5 10  10   5   1
   5:   6 15  20  15   6   1
   6:   7 21  35  35  21   7   1
   7:   8 28  56  70  56  28   8   1
   8:   9 36  84 126 126  84  36   9   1
   9:  10 45 120 210 252 210 120  45  10  1
  10:  11 55 165 330 462 462 330 165  55 11  1
  11:  12 66 220 495 792 924 792 495 220 66 12  1
  ... reformatted by _Wolfdieter Lang_, Mar 23 2015
Production matrix begins
   2   1
  -1   1   1
   1   0   1   1
  -1   0   0   1   1
   1   0   0   0   1   1
  -1   0   0   0   0   1   1
   1   0   0   0   0   0   1   1
  -1   0   0   0   0   0   0   1   1
   1   0   0   0   0   0   0   0   1   1
- _Philippe Deléham_, Jan 29 2014
From _Wolfdieter Lang_, Nov 08 2018: (Start)
Recurrence [_Philippe Deléham_]: T(7, 3) = 2*35 + 35 - 15 - 20 = 70.
Recurrence from Riordan A- and Z-sequences: [1,1,repeat(0)] and [2, repeat(-1, +1)]: From Z: T(5, 0) = 2*5 - 10 + 10 - 5 + 1 = 6. From A: T(7, 3) = 35 + 35 = 70.
Boas-Buck column k=3 recurrence: T(7, 3) = (5/4)*(1 + 5 + 15 + 35) = 70. (End)

Links

Crossrefs

Cf. A007318, A014410, A228196.
Cf. Column sequences: A000027, A000217, A000292, A000332, A000389, A000579 - A000582, A001287, A001288, A010965 - A011001, A017713 - A017764.
Cf. A000012, A008292.

Programs

  • Maple
    for i from 0 to 12 do seq(binomial(i, j)*1^(i-j), j = 1 .. i) od;
  • Mathematica
    Flatten[Table[CoefficientList[D[1/x ((x + 1) Exp[(x + 1) z] - Exp[z]), {z, k}] /. z -> 0, x], {k, 0, 11}]]
CoefficientList[CoefficientList[Series[1/((1 - x)*(1 - x - x*y)), {x, 0, 10}, {y, 0, 10}], x], y] // Flatten (* G. C. Greubel, Nov 22 2017 *)
  • PARI
    for(n=0, 20, for(k=0, n, print1(1/k!*sum(i=0, n, (prod(j=0, k-1, i-j))), ", "))) \\ Derek Orr, Oct 14 2014
  • Sage
    Trow = lambda n: sum((x+1)^j for j in (0..n)).list()
for n in (0..10): print(Trow(n)) # Peter Luschny, Jul 09 2019

Formula

T(n, k) = Sum_{j=k..n} binomial(j,k) = binomial(n+1, k+1), n >= k >= 0, else 0. (Partial sum of column k of A007318 (Pascal), or summation on the upper binomial index (Graham et al. (GKP), eq. (5.10). For the GKP reference see A007318.) - Wolfdieter Lang, Aug 22 2012
E.g.f.: 1/x*((1 + x)*exp(t*(1 + x)) - exp(t)) = 1 + (2 + x)*t + (3 + 3*x + x^2)*t^2/2! + .... The infinitesimal generator for this triangle has the sequence [2,3,4,...] on the main subdiagonal and 0's elsewhere. - Peter Bala, Jul 16 2013
T(n,k) = 2*T(n-1,k) + T(n-1,k-1) - T(n-2,k) - T(n-2,k-1), T(0,0)=1, T(1,0)=2, T(1,1)=1, T(n,k)=0 if k<0 or if k>n. - Philippe Deléham, Dec 27 2013
T(n,k) = A193862(n,k)/2^k. - Philippe Deléham, Jan 29 2014
G.f.: 1/((1-x)*(1-x-x*y)). - Philippe Deléham, Mar 13 2014
From Tom Copeland, Mar 26 2014: (Start)
[From Copeland's 2007 and 2008 comments]
A) O.g.f.: 1 / { [ 1 - t * x/(1-x) ] * (1-x)^2 } (same as Deleham's).
B) The infinitesimal generator for T is given in A132681 with m=1 (same as Bala's), which makes connections to the ubiquitous associated Laguerre polynomials of integer orders, for this case the Laguerre polynomials of order one L(n,-t,1).
C) O.g.f. of row e.g.f.s: Sum_{n>=0} L(n,-t,1) x^n = exp[t*x/(1-x)]/(1-x)^2 = 1 + (2+t)x + (3+3*t+t^2/2!)x^2 + (4+6*t+4*t^2/2!+t^3/3!)x^3+ ... .
D) E.g.f. of row o.g.f.s: ((1+t)*exp((1+t)*x)-exp(x))/t (same as Bala's).
E) E.g.f. for T(n,k)*a(n-k): {(a+t) exp[(a+t)x] - a exp(a x)}/t, umbrally. For example, for a(k)=2^k, the e.g.f. for the row o.g.f.s is {(2+t) exp[(2+t)x] - 2 exp(2x)}/t.
(End)
From Tom Copeland, Apr 28 2014: (Start)
With different indexing
A) O.g.f. by row: [(1+t)^n-1]/t.
B) O.g.f. of row o.g.f.s: {1/[1-(1+t)*x] - 1/(1-x)}/t.
C) E.g.f. of row o.g.f.s: {exp[(1+t)*x]-exp(x)}/t.
These generating functions are related to row e.g.f.s of A111492. (End)
From Tom Copeland, Sep 17 2014: (Start)
A) U(x,s,t)= x^2/[(1-t*x)(1-(s+t)x)] = Sum_{n >= 0} F(n,s,t)x^(n+2) is a generating function for bivariate row polynomials of T, e.g., F(2,s,t)= s^2 + 3s*t + 3t^2 (Buchstaber, 2008).
B) dU/dt=x^2 dU/dx with U(x,s,0)= x^2/(1-s*x) (Buchstaber, 2008).
C) U(x,s,t) = exp(t*x^2*d/dx)U(x,s,0) = U(x/(1-t*x),s,0).
D) U(x,s,t) = Sum[n >= 0, (t*x)^n L(n,-:xD:,-1)] U(x,s,0), where (:xD:)^k=x^k*(d/dx)^k and L(n,x,-1) are the Laguerre polynomials of order -1, related to normalized Lah numbers. (End)
E.g.f. satisfies the differential equation d/dt(e.g.f.(x,t)) = (x+1)*e.g.f.(x,t) + exp(t). - Vincent J. Matsko, Jul 18 2015
The e.g.f. of the Norlund generalized Bernoulli (Appell) polynomials of order m, NB(n,x;m), is given by exponentiation of the e.g.f. of the Bernoulli numbers, i.e., multiple binomial self-convolutions of the Bernoulli numbers, through the e.g.f. exp[NB(.,x;m)t] = (t/(e^t - 1))^(m+1) * e^(xt). Norlund gave the relation to the factorials (x-1)!/(x-1-n)! = (x-1) ... (x-n) = NB(n,x;n), so T(n,m) = NB(m+1,n+2;m+1)/(m+1)!. - Tom Copeland, Oct 01 2015
From Wolfdieter Lang, Nov 08 2018: (Start)
Recurrences from the A- and Z- sequences for the Riordan triangle (see the W. Lang link under A006232 with references), which are A(n) = A019590(n+1), [1, 1, repeat (0)] and Z(n) = (-1)^(n+1)*A054977(n), [2, repeat(-1, 1)]:
T(0, 0) = 1, T(n, k) = 0 for n < k, and T(n, 0) = Sum_{j=0..n-1} Z(j)*T(n-1, j), for n >= 1, and T(n, k) = T(n-1, k-1) + T(n-1, k), for n >= m >= 1.
Boas-Buck recurrence for columns (see the Aug 10 2017 remark in A036521 also for references):
T(n, k) = ((2 + k)/(n - k))*Sum_{j=k..n-1} T(j, k), for n >= 1, k = 0, 1, ..., n-1, and input T(n, n) = 1, for n >= 0, (the BB-sequences are alpha(n) = 2 and beta(n) = 1). (End)
T(n, k) = [x^k] Sum_{j=0..n} (x+1)^j. - Peter Luschny, Jul 09 2019

Extensions

Edited by Tom Copeland and N. J. A. Sloane, Dec 11 2007

A132440 Infinitesimal Pascal matrix: generator (lower triangular matrix representation) of the Pascal matrix, the classical operator xDx, iterated Laguerre transforms, associated matrices of the list partition transform and general Euler transformation for sequences.

Original entry on oeis.org

0, 1, 0, 0, 2, 0, 0, 0, 3, 0, 0, 0, 0, 4, 0, 0, 0, 0, 0, 5, 0, 0, 0, 0, 0, 0, 6, 0, 0, 0, 0, 0, 0, 0, 7, 0, 0, 0, 0, 0, 0, 0, 0, 8, 0, 0, 0, 0, 0, 0, 0, 0, 0, 9, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 10, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 11, 0
Offset: 0

Views

Author

Tom Copeland, Nov 13 2007, Nov 15 2007, Nov 22 2007, Dec 02 2007

Keywords

Comments

Let M(t) = exp(t*T) = lim_{n->oo} (1 + t*T/n)^n.
Pascal matrix = [ binomial(n,k) ] = M(1) = exp(T), truncating the series gives the n X n submatrices.
Inverse Pascal matrix = M(-1) = exp(-T) = matrix for inverse binomial transform.
A(j) = T^j / j! equals the matrix [binomial(n,k) * delta(n-k-j)] where delta(n) = 1 if n=0 and vanishes otherwise (Kronecker delta); i.e., A(j) is a matrix with all the terms 0 except for the j-th lower (or main for j=0) diagonal, which equals that of the Pascal triangle. Hence the A(j)'s form a linearly independent basis for all matrices of the form [binomial(n,k) * d(n-k)] which include as a subset the invertible associated matrices of the list partition transform (LPT) of A133314.
For sequences with b(0) = 1, umbrally,
M[b(.)] = exp(b(.)*T) = [ binomial(n,k) * b(n-k) ] = matrices associated to b by LPT.
[M[b(.)]]^(-1) = exp(c(.)*T) = [ binomial(n,k) * c(n-k) ] = matrices associated to c, where c = LPT(b) . Or,
[M[b(.)]]^(-1) = exp[LPT(b(.))*T] = LPT[M(b(.))] = M[LPT(b(.))]= M[c(.)].
This is related to xDx, the iterated Laguerre transform and the general Euler transformation of a sequence through the comments in A132013 and A132014 and the relation [Sum_{k=0..n} binomial(n,k) * b(n-k) * d(k)] = M(b)*d, (n-th term). See also A132382.
If b(n,x) is a binomial type Sheffer sequence, then M[b(.,x)]*s(y) = s(x+y) when s(y) = (s(0,y),s(1,y),s(2,y),...) is an array for a Sheffer sequence with the same delta operator as b(n,x) and [M[b(.,x)]]^(-1) is given by the formulas above with b(n) replaced by b(n,x) as b(0,x)=1 for a binomial-type Sheffer sequence.
T = I - A132013 and conversely A132013 = I - T, which is the matrix representation for the iterated mixed order Laguerre transform characterized in A132013 (and A132014).
(I-T)^m generates the group [A132013]^m for m = 0,1,2,... discussed in A132014.
The inverse is 1/(I-T) = I + T + T^2 + T^3 + ... = [A132013]^(-1) = A094587 with the associated sequence (0!,1!,2!,3!,...) under the LPT.
And 1/(I-T)^2 = I + 2*T + 3*T^2 + 4*T^3 + ... = [A132013]^(-2) = A132159 with the associated sequence (1!,2!,3!,4!,...) under the LPT.
The matrix operation b = T*a can be characterized in several ways in terms of the coefficients a(n) and b(n), their o.g.f.'s A(x) and B(x), or e.g.f.'s EA(x) and EB(x).
1) b(0) = 0, b(n) = n * a(n-1),
2) B(x) = xDx A(x)
3) B(x) = x * Lag(1,-:xD:) A(x)
4) EB(x) = x * EA(x) where D is the derivative w.r.t. x, (:xD:)^j = x^j*D^j and Lag(n,x) is the Laguerre polynomial.
So the exponentiated operator can be characterized as
5) exp(t*T) A(x) = exp(t*xDx) A(x) = [Sum_{n=0,1,...} (t*x)^n * Lag(n,-:xD:)] A(x) = [exp{[t*u/(1-t*u)]*:xD:} / (1-t*u) ] A(x) (eval. at u=x) = A[x/(1-t*x)]/(1-t*x), a generalized Euler transformation for an o.g.f.,
6) exp(t*T) EA(x) = exp(t*x)*EA(x) = exp[(t+a(.))*x], gen. Euler trf. for an e.g.f.
7) exp(t*T) * a = M(t) * a = [Sum_{k=0..n} binomial(n,k) * t^(n-k) * a(k)].
The umbral extension of formulas 5, 6 and 7 gives formally
8) exp[c(.)*T] A(x) = exp(c(.)*xDx) A(x) = [Sum_{n>=0} (c(.)*x)^n * Lag(n,-:xD:)] A(x) = [exp{[c(.)*u/(1-c(.)*u)]*:xD:} / (1-c(.)*u) ] A(x) (eval. at u=x) = A[x/(1-c(.)*x)]/(1-c(.)*x), where the umbral evaluation should be applied only after a power series in c is obtained,
9) exp[c(.)*T] EA(x) = exp(c(.)*x)*EA(x) = exp[(c(.)+a(.))*x]
10) exp[c(.)*T] * a = M[c(.)] * a = [Sum_{k=0..n} binomial(n,k) * c(n-k) * a(k)] .
The n X n principal submatrix of T is nilpotent, in particular, [Tsub_n]^(n+1) = 0, n=0,1,2,3,....
Note (xDx)^n = x^n D^n x^n = x^n n! (:Dx:)^n/n! = x^n n! Lag(n,-:xD:).
The operator xDx is an important, classical operator explored by among others Dattoli, Al-Salam, Carlitz and Stokes and even earlier investigators.
For a recent treatment of xDx, DxD and more general operators see the paper "Laguerre-type derivatives: Dobinski relations and combinatorial identities". - Karol A. Penson, Sep 15 2009
See Copeland's link for generalized Laguerre functions and connection to fractional differ-integrals in exercises through (:Dx:)^a/a!=(D^a x^a)/a!. - Tom Copeland, Nov 17 2011
From Tom Copeland, Apr 25 2014: (Start)
Conjugation or "similarity" transformations of [dP]=A132440 have an operator interpretation (cf. A074909 and A238363):
In general, select two operators A and B such that A^n = F1(n,B) and B^n = F2(n,A); then A^n = F1(n,F2(.,A)) and B^n = F2(n,F1(.,B)), evaluated umbrally, i.e., F1(n,F2(.,x))=F2(n,F1(.,x))=x^n, implying the polynomials F1 and F2 are an umbral compositional inverse pair.
One such pair are the Bell polynomials Bell(n,x) and falling factorials (x)_n with Bell(n,:xD:)=(xD)^n and (xD)_n=:xD:^n (cf. A074909). Another are the Laguerre polynomials LN(n,x)= n!*Lag(n,x) (A021009), which are umbrally self-inverse, with LN(n,-:xD:)=:Dx:^n and LN(n,:Dx:)= (-:xD:)^n with :Dx:^n=D^n*x^n.
Evaluating, for n>=0, the operator derivative d(B^n)/dA = d(F2(n,A))/dA in the basis B^n, i.e., with A^n finally replaced by F1(n,B), or A^n=F1(.,B)^n=F1(n,B), is equivalent to the matrix conjugation
A) [F2]*[dP]*[F1]
B) = [F2]*[dP]*[F2]^(-1)
C) = [F1]^(-1)*[dP]*[F1],
where [F1] is the lower triangular matrix with the n-th row the coefficients of F1(n,x) and analogously for [F2].
So, given the row vector Rv=(c0 c1 c2 c3 ...) and the column vector Cv(x)=(1 x x^2 x^3 ...)^Transpose, form the power series V(x)=Rv*Cv(x).
D) dV(B)/dA = Rv * [F2]*[dP]*[F1] * Cv(B).
E) With A=D and B=D, F1(n,x)=F2(n,x)=x^n and [F1]=[F2]=I. Then d(B^n)/dA = d(D^n)/dD = n * D^(n-1); therefore, consistently [F2]*[dP]*[F1] = [dP] and dV(D)/dD = Rv * [dP] * Cv(D). (End)

Examples

			Matrix T begins
  0;
  1,0;
  0,2,0;
  0,0,3,0;
  0,0,0,4,0;
  ...

References

  • T. Mansour and M. Schork, Commutation Relations, Normal Ordering, and Stirling Numbers, Chapman and Hall/CRC, 2015, (x^n D^n x^n on p. 187).

Links

Programs

Formula

T = log(P) with the Pascal matrix P:=A007318. This should be read as T_N = log(P_N) with P_N the N X N matrix P, N>=2. Because P_N is lower triangular with all diagonal elements 1, the series log(1_N-(1_N-P_N)) stops after N-1 terms because (1_N-P_N)^N is the 0_N-matrix. - Wolfdieter Lang, Oct 14 2010
Given a polynomial sequence p_n(x) with p_0(x)=1 and the lowering and raising operators L and R defined by L p_n(x) = n * p_(n-1)(x) and R p_n(x) = p_(n+1)(x), the matrix T represents the action of R*L*R in the p_n(x) basis. For p_n(x) = x^n, L = D = d/dx and R = x. For p_n(x) = x^n/n!, L = DxD and R = D^(-1). - Tom Copeland, Oct 25 2012
From Tom Copeland, Apr 26 2014: (Start)
A) T = exp(A238385-I) - I
B) = [St1]*P*[St2] - I
C) = [St1]*P*[St1]^(-1) - I
D) = [St2]^(-1)*P*[St2] - I
E) = [St2]^(-1)*P*[St1]^(-1) - I
where P=A007318, [St1]=padded A008275 just as [St2]=A048993=padded A008277, and I=identity matrix. (End)
From Robert Israel, Oct 02 2015: (Start)
G.f. Sum_{k >= 1} k x^((k+3/2)^2/2 - 17/8) is related to Jacobi theta functions.
If 8*n+17 = y^2 is a square, then a(n) = (y-3)/2, otherwise a(n) = 0. (End)

Extensions

Missing zero added in table by Tom Copeland, Feb 25 2014
Showing 1-10 of 21 results. Next

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

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