A085771 -id:A085771 - 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

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

A308650 Number of permutations of [2n] with n components.

Original entry on oeis.org

1, 1, 7, 58, 531, 5226, 54598, 601924, 6985987, 85328266, 1097775922, 14897635468, 213581648046, 3238686925956, 51972937713900, 882473430354888, 15839021166164451, 300037212548146890, 5986554523174314490, 125537613562829696828, 2760474045847159393466

Offset: 0

Alois P. Heinz, Jun 13 2019

nonn

			a(2) = 7: 1|342, 1|423, 1|432, 21|43, 231|4, 312|4, 321|4.
a(3) = 58: 1|2|4563, 1|2|4635, 1|2|4653, 1|2|5364, ..., 4213|5|6, 4231|5|6, 4312|5|6, 4321|5|6.

Alois P. Heinz, Table of n, a(n) for n = 0..400

Cf. A059438, A085771, A131577, A263484.

p[n_] := p[n] = n! - Sum[k!*p[n - k], {k, 1, n - 1}];
(* T is A059438 *)
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}];
a[n_] := T[2n, n];
Table[a[n], {n, 0, 25}] (* Jean-François Alcover, Aug 31 2021 *)

a(n) = [x^(2n)] (1-1/Sum_{j=0..2n} j!*x^j)^n.
a(n) = A059438(2n,n) = A085771(2n,n) = A263484(2n,n).
a(n) is odd <=> n in { A131577 }.
a(n) ~ sqrt(2*Pi) * n^(n + 5/2) / exp(n-1). - Vaclav Kotesovec, Jun 25 2019

A109281 Triangle T(n,k) of elements of n-th Weyl group of type B whose reduced word uses n-k generators.

Original entry on oeis.org

1, 1, 1, 5, 2, 1, 35, 9, 3, 1, 309, 56, 14, 4, 1, 3287, 443, 84, 20, 5, 1, 41005, 4298, 623, 120, 27, 6, 1, 588487, 49937, 5629, 859, 165, 35, 7, 1, 9571125, 680700, 61300, 7360, 1162, 220, 44, 8, 1, 174230863, 10683103, 793402, 75714, 9584, 1544, 286, 54, 9, 1

Offset: 0

Mike Zabrocki, Aug 19 2005

Row sums are 2^n n!.

G.f. for k-th column is given by (1-1/g(x))^(k-1)*g(2x)/g(x).

			T(3,1)=9 because B_3 is generated by {t,s1,s2} where t^2=s1^2=s2^2=(s1 s2)^3=(t s1)^4=(t s2)^2=1.
The 9 elements which only use 2 generators are {s1 s2, s1 s2 s1, s2 s1, s2 t, t s1, s1 t s1, s1 t s1 t, s1 t, t s1 t}.
Triangle starts:
1;
1, 1;
5, 2, 1;
35, 9, 3, 1;
309, 56, 14, 4, 1;
...

N. Bergeron, C. Hohlweg, M. Zabrocki, Posets related to the connectivity set of Coxeter groups, arXiv:math/0509271 [math.CO], 2005-2006.

Cf. A109253, A003319, A085771, A059438.

For the similar sequence in type D, see A112226.

f:=proc(n,k) local gx; gx:=add(i!*x^i,i=0..n); coeff(series((1-1/gx)^k*subs(x=2*x,gx)/gx,x,n+1),x,n); end:

nmax = 9;
g[x_] = Sum[n!*x^n, {n, 0, nmax}];
gf[x_, t_] = g[2*x]/(t + (1 - t)*g[x]);
T[n_, k_] := SeriesCoefficient[gf[x, t], {x, 0, n}] // SeriesCoefficient[#, {t, 0, k}]&;
Table[T[n, k], {n, 0, nmax}, {k, 0, n}] // Flatten (* Jean-François Alcover, Nov 25 2017 *)

G.f.: g(2x)/(t+(1-t)g(x)) where g(x) = sum_{n>=0} n! x^n.

