|
%I #163 Dec 17 2023 10:30:53
%S 1,0,1,0,1,1,0,1,2,1,0,1,3,3,1,0,1,4,6,4,1,0,1,5,10,10,5,1,0,1,6,15,
%T 20,15,6,1,0,1,7,21,35,35,21,7,1,0,1,8,28,56,70,56,28,8,1,0,1,9,36,84,
%U 126,126,84,36,9,1,0,1,10,45,120,210,252,210,120,45,10,1,0,1,11,55,165,330,462,462,330,165,55,11,1
%N Number of compositions of n with k parts, T(n, k) = binomial(n-1, k-1) for n, k >= 1 and T(n, 0) = 0^n, triangle read by rows for n >= 0 and 0 <= k <= n.
%C Previous name was: Riordan array (1, 1/(1-x)) read by rows.
%C Note this Riordan array would be denoted (1, x/(1-x)) by some authors.
%C Columns have g.f. (x/(1-x))^k. Reverse of A071919. Row sums are A011782. Antidiagonal sums are Fibonacci(n-1). Inverse as Riordan array is (1, 1/(1+x)). A097805=B*A059260*B^(-1), where B is the binomial matrix.
%C (0,1)-Pascal triangle. - _Philippe Deléham_, Nov 21 2006
%C (n+1) * each term of row n generates triangle A127952: (1; 0, 2; 0, 3, 3; 0, 4, 8, 4; ...). - _Gary W. Adamson_, Feb 09 2007
%C Triangle T(n,k), 0<=k<=n, read by rows, given by [0,1,0,0,0,0,0,...] DELTA [1,0,0,0,0,0,0,...] where DELTA is the operator defined in A084938. - _Philippe Deléham_, Dec 12 2008
%C From _Paul Weisenhorn_, Feb 09 2011: (Start)
%C Triangle read by rows: T(r,c) is the number of unordered partitions of n=r*(r+1)/2+c into (r+1) parts < (r+1) and at most pairs of equal parts and parts in neighboring pairs have difference 2.
%C Triangle read by rows: T(r,c) is the number of unordered partitions of the number n=r*(r+1)/2+(c-1) into r parts < (r+1) and at most pairs of equal parts and parts in neighboring pairs have difference 2. (End)
%C Triangle read by rows: T(r,c) is the number of ordered partitions (compositions) of r into c parts. - _Juergen Will_, Jan 04 2016
%C From _Tom Copeland_, Oct 25 2012: (Start)
%C Given a basis composed of a sequence of polynomials p_n(x) characterized by ladder (creation / annihilation, or raising / lowering) operators defined by R p_n(x) = p_(n+1)(x) and L p_n(x) = n p_(n-1)(x) with p_0(x)=1, giving the number operator # p_n(x) = RL p_n(x) = n p_n(x), the lower triangular padded Pascal matrix Pd (A097805) serves as a matrix representation of the operator exp(R^2*L) = exp(R#) =
%C 1) exp(x^2D) for the set x^n and
%C 2) D^(-1) exp(t*x)D for the set x^n/n! (see A218234).
%C (End)
%C From _James East_, Apr 11 2014: (Start)
%C Square array a(m,n) with m,n=0,1,2,... read by off-diagonals.
%C a(m,n) gives the number of order-preserving functions f:{1,...,m}->{1,...,n}. Order-preserving means that x<y implies f(x)<f(y) for all x,y.
%C a(n,n)=A088218(n) is the size of the semigroup O_n of all order-preserving transformations of {1,...,n}.
%C Read as a triangle, this sequence may be obtained by augmenting Pascal's triangle by appending the column 1,0,0,0,... on the left.
%C (End)
%C A formula based on the partitions of n with largest part k is given as a Sage program below. The 'conjugate' formula leads to A048004. - _Peter Luschny_, Jul 13 2015
%C From _Wolfdieter Lang_, Feb 17 2017: (Start)
%C The transposed of this lower triangular Riordan matrix of the associated type T provides the transition matrix between the monomial basis {x^n}, n >= 0, and the basis {y^n}, n >= 0, with y = x/(1-x): x^0 = 1 = y^0, x^n = Sum_{m >= n} Ttrans(n,m) y^m, for n >= 1, with Ttrans(n,m) = binomial(m-1,n-1).
%C Therefore, if a transformation with this Riordan matrix from a sequence {a} to the sequence {b} is given by b(n) = Sum_{m=0..n} T(n, m)*a(m), with T(n, m) = binomial(n-1, m-1), for n >= 1, then Sum_{n >= 0} a(n)*x^n = Sum_{n >= 0} b(n)*y^n, with y = x/(1-x) and vice versa. This is a modified binomial transformation; the usual one belongs to the Pascal Riordan matrix A007318. (End)
%C From _Gus Wiseman_, Jan 23 2022: (Start)
%C Also the number of compositions of n with alternating sum k, with k ranging from -n to n in steps of 2. For example, row n = 6 counts the following compositions (empty column indicated by dot):
%C . (15) (24) (33) (42) (51) (6)
%C (141) (132) (123) (114)
%C (1113) (231) (222) (213)
%C (1212) (1122) (321) (312)
%C (1311) (1221) (1131) (411)
%C (2112) (2121)
%C (2211) (3111)
%C (11121) (11112)
%C (12111) (11211)
%C (111111) (21111)
%C The reverse-alternating version is the same. Counting compositions by all three parameters (sum, length, alternating sum) gives A345197. Compositions of 2n with alternating sum 2k with k ranging from -n + 1 to n are A034871. (End)
%C Also the convolution triangle of A000012. - _Peter Luschny_, Oct 07 2022
%C From _Sergey Kitaev_, Nov 18 2023: (Start)
%C Number of permutations of length n avoiding simultaneously the patterns 123 and 132 with k right-to-left maxima. A right-to-left maximum in a permutation a(1)a(2)...a(n) is position i such that a(j) < a(i) for all i < j.
%C Number of permutations of length n avoiding simultaneously the patterns 231 and 312 with k right-to-left minima (resp., left-to-right maxima). A right-to-left minimum (resp., left-to-right maximum) in a permutation a(1)a(2)...a(n) is position i such that a(j) > a(i) for all j > i (resp., a(j) < a(i) for all j < i).
%C Number of permutations of length n avoiding simultaneously the patterns 213 and 312 with k right-to-left maxima (resp., left-to-right maxima).
%C Number of permutations of length n avoiding simultaneously the patterns 213 and 231 with k right-to-left maxima (resp., right-to-left minima). (End)
%D D. E. Knuth, The Art of Computer Programming, vol. 4A, Combinatorial Algorithms, Part 1, Section 7.2.1.3, 2011.
%H Alois P. Heinz, <a href="/A097805/b097805.txt">Rows n = 0..140, flattened</a>
%H Tom Copeland, <a href="http://tcjpn.wordpress.com/2012/11/29/infinigens-the-pascal-pyramid-and-the-witt-and-virasoro-algebras/">Infinitesimal Generators, the Pascal Pyramid, and the Witt and Virasoro Algebras</a>
%H James East and Peter J. McNamara, <a href="http://ajc.maths.uq.edu.au/pdf/49/ajc_v49_p095.pdf">On the work performed by a transformation semigroup</a>, Australas. J. Combin. 49 (2011), 95-109.
%H Tian Han and Sergey Kitaev, <a href="https://arxiv.org/abs/2311.02974">Joint distributions of statistics over permutations avoiding two patterns of length 3</a>, arXiv:2311.02974 [math.CO], 2023.
%H Wolfdieter Lang, <a href="https://arxiv.org/abs/1708.01421">On Generating functions of Diagonals Sequences of Sheffer and Riordan Number Triangles</a>, arXiv:1708.01421 [math.NT], August 2017.
%H Huyile Liang, Yanni Pei, and Yi Wang, <a href="https://arxiv.org/abs/2302.11856">Analytic combinatorics of coordination numbers of cubic lattices</a>, arXiv:2302.11856 [math.CO], 2023. See p. 8.
%H P. A. MacMahon, <a href="http://www.jstor.org/stable/90632">Memoir on the Theory of the Compositions of Numbers</a>, Phil. Trans. Royal Soc. London A, 184 (1893), 835-901. - _Juergen Will_, Jan 02 2016
%H Franck Ramaharo, <a href="https://arxiv.org/abs/1805.10680">A generating polynomial for the pretzel knot</a>, arXiv:1805.10680 [math.CO], 2018.
%F Number triangle T(n, k) defined by T(n,k) = Sum_{j=0..n} binomial(n, j)*if(k<=j, (-1)^(j-k), 0).
%F T(r,c) = binomial(r-1,c-1), 0 <= c <= r. - _Paul Weisenhorn_, Feb 09 2011
%F G.f.: (-1+x)/(-1+x+x*y). - _R. J. Mathar_, Aug 11 2015
%F a(0,0) = 1, a(n,k) = binomial(n-1,n-k) = binomial(n-1,k-1) _Juergen Will_, Jan 04 2016
%F G.f.: (x^1 + x^2 + x^3 + ...)^k = (x/(1-x))^k. - _Juergen Will_, Jan 04 2016
%F From _Tom Copeland_, Nov 15 2016: (Start)
%F E.g.f.: 1 + x*[e^((x+1)t)-1]/(x+1).
%F This padded Pascal matrix with the odd columns negated is NpdP = M*S = S^(-1)*M^(-1) = S^(-1)*M, where M(n,k) = (-1)^n A130595(n,k), the inverse Pascal matrix with the odd rows negated, S is the summation matrix A000012, the lower triangular matrix with all elements unity, and S^(-1) = A167374, a finite difference matrix. NpdP is self-inverse, i.e., (M*S)^2 = the identity matrix, and has the e.g.f. 1 - x*[e^((1-x)t)-1]/(1-x).
%F M = NpdP*S^(-1) follows from the well-known recursion property of the Pascal matrix, implying NpdP = M*S.
%F The self-inverse property of -NpdP is implied by the self-inverse relation of its embedded signed Pascal submatrix M (cf. A130595). Also see A118800 for another proof.
%F Let P^(-1) be A130595, the inverse Pascal matrix. Then T = A200139*P^(-1) and T^(-1) = padded P^(-1) = P*A097808*P^(-1). (End)
%F The center (n>0) is T(2n+1,n+1) = A000984(n) = 2*A001700(n-1) = 2*A088218(n) = A126869(2n) = 2*A138364(2n-1). - _Gus Wiseman_, Jan 25 2022
%e G.f. = 1 + x * (x + x^3 * (1 + x) + x^6 * (1 + x)^2 + x^10 * (1 + x)^3 + ...). - _Michael Somos_, Aug 20 2006
%e The triangle T(n, k) begins:
%e n\k 0 1 2 3 4 5 6 7 8 9 10 ...
%e 0: 1
%e 1: 0 1
%e 2: 0 1 1
%e 3: 0 1 2 1
%e 4: 0 1 3 3 1
%e 5: 0 1 4 6 4 1
%e 6: 0 1 5 10 10 5 1
%e 7: 0 1 6 15 20 15 6 1
%e 8: 0 1 7 21 35 35 21 7 1
%e 9: 0 1 8 28 56 70 56 28 8 1
%e 10: 0 1 9 36 84 126 126 84 36 9 1
%e ... reformatted _Wolfdieter Lang_, Jul 31 2017
%e From _Paul Weisenhorn_, Feb 09 2011: (Start)
%e T(r=5,c=3) = binomial(4,2) = 6 unordered partitions of the number n = r*(r+1)/2+c = 18 with (r+1)=6 summands: (5+5+4+2+1+1), (5+5+3+3+1+1), (5+4+4+3+1+1), (5+5+3+2+2+1), (5+4+4+2+2+1), (5+4+3+3+2+1).
%e T(r=5,c=3) = binomial(4,2) = 6 unordered partitions of the number n = r*(r+1)/2+(c-1) = 17 with r=5 summands: (5+5+4+2+1), (5+5+3+3+1), (5+5+3+2+2), (5+4+4+3+1), (5+4+4+2+2), (5+4+3+3+2). (End)
%e From _James East_, Apr 11 2014: (Start)
%e a(0,0)=1 since there is a unique (order-preserving) function {}->{}.
%e a(m,0)=0 for m>0 since there is no function from a nonempty set to the empty set.
%e a(3,2)=4 because there are four order-preserving functions {1,2,3}->{1,2}: these are [1,1,1], [2,2,2], [1,1,2], [1,2,2]. Here f=[a,b,c] denotes the function defined by f(1)=a, f(2)=b, f(3)=c.
%e a(2,3)=6 because there are six order-preserving functions {1,2}->{1,2,3}: these are [1,1], [1,2], [1,3], [2,2], [2,3], [3,3].
%e (End)
%p b:= proc(n, i, p) option remember; `if`(n=0, p!, `if`(i<1, 0,
%p expand(add(b(n-i*j, i-1, p+j)/j!*x^j, j=0..n/i))))
%p end:
%p T:= n-> (p-> seq(coeff(p, x, i), i=0..degree(p)))(b(n$2, 0)):
%p seq(T(n), n=0..20); # _Alois P. Heinz_, May 25 2014
%p # Alternatively:
%p T := proc(k,n) option remember;
%p if k=n then 1 elif k=0 then 0 else
%p add(T(k-1,n-i), i=1..n-k+1) fi end:
%p A097805 := (n,k) -> T(k,n):
%p for n from 0 to 12 do seq(A097805(n,k), k=0..n) od; # _Peter Luschny_, Mar 12 2016
%p # Uses function PMatrix from A357368.
%p PMatrix(10, n -> 1); # _Peter Luschny_, Oct 07 2022
%t T[0, 0] = 1; T[n_, k_] := Binomial[n-1, k-1]; Table[T[n, k], {n, 0, 12}, {k, 0, n}] // Flatten (* _Jean-François Alcover_, Sep 03 2014, after _Paul Weisenhorn_ *)
%t Table[Length[Select[Join@@Permutations/@IntegerPartitions[n],Length[#]==k&]],{n,0,10},{k,0,n}] (* _Gus Wiseman_, Jan 23 2022 *)
%o (PARI) {a(n) = my(m); if( n<2, n==0, n--; m = (sqrtint(8*n + 1) - 1)\2; binomial(m-1, n - m*(m + 1)/2))}; /* _Michael Somos_, Aug 20 2006 */
%o (PARI) T(n,k) = if (k==0, 0^n, binomial(n-1, k-1)); \\ _Michel Marcus_, May 06 2022
%o (PARI) row(n) = vector(n+1, k, k--; if (k==0, 0^n, binomial(n-1, k-1))); \\ _Michel Marcus_, May 06 2022
%o (Sage)
%o # Illustrates a basic partition formula, is not efficient as a program for large n.
%o def A097805_row(n):
%o r = []
%o for k in (0..n):
%o s = 0
%o for q in Partitions(n, max_part=k, inner=[k]):
%o s += mul(binomial(q[j],q[j+1]) for j in range(len(q)-1))
%o r.append(s)
%o return r
%o [A097805_row(n) for n in (0..9)] # _Peter Luschny_, Jul 13 2015
%o (Python)
%o from math import comb
%o def T(n, k): return comb(n-1, k-1) if k != 0 else k**n # _Peter Luschny_, May 06 2022
%Y Case m=0 of the polynomials defined in A278073.
%Y Cf. A000012 (diagonal), A011782 (row sums), A088218 (central terms).
%Y Cf. A007318, A048004, A127952, A118800, A200139, A130595, A167374.
%Y The terms just left of center in odd-indexed rows are A001791, even A002054.
%Y The odd-indexed rows are A034871.
%Y Row sums without the center are A058622.
%Y The unordered version is A072233, without zeros A008284.
%Y Right half without center has row sums A027306(n-1).
%Y Right half with center has row sums A116406(n).
%Y Left half without center has row sums A294175(n-1).
%Y Left half with center has row sums A058622(n-1).
%Y A025047 counts alternating compositions.
%Y A098124 counts balanced compositions, unordered A047993.
%Y A106356 counts compositions by number of maximal anti-runs.
%Y A344651 counts partitions by sum and alternating sum.
%Y A345197 counts compositions by sum, length, and alternating sum.
%Y Cf. A000346, A000984, A001700, A008549, A008965, A114121, A124754, A238279, A345907, A345908, A346632.
%K easy,nonn,tabl
%O 0,9
%A _Paul Barry_, Aug 25 2004
%E Corrected by _Philippe Deléham_, Oct 05 2005
%E New name using classical terminology by _Peter Luschny_, Feb 05 2019
|
