A322670 -id:A322670 - cp's OEIS frontend

A023998 Number of block permutations on an n-set which are uniform, i.e., corresponding blocks have same size.

1, 1, 3, 16, 131, 1496, 22482, 426833, 9934563, 277006192, 9085194458, 345322038293, 15024619744202, 740552967629021, 40984758230303149, 2527342803112928081, 172490568947825135203, 12952575262915522547136, 1064521056888312620947794, 95305764621957309071404877

Offset: 0

Des FitzGerald (D.FitzGerald(AT)utas.edu.au)

Number of games of simple patience with n cards. Take a shuffled deck of n cards labeled 1..n; as each card is dealt it is placed either on a higher-numbered card or starts a new pile to the right. Cards are not moved once they are placed. Suggested by reading Aldous and Diaconis. - N. J. A. Sloane, Dec 19 1999

Number of set partitions of [2n] such that within each block the numbers of odd and even elements are equal. a(2) = 3: 1234, 12|34, 14|23; a(3) = 16: 123456, 1234|56, 1236|45, 1245|36, 1256|34, 12|3456, 12|34|56, 12|36|45, 1346|25, 1456|23, 14|2356, 14|23|56, 16|2345, 16|23|45, 14|25|36, 16|25|34. - Alois P. Heinz, Jul 14 2016

			For n=3 there are 25 block permutations, of which 9 of the form ({1} maps to {1,2}; {2,3} maps to {3}), are not uniform. Hence a(3) = 25 - 9 = 16.
Alternatively, for n=3 the 6 permutations of 3 cards produce 16 games, as follows: 123 -> {1,2,3}; 132 -> {1,32}, {1,3,2}; 213 -> {21,3}, {2,1,3}; 231 -> {21,3}, {2,31}, {2,3,1}; 312 -> {31,2}, {32,1}, {3,1,2}; 321 -> {321}, {32,1}, {31,2}, {3,21}, {3,2,1}.
G.f.: A(x) = 1 + x + 3*x^2/2!^2 + 16*x^3/3!^2 + 131*x^4/4!^2 + 1496*x^5/5!^2 + ...
log(A(x)) = x + x^2/2!^2 + x^3/3!^2 + x^4/4!^2 + x^5/5!^2 + ...

Reinhard Zumkeller, Table of n, a(n) for n = 0..300
M. Aguiar and R. C. Orellana, The Hopf algebra of uniform block permutations, J. Algebr. Comb. 28 (2008) 115-138
D. Aldous and P. Diaconis, Longest increasing subsequences: from patience sorting to the Baik-Deift-Johansson theorem, Bull. Amer. Math. Soc. 36 (1999), 413-432.
H. Cheballah, S. Giraudo, and R. Maurice, Combinatorial Hopf algebra structure on packed square matrices, arXiv preprint arXiv:1306.6605 [math.CO], 2013.
Fabian Faulstich, Bernd Sturmfels, and Svala Sverrisdóttir, Algebraic Varieties in Quantum Chemistry, arXiv:2308.05258 [math.AG], 2023.
D. G. FitzGerald and Jonathan Leech, Dual symmetric inverse monoids and representation theory, J. Australian Mathematical Society (Series A), Vol. 64 (1998), pp. 345-367.
Raúl E. González-Torres, A geometric study of cores of idempotent stochastic matrices, Linear Algebra Appl. 527, 87-127 (2017).
Rosa Orellana, Franco Saliola, Anne Schilling, and Mike Zabrocki, The lattice of submonoids of the uniform block permutations containing the symmetric group, arXiv:2405.09710 [math.CO], 2024. See p. 3.
Sebastian Volz, Design and Implementation of Efficient Algorithms for Operations on Partitions of Sets, Bachelor Thesis, Saarland Univ. (Germany, 2023). See p. 45.

Cf. A023997, A002720, A061691.
Cf. A132813.
Column k=2 of A275043.
Main diagonal of A321296 and of A322670.

a023998 n = a023998_list !! n
a023998_list = 1 : f 2 [1] a132813_tabl where
   f x ys (zs:zss) = y : f (x + 1) (ys ++ [y]) zss where
                     y = sum $ zipWith (*) ys zs
-- Reinhard Zumkeller, Apr 04 2014

