A023998
Number of block permutations on an n-set which are uniform, i.e., corresponding blocks have same size.
Original entry on oeis.org
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)
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.
-
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 */
A192721
The number of pairs of permutations in the product group S_n X S_n with k common descents, n >= 1 and 0 <= k <= n-1.
Original entry on oeis.org
1, 3, 1, 19, 16, 1, 211, 299, 65, 1, 3651, 7346, 3156, 246, 1, 90921, 237517, 160322, 28722, 917, 1, 3081513, 9903776, 9302567, 2864912, 245407, 3424, 1, 136407699, 520507423, 632274183, 288196659, 46261609, 2041965, 12861, 1
Offset: 1
The triangle begins
n/k|.....0.......1.......2......3....4.....5
============================================
..1|.....1
..2|.....3.......1
..3|....19......16.......1
..4|...211.....299......65......1
..5|..3651....7346....3156....246....1
..6|.90921..237517..160322..28722..917.....1
..
Row 3 entries T(3,0) = 19, T(3,1) = 16 and T(3,2) = 1 can be read from the following table:
============================================
Number of common descents in S_3 x S_3
============================================
.
...|.123...132...213...231...312...321
======================================
123|..0.....0.....0.....0.....0.....0
132|..0.....1.....0.....1.....0.....1
213|..0.....0.....1.....0.....1.....1
231|..0.....1.....0.....1.....0.....1
312|..0.....0.....1.....0.....1.....1
321|..0.....1.....1.....1.....1.....2
Matrix identity A192721 * A007318 = row reverse of A192722:
/...1................\ /..1..............\
|...3.....1...........||..1....1..........|
|..19....16.....1.....||..1....2....1.....|
|.211...299....65....1||..1....3....3....1|
|.....................||..................|
=
/...1...................\
|...4......1.............|
|..36.....18......1......|
|.576....432.....68.....1|
|........................|
- Alois P. Heinz, Rows n = 1..45, flattened
- L. Carlitz, R. Scoville and T. Vaughan, Enumeration of pairs of permutations and sequences, Bull. Amer. Math. Soc., 80 (1974), 881-884.
- L. Carlitz, R. Scoville, T. Vaughan, Enumeration of pairs of permutations, Discrete Math. 14, (1976) 215-239.
- J-Marc Fedou and D. Rawlings, More statistics on permutation pairs, The Electronic Journal of Combinatorics, 1 (1994) #R11.
- M. V. Koutras, Eulerian numbers associated with sequences of polynomials, Fibonacci Quart. 32 (1994) 44-57.
- T. Mendes, J. Remmel, A. Riehl, A Generalization of the Generating Functions for Descent Statistic.
- R. P. Stanley, Binomial posets, Möbius inversion and permutation enumeration, J. Combinat. Theory, A 20 (1976), 336-356.
-
#A192721
#J = sum {n>=0} z^n/n!^2
J := unapply(BesselJ(0, 2*I*sqrt(z)),z):
G := (1-x)/(-x + J(z*(x-1))):
Gser := simplify(series(G, z = 0, 12)):
for n from 1 to 10 do
P[n] := n!^2*sort(coeff(Gser, z, n)) od:
for n from 1 to 10 do seq(coeff(P[n],x,k), k = 0..n-1) od;
# gives sequence in triangular form
-
max = 9; j[z_] := BesselJ[0, 2 I*Sqrt[z]]; g = (1 - x)/(-x + j[z*(x - 1)]); gser = Series[g, {z, 0, max}]; p[n_] := n!^2 Coefficient[ gser, z, n]; a[n_, k_] := Coefficient[ p[n], x, k]; Flatten[ Table[ a[n, k], {n, 1, max-1}, {k, 0, n-1}]] (* Jean-François Alcover, Dec 13 2011, after Maple *)
A061692
Triangle of generalized Stirling numbers.
Original entry on oeis.org
1, 1, 4, 1, 27, 36, 1, 172, 864, 576, 1, 1125, 17500, 36000, 14400, 1, 7591, 351000, 1746000, 1944000, 518400, 1, 52479, 7197169, 80262000, 191394000, 133358400, 25401600, 1, 369580, 151633440, 3691514176, 17188416000, 23866214400, 11379916800, 1625702400
Offset: 1
1; 1,4; 1,27,36; 1,172,864,576; ...
-
b:= proc(n) option remember; expand(
`if`(n=0, 1, add(x*b(n-i)/i!^3, i=1..n)))
end:
T:= n-> (p-> seq(coeff(p, x, i)/i!, i=1..n))(b(n)*n!^3):
seq(T(n), n=1..10); # Alois P. Heinz, Sep 10 2019
-
R[0, ] = 1; R[n, x_] := R[n, x] = x*Sum[Binomial[n, k]^2*Binomial[n-1, k]*R[k, x], {k, 0, n-1}]; Table[CoefficientList[R[n, x], x] // Rest, {n, 1, 8}] // Flatten (* Jean-François Alcover, Sep 01 2015, after Peter Bala *)
A192722
T(n,k) = Sum of multinomial(n; n_1,n_2,...,n_k)^2, where the sum extends over all compositions (n_1,n_2,...,n_k) of n into exactly k nonnegative parts.
Original entry on oeis.org
1, 1, 4, 1, 18, 36, 1, 68, 432, 576, 1, 250, 3900, 14400, 14400, 1, 922, 32400, 252000, 648000, 518400, 1, 3430, 262542, 3880800, 19404000, 38102400, 25401600, 1, 12868, 2119152, 56664384, 493920000, 1795046400, 2844979200, 1625702400
Offset: 1
The triangle begins
n/k|..1.....2.......3........4........5........6
================================================
.1.|..1
.2.|..1.....4
.3.|..1....18.....36
.4.|..1....68.....432......576
.5.|..1...250....3900....14400....14400
.6.|..1...922...32400...252000...648000...518400
...
T(4,2) = 68:
There are 3 compositions of 4 into 2 parts, namely, 4 = 2 + 2 = 1 + 3 = 3 + 1; hence
T(4,2) = (4!/(2!*2!))^2 + (4!/(1!*3!))^2 + (4!/(3!*1!))^2
= 36 + 16 + 16 = 68.
Matrix identity: A192721 * Pascal's triangle = row reverse of A192722:
/...1................\ /..1..............\
|...3.....1...........||..1....1..........|
|..19....16.....5.....||..1....2....1.....|
|.211...299....65....1||..1....3....3....1|
|.....................||..................|
=
/...1...................\
|...4......1.............|
|..36.....18......1......|
|.576....432.....68.....1|
|........................|
-
J := unapply(BesselJ(0, 2*sqrt(-1)*sqrt(z)), z):
G := 1/(1-x*(J(z)-1)):
Gser := simplify(series(G, z = 0, 15)):
for n from 1 to 14 do
P[n] := n!^2*sort(coeff(Gser, z, n)) od:
for n from 1 to 14 do seq(coeff(P[n], x, k), k = 1..n) od;
# yields sequence in triangular form
# second Maple program:
b:= proc(n) option remember; expand(
`if`(n=0, 1, add(x*b(n-i)/i!^2, i=1..n)))
end:
T:= n-> (p-> seq(coeff(p, x, i), i=1..n))(b(n)*n!^2):
seq(T(n), n=1..14); # Alois P. Heinz, Sep 10 2019
-
b[n_] := b[n] = Expand[If[n == 0, 1, Sum[x b[n-i]/i!^2, {i, 1, n}]]];
T[n_] := Function[p, Table[Coefficient[p, x, i], {i, 1, n}]][b[n] n!^2];
Table[T[n], {n, 1, 14}] // Flatten (* Jean-François Alcover, Dec 07 2019, after Alois P. Heinz *)
A343254
Triangle read by rows: T(n,k) is the number of 2-balanced partitions of a set of n elements in which the first and the second subsets have cardinality k, for n >= 0, k = 0..floor(n/2).
Original entry on oeis.org
1, 1, 2, 1, 5, 2, 15, 5, 3, 52, 15, 8, 203, 52, 25, 16, 877, 203, 89, 53, 4140, 877, 354, 197, 131, 21147, 4140, 1551, 810, 512, 115975, 21147, 7403, 3643, 2193, 1496, 678570, 115975, 38154, 17759, 10201, 6697, 4213597, 678570, 210803, 93130, 51146, 32345, 22482
Offset: 0
T(4,1) = 5, number of 2-balanced partitions of a set A of 4 elements with 1 element in the first subset and 1 element in the second subset: A={a} U {b} U {c,d}. The five partitions are: ((a,b),(c),(d)), ((a,b),(c,d)), ((a,b,c),(d)), ((a,b,d),(c)), ((a,b,c,d)). Note that if a block contains a, then it must contain b. Thus, T(n,1) = T(n-1,0).
Triangle T(n,k) begins:
1;
1;
2, 1;
5, 2;
15, 5, 3;
52, 15, 8;
203, 52, 25, 16;
877, 203, 89, 53;
4140, 877, 354, 197, 131;
21147, 4140, 1551, 810, 512;
115975, 21147, 7403, 3643, 2193, 1496;
678570, 115975, 38154, 17759, 10201, 6697;
4213597, 678570, 210803, 93130, 51146, 32345, 22482;
...
- Alois P. Heinz, Rows n = 0..200, flattened
- Francesca Aicardi, Balanced partitions, preprint on researchgate, 2021.
- Francesca Aicardi, Diego Arcis, and Jesús Juyumaya, Brauer and Jones tied monoids, arXiv:2107.04170 [math.RT], 2021.
A061689
Generalized Stirling numbers.
Original entry on oeis.org
1, 34, 650, 10500, 161700, 2493120, 39372480, 644112000, 10977120000, 195392736000, 3636061228800, 70737918451200, 1437896940480000, 30512401920000000, 675213301002240000, 15564170478624768000, 373267990604500992000, 9302809053765427200000
Offset: 1
A061690
Generalized Stirling numbers.
Original entry on oeis.org
0, 0, 6, 72, 650, 5400, 43757, 353192, 2862330, 23352300, 191891117, 1587587760, 13215894133, 110619113423, 930376519256, 7858437064232, 66627124896218, 566791391339532, 4836144006188165, 41375938305568772, 354859541163656045
Offset: 1
Showing 1-7 of 7 results.
Comments