A308650 -id:A308650 - cp's OEIS frontend

A059438 Triangle T(n,k) (1 <= k <= n) read by rows: T(n,k) is the number of permutations of [1..n] with k components.

1, 1, 1, 3, 2, 1, 13, 7, 3, 1, 71, 32, 12, 4, 1, 461, 177, 58, 18, 5, 1, 3447, 1142, 327, 92, 25, 6, 1, 29093, 8411, 2109, 531, 135, 33, 7, 1, 273343, 69692, 15366, 3440, 800, 188, 42, 8, 1, 2829325, 642581, 125316, 24892, 5226, 1146, 252, 52, 9, 1

Offset: 1

N. J. A. Sloane, Feb 01 2001

			Triangle begins:
[1] [     1]
[2] [     1,     1]
[3] [     3,     2,     1]
[4] [    13,     7,     3,    1]
[5] [    71,    32,    12,    4,   1]
[6] [   461,   177,    58,   18,   5,   1]
[7] [  3447,  1142,   327,   92,  25,   6,  1]
[8] [ 29093,  8411,  2109,  531, 135,  33,  7, 1]
[9] [273343, 69692, 15366, 3440, 800, 188, 42, 8, 1]

G. C. Greubel, Table of n, a(n) for the first 50 rows, flattened
Louis Comtet, Advanced Combinatorics, Reidel, 1974, p. 262 (#14).
Antonio Di Crescenzo, Barbara Martinucci, and Abdelaziz Rhandi, A linear birth-death process on a star graph and its diffusion approximation, arXiv:1405.4312 [math.PR], 2014.
FindStat - Combinatorial Statistic Finder, The decomposition number of a permutation.
Peter Hegarty and Anders Martinsson, On the existence of accessible paths in various models of fitness landscapes, arXiv:1210.4798 [math.PR], 2012-2014. - From _N. J. A. Sloane_, Jan 01 2013
Sergey Kitaev and Philip B. Zhang, Distributions of mesh patterns of short lengths, arXiv:1811.07679 [math.CO], 2018.

A version with reflected rows is A263484.
Diagonals give A003319, A059439, A059440, A055998.
Cf. A000007, A085771, A084938.
T(2n,n) gives A308650.

# Uses function PMatrix from A357368. Adds column 1, 0, 0, ... to the left.
PMatrix(10, A003319); # Peter Luschny, Oct 09 2022

(* p = indecomposable permutations = A003319 *) p[n_] := p[n] = n! - Sum[ k!*p[n-k], {k, 1, n-1}]; t[n_, k_] /; n < k = 0; t[n_, 1] := p[n]; t[n_, k_] /; n >= k := t[n, k] = Sum[ t[n-j, k-1]*p[j], {j, 1, n}]; Flatten[ Table[ t[n, k], {n, 1, 10}, {k, 1, n}] ] (* Jean-François Alcover, Mar 06 2012, after Philippe Deléham *)

def A059438_triangle(dim) :
    R = PolynomialRing(ZZ, 'x')
    C = [R(0)] + [R(1) for i in range(dim+1)]
    A = [(i + 2) // 2 for i in range(dim+1)]
    A[0] = R.gen(); T = []
    for k in range(1, dim+1) :
        for n in range(k, 0, -1) :
            C[n] = C[n-1] + C[n+1] * A[n-1]
        T.append(list(C[1])[1::])
    return T
A059438_triangle(8) # Peter Luschny, Sep 10 2022

# Alternatively, using the function PartTrans from A357078:
# Adds a (0,0)-based column (1, 0, 0, ...) to the left of the triangle.
dim = 10
A = ZZ[['t']]; g = A([0]+[factorial(n) for n in range(1, 30)]).O(dim+2)
PartTrans(dim, lambda n: list(g / (1 +  g))[n]) # Peter Luschny, Sep 11 2022

Let f(x) = Sum_{n >= 0} n!*x^n, g(x) = 1 - 1/f(x). Then g(x) is g.f. for first diagonal A003319 and Sum_{n >= k} T(n, k)*x^n = g(x)^k.
Triangle T(n, k), n > 0 and k > 0, read by rows; given by [0, 1, 2, 2, 3, 3, 4, 4, 5, 5, 6, 6, ...] DELTA A000007 where DELTA is Deléham's operator defined in A084938.
T(n+k, k) = Sum_{a_1 + a_2 + ... + a_k = n} A003319(a_1)*A003319(a_2)*...*A003319(a_k). T(n, k) = 0 if n < k, T(n, 1) = A003319(n) and for n >= k T(n, k)= Sum_{j>=1} T(n-j, k-1)* A003319(j). A059438 is formed from the self convolution of its first column (A003319). - Philippe Deléham, Feb 04 2004
Sum_{k>0} T(n, k) = n!; see A000142. - Philippe Deléham, Feb 05 2004
If g(x) = x + x^2 + 3*x^3 + 13*x^4 + ... is the generating function for the number of permutations with no global descents, then 1/(1-g(x)) is the generating function for n!. Setting t=1 in f(x, t) implies Sum_{k=1..n} T(n,k) = n!. Let g(x) be the o.g.f. for A003319. Then the o.g.f. for this table is given by f(x, t) = 1/(1 - t*g(x)) - 1 (i.e., the coefficient of x^n*t^k in f(x,t) is T(n,k)). - Mike Zabrocki, Jul 29 2004

More terms from Vladeta Jovovic, Mar 04 2001

A085771 Triangle read by rows. T(n, k) = A059438(n, k) for 1 <= k <= n, and T(n, 0) = n^0.

Original entry on oeis.org

1, 0, 1, 0, 1, 1, 0, 3, 2, 1, 0, 13, 7, 3, 1, 0, 71, 32, 12, 4, 1, 0, 461, 177, 58, 18, 5, 1, 0, 3447, 1142, 327, 92, 25, 6, 1, 0, 29093, 8411, 2109, 531, 135, 33, 7, 1, 0, 273343, 69692, 15366, 3440, 800, 188, 42, 8, 1, 0, 2829325, 642581, 125316, 24892, 5226, 1146, 252, 52, 9, 1

Offset: 0

Philippe Deléham, Jul 22 2003

The convolution triangle of A003319, the number of irreducible permutations. - Peter Luschny, Oct 09 2022

			Triangle starts:
[0] [1]
[1] [0,      1]
[2] [0,      1,     1]
[3] [0,      3,     2,     1]
[4] [0,     13,     7,     3,    1]
[5] [0,     71,    32,    12,    4,   1]
[6] [0,    461,   177,    58,   18,   5,   1]
[7] [0,   3447,  1142,   327,   92,  25,   6,  1]
[8] [0,  29093,  8411,  2109,  531, 135,  33,  7, 1]
[9] [0, 273343, 69692, 15366, 3440, 800, 188, 42, 8, 1]

L. Comtet, Advanced Combinatorics, Reidel, 1974, p. 262 (#14).

FindStat - Combinatorial Statistic Finder, The decomposition number of a permutation.

T(2*n, n) = A308650(n).
Variants: A059439, A263484 (row reversed).
Cf. A003319, A059440, A055998, A059438, A000007, A084938.

# Uses function PMatrix from A357368.
PMatrix(10, A003319); # Peter Luschny, Oct 09 2022

# Using function delehamdelta from A084938.
def A085771_triangle(n) :
    a = [0, 1] + [(i + 3) // 2 for i in range(1, n-1)]
    b = [0^i for i in range(n)]
    return delehamdelta(a, b)
A085771_triangle(9) # Peter Luschny, Sep 10 2022

Let f(x) = Sum_{n>=0} n!*x^n, g(x) = 1 - 1/f(x). Then g(x) is the g.f. of the second column, A003319.
Triangle T(n, k) read by rows, given by [0, 1, 2, 2, 3, 3, 4, 4, 5, 5, 6, 6, ...] DELTA A000007, where DELTA is Deléham's operator defined in A084938.
G.f.: 1/(1 - xy/(1 - x/(1 - 2x/(1 - 2x/(1 - 3x/(1 - 3x/(1 - 4x/(1-.... (continued fraction). - Paul Barry, Jan 29 2009

A263484 Triangle read by rows: T(n,k) (n>=1, 0<=k

Original entry on oeis.org

1, 1, 1, 1, 2, 3, 1, 3, 7, 13, 1, 4, 12, 32, 71, 1, 5, 18, 58, 177, 461, 1, 6, 25, 92, 327, 1142, 3447, 1, 7, 33, 135, 531, 2109, 8411, 29093, 1, 8, 42, 188, 800, 3440, 15366, 69692, 273343, 1, 9, 52, 252, 1146, 5226, 24892, 125316, 642581, 2829325

Offset: 1

Christian Stump, Oct 19 2015

Row sums give A000142, n >= 1.
From Allan C. Wechsler, Jun 14 2019 (Start):
Suppose we are permuting the numbers from 1 through 5. For example, consider the permutation (1,2,3,4,5) -> (3,1,2,5,4). Notice that there is exactly one point where we can cut this permutation into two consecutive pieces in such a way that no item is permuted from one piece to the other, namely (3,1,2 | 5,4). This "cut" has the property that all the indices to its left are less than all the indices to its right. There are no other such cut-points: (3,1 | 2,5,4) doesn't work, for example, because 3 > 2.
Stanley defines the "connectivity set" as the set of positions at which you can make such a cut. In this case, the connectivity set is {3}.
In the present sequence, T(n,k) is the number of permutations of n elements with k cut points. (End)
Essentially the same triangle as [1, 0, 0, 0, 0, 0, 0, 0, ...] DELTA [0, 1, 2, 2, 3, 3, 4, 4, 5, ...] where DELTA is the operator defined in A084938. - Philippe Deléham, Feb 18 2020

			Triangle begins:
  1,
  1, 1,
  1, 2,  3,
  1, 3,  7, 13,
  1, 4, 12, 32,  71,
  1, 5, 18, 58, 177, 461,
  ...
Triangle [1, 0, 0, 0, 0, ...] DELTA [0, 1, 2, 2, 3, 3, ...]:
  1;
  1, 0;
  1, 1,  0;
  1, 2,  3,  0;
  1, 3,  7, 13,  0;
  1, 4, 12, 32, 71, 0;
... - _Philippe Deléham_, Feb 18 2020

Alois P. Heinz, Rows n = 0..150, flattened
FindStat - Combinatorial Statistic Finder, The cardinality of the complement of the connectivity set.
Mathematics Stack Exchange, Discussion of this sequence, June 2019.
Richard P. Stanley, The Descent Set and Connectivity Set of a Permutation, arXiv:math/0507224 [math.CO], 2005.

Cf. A000142.
T(n,n-1) gives A003319.
A version with reflected rows is A059438, A085771.
T(2n,n) gives A308650.

rows = 11;
(* DELTA is defined in A084938 *)
Most /@ DELTA[Table[Boole[n == 1], {n, rows}], Join[{0, 1}, LinearRecurrence[{1, 1, -1}, {2, 2, 3}, rows]], rows] // Flatten (* Jean-François Alcover, Feb 18 2020, after Philippe Deléham *)

# cf. FindStat link
def statistic(x):
     return len(set(x.reduced_word()))
for n in [1..6]:
    for pi in Permutations(n):
        print(pi, "=>", statistic(pi))

More terms from Fred Lunnon and Christian Stump

Name changed by Georg Fischer as proposed by Allan C. Wechsler, Jun 13 2019

cp's OEIS Frontend

A059438 Triangle T(n,k) (1 <= k <= n) read by rows: T(n,k) is the number of permutations of [1..n] with k components.

Views

Author

Keywords

Examples

Links

Crossrefs

Programs

Maple

Mathematica

SageMath

SageMath

Formula

Extensions

A085771 Triangle read by rows. T(n, k) = A059438(n, k) for 1 <= k <= n, and T(n, 0) = n^0.

Views

Author

Keywords

Comments

Examples

References

Links

Crossrefs

Programs

Maple

SageMath

Formula

A263484 Triangle read by rows: T(n,k) (n>=1, 0<=k

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

SageMath

Extensions