KEYWORDS:  Variations, Arrangements, Permutations, 
Hasse Diagram, Boolean Algebra, Factorial Function,
Double Factorial, Combinatorial Schemes, OEIS

A Generalization of the
Factorial Function related to
Variations(A007526 -> A128195) and
Arrangements(A000522 -> A128196).

A Scheme of Variations

According to Donald E. Knuth eighteenth and nineteenth century 
combinatorialists call the number of permutations of nonempty subsets 
of {1,...,n} `variations´ of n distinct objects. In this sense we use 
this term here. 
 
Our starting point is the following simple scheme, which creates
variants of variations. It was discussed, probably for the first time,
on de.sci.mathematik on 7 Jun. 2003 (thread `Variatio delectat´).

    v(x) = if x <= 1 then x else x+v(x-1)*x
    VarScheme(k,n) = k^(n+1)*v(n+1/k)

Put more succinctly [Thomas Mautsch]:
 
    VarScheme(k,n) = (n*k+1)*(VarScheme(k,n-1) + k^n),
    VarScheme(k,0) = 1.

      n >= 0 ->
[k=0] 1,  1,   1,     1,      1,      1,          1,          1,            1
[k=1] 1,  4,  15,    64,    325,    1956,     13699,     109600,       986409
[k=2] 1,  9,  65,   511,   4743,   52525,    683657,   10256775,    174369527
[k=3] 1, 16, 175,  2020,  27313,  440896,   8390875,  184647364,   4616348125
[k=4] 1, 25, 369,  5629, 100045, 2122449,  53163625, 1542220261,  50895431301
[k=5] 1, 36, 671, 12736, 280581, 7376356, 229151411, 8252263296, 338358810761

The starting observation is that the second row (k=1) is a classical sequence
counting the variations of n distinct objects. Our aim is to study the third
row (k=2), which we call 'double variations' to relate them to the 'double 
factorials' or 'variations on half' because the half integral values n+1/2 
play a central role in this sequence.

However, also note the columns. VarScheme(k, 1) are the squares. 
Also the numbers VarScheme(k, 2) are well known: They are the 'rhombic 
dodecahedral numbers' n^4 - (n-1)^4, listed on OEIS as sequence A005917.

We also see, as commented by Thomas Mautsch, that the n-th column of 
VarScheme(k,n) is a polynomial in k, divisible by (n*k+1). 

                                                (k >= 0)  
 VarScheme(k,0) = (0*k+1)*(0*k^0+1)           = 1, 1, 1, 1,..
 VarScheme(k,1) = (1*k+1)*(1*k^1+1)           = 1, 4, 9, 16,..
 VarScheme(k,2) = (2*k+1)*(2*k^2+2*k+1)       = 1, 15, 65, 175,..
 VarScheme(k,3) = (3*k+1)*(5*k^3+6*k^2+4*k+1) = 1, 64, 511, 2020,..

OEIS-id: A007526    [Excerpt]

( 1) Name: Variations of n distinct objects
( 2) Values (n>=0): 0, 1, 4, 15, 64, 325, 1956, 13699, 109600, 986409,..
( 3) ClosedForm: a(n) = Sum(k=0..n, n!/k!) - 1;
( 4) RecursiveForm: a(n) = n(a(n-1)+1), a(0)=0.
( 5) GeneralizedForm: For x > 0  
     a(x) = exp(1)*Integral_{t=0..inf} exp(-exp(t/x)+t) dt
( 6) Comment: a(n) = floor(e*n! - 1)
( 7) egf(x) = x*exp(x)/(1-x)
( 8) IsSpecialCaseOf: a(n) = VarScheme(1,n) 
( 9) Combinatorial interpretation:
     The number of permutations of nonempty subsets of {1,...,n}.
     The number of non-empty sequences with n or fewer terms,
     each a distinct element of {1,...,n}.
     for example n=3: 1,2,3,12,21,13,31,23,32,123,132,231,213,312,321

OEIS-id: A128195

( 1) Name: Variations on half 
( 2) Values (n>=0): 1, 9, 65, 511, 4743, 52525, 683657, 10256775, 174369527,