A112226 Table T(n,k) of number of elements of Weyl group of type D of order 2^{n-1} n! such that a reduced word uses exactly n-k distinct simple reflections 0 <= k <= n, n>=1.

Original entry on oeis.org

0, 0, 1, 1, 2, 1, 13, 7, 3, 1, 135, 40, 12, 4, 1, 1537, 293, 66, 18, 5, 1, 19811, 2646, 451, 100, 25, 6, 1, 289073, 28887, 3753, 663, 143, 33, 7, 1, 4741923, 374820, 37798, 5232, 940, 196, 42, 8, 1, 86705417, 5676121, 457508, 49444, 7174, 1294, 260, 52, 9, 1

Offset: 0

Mike Zabrocki, Aug 28 2005

The first two rows of this table are not well-defined. This is an analog of the notion of permutations with k components for type D (see A059438)

			D_3 is generated by {s_0,s_1,s_2} where s_0^2 = s_1^2 = s_2^2 = (s_0 s_1)^2 = (s_0 s_2)^3 = (s_1 s_2)^2, the elements of this group can be broken up into 4 sets with reduced words as {1}, {s_0, s_1, s_2}, {s_0 s_1, s_1 s_2, s_2 s_1, s_1 s_2 s_1, s_0 s_2, s_2 s_0, s_0 s_2 s_0} hence T(3,3)=1, T(3,2)=3 and T(3,1)=7. T(3,0)=13 since the remaining 13 elements will have reduced words where all three simple reflections appear.

N. Bergeron, C. Hohlweg, M. Zabrocki, Posets related to the connectivity set of Coxeter groups

Cf. A112225, A003319, A109253, A109281, A085771, A059438.

f2:=proc(n,k) local i,gx,g2x; gx:=add(i!*x^i, i=0..n); g2x:=subs(x=2*x,gx); coeff(series(((g2x+3)/(2*gx) + x)*(1-1/gx)^k - x*(1-1/gx)^(k-1),x,n+1),x,n); end: f1:=n->coeff(series((add(2^k*k!*x^k,k=1..n)+4)/add(2*k!*x^k,k=0..n)+x-2,x,n+1),x,n); T:=(n,k)->if k=0 then f1(n) else f2(n,k) fi;

max = 10;
fA = 1 - 1/Sum[n!*x^n, {n, 0, max}] + O[x]^max;
fD = (3 + Sum[2^n*n!*x^n, {n, 0, max}])/(2*Sum[n!*x^n, {n, 0, max}]) + x - 2 + O[x]^max;
f = (2*t*fA - 2*t*x + t^2*x*fA + fD)/(1 - t*fA);
row[n_] := CoefficientList[ SeriesCoefficient[f, {x, 0, n}], t];
Join[{{0}}, {{0, 1}}, Table[row[n], {n, 2, max - 1}]] // Flatten (* Jean-François Alcover, Nov 28 2017 *)

G.f.: (g(2x) - (2 t x - 4 t - 2 x + 4) g(x) - 4 t + 3)/(2(t + (1-t) g(x))) where g(x) = sum_{n >= 0} n! x^n o.g.f. for first column given by (g(2x)+3)/(2g(x)) + x - 2 o.g.f. for k^th (k>1) column given by ((g(2x)+3)/(2g(x)) + x)*(1-1/g(x))^{k-1} - x (1-1/g(x))^{k-2}

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

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

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

SageMath

Extensions

A308650 Number of permutations of [2n] with n components.

Views

Author

Keywords

Examples

Links

Crossrefs

Programs

Mathematica

Formula

A109281 Triangle T(n,k) of elements of n-th Weyl group of type B whose reduced word uses n-k generators.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Maple

Mathematica

Formula

A112226 Table T(n,k) of number of elements of Weyl group of type D of order 2^{n-1} n! such that a reduced word uses exactly n-k distinct simple reflections 0 <= k <= n, n>=1.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Maple

Mathematica

Formula