b:= proc(n) option remember; `if`(n=0, 1,
      add(b(n-i)*binomial(n-1, i-1)/i!, i=1..n))
    end:
a:= n-> b(n)*n!:
seq(a(n), n=0..25);  # Alois P. Heinz, May 11 2016

a[0] = 1; a[n_] := a[n] = Sum[Binomial[n, k] Binomial[n-1, k] a[k], {k, 0, n-1}];
Array[a, 25, 0] (* Jean-François Alcover, Jul 28 2016 *)
nmax = 20; CoefficientList[Series[E^(-1 + BesselI[0, 2*Sqrt[x]]), {x, 0, nmax}], x]*Range[0, nmax]!^2 (* Vaclav Kotesovec, Jun 09 2019 *)

a(n)=if(n==0,1,sum(k=0,n-1,binomial(n,k)*binomial(n-1,k)*a(k))) \\ Paul D. Hanna, Aug 15 2007

{a(n)=n!^2*polcoeff(exp(sum(m=1, n, x^m/m!^2)+x*O(x^n)), n)} /* Paul D. Hanna */

N=66; x='x+O('x^N); /* that many terms */
Vec(serlaplace(serlaplace(exp(sum(n=1, N, x^n/n!^2))))) /* show terms */
/* Joerg Arndt, Jul 12 2011 */

v=vector(N); v[1]=1;
for (n=1,N-1, v[n+1]=sum(k=0,n-1, binomial(n,k)*binomial(n-1,k)*v[k+1]) );
v /* show terms */
/* Joerg Arndt, Jul 12 2011 */

a(n) = Sum_{k=0..n-1} C(n,k)*C(n-1,k)*a(k) for n>0 with a(0)=1. - Paul D. Hanna, Aug 15 2007
G.f.: Sum_{n>=0} a(n)*x^n/n!^2 = exp( Sum_{n>=1} x^n/n!^2 ). [Paul D. Hanna, Jan 04 2011; merged from duplicate entry A179119]
Row sums of A061691.
Generating function: Let J(z) = Sum_{n>=0} z^n/n!^2. Then exp(J(z)-1) = Sum_{n>=0} a(n)*z^n/n!^2 = 1 + z + 3*z^2/2!^2 + 16*z^3/3!^2 + .... - Peter Bala, Jul 11 2011

More terms from Vladeta Jovovic, Sep 03 2002

A321296 Number T(n,k) of colored set partitions of [n] where colors of the elements of subsets are in (weakly) increasing order and exactly k colors are used; triangle T(n,k), n>=0, 0<=k<=n, read by rows.

Original entry on oeis.org

1, 0, 1, 0, 2, 3, 0, 5, 20, 16, 0, 15, 122, 237, 131, 0, 52, 774, 2751, 3524, 1496, 0, 203, 5247, 30470, 68000, 65055, 22482, 0, 877, 38198, 341244, 1181900, 1913465, 1462320, 426833, 0, 4140, 298139, 3949806, 19946654, 48636035, 61692855, 39282229, 9934563

Offset: 0

Alois P. Heinz, Aug 29 2019

			T(3,2) = 20: 1a2a3b, 1a2b3b, 1a|2a3b, 1a|2b3b, 1b|2a3a, 1b|2a3b, 1a3b|2a, 1b3b|2a, 1a3a|2b, 1a3b|2b, 1a2b|3a, 1b2b|3a, 1a2a|3b, 1a2b|3b, 1a|2a|3b, 1a|2b|3a, 1b|2a|3a, 1a|2b|3b, 1b|2a|3b, 1b|2b|3a.
Triangle T(n,k) begins:
  1;
  0,   1;
  0,   2,     3;
  0,   5,    20,     16;
  0,  15,   122,    237,     131;
  0,  52,   774,   2751,    3524,    1496;
  0, 203,  5247,  30470,   68000,   65055,   22482;
  0, 877, 38198, 341244, 1181900, 1913465, 1462320, 426833;
  ...

Alois P. Heinz, Rows n = 0..140, flattened
Wikipedia, Partition of a set

Columns k=0-2 give: A000007, A000110 (for n>0), A325890.
Main diagonal gives A023998.
Row sums give A325888.
T(2n,n) gives A325889.
Cf. A322670.