( 3) Closed form:
     a(n) = (2n+1)!/(n! 2^n) Sum(k=0..n, 4^k*k!/(2k)!) [Gottfried Helms]
     a(n) = 2^n (2n+1) Sum(k=0..n, Gamma(n+1/2)/Gamma(k+1/2))
     a(n) = 2^(n+1) Gamma(n+3/2) Sum(k=0..n, 1/Gamma(k+1/2))
     
     a(n) = A128196(n)*A005408(n)
     a(n) = A128196(n+1)-A000079(n+1)

( 4) Recursive form: 
     a(n) = 2^(n+1)*v(n+1/2) with v(x) = if x <= 1 then x else x(v(x-1)+1).
     a(n) = (2n+1)*(a(n-1)+2^n), a(0) = 1  [Wolfgang Thumser]


  Note: The following constants will be used in the next formulas. 
  K = (1-exp(1)*Gamma(1/2,1))/Gamma(1/2)
  M = sqrt(2)(1+exp(1)(Gamma(1/2)-Gamma(1/2,1)))

( 5) Generalized form: For x>0  
     a(x) = 2^(x+1)(x+1/2)(exp(1) Gamma(x+1/2,1) + K Gamma(x+1/2))

( 6) Asymptotic formula:  
     a(n) ~ 2^(n+5/2)*Gamma(n+3/2)
     a(n) ~ (exp(1)+K)*2^(n+1)*(n+1/2)!
     a(n) ~ M(2n+1)(2exp(-1)(n-1/(24*n+19/10*1/n)))^n

( 7) Comment: a(n) and a(n+1) are relative prime.

( 8) deq of egf: w'(1-2x)-3w = (8x+6)e^(2x)  [Wolfgang Thumser]

( 9) Maple: a := n -> `if`(n=0,1,(2*n+1)*(a(n-1)+2^n)); 

(10) Combinatorial interpretation:

VarScheme(k,n) = (n*k+1)*(VarScheme(k,n-1) + k^n),
VarScheme(k,0) = 1.

k | n ->
[0]  1,  1,   1,     1,      1,       1,         1,          1,            1
[1]  1,  4,  15,    64,    325,    1956,     13699,     109600,       986409
[2]  1,  9,  65,   511,   4743,   52525,    683657,   10256775,    174369527
[3]  1, 16, 175,  2020,  27313,  440896,   8390875,  184647364,   4616348125
[4]  1, 25, 369,  5629, 100045, 2122449,  53163625, 1542220261,  50895431301
[5]  1, 36, 671, 12736, 280581, 7376356, 229151411, 8252263296, 338358810761   
     
a(n) is the third row of this scheme, a(n) = VarScheme(2,n).
The second row counts the variations of n distinct objects A007526.
The second column is sequence A000290. The third column is sequence A005917.
If this square array is scanned by antidiagonals it gives the triangle 
A126062.

OEIS-id: A128196

( 1) Name: A weighted sum of double factorials. 
( 2) Values (n>=0): 1, 3, 13, 73, 527, 4775, 52589, 683785, 10257031,...

( 3) Closed form:
     a(n) = (2n)!/(n! 2^n) Sum(k=0..n, 4^k k!/(2k)!)
     a(n) = 2^n Gamma(n+1/2) Sum(k=0..n, 1/Gamma(k+1/2))
     a(n) = Sum(k=0..n, 2^k n!!/k!!) 
            [n!! defined as A001147(n), Gottfried Helms]
     a(n) = Sum(k=0..n, 2^(2k-n)((n+1)! Catalan(n))/((k+1)! Catalan(k))) 
            [Catalan(n) A000108]
     a(n) = Sum(k=0..n, 2^(2k-n) QuadFact(n)/QuadFact(k)) 
            [QuadFact(n) A001813]
     a(n) = Sum(k=0..n, 2^(2k-n) (-1)^(n-k) A097388(n)/A097388(k) ) 

     a(n) = A001147(n) Sum(k=0..n, 2^k / A001147(k))
     a(n) = A128195(n)/A005408(n)
     a(n) = A128195(n-1)+A000079(n) (if n>0)

