KEYWORDS: Variations, Arrangements, Permutations, Hasse Diagram, Boolean Algebra, Factorial Function, Double Factorial, Combinatorial Schemes, OEIS
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]