A:= proc(n, k) option remember; `if`(n=0, 1, add(A(n-j, k)*
      binomial(n-1, j-1)*binomial(k+j-1, j), j=1..n))
    end:
T:= (n, k)-> add(A(n, k-i)*(-1)^i*binomial(k, i), i=0..k):
seq(seq(T(n, k), k=0..n), n=0..10);

A[n_, k_] := A[n, k] = If[n == 0, 1, Sum[A[n-j, k] Binomial[n-1, j-1]* Binomial[k + j - 1, j], {j, n}]];
T[n_, k_] := Sum[A[n, k - i] (-1)^i Binomial[k, i], {i, 0, k}];
Table[T[n, k], {n, 0, 10}, {k, 0, n}] // Flatten (* Jean-François Alcover, Apr 30 2020, after Alois P. Heinz *)

A325478 Number of colored set partitions of [n] where colors of the elements of subsets are distinct and in increasing order and all colors of an initial interval of the color palette are used.

Original entry on oeis.org

1, 1, 4, 29, 329, 5252, 110955, 2972769, 97922354, 3872594811, 180459028989, 9759149087646, 604841170643957, 42508077480226893, 3357224252026104140, 295651782273190911233, 28834727303442640011901, 3095877335697619795977036, 363977673792652615285223095

Offset: 0

Alois P. Heinz, Sep 06 2019

nonn

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

Row sums of A322670.

b:= proc(n, k) option remember; `if`(n=0, 1, add(b(n-j, k)*
      binomial(n-1, j-1)*binomial(k, j), j=1..min(k, n)))
    end:
a:= n-> add(add(b(n, k-i)*(-1)^i*binomial(k, i), i=0..k), k=0..n):
seq(a(n), n=0..23);

b[n_, k_] := b[n, k] = If[n == 0, 1, Sum[b[n - j, k] Binomial[n - 1, j - 1] Binomial[k, j], {j, 1, Min[k, n]}]];
a[n_] := Sum[Sum[b[n, k - i] (-1)^i Binomial[k, i], {i, 0, k}], {k, 0, n}];
a /@ Range[0, 23] (* Jean-François Alcover, Dec 14 2020, after Alois P. Heinz *)

A325481 Number of colored set partitions of [2n] where colors of the elements of subsets are distinct and in increasing order and exactly n colors are used.

Original entry on oeis.org

1, 1, 41, 8020, 4396189, 5226876501, 11581358373398, 43225961160925257, 252807246693691825421, 2194141947654736889023357, 27084992620572948369385642201, 459597167193175440533390098112664, 10424556988338412210154331381461375830

Offset: 0

Alois P. Heinz, Sep 06 2019

nonn

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

Cf. A322670.

b:= proc(n, k) option remember; `if`(n=0, 1, add(b(n-j, k)*
      binomial(n-1, j-1)*binomial(k, j), j=1..min(k, n)))
    end:
a:= n-> add(b(2*n, n-i)*(-1)^i*binomial(n, i), i=0..n):
seq(a(n), n=0..14);

b[n_, k_] := b[n, k] = If[n == 0, 1, Sum[b[n - j, k] Binomial[n - 1, j - 1] Binomial[k, j], {j, 1, Min[k, n]}]];
a[n_] := Sum[b[2n, n - i] (-1)^i Binomial[n, i], {i, 0, n}];
a /@ Range[0, 14] (* Jean-François Alcover, Dec 14 2020, after Alois P. Heinz *)

a(n) = A322670(2n,n).

A325482 Number of colored set partitions of [n] where colors of the elements of subsets are distinct and in increasing order and exactly two colors are used.

Original entry on oeis.org

3, 12, 41, 140, 497, 1848, 7191, 29184, 123107, 538076, 2430353, 11317644, 54229905, 266906856, 1347262319, 6965034368, 36833528195, 199037675052, 1097912385849, 6176578272780, 35409316648433, 206703355298072, 1227820993510151, 7416522514174080

Offset: 2

Alois P. Heinz, Sep 06 2019