( 4) Recursive form: a(n) = (2n-1)*a(n-1) + 2^n; a(0) = 1 
     [Gottfried Helms]
     
  Note: The following constants will be used in the next formulas. 
  K = (1-exp(1)*Gamma(1/2,1))/Gamma(1/2)
  M = sqrt(2)(1+exp(1)(Gamma(1/2)-Gamma(1/2,1)))

( 5) Generalized form: For x>0  
     a(x) = 2^x(exp(1)*Gamma(x+1/2,1) + K*Gamma(x+1/2))

( 6) Asymptotic formula:  
     a(n) ~ 2^n*(1+(exp(1)+K)*(n-1/2)!)
     a(n) ~ M(2exp(-1)(n-1/(24*n+19/10*1/n)))^n

( 7) Comment: a(n) and a(n+1) are relative prime.

( 8) Maple: a := n -> `if`(n=0,1,(2*n-1)*a(n-1)+2^n);
( 9) Combinatorial interpretation:

     a(n) is the sum of rows in the following triangle T(n,k) (n,k>=0)
     
           1 
           1,       2
           3,       6,       4 
          15,      30,      20,       8
         105,     210,     140,      56,     16
         945,    1890,    1260,     504,    144,    32
       10395,   20790,   13860,    5544,   1584,   352,    64
      135135,  270270,  180180,   72072,  20592,  4576,   832,  128
     
      First column is A001147, second column is A097801.
      The diagonal is A000079, the sub-diagonal is A014480. 
      
      Let G be the matrix (n!! defined as A001147(n), -1!! = 1).

      (-1)!!/(-1)!!
         1!!/(-1)!!    1!!/1!!
         3!!/(-1)!!    3!!/1!!    3!!/3!!
         5!!/(-1)!!    5!!/1!!    5!!/3!!    5!!/5!!
         .....
	 	
      Let H be the diagonal matrix diag(1,2,4,8,...). 
      Then T = G*H. [Gottfried Helms]

Comment on A000522

The sequence A000522 counts the total number of arrangements of
a set with n elements.

    1, 2, 5, 16, 65, 326, 1957, 13700,... 

