Essays/Bifactorial

Definition

Bifactorial n B m or $B_{n}^{m}$ is the number of ways of picking the marked item in choice m out of n choices with n-1 alternating withdrawals of unmarked items, both without replacement, out of 2n-1 total items.

The value of $B_{n}^{m}$ is the product the mth row of a n x n triangular matrix with unit diagonal, even factorials in the lower half and odd ones in the upper, growing up and to the left from the bottom right corner. Such table describes options in the Generalized Monty Hall problem.

attachment:bitab.png

In general, the value of bifactorial m of n is given explicitly by

$B_{n}^{m}={\frac {(2(n-m)-1)!!\,(2(n-1))!!}{(2(n-m))!!}}={\frac {F_{o}(n-m)F_{e}(n-1)}{F_{e}(n-m)}},\quad 1\leq m\leq n$

By definition, using double factorial, we can write

   Fe=: 2&^ * !
   Fo=: !@+: % 2&^ * !
   Fd=: (Fe@-:)`(Fo@-:@>:)@.(2&|)"0

   (Fd@<:@+:@- * <:@[ %&(Fd@+:) -)"0/~ >:i.4
 1  0  0  0
 1  2  0  0
 3  4  8  0
15 18 24 48

Or using the expressions for even and odd factorials directly,

B=: (Fo@- * <:@[ %&Fe -)"0     NB. bifactorial: n B m

Note: as other arithmetic functions, it needs to be scalar, this is why we apply rank 0.

Monty Hall Frequencies

Generalized Monty Hall frequencies in sample spaces by total choices in rows.

   B table~ >:i.8
+-+-------------------------------------------------------+
|B|     1      2      3      4      5      6      7      8|
+-+-------------------------------------------------------+
|1|     1      0      0      0      0      0      0      0|
|2|     1      2      0      0      0      0      0      0|
|3|     3      4      8      0      0      0      0      0|
|4|    15     18     24     48      0      0      0      0|
|5|   105    120    144    192    384      0      0      0|
|6|   945   1050   1200   1440   1920   3840      0      0|
|7| 10395  11340  12600  14400  17280  23040  46080      0|
|8|135135 145530 158760 176400 201600 241920 322560 645120|
+-+-------------------------------------------------------+

Properties

The first column and the diagonal contain odd and even double factorials respectively.

(B~ -: Fe@<:) >:i.10 1	$B_{n}^{n}=F_{e}(n-1)=(2(n-1))!!$
(B&1 -: Fo@<:) >:i.10 1	$B_{n}^{1}=F_{o}(n-1)=(2(n-1)-1)!!$
((B>:)/ -: (B * +:@- % <:@+:@-)/)~ >:i.10 1	$B_{n}^{m+1}=B_{n}^{m}{\frac {2(n-m)}{2(n-m)-1}}$
((B&>:)/ -: (B * 2 * [)"0/)~ >:i.10 1	$B_{n+1}^{m+1}=B_{n}^{m}2n$
({."1@}. -: +/"1@}:) B/~ >:i.10 1	$B_{n+1}^{1}=\sum _{i=1}^{n}B_{n}^{i}$

Writen as a square array with diagonals in rows, bifactorial table has the following form

   Bd=: (Fo@[ * Fe@+ % Fe@[)&<:"0    NB. same as (<:@+ B ])"0
   Bd table~ >:i.6x                  NB. cf ([!+)"0/~i.6
+--+-------------------------------------------+
|Bd|  1     2      3       4        5         6|
+--+-------------------------------------------+
|1 |  1     2      8      48      384      3840|
|2 |  1     4     24     192     1920     23040|
|3 |  3    18    144    1440    17280    241920|
|4 | 15   120   1200   14400   201600   3225600|
|5 |105  1050  12600  176400  2822400  50803200|
|6 |945 11340 158760 2540160 45722880 914457600|
+--+-------------------------------------------+

$B_{n}^{m}$ is divisible by binomial coefficients $C_{n-1}^{m-1}$

   ((<:@+ B ])&>: % [!+)"0/~ i.6x
  1    2    8    48    384    3840
  1    2    8    48    384    3840
  3    6   24   144   1152   11520
 15   30  120   720   5760   57600
105  210  840  5040  40320  403200
945 1890 7560 45360 362880 3628800

to form the product of odd and even factorials

   (([!+)"0/~ * Fo */ Fe) i.6x
  1     2      8      48      384      3840
  1     4     24     192     1920     23040
  3    18    144    1440    17280    241920
 15   120   1200   14400   201600   3225600
105  1050  12600  176400  2822400  50803200
945 11340 158760 2540160 45722880 914457600

Thus, $B_{n+1}^{m+1}=C_{n}^{m}F_{o}(n-m)F_{e}(m)=C_{n}^{m}(2(n-m)-1)!!(2m)!!$

   (B&>:/~ -: (!~ * Fo@- * Fe@])"0/~) i.8
1

Bifactorial Sequence

Bifactorial numbers make a naturally ordered monotonous sequence, corresponding to the order of indices $(n,m),m\leq n$.

   list ;<@(B >:@i.)"0 >:i.10x
1         1         2         3         4         8         15
18        24        48        105       120       144       192
384       945       1050      1200      1440      1920      3840
10395     11340     12600     14400     17280     23040     46080
135135    145530    158760    176400    201600    241920    322560
645120    2027025   2162160   2328480   2540160   2822400   3225600
3870720   5160960   10321920  34459425  36486450  38918880  41912640
45722880  50803200  58060800  69672960  92897280  185794560

Bifactorial Distribution

Amazingly, the magnitude of each nth sample space (total by nth row) is an odd double factorial too, by value equal to the first cell of the next row.

   +/"1 B/~ >:i.7
1 3 15 105 945 10395 135135

So the probability of picking the marked item in choice m of total n choices in uniform Monty Hall sample space produces Bifactorial Distribution with density function $P(m|n)={{B_{n}^{m}} \over {B_{n+1}^{1}}},\quad m\leq n$, the corresponding Monty Hall densities.

   Pmh=: (B % >:@[ B 1:)"0   NB. probability P(m|n)
   Pmhf=: ]&.(0j3&":)@Pmh    NB. formatted
   Pmhf  table~ >:i.8
+----+-----------------------------------------------+
|Pmhf|    1     2     3     4     5     6     7     8|
+----+-----------------------------------------------+
|1   |    1     0     0     0     0     0     0     0|
|2   |0.333 0.667     0     0     0     0     0     0|
|3   |  0.2 0.267 0.533     0     0     0     0     0|
|4   |0.143 0.171 0.229 0.457     0     0     0     0|
|5   |0.111 0.127 0.152 0.203 0.406     0     0     0|
|6   |0.091 0.101 0.115 0.139 0.185 0.369     0     0|
|7   |0.077 0.084 0.093 0.107 0.128  0.17 0.341     0|
|8   |0.067 0.072 0.078 0.087 0.099 0.119 0.159 0.318|
+----+-----------------------------------------------+

In fractional form

   x:@Pmh table~ >:i.8
+------+-----------------------------------------------------------------+
|x:@Pmh|   1      2      3        4        5        6         7         8|
+------+-----------------------------------------------------------------+
|1     |   1      0      0        0        0        0         0         0|
|2     | 1r3    2r3      0        0        0        0         0         0|
|3     | 1r5   4r15   8r15        0        0        0         0         0|
|4     | 1r7   6r35   8r35    16r35        0        0         0         0|
|5     | 1r9   8r63 16r105   64r315  128r315        0         0         0|
|6     |1r11  10r99 80r693   32r231  128r693  256r693         0         0|
|7     |1r13 12r143 40r429 320r3003 128r1001 512r3003 1024r3003         0|
|8     |1r15 14r195 56r715 112r1287 128r1287 256r2145 1024r6435 2048r6435|
+------+-----------------------------------------------------------------+

Razed densities for the first n=1..20

   <@(Pmh >:@i.)"0 >:i.4
+-+-----------------+---------------------+-----------------------------------+
|1|0.333333 0.666667|0.2 0.266667 0.533333|0.142857 0.171429 0.228571 0.457143|
+-+-----------------+---------------------+-----------------------------------+
   ;<@(Pmh >:@i.)"0 >:i.4
1 0.333333 0.666667 0.2 0.266667 0.533333 0.142857 0.171429 0.228571 0.457143

   load 'plot'
   plot ;<@(Pmh >:@i.)"0 >:i.20

attachment:freqtab1.png

and the envelopes corresponding to first and last choices of the families for n=20,50,100,200.

   plot |:({.,{:)@(Pmh >:@i.)"0 >:i.20x

attachment:freqtab2.png

And the log of frequencies looks like this

   plot ^.;<@(B >:@i.)"0 >:i.10

attachment:freqtab3.png

See Also

• Double Factorial
• Generalized Monty Hall
• OEIS:A122774 Triangle of bifactorial numbers, n B m = (2(n-m)-1)!! (2(n-1))!! / (2(n-m))!!, read by rows
• OEIS:A000165 Double factorial numbers: (2n)!! = 2^n*n! (even)
• OEIS:A001147 Double factorial numbers: (2n-1)!! = 1.3.5....(2n-1) (odd)
• OEIS:A006882 Double factorials n!!: a(n)=n*a(n-2)
• OEIS:A007318 Pascal's triangle read by rows: C(n,k) = binomial(n,k) = n!/(k!*(n-k)!), 0<=k<=n
• MathWorld:DoubleFactorial, Mathworld
• MathWorld:GeometricDistribution, Mathworld
• MathWorld:BinomialDistribution, Mathworld
• Virtual Laboratories in Probability and Statistics