nonn

			a(3) = 12: 1a|2a3b, 1b|2a3b, 1a3b|2a, 1a3b|2b, 1a2b|3a, 1a2b|3b, 1a|2a|3b, 1a|2b|3a, 1b|2a|3a, 1a|2b|3b, 1b|2a|3b, 1b|2b|3a.

Alois P. Heinz, Table of n, a(n) for n = 2..792

Column k=2 of A322670.

b:= proc(n, k) option remember; `if`(n=0, 1, add(b(n-j, k)*
      binomial(n-1, j-1)*binomial(k, j), j=1..min(k, n)))
    end:
a:= n-> (k-> add(b(n, k-i)*(-1)^i*binomial(k, i), i=0..k))(2):
seq(a(n), n=2..27);

b[n_, k_] := b[n, k] = If[n == 0, 1, Sum[b[n - j, k] Binomial[n - 1, j - 1] Binomial[k, j], {j, 1, Min[k, n]}]];
a[n_] := With[{k = 2}, Sum[b[n, k - i] (-1)^i Binomial[k, i], {i, 0, k}]];
a /@ Range[2, 27] (* Jean-François Alcover, Dec 14 2020, after Alois P. Heinz *)

E.g.f.: 1-2*exp(x)+exp(x*(x+4)/2).

a(n) ~ n^(n/2) * exp(-1 + 2*sqrt(n) - n/2) / sqrt(2). - Vaclav Kotesovec, Sep 18 2019

A325930 Total number of colors used in all colored set partitions of [n] where colors of the elements of subsets are distinct and in increasing order and the colors span an initial interval of the color palette.

Original entry on oeis.org

0, 1, 7, 73, 1075, 21066, 527122, 16313963, 609352653, 26938878757, 1387465470527, 82169954359252, 5534425340505464, 419977314311140561, 35617039966665620743, 3352008343756176938273, 347915661537105210844323, 39607489635223003610928042

Offset: 0

Alois P. Heinz, Sep 08 2019

nonn

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

Cf. A322670.

b:= proc(n, k) option remember; `if`(n=0, 1, add(b(n-j, k)*
      binomial(n-1, j-1)*binomial(k, j), j=1..min(k, n)))
    end:
a:= n-> add(k*add(b(n, k-i)*(-1)^i*binomial(k, i), i=0..k), k=0..n):
seq(a(n), n=0..18);

b[n_, k_] := b[n, k] = If[n == 0, 1, Sum[b[n - j, k] Binomial[n - 1, j - 1] Binomial[k, j], {j, 1, Min[k, n]}]];
a[n_] := Sum[k Sum[b[n, k-i] (-1)^i Binomial[k, i], {i, 0, k}], {k, 0, n}];
a /@ Range[0, 18] (* Jean-François Alcover, Dec 15 2020, after Alois P. Heinz *)

a(n) = Sum_{k=1..n} k * A322670(n,k).

cp's OEIS Frontend

A023998 Number of block permutations on an n-set which are uniform, i.e., corresponding blocks have same size.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Haskell

Maple

Mathematica

PARI

PARI

PARI

PARI

Formula

Extensions

A321296 Number T(n,k) of colored set partitions of [n] where colors of the elements of subsets are in (weakly) increasing order and exactly k colors are used; triangle T(n,k), n>=0, 0<=k<=n, read by rows.

Views

Author

Keywords

Examples

Links

Crossrefs

Programs

Maple

Mathematica

A325478 Number of colored set partitions of [n] where colors of the elements of subsets are distinct and in increasing order and all colors of an initial interval of the color palette are used.

Views

Author

Keywords

Links

Crossrefs

Programs

Maple

Mathematica

A325481 Number of colored set partitions of [2n] where colors of the elements of subsets are distinct and in increasing order and exactly n colors are used.

Views

Author

Keywords

Links

Crossrefs

Programs

Maple

Mathematica

Formula

A325482 Number of colored set partitions of [n] where colors of the elements of subsets are distinct and in increasing order and exactly two colors are used.

Views

Author

Keywords

Examples

Links

Crossrefs

Programs

Maple

Mathematica

Formula

A325930 Total number of colors used in all colored set partitions of [n] where colors of the elements of subsets are distinct and in increasing order and the colors span an initial interval of the color palette.

Views

Author

Keywords

Links

Crossrefs

Programs

Maple

Mathematica

Formula