A180401 Stirling-like sequence obtained from bipartite 0-1 tableaux.

1, 0, 1, 0, 1, 1, 0, 4, 4, 1, 0, 36, 33, 10, 1, 0, 576, 480, 148, 20, 1, 0, 14400, 10960, 3281, 483, 35, 1, 0, 518400, 362880, 103824, 15552, 1288, 56, 1, 0, 25401600, 16465680, 4479336, 663633, 57916, 2982, 84, 1, 0, 1625702400, 981872640, 253732096, 36690816, 3252624, 181312, 6216, 120, 1

Offset

1,8

Comments

Gives the number of ways to construct pairs of permutations of an n-element set into k cycles such that the sum of the minima of the i-th cycle of the first permutation and the (k-i+1)-th cycle of the second permutation is n+1.

Links

Table of n, a(n) for n=1..55.

K. J. M. Gonzales, Enumeration of Restricted Permutation Pairs and Partitions Pairs via 0-1 Tableaux, arXiv:1008.4192 [math.CO], 2010-2014.

A. de Medicis and P. Leroux, Generalized Stirling Numbers, Convolution Formulae and p,q-Analogues, Can. J. Math. 47 (1995), 474-499.

Formula

G.f.: sum_{all r=>0} C(n,k) x^r = prod_{all v+w=n,0<=v,w<=n-1} (x+vw)

Symm. f: C(n,k)=sum_{all 0 <=i_1<i_2<...<i_{n-k}<=n-1}

(i_1*(n-1)-i_1)*(i_2*(n-1)-i_2)*...*(i_{n-k}*(n-1)-i_{n-k})

Recurrences: Let C(n,k;r)=sum_{all 0 <=i_1<i_2<...<i_{n-k}<=n-1}

(i_1*(r+(n-1)-i_1))*(i_2*(r+(n-1)-i_2))*...*(i_{n-k}*(r+(n-1)-i_{n-k})). Then,

C(n,k)=C(n-1,k-1,1)+(n)C(n-1,k,1)

Example

For n=6, C(6,0)=0, C(6,1)=0, C(6,2)=1, C(6,3)=32, C(6,4)=67, C(6,5)=20, C(6,6)=1

Prog

(R) ## Runs on R 2.7.1
## Here, beta=r in recurrences
cnk<-function(n, k, beta=0){
alpha=0
as<-function(j){j}
bs<-function(j){j}
form.seq<-function(n, fcn){ss<-NULL; for(i in 0:n){ss<-c(ss, fcn(i))}; ss}
seq.a<-form.seq(n+alpha+1, as)
seq.b<-form.seq(n+beta+1, bs)
v<-function(i){i}
w<-function(i){i}
if(n>k){
Atab<-combn(1:n-1, n-k)
Btab<-n-1-Atab+beta
Atab<-Atab+alpha
px<-NULL
for(i in 1:ncol(Atab)){
partial<-NULL
for(j in 1:nrow(Atab)){
partial<-c(partial, (v(seq.a[Atab[j, i]+1])*w(seq.b[Btab[j, i]+1])))
} # for(j in 1:nrow(Atab))
px<-c(px, prod(partial))
}# for(i in 1:ncol(Atab))
} # if(n>k)
if(n>k) x<-sum(px)
if(n==k) x=1
if(n<k) x=0
x
}
# Example
cnk(7, 4)

Crossrefs

Cf. A000292, A080251.

Sequence in context: A163353 A164612 A309748 * A354043 A057270 A057278

Adjacent sequences: A180398 A180399 A180400 * A180402 A180403 A180404

Keyword

nonn,tabl

Author

Ken Joffaniel M Gonzales, Sep 02 2010, Sep 27 2010

Status

approved