A180401 - OEIS

%I #19 Jan 08 2025 10:39:13

%S 1,0,1,0,1,1,0,4,4,1,0,36,33,10,1,0,576,480,148,20,1,0,14400,10960,

%T 3281,483,35,1,0,518400,362880,103824,15552,1288,56,1,0,25401600,

%U 16465680,4479336,663633,57916,2982,84,1,0,1625702400,981872640,253732096,36690816,3252624,181312,6216,120,1

%N Stirling-like sequence obtained from bipartite 0-1 tableaux.

%C 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.

%H K. J. M. Gonzales, <a href="https://arxiv.org/abs/1008.4192">Enumeration of Restricted Permutation Pairs and Partitions Pairs via 0-1 Tableaux</a>, arXiv:1008.4192 [math.CO], 2010-2014.

%H A. de Medicis and P. Leroux, <a href="https://doi.org/10.4153/CJM-1995-027-x">Generalized Stirling Numbers, Convolution Formulae and p,q-Analogues</a>, Can. J. Math. 47 (1995), 474-499.

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

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

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

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

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

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

%e 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

%o (R) ## Runs on R 2.7.1

%o ## Here, beta=r in recurrences

%o cnk<-function(n,k,beta=0){

%o alpha=0

%o as<-function(j){j}

%o bs<-function(j){j}

%o form.seq<-function(n,fcn){ss<-NULL;for(i in 0:n){ss<-c(ss,fcn(i))};ss}

%o seq.a<-form.seq(n+alpha+1,as)

%o seq.b<-form.seq(n+beta+1,bs)

%o v<-function(i){i}

%o w<-function(i){i}

%o if(n>k){

%o Atab<-combn(1:n-1,n-k)

%o Btab<-n-1-Atab+beta

%o Atab<-Atab+alpha

%o px<-NULL

%o for(i in 1:ncol(Atab)){

%o partial<-NULL

%o for(j in 1:nrow(Atab)){

%o partial<-c(partial,(v(seq.a[Atab[j,i]+1])*w(seq.b[Btab[j,i]+1])))

%o } # for(j in 1:nrow(Atab))

%o px<-c(px,prod(partial))

%o }# for(i in 1:ncol(Atab))

%o } # if(n>k)

%o if(n>k) x<-sum(px)

%o if(n==k) x=1

%o if(n<k) x=0

%o x

%o }

%o # Example

%o cnk(7,4)

%Y Cf. A000292, A080251.

%K nonn,tabl

%O 1,8

%A _Ken Joffaniel M Gonzales_, Sep 02 2010, Sep 27 2010