A357078 -id:A357078 - cp's OEIS frontend

A357079 Triangle read by rows. T(n, k) = A356265(n, k) + A357078(n, k) for 0 <= k <= n.

1, 0, 1, 0, 1, 1, 0, 3, 2, 1, 0, 9, 12, 2, 1, 0, 49, 37, 31, 2, 1, 0, 329, 149, 176, 63, 2, 1, 0, 2561, 794, 853, 702, 127, 2, 1, 0, 22369, 5599, 3836, 5709, 2549, 255, 2, 1, 0, 216225, 47275, 18422, 37609, 33949, 8886, 511, 2, 1, 2291457, 451176, 107535, 218506, 344670, 184653, 29777, 1023, 2, 1

Offset: 0

Peter Luschny, Sep 11 2022

The triangle is the termwise sum of a refinement of the number of irreducible permutations A357078, and A356265, which is a refinement of the number of reducible permutations.

			Triangle T(n, k) starts:                                 [Row sums]
[0] 1;                                                       [1]
[1] 0,     1;                                                [1]
[2] 0,     1,      1;                                        [2]
[3] 0,     3,      2,     1;                                 [6]
[4] 0,     9,     12,     2,     1;                          [24]
[5] 0,    49,     37,    31,     2,     1;                   [120]
[6] 0,   329,    149,   176,    63,     2,    1;             [720]
[7] 0,   2561,   794,   853,   702,   127,    2,   1;        [5040]
[8] 0,  22369,  5599,  3836,  5709,  2549,  255,   2, 1;     [40320]
[9] 0, 216225, 47275, 18422, 37609, 33949, 8886, 511, 2, 1;  [362880]

Cf. A356265, A357078, A059438, A003319.

def A357079_triangle(dim):
    T = A357078_triangle(dim)
    return [[0^n] + [T[n][k+1] + A356265_row(n)[k]
           for k in range(n)] for n in range(dim)]
A357079_triangle(9)

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.

Original entry on oeis.org

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

cp's OEIS Frontend

A357079 Triangle read by rows. T(n, k) = A356265(n, k) + A357078(n, k) for 0 <= k <= n.

Views

Author

Keywords

Comments

Examples

Crossrefs

Programs

SageMath

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