|
%I #214 Nov 17 2023 12:21:19
%S 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,
%T 28,56,70,56,28,8,1,9,36,84,126,126,84,36,9,1,10,45,120,210,252,210,
%U 120,45,10,1,11,55,165,330,462,462,330,165,55,11
%N Running sum of Pascal's triangle (A007318), or beheaded Pascal's triangle read by beheaded rows.
%C 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
%C The "almost triangular" partitions are the ones cycled by the operation of "Bulgarian solitaire", as defined by Martin Gardner.
%C Start with A007318 - I (I = Identity matrix), then delete right border of zeros. - _Gary W. Adamson_, Jun 15 2007
%C 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
%C 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
%C 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
%C Reversal of A135278. - _Philippe Deléham_, Feb 11 2012
%C For a closed-form formula for arbitrary left and right borders of Pascal-like triangles see A228196. - _Boris Putievskiy_, Aug 19 2013
%C For a closed-form formula for generalized Pascal's triangle see A228576. - _Boris Putievskiy_, Sep 09 2013
%C 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]
%C A) = [St2]*[dP]*[St1] = A048993*A132440*[padded A008275]
%C B) = [St2]*[dP]*[St2]^(-1)
%C C) = [St1]^(-1)*[dP]*[St1],
%C where [St1]=padded A008275 just as [St2]=A048993=padded A008277 whereas [padded A074909]=A007318-I with I=identity matrix. - _Tom Copeland_, Apr 25 2014
%C 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
%C From _Tom Copeland_, Nov 12 2014: (Start)
%C 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).
%C 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).
%C 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.
%C 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.
%C 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.
%C 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.
%C 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)
%C 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
%C 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
%C 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
%C 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
%C From _Tom Copeland_, Jul 10 2018: (Start)
%C 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
%C 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)
%H Reinhard Zumkeller, <a href="/A074909/b074909.txt">Rows n = 0..150 of triangle, flattened</a>
%H Feryal Alayont and Evan Henning, <a href="https://cs.uwaterloo.ca/journals/JIS/VOL26/Alayont/ala4.html">Edge Covers of Caterpillars, Cycles with Pendants, and Spider Graphs</a>, J. Int. Seq. (2023) Vol. 26, Art. 23.9.4.
%H Paul Barry, <a href="https://arxiv.org/abs/1805.02274">On the f-Matrices of Pascal-like Triangles Defined by Riordan Arrays</a>, arXiv:1805.02274 [math.CO], 2018.
%H Tom Copeland, <a href="https://tcjpn.wordpress.com/2014/12/23/appell-ops-cumulants-noncrossing-partitions-dyck-lattice-paths-and-inversion">Appell polynomials, cumulants, noncrossing partitions, Dyck lattice paths, and inversion</a>, 2014.
%H Tom Copeland, <a href="http://tcjpn.wordpress.com/2015/12/21/generators-inversion-and-matrix-binomial-and-integral-transforms/">Generators, Inversion, and Matrix, Binomial, and Integral Transforms</a>, 2015.
%H Sela Fried, <a href="https://arxiv.org/abs/2202.13061">The expected degree of noninvertibility of compositions of functions and a related combinatorial identity</a>, arXiv:2202.13061 [math.CO], 2022.
%H J. R. Griggs, <a href="http://dx.doi.org/10.1006/aama.1998.0597">The Cycling of Partitions and Compositions under Repeated Shifts</a>, Advances in Applied Mathematics, Volume 21, Issue 2, August 1998, Pages 205-227.
%H P. Olver, <a href="http://www.math.umn.edu/~olver/di_/contact.pdf">The canonical contact form</a> p. 7.
%H D. P. Walsh, <a href="http://www.mtsu.edu/~dwalsh/ACYCINCR.pdf">A short note on increasing acyclic functions</a>
%F T(n, k) = Sum_{i=0..n} C(i, n-k) = C(n+1, k).
%F Row n has g.f. (1+x)^(n+1)-x^(n+1).
%F 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
%F 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
%F 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
%F G.f. for column k (with leading zeros): x^(k-1)*(1/(1-x)^(k+1)-1), k >= 0. - _Wolfdieter Lang_, Nov 04 2014
%F 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
%F 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
%F T(n, k) = (1/k!) * Sum_{i=0..k} Stirling1(k,i)*(n+1)^i, for 0<=k<=n. - _Ridouane Oudra_, Oct 23 2022
%e T(4,2) = 0+0+1+3+6 = 10 = binomial(5, 2).
%e Triangle T(n,k) begins:
%e n\k 0 1 2 3 4 5 6 7 8 9 10 11
%e 0: 1
%e 1: 1 2
%e 2: 1 3 3
%e 3: 1 4 6 4
%e 4: 1 5 10 10 5
%e 5: 1 6 15 20 15 6
%e 6: 1 7 21 35 35 21 7
%e 7: 1 8 28 56 70 56 28 8
%e 8: 1 9 36 84 126 126 84 36 9
%e 9: 1 10 45 120 210 252 210 120 45 10
%e 10: 1 11 55 165 330 462 462 330 165 55 11
%e 11: 1 12 66 220 495 792 924 792 495 220 66 12
%e ... Reformatted. - _Wolfdieter Lang_, Nov 04 2014
%e .
%e 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
%e [0] 1, 1, 1, 1, 1, 1, 1, 1, 1, ... A000012
%e [1] 2, 3, 4, 5, 6, 7, 8, 9, 10, ... A000027
%e [2] 3, 6, 10, 15, 21, 28, 36, 45, 55, ... A000217
%e [3] 4, 10, 20, 35, 56, 84, 120, 165, 220, ... A000292
%e [4] 5, 15, 35, 70, 126, 210, 330, 495, 715, ... A000332
%e [5] 6, 21, 56, 126, 252, 462, 792, 1287, 2002, ... A000389
%e [6] 7, 28, 84, 210, 462, 924, 1716, 3003, 5005, ... A000579
%e [7] 8, 36, 120, 330, 792, 1716, 3432, 6435, 11440, ... A000580
%e [8] 9, 45, 165, 495, 1287, 3003, 6435, 12870, 24310, ... A000581
%e [9] 10, 55, 220, 715, 2002, 5005, 11440, 24310, 48620, ... A000582
%p A074909 := proc(n,k)
%p if k > n or k < 0 then
%p 0;
%p else
%p binomial(n+1,k) ;
%p end if;
%p end proc: # _Zerinvary Lajos_, Nov 09 2006
%t 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}]]]
%o (Haskell)
%o a074909 n k = a074909_tabl !! n !! k
%o a074909_row n = a074909_tabl !! n
%o a074909_tabl = iterate
%o (\row -> zipWith (+) ([0] ++ row) (row ++ [1])) [1]
%o -- _Reinhard Zumkeller_, Feb 25 2012
%o (PARI) print1(1);for(n=1,10,for(k=1,n,print1(", "binomial(n,k)))) \\ _Charles R Greathouse IV_, Mar 26 2013
%o (GAP) Flat(List([0..10],n->List([0..n],k->Binomial(n+1,k)))); # _Muniru A Asiru_, Jul 10 2018
%o (Magma) /* As triangle */ [[Binomial(n+1,k): k in [0..n]]: n in [0.. 15]]; // _Vincenzo Librandi_, Jul 22 2018
%Y Cf. A007318, A181971, A228196, A228576.
%Y Row sums are A000225, diagonal sums are A052952.
%Y The number of acyclic functions is A058127.
%Y Cf. A008292, A090582, A019538, A049019, A133314, A135278, A133437, A111785, A126216, A134685, A133932, A248727, A033282, A134264.
%Y Cf. A000027, A000217, A000292, A000332, A000389, A000579, A000580, A000581, A000582.
%Y Cf. A325191.
%K easy,nonn,tabl
%O 0,3
%A _Wouter Meeussen_, Oct 01 2002
%E 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
%E Formula section edited, checked and corrected by _Wolfdieter Lang_, Nov 04 2014
|
