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
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
KEYWORD
nonn,tabl
AUTHOR
Ken Joffaniel M Gonzales, Sep 02 2010, Sep 27 2010
STATUS
approved