a(n) is the sum of rows in the following triangle A(n, k) (n,k >= 0)
[A094587, cf. also A008279 triangle of `permutation coefficients´, 
the number of permutations of n things k at a time.]

         1
         1,     1
         2,     2,     1
         6,     6,     3,    1
        24,    24,    12,    4,    1
       120,   120,    60,   20,    5,   1
       720,   720,   360,  120,   30,   6,  1
      5040,  5040,  2520,  840,  210,  42,  7, 1

Multiplying the columns by 1,2,4,8,16,... respectively we find the
following triangle B(n, k) (n, k >= 0), which is in correspondence to
the triangle T(n, k) described above (A128196). In fact the 
correspondence is nothing more than a formal substitution n! -> n!!.  

        1
        1,     2
        2,     4,     4
        6,    12,    12,     8
       24,    48,    48,    32,    16
      120,   240,   240,   160,    80,    32
      720,  1440,  1440,   960,   480,   192,   64
     5040, 10080, 10080,  6720,  3360,  1344,  448,  128

Looking at the sum of rows in this triangle we find the sequence

        1, 3, 10, 38, 168, 872, 5296, 37200, 297856,...

With the help of OEIS we can identify this sequence as A010842.
Ross La Haye describes this sequence as the total number of walks
in the Hasse diagram of a Boolean algebra of order n. And as
the binomial transform of A000522.

Moreover we are routed to the sequence A090802 by Ross La Haye 
which displays the triangle B in the form H(n, k) = B(n, n-k).  
H(n, k) are the number of k-length walks in the Hasse diagram of
a Boolean algebra of order n.


A Scheme of Arrangements

The term 'arrangement' is used here in similar sense as it is used 
when we say that the sequence A000522 counts the total number of 
arrangements of a set with n elements.
 
The following simple scheme is closely related to the scheme of 
variations and creates variants of arrangements. 

   ArrScheme(k,n) = VarScheme(k,n-1) + k^n,  ArrScheme(k,0) = 1. 
   VarScheme(k,n) = (n*k+1)*(VarScheme(k,n-1) + k^n), VarScheme(k,0) = 1.

         n >= 0 ->
   [k=0] 1, 1,   1,    1,     1,       1,        1,          1
   [k=1] 1, 2,   5,   16,    65,     326,     1957,      13700 [A000522]
   [k=2] 1, 3,  13,   73,   527,    4775,    52589,     683785 [A128196]
   [k=3] 1, 4,  25,  202,  2101,   27556,   441625,    8393062
   [k=4] 1, 5,  41,  433,  5885,  101069,  2126545,   53180009
   [k=5] 1, 6,  61,  796, 13361,  283706,  7391981,  229229536
   [k=6] 1, 7,  85, 1321, 26395,  667651, 20743837,  767801905
   [k=7] 1, 8, 113, 2038, 47237, 1386680, 50038129, 2152463090 

We observe that the second row (k=1) is the classical sequence counting
the arrangements of a set with n elements A000522 and the third row (k=2)
is the sequence A128196 which we discussed in detail above.

If we scan this square array by antidiagonals it will be written as

    1,
    1, 1,
    1, 2,  1,
    1, 3,  5,   1,
    1, 4, 13,  16,    1,
    1, 5, 25,  73,   65,    1,
    1, 6, 41, 202,  527,  326,    1,
    1, 7, 61, 433, 2101, 4775, 1957, 1,

In this form the scheme of arrangements is listed as A128198 and is
the counterpart of the scheme of variations listed as A126062.

The relations between Factorial(k,n), Variation(k,n)
and Arrangement(k,n).

The connection between a generalized factorial function and a 
generalization of the sequence of variations and the sequence of 
arrangements is the most important relation considered here. 
Let us review it in a systematic framework.

First we define the function factorial(n,k). 

    fk(k,n) = (k*n)!/((n*(k-1))!*k^n)

    f1(n)   = (1*n)!/((n*0)!*1^n)
    f2(n)   = (2*n)!/((n*1)!*2^n)

Note that f1(n) = fk(1,n) = n! and f2(n) = fk(2,n) = n!!
Here n!! denotes the sequence A001147(n>=0) = 1,1,3,15,105,945,...

Now we can state in a uniform way the result of our little 
investigation:

    var1(n) = (1*n+1)*Sum(k=0..n, 1^k*f1(n)/f1(k))
    var2(n) = (2*n+1)*Sum(k=0..n, 2^k*f2(n)/f2(k))
 
The formal correspondence of these two identities describes in
a nutshell our finding.

    sequence(var1(n)) ~ A007526 = 1,4,15,64,325,1956,...
    sequence(var2(n)) = A128195 = 1,9,65,511,4743,52525,...

Moreover, treated without the factor (k*n+1) we find a generalization
of the number of arrangements of a set with n elements.

    arr1(n) = Sum(k=0..n, 1^k*f1(n)/f1(k))
    arr2(n) = Sum(k=0..n, 2^k*f2(n)/f2(k))
 
This time this correspondence can be found on OEIS as:

    sequence(arr1(n)) = A000522 = 1,2,5,16,65,326,1957,...
    sequence(arr2(n)) = A128196 = 1,3,13,73,527,4775,...
 
Amazingly it seems as if this connection has not been studied
before. The sequences A128195 and A128196 have been published
at OEIS on Feb. 25, 2007.

Asymptotics

Let l(n) = Gamma(1/2)+exp(1)(Gamma(n+1/2,1)
           /Gamma(n+1/2)-Gamma(1/2,1)/Gamma(1/2)).

    L = limit(n = infinity, l(n))
      = exp(1)+(1-exp(1)*Gamma(1/2,1))/Gamma(1/2)
      = hypergeom([1],[1/2],1)/Gamma(1/2)
      = 2.8548878358509945178976165784229199...

Since A128195(n) = 2^(n+1) Gamma(n+3/2) Sum(k=0..n, 1/Gamma(k+1/2))
and l(n) = Sum(k=0..n, 1/Gamma(k+1/2)) we have the asymptotic relation

      A128195approx(n) ~ L*2^(n+1)*Gamma(n+3/2)
 
      A128195(20) = 66354194462262066931070375 
A128195approx(20) ~ 66354194462262066933269596
 
Thus A128195approx(20) gives almost 20 valid decimal digits!
Similarly we have

      A128196approx(n) ~ 2^n*(1+L*(n-1/2)!)
     
      A128196(20) = 1618394986884440656855375
A128196approx(20) ~ 1618394986884440657957590

Again a remarkable good approximation based on a very simple formula.

However, if one wants to avoid the evaluation of the factorial function
there is another asymptotic approximation, based on the foregoing 
approximation and on an asymptotic approximation of the factorial. 
This approximation can be found as the luschny*(n) approximation.

Let M = sqrt(2)*(1+exp(1)*(Gamma(1/2)-Gamma(1/2,1))) 
      = 7.1561425702442093683438
then
         
   A128196asympt(n) = M(2exp(-1)(n-1/(24*n+19/10*1/n)))^n 

For example A128196(20) = .16183949868*10^25
      A128196asympt(20) ~ .16183949871*10^25
      
But since A128195(n) = (2n+1)A128196(n) we also have found 
an asymptotic approximation to A128195(n).

   A128195asympt(n) = M(2n+1)(2exp(-1)(n-1/(24*n+19/10*1/n)))^n
      
For example A128195(20) = .66354194462*10^26
      A128195asympt(20) ~ .66354194475*10^26

Appendix

Consider arrangements of n chords in a circle by number of 
intersections. Here is the beginning of these partitions of n!!.

Things get hard to compute very soon. Here the first 10 cases, 
compared to the 6+1/2 cases of A067311. 

1 = 1, 3 = 2+1, 
15 = 5+6+3+1, 105 = 14+28+28+20+10+4+1,

945 = 42+120+180+195+165+117+70+35+15+5+1,

10395 = 132+495+990+1430+1650+1617+1386+1056+726+451+252+126+56+21+6+1,

135135 = 429+2002+5005+9009+13013+16016+17381+16991+15197+12558+9646
+6916+4641+2912+1703+924+462+210+84+28+7+1, 

2027025 = 1430+8008+24024+51688+89180+131040+169988+199264+214578
+214760+201460+178248+149464+119168+90540+65640+45438+30024+18908
+11320+6420+3432+1716+792+330+120+36+8+1,  

34459425 = 4862+31824+111384+278460+556920+946764+1419432+1922904
+2394450+2775080+3021444+3112632+3051024+2858040+2567340+2217480
+1845486+1482264+1150220+862920+626076+439263+297891+195075+123165
+74817+43605+24293+12870+6435+3003+1287+495+165+45+9+1, 

654729075 = 16796+125970+503880+1434120+3255840+6267492+10620240
+16240440+22810260+29809670+36604944+42558480+47132160+49961640
+50891880+49974237+47432550+43609845+38908580+33735735+28459530
+23380830+18719370+14612805+11125260+8261523+5983290+4224935
+2907190+1947880+1269466+803605+493240+292885+167770+92359+48620
+24310+11440+5005+2002+715+220+55+10+1. 

See also:
John Riordan, "The Distribution of Crossings of Chords Joining 
Pairs of 2n Points on a Circle". Mathematics of Computation, 
Vol. 29, No. 129 (Jan., 1975), pp. 215-222

A007526 a(n) = VarScheme(1,n) displayed in A128195.
A005917 a(n) = VarScheme(n,2) displayed in A128196.
A001147 First column in the triangle displayed in A128196.
A097801 Second column in triangle displayed in A128196.
A014480 Sub-diagonal in triangle displayed in A128196.

Concerned with sequences:
A128195 A128196 A128198 A126062 A126063
A126064 A094587 A007526 A000522 A010842
A090802 A001147 A005917 A014480 A097801  
[Last edited: 2007-03-02]