[seqfan] Re: "half-Stirling numbers of the first kind"

Tue Oct 2 10:38:34 CEST 2012

Dear SeqFans,

>From my previous message one can conclude that simply a permutation (k_1,...,k_n)  is suitable if and only if k_{n-1}<k_n, and it is easily proved   by induction. 
   Now the half-permanent  is a tool to enumerate the permutations with a constraint on the relative position of two last symbols (with the pattern ... n-1 ... n ....) and with an arbitrary set B of inhibited positions. Indeed, consider (0,1)-matrix A with zeros on the set B. Then hperm(A) equals the number of the considered permutations, and the definition of hperm(A) is an algorithm
of their enumeration. If we need  to enumerate the permutations with a constraint on the relative position of THREE last symbols (with the pattern ...n-2... n-1 ... n ....) and with an arbitrary set B of inhibited positions,
then, in a similar way, we can introduce for n>=3 "(1/6)-permanent" with the initial value for 3x3 square matrix a=(a_{11},a{12},...,a_{33}) :
(1/6)-perm(a)=a_{11}*a{22}*a_{33}, etc. Thus, for a given constraint, we can introduce the corresponding "fractional permanent". As for the permanent, it is interesting to research the questions connected with the upper and lower estimates of it (not necessarily for (0,1)-matrices).
In the conclusion,  an interesting question arises. As very well known, the determinant possesses much more simple calculating properties than the permanent. What can we say about a pair "fractional permanent-fractional determinant" ( for example, the "row-definition" of half-determinant includes the alternation of signs)? I am not an optimist in that, but this question is rather natural.

Regards,
Vladimir

----- Original Message -----
From: Vladimir Shevelev <shevelev at bgu.ac.il>
Date: Monday, October 1, 2012 1:34
Subject: [seqfan] Re: "half-Stirling numbers of the first kind"
To: Sequence Fanatics Discussion list <seqfan at list.seqfan.eu>

