This site is supported by donations to The OEIS Foundation.

User:Peter Luschny/GeneralizedBinomialCoefficients

From OeisWiki

Jump to: navigation, search

Contents

Generalized Binomial Coefficients

Our goal is to define a triangle of binomial coefficients where the swinging factorial is always the middle coefficient, and not only in the case when n is even .

To this end we define the generalized binomial coefficient for integer \scriptstyle n \geq 0, \scriptstyle m \geq 1 as

 \text{C}_{n,k}^{(m)} = 0 if \scriptstyle k < 0 or \scriptstyle k > mn, and otherwise
 \text{C}_{n,k}^{(m)}=\frac{n!}{(n-\left\lceil k/m\right\rceil)!\left\lfloor k/m\right\rfloor !} \qquad\left(0\leq k\leq mn\right) \, .

In the sequel we will look only at the case m = 2. For this case we will introduce a more persuasive notation and a different enumeration. We set


\binom{n}{k}_{2} = \text{C}_{n,\,n+k}^{(2)} \qquad \left(n\geq0,\ -n\leq k\leq n\right) \ .

This gives the following symmetric representation


\binom{n}{k}_{2} = \frac{n!}{{\Omega_{n-k}! \ \Omega_{n+k}!}} \ , \quad \text{where} \ \Omega_{x} := \frac{x - \left[{x} \ \text{odd} \right]}{2} \ .

We see that the central term of this generalization of the binomial coefficients is the swinging factorial. This means


\binom{n}{0}_{2}= n \wr \, .

We see directly that


\binom{n}{n}_{2} = 1, \ \binom{n}{n-1}_{2} = n .

Also the symmetry relation is clear


\binom{n}{k}_{2}= \binom{n}{-k}_{2} \quad \left(0\leq k\leq n\right) \ .


If we set \scriptstyle \binom{n}{n}_{2}=\binom{n}{-n}_{2}=1 and \scriptstyle \binom{n}{n-1}_{2} = \binom{n}{1-n}_{2} = n, then the generalized binomial coefficients can be computed for \scriptstyle n \geq 2 and \scriptstyle -n+2 \leq k \leq n-2 by the recurrence



\binom{n}{k}_{2} = \binom{n-1}{k-1}_{2}+ \left[{n-k} \ \text{odd} \right] \binom{n-1}{k}_{2}+\binom{n-1}{k+1}_{2} \ .


To show this we introduce the abbreviation


s_{n,k} = \Omega_{n-k}! \ \Omega_{n+k}! \ .

Now the recurrence equation can be written


\frac{n!}{s_{n,k}}=\frac{(n-1)!}{s_{n-1,k-1}} + \left[{n-k} \ \text{odd} \right] \frac{(n-1)!}{s_{n-1,k}}+\frac{(n-1)!}{s_{n-1,k+1}}\ .

If \scriptstyle n \geq 2 and \scriptstyle -n+2 \leq k \leq n-2 this is equivalent to


\frac{n!}{\left(n-1\right)!} = \frac{s_{n,k}}{s_{n-1,k-1}}+\left[{n-k} \ \text{odd} \right] \frac{s_{n,k}}{s_{n-1,k}}+\frac{s_{n,k}}{s_{n-1,k+1}} \ .

The left hand side of the equation is n, and the right hand side also, because

 \frac{s_{n,k}}{s_{n-1,k-1}}  =\frac n2+\frac k2- \frac12 \left[{n-k} \ \text{odd} \right] \ ,
 \left[{n-k} \ \text{odd} \right] \frac{s_{n,k}}{s_{n-1,k}}  = \left[{n-k} \ \text{odd} \right] \ ,
 \frac{s_{n,k}}{s_{n-1,k+1}} = \frac n2-\frac k2- \frac12 \left[{n-k} \ \text{odd} \right] . \quad \diamond

Looking at table 1 below we see the classical binomial triangle embedded: the pictorial representation of Pascal's triangle \scriptstyle \binom nk originates from \scriptstyle \binom nk_{2} by deleting those entries, where n and k have a different parity. On formal ground we have


\binom{n}{k} = \binom{n}{2k-n}_{2} \qquad \left(0 \leq k \leq n \right) \ .

Appendix

Tabel 1. \ \binom{n}{k}_{2} \
n \ k -6 -5 -4 -3 -2 -1 0 1 2 3 4 5 6
0             1            
1           1 1 1          
2         1 2 2 2 1        
3       1 3 3 6 3 3 1      
4     1 4 4 12 6 12 4 4 1    
5   1 5 5 20 10 30 10 20 5 5 1  
6 1 6 6 30 15 60 20 60 15 30  6  6  1
Table 2.  \Omega_{n-k}! \ \Omega_{n+k}! = \ n! \ / \ \binom{n}{k}_{2}
n \ k -6 -5 -4 -3 -2 -1 0 1 2 3 4 5 6
0             1            
1           1 1 1          
2         2 1 1 1 2        
3       6 2 2 1 2 2 6      
4     24 6 6 2 4 2 6 6 24    
5   120 24 24 6 12 4 12 6 24 24 120  
6 720 120 120 24 48 12 36 12 48 24 120 120 720

Sequences

OEIS
A162246 \ \text{C}_{n,k}^{(2)} \
A056040  {n} \wr
A098361 n! (n-k)! \quad
A180274  \Omega_{n-k}! \ \Omega_{n+k}!
A180064 n! \ / {n} \wr


Maple

C := proc(m,n,k)
if k < 0 or k > m*n then 0 else
n!/(floor(k/m)!*(n-ceil(k/m))!) fi end:
C2 := proc(n,k) C(2,n,n+k) end;
Omega := proc(n) (n-(n mod 2))/2 end: 
C2o := proc(n,k) n!/(Omega(n-k)!*Omega(n+k)!) end:
Personal tools