login
The OEIS is supported by the many generous donors to the OEIS Foundation.

 

Logo
Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
A023998 Number of block permutations on an n-set which are uniform, i.e., corresponding blocks have same size. 27
1, 1, 3, 16, 131, 1496, 22482, 426833, 9934563, 277006192, 9085194458, 345322038293, 15024619744202, 740552967629021, 40984758230303149, 2527342803112928081, 172490568947825135203, 12952575262915522547136, 1064521056888312620947794, 95305764621957309071404877 (list; graph; refs; listen; history; text; internal format)
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

Reinhard Zumkeller, Table of n, a(n) for n = 0..300

M. Aguiar, 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, R. Maurice, Combinatorial Hopf algebra structure on packed square matrices, arXiv preprint arXiv:1306.6605 [math.CO], 2013.

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.

González-Torres, Raúl E. A geometric study of cores of idempotent stochastic matrices. Linear Algebra Appl. 527, 87-127 (2017).

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. A023997, A002720, A061691.

Cf. A132813.

Column k=2 of A275043.

Main diagonal of A321296 and of A322670.

Sequence in context: A121673 A273997 A051921 * A241464 A341852 A141628

Adjacent sequences: A023995 A023996 A023997 * A023999 A024000 A024001

KEYWORD

nonn,nice

AUTHOR

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

EXTENSIONS

More terms from Vladeta Jovovic, Sep 03 2002

STATUS

approved

Lookup | Welcome | Wiki | Register | Music | Plot 2 | Demos | Index | Browse | More | WebCam
Contribute new seq. or comment | Format | Style Sheet | Transforms | Superseeker | Recents
The OEIS Community | Maintained by The OEIS Foundation Inc.

License Agreements, Terms of Use, Privacy Policy. .

Last modified January 29 15:06 EST 2023. Contains 359923 sequences. (Running on oeis4.)