login

Year-end appeal: Please make a donation to the OEIS Foundation to support ongoing development and maintenance of the OEIS. We are now in our 61st year, we have over 378,000 sequences, and we’ve reached 11,000 citations (which often say “discovered thanks to the OEIS”).

A023998
Number of block permutations on an n-set which are uniform, i.e., corresponding blocks have same size.
29
1, 1, 3, 16, 131, 1496, 22482, 426833, 9934563, 277006192, 9085194458, 345322038293, 15024619744202, 740552967629021, 40984758230303149, 2527342803112928081, 172490568947825135203, 12952575262915522547136, 1064521056888312620947794, 95305764621957309071404877
OFFSET
0,3
COMMENTS
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
LINKS
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.
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(x*(J(z)-1) = Sum_{n>=0} a(n)*z^n/n!^2 = 1 + z + 3*z^2/2!^2 + 36*z^3/3!^2 + .... - Peter Bala, Jul 11 2011
EXAMPLE
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 + ...
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 *)
PROG
(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 */
(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
CROSSREFS
Cf. A132813.
Column k=2 of A275043.
Main diagonal of A321296 and of A322670.
Sequence in context: A121673 A273997 A051921 * A241464 A341852 A141628
KEYWORD
nonn,nice
AUTHOR
Des FitzGerald (D.FitzGerald(AT)utas.edu.au)
EXTENSIONS
More terms from Vladeta Jovovic, Sep 03 2002
STATUS
approved