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

 

Logo

The October issue of the Notices of the Amer. Math. Soc. has an article about the OEIS.

Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
A074909 Running sum of Pascal's triangle (A007318), or beheaded Pascal's triangle read by beheaded rows. 56
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 (list; table; graph; refs; listen; history; text; internal format)
OFFSET

0,3

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! = Binom(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)

LINKS

Reinhard Zumkeller, Rows n = 0..150 of triangle, flattened

Paul Barry, On the f-Matrices of Pascal-like Triangles Defined by Riordan Arrays, arXiv:1805.02274 [math.CO], 2018.

T. Copeland, Appell polynomials, cumulants, noncrossing partitions, Dyck lattice paths, and inversion, 2014.

T. Copeland, Generators, Inversion, and Matrix, Binomial, and Integral Transforms, 2015.

J. R. Griggs, The Cycling of Partitions and Compositions under Repeated Shifts, Advances in Applied Mathematics, Volume 21, Issue 2, August 1998, Pages 205-227.

P. Olver, The canonical contact form p. 7.

D. P. Walsh, A short note on increasing acyclic functions

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: 0<k<n, T(n, 0)=1, T(n, n)=n. - Reinhard 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

EXAMPLE

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

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}]]]

PROG

(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

(PARI) print1(1); for(n=1, 10, for(k=1, n, print1(", "binomial(n, k)))) \\ Charles R Greathouse IV, Mar 26 2013

(GAP) Flat(List([0..10], n->List([0..n], k->Binomial(n+1, k)))); # Muniru A Asiru, Jul 10 2018

(MAGMA) /* As triangle */ [[Binomial(n+1, k): k in [0..n]]: n in [0.. 15]]; // Vincenzo Librandi, Jul 22 2018

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.

Sequence in context: A057145 A134394 A284855 * A135278 A034356 A075195

Adjacent sequences:  A074906 A074907 A074908 * A074910 A074911 A074912

KEYWORD

easy,nonn,tabl

AUTHOR

Wouter Meeussen, Oct 01 2002

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

STATUS

approved

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

License Agreements, Terms of Use, Privacy Policy. .

Last modified September 25 01:17 EDT 2018. Contains 315360 sequences. (Running on oeis4.)