|
|
A097805
|
|
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.
|
|
177
|
|
|
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, 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, 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
(list;
table;
graph;
refs;
listen;
history;
text;
internal format)
|
|
|
OFFSET
|
0,9
|
|
COMMENTS
|
Previous name was: Riordan array (1, 1/(1-x)) read by rows.
Note this Riordan array would be denoted (1, x/(1-x)) by some authors.
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.
(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
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
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.
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)
Triangle read by rows: T(r,c) is the number of ordered partitions (compositions) of r into c parts. - Juergen Will, Jan 04 2016
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#) =
1) exp(x^2D) for the set x^n and
2) D^(-1) exp(t*x)D for the set x^n/n! (see A218234).
(End)
Square array a(m,n) with m,n=0,1,2,... read by off-diagonals.
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.
a(n,n)=A088218(n) is the size of the semigroup O_n of all order-preserving transformations of {1,...,n}.
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.
(End)
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
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).
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)
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):
. (15) (24) (33) (42) (51) (6)
(141) (132) (123) (114)
(1113) (231) (222) (213)
(1212) (1122) (321) (312)
(1311) (1221) (1131) (411)
(2112) (2121)
(2211) (3111)
(11121) (11112)
(12111) (11211)
(111111) (21111)
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)
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.
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).
Number of permutations of length n avoiding simultaneously the patterns 213 and 312 with k right-to-left maxima (resp., left-to-right maxima).
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)
|
|
REFERENCES
|
D. E. Knuth, The Art of Computer Programming, vol. 4A, Combinatorial Algorithms, Part 1, Section 7.2.1.3, 2011.
|
|
LINKS
|
|
|
FORMULA
|
Number triangle T(n, k) defined by T(n,k) = Sum_{j=0..n} binomial(n, j)*if(k<=j, (-1)^(j-k), 0).
a(0,0) = 1, a(n,k) = binomial(n-1,n-k) = binomial(n-1,k-1) Juergen Will, Jan 04 2016
G.f.: (x^1 + x^2 + x^3 + ...)^k = (x/(1-x))^k. - Juergen Will, Jan 04 2016
E.g.f.: 1 + x*[e^((x+1)t)-1]/(x+1).
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).
M = NpdP*S^(-1) follows from the well-known recursion property of the Pascal matrix, implying NpdP = M*S.
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.
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)
|
|
EXAMPLE
|
G.f. = 1 + x * (x + x^3 * (1 + x) + x^6 * (1 + x)^2 + x^10 * (1 + x)^3 + ...). - Michael Somos, Aug 20 2006
The triangle T(n, k) begins:
n\k 0 1 2 3 4 5 6 7 8 9 10 ...
0: 1
1: 0 1
2: 0 1 1
3: 0 1 2 1
4: 0 1 3 3 1
5: 0 1 4 6 4 1
6: 0 1 5 10 10 5 1
7: 0 1 6 15 20 15 6 1
8: 0 1 7 21 35 35 21 7 1
9: 0 1 8 28 56 70 56 28 8 1
10: 0 1 9 36 84 126 126 84 36 9 1
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).
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)
a(0,0)=1 since there is a unique (order-preserving) function {}->{}.
a(m,0)=0 for m>0 since there is no function from a nonempty set to the empty set.
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.
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].
(End)
|
|
MAPLE
|
b:= proc(n, i, p) option remember; `if`(n=0, p!, `if`(i<1, 0,
expand(add(b(n-i*j, i-1, p+j)/j!*x^j, j=0..n/i))))
end:
T:= n-> (p-> seq(coeff(p, x, i), i=0..degree(p)))(b(n$2, 0)):
# Alternatively:
T := proc(k, n) option remember;
if k=n then 1 elif k=0 then 0 else
add(T(k-1, n-i), i=1..n-k+1) fi end:
# Uses function PMatrix from A357368.
|
|
MATHEMATICA
|
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 *)
Table[Length[Select[Join@@Permutations/@IntegerPartitions[n], Length[#]==k&]], {n, 0, 10}, {k, 0, n}] (* Gus Wiseman, Jan 23 2022 *)
|
|
PROG
|
(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 */
(PARI) T(n, k) = if (k==0, 0^n, binomial(n-1, k-1)); \\ Michel Marcus, May 06 2022
(PARI) row(n) = vector(n+1, k, k--; if (k==0, 0^n, binomial(n-1, k-1))); \\ Michel Marcus, May 06 2022
(Sage)
# Illustrates a basic partition formula, is not efficient as a program for large n.
r = []
for k in (0..n):
s = 0
for q in Partitions(n, max_part=k, inner=[k]):
s += mul(binomial(q[j], q[j+1]) for j in range(len(q)-1))
r.append(s)
return r
(Python)
from math import comb
def T(n, k): return comb(n-1, k-1) if k != 0 else k**n # Peter Luschny, May 06 2022
|
|
CROSSREFS
|
Case m=0 of the polynomials defined in A278073.
The terms just left of center in odd-indexed rows are A001791, even A002054.
Row sums without the center are A058622.
Right half without center has row sums A027306(n-1).
Right half with center has row sums A116406(n).
Left half without center has row sums A294175(n-1).
Left half with center has row sums A058622(n-1).
A025047 counts alternating compositions.
A106356 counts compositions by number of maximal anti-runs.
A344651 counts partitions by sum and alternating sum.
A345197 counts compositions by sum, length, and alternating sum.
Cf. A000346, A000984, A001700, A008549, A008965, A114121, A124754, A238279, A345907, A345908, A346632.
|
|
KEYWORD
|
|
|
AUTHOR
|
|
|
EXTENSIONS
|
New name using classical terminology by Peter Luschny, Feb 05 2019
|
|
STATUS
|
approved
|
|
|
|