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
Examples
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 + ...
Links
- 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.
Crossrefs
Programs
-
Haskell
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 -
Maple
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 -
Mathematica
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 *) -
PARI
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
-
PARI
{a(n)=n!^2*polcoeff(exp(sum(m=1, n, x^m/m!^2)+x*O(x^n)), n)} /* Paul D. Hanna */ -
PARI
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 */ -
PARI
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 */
Formula
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
Extensions
More terms from Vladeta Jovovic, Sep 03 2002
Comments