> Dear SeqFans,
> 
> It appears that the problem 3) has a simple solution. Consider a 
> permutation 
>  (k_1,...,k_n) of numbers (1,...,n). A test when it is a 
> permutation 
>  of  the second indices in summands of hperm of square 
> matrix A={a_(i,j)} of order n (let us call such a permutation a 
> suitable one) is the following.
> We distinguish two cases. 1) Both k_{n-1} and k_n differ from 1 
> and n. Then the permutation is suitable iff k_{n-
> 1}<k_n;  
>  2) Otherwise, the permutation is suitable iff  k_{n-
> 1}=1 or (and) k_n=n.
> 
> Regards,
> Vladimir
> 
> 
> 
> ----- Original Message -----
> From: Vladimir Shevelev <shevelev at bgu.ac.il>
> Date: Tuesday, September 25, 2012 4:31
> Subject: [seqfan] Re: "half-Stirling numbers of the first kind"
> To: Sequence Fanatics Discussion list <seqfan at list.seqfan.eu>
> 
> > Dear Olivier,
> > 
> > You are right, they are equivalent problems, and your 
> > calculation is excellent. However, concretely in this problem, 
> I 
> > am not able to describe this constraint on the  relative 
> > position of two first symbols, such that the problem 3) 
> remains open.
> > 
> > Best regards,
> > Vladimir
> > 
> > ----- Original Message -----
> > From: Olivier Gerard <olivier.gerard at gmail.com>
> > Date: Tuesday, September 25, 2012 2:22
> > Subject: [seqfan] Re: "half-Stirling numbers of the first kind"
> > To: Sequence Fanatics Discussion list <seqfan at list.seqfan.eu>
> > 
> > > Dear Vladimir,
> > > 
> > > If I understand your idea correctly, this is equivalent to 
> the 
> > > followingproblem:
> > > 
> > > Counting permutations by cycles with a constraint on the 
> > > relative position
> > > of two first symbols (as
> > > you are starting from a 2x2 matrix). Permutations with the 
> > > pattern ... 1
> > > ... 2 .... are easy to compute.
> > > 
> > > This gives the following triangle:
> > > 
> > > 0 | 0
> > > 
> > > 1 | 0 1
> > > 
> > > 3 | 1 1 1
> > > 
> > > 12 | 3 5 3 1
> > > 
> > > 60 | 12 24 17 6 1
> > > 
> > > 360 | 60 134 110 45 10 1
> > > 
> > > 2520 | 360 870 799 375 100 15 1
> > > 
> > > 20160 | 2520 6474 6489 3409 1050 196 21 1
> > > 
> > > 
> > > It is not currently in the OEIS. If you agree, I propose to 
> > > enter it in the
> > > Encyclopedia with reference to this mail.
> > > 
> > > 
> > > With my best regards,
> > > 
> > > 
> > > Olivier GERARD
> > > 
> > > 
> > > 
> > > On Tue, Sep 25, 2012 at 2:42 PM, Vladimir Shevelev 
> > > <shevelev at bgu.ac.il>wrote:
> > > > Dear SeqFans,
> > > >
> > > > Let us define recursively half-permanent (hperm) of a 
> square 
> > > nxn (n>=2)
> > > > matrix. For 2x2 matrix A with usual 2-index numeration 
> > > elements, we put
> > > >  hperm(A)=a_{11}*a_{22}. For 3x3 matrix, by the 
> > expansion 
> > > over its first
> > > > row (without alternating signs),  and using the 
> > > definition of
> > > > half-permanent for 2x2 matrices, we define
> > > >  
> > > 
> > 
> hperm(A)=a_{11}*a_{22}*a_{33}+a_{12}*a_{21}*a_{33}+a_{13}*a_{21}*a_{32}.> In the same way, using the definition of half-permanent for 3x3 matrices,
> > > > we define hperm(A) for 4x4 matrix, etc.
> > > > Consider permutations of (1,2), (1,2,3), (1,2,3,4), etc. 
> > given 
> > > by the
> > > > second indices in summands.  In case n=2, we have 
> only 
> > > permutation (1,2)
> > > > with two cycles; in case
> > > > n=3, we have 3 permutations (1,2,3),(2,1,3),(3,1,2) with 
> > 3,2,1 
> > > cycles> respectively; in case n=4 we have 12 permutations: 
> one 
> > > with 4 cycles, 3
> > > > with 3 cycles, 5 with 2 cycles and 3 with one cycle. Thus 
> we 
> > > obtain the
> > > > triangle (number of permutations of n elements over number 
> > of 
> > > cycles:> 1,2,3,...)
> > > > (1)
> > > > 0 1
> > > > 1 1 1
> > > > 3 5 3 1
> > > > ....
> > > > with row sums n!/2, n>=2.
> > > > It is natural to call these numbers "half-Stirling of the 
> > > first kind".
> > > > Problems: 1) To coninue the triangle; 2) To find a GF for 
> > half-
> > > Stirling> numbers of the first kind; 3) Consider a 
> permutation 
> > > (k_1,...,k_n) of
> > > > numbers (1,...,n). To find a test when it is a permutation 
> > of 
> > > the second
> > > > indices in summands of hperm of square matrix A={a_(i,j)} 
> of 
> > > order n.
> > > >
> > > > Regards,
> > > > Vladimir
> > > >
> > > >
> > > >  Shevelev Vladimir‎
> > > >
> > > > _______________________________________________
> > > >
> > > > Seqfan Mailing list - http://list.seqfan.eu/
> > > >
> > > 
> > > _______________________________________________
> > > 
> > > Seqfan Mailing list - http://list.seqfan.eu/
> > > 
> > 
> >  Shevelev Vladimir‎
> > 
> > _______________________________________________
> > 
> > Seqfan Mailing list - http://list.seqfan.eu/
> > 
> 
>  Shevelev Vladimir‎
> 
> _______________________________________________
> 
> Seqfan Mailing list - http://list.seqfan.eu/
> 

 Shevelev Vladimir‎