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.

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

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.

(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+(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

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_(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)

From James East, Apr 11 2014: (Start)

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

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/(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)

From Gus Wiseman, Jan 23 2022: (Start)

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)

Also the convolution triangle of A000012. - Peter Luschny, Oct 07 2022

From Sergey Kitaev, Nov 18 2023: (Start)

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

Alois P. Heinz, Rows n = 0..140, flattened

Tom 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), 95-109.

Tian Han and Sergey Kitaev, Joint distributions of statistics over permutations avoiding two patterns of length 3, arXiv:2311.02974 [math.CO], 2023.

Wolfdieter Lang, On Generating functions of Diagonals Sequences of Sheffer and Riordan Number Triangles, arXiv:1708.01421 [math.NT], August 2017.

Huyile Liang, Yanni Pei, and Yi Wang, Analytic combinatorics of coordination numbers of cubic lattices, arXiv:2302.11856 [math.CO], 2023. See p. 8.

P. A. MacMahon, Memoir on the Theory of the Compositions of Numbers, Phil. Trans. Royal Soc. London A, 184 (1893), 835-901. - 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)^(j-k), 0).

T(r,c) = binomial(r-1,c-1), 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(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

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 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)

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

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+(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)
From James East, Apr 11 2014: (Start)
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)):
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(k-1, n-i), i=1..n-k+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
# Uses function PMatrix from A357368.
PMatrix(10, n -> 1);  # Peter Luschny, Oct 07 2022

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.
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
(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.

Cf. A000012 (diagonal), A011782 (row sums), A088218 (central terms).

Cf. A007318, A048004, A127952, A118800, A200139, A130595, A167374.

The terms just left of center in odd-indexed rows are A001791, even A002054.

The odd-indexed rows are A034871.

Row sums without the center are A058622.

The unordered version is A072233, without zeros A008284.

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.

A098124 counts balanced compositions, unordered A047993.

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.

Sequence in context: A213889 A363779 A110555 * A071919 A321791 A339649

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