A059438 -id:A059438 - cp's OEIS frontend

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

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.

A355488 Expansion of g.f. f/(1+2*f) where f is the g.f. of nonempty permutations.

Original entry on oeis.org

0, 1, 0, 2, 8, 48, 328, 2560, 22368, 216224, 2291456, 26430336, 329805952, 4429255168, 63730438656, 978479250944, 15972310317056, 276292865550336, 5049672714569728, 97245533647568896, 1968395389124714496, 41783552069858877440, 928204423021249003520

Offset: 0

F. Chapoton, Jul 04 2022

nonn

This is to factorials what Fine numbers are to Catalan numbers. There is no known combinatorial interpretation.
The same construction, applied to the central binomials, leads to A126984, apart from signs and the first term. - Peter Luschny, Jul 22 2022
a(n) is the number of permutations of [n] whose number of components is odd minus the number of those permutations with an even number of components. - Peter Luschny, Sep 10 2022

			Consider the permutations of [3]: [2,3,1], [3,1,2] and [3,2,1] have 1 component,
[1,3,2] and [2,1,3] have 2 components, and [1,2,3] has three components. Thus 3 - 2 + 1 = 2 = a(3). - _Peter Luschny_, Sep 10 2022

David Callan, Counting Stabilized-Interval-Free Permutations, Journal of Integer Sequences, Vol. 7 (2004), Article 04.1.8.
FindStat - Combinatorial Statistic Finder, The number of connected components of a permutation.

Cf. A000108, A003319, A000957, A000142, A052186, A126984, A059438, A122827.

a:= n-> (f-> coeff(series(f/(1+2*f), x, n+1), x, n))(add(j!*x^j, j=1..n)):
seq(a(n), n=0..23);  # Alois P. Heinz, Jul 20 2022

nmax=22; f[x_]:=Sum[i! x^i,{i,nmax}]; CoefficientList[Series[f[x]/(1+2f[x]),{x,0,nmax}],x] (* Stefano Spezia, Jul 04 2022 *)

A = QQ[['t']]
f = A([0] + [factorial(n) for n in range(1,30)]).O(30)
print(list(f/(1+2*f)))

# Uses function A059438_triangle.
def A355488_list(size):
    triangle = A059438_triangle(size)
    return [0] + [sum((-1)^k*t for (k,t) in enumerate(row)) for row in triangle]
print(A355488_list(20))  # Peter Luschny, Sep 10 2022

G.f.: f/(1+2*f) where f is (the g.f. of A000142) - 1.

a(n) = -Sum_{k=1..n} (-1)^k * A059438(n, k) for n >= 1. - Peter Luschny, Sep 10 2022

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}

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

Original entry on oeis.org

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)

A091139 Row sums of triangle A091063.

Original entry on oeis.org

1, 1, 2, 5, 16, 66, 346, 2229, 17000, 148898, 1465364, 15957314, 190158712, 2459041744, 34278016954, 512253587397, 8168812190472, 138450960309882

Offset: 0

Paul D. Hanna, Dec 21 2003

nonn

The initial terms of the binomial transform of the n-th row of triangle A091063 forms the n-th row of triangle A059438 transposed (permutations of [1..n] with k components); the row sums of A059438 equal the factorials.

Cf. A091063.

G.f.: A(x) = 1/(1-x*g(x)) where g(x) is the g.f. of A075834 shift 1 place left.

A356324 a(n) is the first split point of the permutation p if p is the n-th permutation (in lexicographic order (A030298 prepended by the empty permutation)), or zero if it has no split point.

Original entry on oeis.org

0, 0, 1, 0, 1, 1, 2, 0, 0, 0, 1, 1, 1, 1, 1, 1, 2, 2, 3, 0, 0, 0, 3, 0, 3, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 2, 2, 2, 2, 2, 2, 3, 3, 4, 0, 0, 0, 4, 0, 4, 0, 0, 0, 0, 0, 0, 0, 0, 0, 3, 3, 4, 0, 0

Offset: 0

Peter Luschny, Aug 03 2022

A permutation p in [n] (where n >= 0) is reducible if there exist an i in 1..n-1 such that for all j in the range 1..i and all k in the range i+1..n it is true that p(j) < p(k). (Note that a range a..b includes a and b.) If such an i exists we say that i splits the permutation p at i and that i is a split point of p.
The list of permutations starts with the empty permutation (), which has no split points. The first permutation which has a split point is (1, 2).
The number of terms corresponding to the permutations of [n] which vanish is A003319(n), and the numbers of nonzero terms is A356291(n).

			Rows give the terms corresponding to the permutations of [n].
[0] [0]
[1] [0]
[2] [1, 0]
[3] [1, 1, 2, 0, 0, 0]
[4] [1, 1, 1, 1, 1, 1, 2, 2, 3, 0, 0, 0, 3, 0, 3, 0, 0, 0, 0, 0, 0, 0, 0, 0]

Cf. A003319, A356291, A059438, A030298.

def FirstSplit(p) -> int:
    n = p.size()
    for i in (1..n-1):
        ok = True
        for j in (1..i):
            if not ok: break
            for k in (i + 1..n):
                if p(j) > p(k):
                    ok = False
                    break
        if ok: return i
    return 0
def A356324_row(n): return [FirstSplit(p) for p in Permutations(n)]
for n in range(6): print(A356324_row(n))

cp's OEIS Frontend

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

A355488 Expansion of g.f. f/(1+2*f) where f is the g.f. of nonempty permutations.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Maple

Mathematica

SageMath

SageMath

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

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

A091139 Row sums of triangle A091063.

Views

Author

Keywords

Comments

Crossrefs

Formula

A356324 a(n) is the first split point of the permutation p if p is the n-th permutation (in lexicographic order (A030298 prepended by the empty permutation)), or zero if it has no split point.

Views

Author

Keywords

Comments

Examples

Crossrefs

Programs

SageMath