

A097805


Compositions of n with k parts, T(n, k) = binomial(n1, k1) for n, k >= 1 and T(n, 0) = 0^n, triangle read by rows for n >= 0 and 0 <= k <= n.


76



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/(1x)) read by rows.
Note this Riordan array would be denoted (1, x/(1x)) by some authors.
Columns have g.f. (x/(1x))^k. Reverse of A071919. Row sums are A011782. Antidiagonal sums are Fibonacci(n1). Inverse as Riordan array is (1, 1/(1+x)). A097805=B*A059260*B^(1), where B is the binomial matrix.
(0,1)Pascal triangle.  Philippe Deléham, Nov 21 2006
(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
From Paul Weisenhorn, Feb 09 2011: (Start)
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+(c1) 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
From Tom Copeland, Oct 25 2012: (Start)
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_(n1)(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)
From James East, Apr 11 2014: (Start)
Square array a(m,n) with m,n=0,1,2,... read by offdiagonals.
a(m,n) gives the number of orderpreserving functions f:{1,...,m}>{1,...,n}. Orderpreserving 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 orderpreserving 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
From Wolfdieter Lang, Feb 17 2017: (Start)
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/(1x): x^0 = 1 = y^0, x^n = Sum_{m >= n} Ttrans(n,m) y^m, for n >= 1, with Ttrans(n,m) = binomial(m1,n1).
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(n1, m1), for n >= 1, then Sum_{n >= 0} a(n)*x^n = Sum_{n >= 0} b(n)*y^n, with y = x/(1x) and vice versa. This is a modified binomial transformation; the usual one belongs to the Pascal Riordan matrix A007318. (End)


REFERENCES

D. E. Knuth, The Art of Computer Programming, vol. 4A, Combinatorial Algorithms, Part 1, Section7.2.1.3, 2011.


LINKS

Alois P. Heinz, Rows n = 0..140, flattened
T. Copeland, Infinitesimal Generators, the Pascal Pyramid, and the Witt and Virasoro Algebras
James East and Peter J. McNamara, On the work performed by a transformation semigroup, Australas. J. Combin. 49 (2011), 95109.
Wolfdieter Lang, On Generating functions of Diagonals Sequences of Sheffer and Riordan Number Triangles, arXiv:1708.01421 [math.NT], August 2017.
P. A. MacMahon, Memoir on the Theory of the Compositions of Numbers, Phil. Trans. Royal Soc. London A, 184 (1893), 835901.  Juergen Will, Jan 02 2016
Franck Ramaharo, A generating polynomial for the pretzel knot, arXiv:1805.10680 [math.CO], 2018.


FORMULA

Number triangle T(n, k) defined by T(n,k) = Sum_{j=0..n} binomial(n, j)*if(k<=j, (1)^(jk), 0).
T(r,c) = binomial(r1,c1), 0<=c<=r.  Paul Weisenhorn, Feb 09 2011
G.f.: (1+x)/(1+x+x*y).  R. J. Mathar, Aug 11 2015
a(0,0) = 1, a(n,k) = binomial(n1,nk) = binomial(n1,k1) Juergen Will, Jan 04 2016
G.f.: (x^1+x^2+x^3+...)^k = (x/(1x))^k Juergen Will, Jan 04 2016
From Tom Copeland, Nov 15 2016: (Start)
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 selfinverse, i.e., (M*S)^2 = the identity matrix, and has the e.g.f. 1  x*[e^((1x)t)1]/(1x).
M = NpdP*S^(1) follows from the wellknown recursion property of the Pascal matrix, implying NpdP = M*S.
The selfinverse property of NpdP is implied by the selfinverse 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
... reformatted Wolfdieter Lang, Jul 31 2017
From Paul Weisenhorn, Feb 09 2011: (Start)
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+(c1) = 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)
From James East, Apr 11 2014: (Start)
a(0,0)=1 since there is a unique (orderpreserving) 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 orderpreserving 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 orderpreserving 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(ni*j, i1, 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)):
seq(T(n), n=0..20); # Alois P. Heinz, May 25 2014
# Alternatively:
T := proc(k, n) option remember;
if k=n then 1 elif k=0 then 0 else
add(T(k1, ni), i=1..nk+1) fi end:
A097805 := (n, k) > T(k, n):
for n from 0 to 12 do seq(A097805(n, k), k=0..n) od; # Peter Luschny, Mar 12 2016


MATHEMATICA

T[0, 0] = 1; T[n_, k_] := Binomial[n1, k1]; Table[T[n, k], {n, 0, 12}, {k, 0, n}] // Flatten (* JeanFrançois Alcover, Sep 03 2014, after Paul Weisenhorn *)


PROG

(PARI) {a(n) = my(m); if( n<2, n==0, n; m = (sqrtint(8*n + 1)  1)\2; binomial(m1, n  m*(m + 1)/2))}; /* Michael Somos, Aug 20 2006 */
(Sage)
# Illustrates a basic partition formula, is not efficient as a program for large n.
def A097805_row(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
[A097805_row(n) for n in (0..9)] # Peter Luschny, Jul 13 2015
(MAGMA) /* As triangle */ [[Binomial(n1, k1) : k in [1..n]]: n in [1.. 10]]; // Vincenzo Librandi, Jul 14 2015


CROSSREFS

Case m=0 of the polynomials defined in A278073.
Cf. A000012 (diagonal), A011782 (row sums), A088218 (central terms).
Cf. A007318, A048004, A127952, A118800, A200139, A130595, A167374.
Sequence in context: A119337 A213889 A110555 * A071919 A321791 A277504
Adjacent sequences: A097802 A097803 A097804 * A097806 A097807 A097808


KEYWORD

easy,nonn,tabl


AUTHOR

Paul Barry, Aug 25 2004


EXTENSIONS

Corrected by Philippe Deléham, Oct 05 2005
New name using classical terminology by Peter Luschny, Feb 05 2019


STATUS

approved



