Conference rusure::math

>    	3. What is a general formual for an N-button lock?
>    Since I belive that this is a medium difficulty problem, lets let
>    some infrequent/new contributors have a chance at it first.

Before the infrequent/new contributors spend too much effort chasing this 
one, note that it is of considerably more than medium difficulty. The 
general solution involves computing p(n), the number of partitions of n,
i.e. the number of ways in which the integer n can be split up into smaller 
integers that add up to n; and no explicit formula for this function is 
known. It should not be too hard to get explicit results for the cases 5
and 6, though, since p(5) = 7 and p(6) = 11.

    Let f(n) be the number of valid combinations for an n-button lock.

				n-1    n
    Then, f(0) = 1, and f(n) = Sigma (   ) f(i)
				i=0    i

    I'd expect the general formula to be something like:

	f(n) =	a*(2*n)!
		a*((n+b)!)^2
		a*(b*n+c)^n

    Or a sum of such expressions.  So far, I haven't 'lucked' upon it.

The following approximation may be of some interest:

    f[k] = 1.442695041 * k * f[k-1]

The approximation is very good, at least up to k=30.


This implies that:

    f[k] = (1.442695041)^k * k!

may give a good approximation to f[k]; using Stirling's approximation,
and some guessing, we find the following approximation:

			 (k+1/2)            k
    f[k] = sqrt(10/3) * k        * (259/488)

    I think Lynn is right (as usual).
    
    Therefore let me make it official:
    
    	This topic is open to all, fell free to pile on.
    
    
    -- Barry

Here are the first few numbers in the sequence.  Several patterns are
noticable (for example, consider the numbers modulo 3, 5, or 7 -- but
we'd expect some periodicity from the form of the recursive definition).
I haven't found a (non-recursive) formula for f[n].  My current guess
is that it's of the form: f[n] = p(n) * n! + q(n), where p(n) and q(n)
are polynomials.
					- Gilbert

f[ 1]= 1
f[ 2]= 3
f[ 3]= 13
f[ 4]= 75
f[ 5]= 541
f[ 6]= 4683
f[ 7]= 47293
f[ 8]= 545835
f[ 9]= 7087261
f[10]= 102247563
f[11]= 1622632573
f[12]= 28091567595
f[13]= 526858348381
f[14]= 10641342970443
f[15]= 230283190977853
f[16]= 5315654681981355
f[17]= 130370767029135901
f[18]= 3385534663256845323
f[19]= 92801587319328411133
f[20]= 2677687796244384203115
f[21]= 81124824998504073881821
f[22]= 2574844419803190384544203
f[23]= 85438451336745709294580413
f[24]= 2958279121074145472650648875
f[25]= 106697365438475775825583498141
f[26]= 4002225759844168492486127539083
f[27]= 155897763918621623249276226253693
f[28]= 6297562064950066033518373935334635
f[29]= 263478385263023690020893329044576861
f[30]= 11403568794011880483742464196184901963
f[31]= 510008036574269388430841024075918118973
f[32]= 23545154085734896649184490637144855476395
f[33]= 1120959742203056268267494209293006882589981
f[34]= 54984904077825684862426868390301049750104843
f[35]= 2776425695289206002630310219593685496163584253
f[36]= 144199280951655469628360978109406917583513090155
f[37]= 7697316738562185268347644943000493480404209089501
f[38]= 421985466101260424678587486718115935844245187819723
f[39]= 23743057231588741419119534567705900419786127935577533
f[40]= 1370159636942236704917645663312384364386256449136591915
f[41]= 81045623051154285047127402304207782853156976521592907421
f[42]= 4910812975389574954318759599939388855544783946694910718603
f[43]= 304646637632091740261982544696657582136519552428876887346813
f[44]= 19338536506753895707368358095646384573117824953447578202397675
f[45]= 1255482482235481041484313695469155949742941807533901307975355741
f[46]= 83318804148028351409201335290659562069258599933450396080176273483
f[47]= 5649570401186486930330812460375430692673276472202704742218853260093
f[48]= 391229145645351175841837029639030040330277058716846008212321196523435
f[49]= 27656793065414932606012896651489726461435178241015434306518713649426461
f[50]= 1995015910118319790635433747742913123711612309013079035980385090523556363

I think the p(n)*n! + q(n) approximation is doomed to failure since no
polynomial p(n) can increase as fast as the empirical (1.44...)^n given in .3;

If you consider the Fibonacci-like series given by the recurrence:

	F'(0) = F'(-1) = F'(-2) = 1

	F'(i) = F'(i-1) + F'(i-3) for i > 0

Then (F'(n) * n!) / 2 is a fair approximation to f[n], mostly because the ratio
F'(n+1)/F'(n) is asymptotically 1.4655... (the real root of X^3 - X^2 - 1 = 0)
which is close to the ratio given in .3. Unfortunately, the ratio in .3
does not seem to be the root of any polynomial of up to degree 9 with
coefficients in {-2,-1,0,1,2}, although intuition says that it must 
converge to an algebraic number....

 n	f[n]	F'(n)	F'(n) * n! / 2
---	-------	-----	----------------
 1	1	2	1
 2	3	3	3
 3	13	4	12
 4	75	6	72
 5	541	9	540
 6	4683	13	4680
 7	47293	19	47880
 8	545835	27	544320

Using H-floating, I calculated f(1) thru f(300), and displayed:

	f(k) / (k * f(k-1))

This quantity converged quickly (by k=30) to:

	 1.4426950408889634073599246810019

Yes, the cube root of 3 is close, but looking further down Knuth's
'Tables of Numerical Quantities', I noticed:

1/ln 2 = 1.4426950408889634073599246810018921374266


Assuming this has little to do with chance, I ventured that asymptotically,

	f(k) = w * k! * (1/ln 2)^k

where w is some constant.  The series also yields a quick convergence for w,
and it was found to be a very good approximation to 1/(2 ln 2).  The following
approximation is very good:

	f(k) = k! * (1/ln 2)^(k+1) / 2

This is good even for small k, as the first few values show:

	f(1) =   1.04068
	f(2) =   3.00278
	f(3) =  12.99629
	f(4) =  74.99873
	f(5) = 541.00152


However, this still doesn't give a completely satisfactory answer since
f(k) is really an integer.  Think Stirling's approximation for factorials
may help get rid of the ln 2, ...

	            pi k      k   k
	f(k) = sqrt(----) (------)  / ln 2
		      2    e ln 2

Needless to say, this doesn't help the formula.

I hate to throw a small monkey wrench in this discussion, but in the real
world, the following statement is false for this kind of lock...

>    	1. Every button must be used exactly once in the combination.

I know of one (and only one) such lock where one digit is skipped entirely...

-Mike

re .8:

> I know of one (and only one) such lock where one digit is skipped entirely...

If exactly one of the n buttons must be skipped, then the number of
combinations is:  n * f(n-1), where f(k) is the solution to .0's problem.

In fact, the numbers of additional combinations introduced by requiring
1, 2, 3, ... n-1 of the n buttons to be excluded exactly duplicates the terms
of the sum in the recurrence relation given in .2, so that if there are no
restrictions on how many buttons are excluded in the combination the number
of possible combinations is 2*f(n)-1 (or 2*f(n) if you allow all buttons to be
excluded, which is the case when you have an open door with a dummy lock on it).



re .6 and .8: So much for my intuition....

Hmmm.  The 'largest' root of 1 + x/1! + x^2/2! + ... + x^n/n! = 2
may not be near 1/ln 2.  Shouldn't there be a negative root with
larger absolute value?

Can MAPLE find all roots, *numericaly*, rather than algebraically?

    It would probably be best to get an asymptotic estimate of the
    largest negative root of 1 + x + x^2/2! + ... + x^n/n! - 2 = 0
    (for even n) by yet another use of Stirlings approx to n!.

    f(x) = 1 + x + x^2/2! + ... + x^n/n! - 2
	 = e^x - (x^(n+1)/(n+1)! + ... ) - 2

    Since e^x will be negligable for large negative x we could simplify
    this to

	x ~= (2*sqrt(2*(n+1)*pi))^(1/(n+1))*(n+1)/e

    You can get the largest root of a polynomial by forming a recurrance
    relation which characteristic equation is the polynomial.

    This lock problem was neat, I wish there was more time to play with
    these things...

    - Jim

    A few sample numbers:

   N      Estimate        Residual      Accurate       Residual
   -      --------        ---------     --------       --------
   2    -2.1201751927   -0.8726E+00   -2.7320508076   -0.5961E-24
   4    -2.9167923182   -0.7830E+00   -3.2652960444   -0.5031E-30
   6    -3.6847066921   -0.7376E+00   -3.9545373104   -0.6078E-30
   8    -4.4453995049   -0.7071E+00   -4.6771290692   -0.8151E-30
  10    -5.2023553673   -0.6843E+00   -5.4113416095   -0.2966E-30
  12    -5.9567753352   -0.6665E+00   -6.1505582316    0.1194E-30
  14    -6.7092767593   -0.6523E+00   -6.8921592920    0.1202E-30
  16    -7.4602478877   -0.6409E+00   -7.6349317097   -0.6433E-30
  18    -8.2099596635   -0.6314E+00   -8.3782551890    0.3420E-30
  20    -8.9586127052   -0.6236E+00   -9.1217920920    0.6471E-30
  22    -9.7063612954   -0.6170E+00   -9.8653517832    0.7704E-32
  24   -10.4533273040   -0.6113E+00  -10.6088249265   -0.4491E-30
  26   -11.1996089820   -0.6065E+00  -11.3521491462   -0.8120E-30
  28   -11.9452868465   -0.6022E+00  -12.0952900281   -0.2157E-30
  30   -12.6904277872   -0.5985E+00  -12.8382301452   -0.2843E-30
  32   -13.4350880221   -0.5952E+00  -13.5809625087   -0.5562E-30
  34   -14.1793152804   -0.5923E+00  -14.3234865602   -0.7319E-31
  36   -14.9231504463   -0.5896E+00  -15.0658056719   -0.6063E-30
  38   -15.6666288193   -0.5872E+00  -15.8079255652   -0.1234E-27
  40   -16.4097810947   -0.5851E+00  -16.5498533001   -0.2350E-28
  42   -17.1526341361   -0.5831E+00  -17.2915966264    0.2651E-27
  44   -17.8952115920   -0.5813E+00  -18.0331635671    0.1024E-27
  46   -18.6375343914   -0.5796E+00  -18.7745621523    0.1180E-26
  48   -19.3796211484   -0.5781E+00  -19.5158002517    0.1648E-26
  50   -20.1214884927   -0.5767E+00  -20.2568854733    0.7786E-27

1.  I suspect that the real-world locks don't require you to use up
*any* minimum number of digits (although it is conceivable that you
can configure them so that it is impossible for the person who sets
the combination to select one that is too simple).  This is because
I know of three such locks which used no more than a total of three
digits.

2.  I know someone who can pick those locks just by feel - no stethoscopes,
X-ray machines or scredrivers needed.
				/AHM

    Maybe I am missing something. Consider a set of 6 objects. I believe
    the lock problem to be equivalent to enummerating the partions of
    the set. Each partition of a set of six objects has a "signature".
    For example two sets of 3 which we will write as (3(2)) or 3 sets
    consisting of 1, 2, and 3 objects resp. which we will write as (1,2,3).
    
    Let us ennumerate the partitions of a six set.
    
    (1(6)),  (1(4),2),   (1(3),3), (1(2),2(2)), (1(2),4), (1,5), (1,2,3),
    
    (2,4), (2(3)), (3(2)), (6).
    
    Next we calculate how many partition of the six set have these
    signatures respectively:
    
    1,   15,  20,  45,  15, 6, 60, 15, 15, 10, 1
    
    Add'em up and get 203.  Where did I err?
    
    R.J.Kolker
    
    

    Re .15:
    
    {{A}, {B}} is a partition of {A, B}, but the lock requires _order_ when
    the sets of buttons are pressed, giving two combinations as ({A}, {B})
    and ({B}, {A}).                   
    
    
    				-- edp 

    re .16
    
    Many thanks. It always helps to know the problem one is working
    on.
    

When I was in graduate school I was interested in partitions and my prof. 
indicated that p(n) was still an open question. In retrospect, I think he 
meant that a *simple* formulation was not known, because I recently found 
that there exists a complex formula. It was discovered by Ramanujan ca. 
1913 and recorded in a 1936 monograph by Hardy on Ramanujan's work. This
was brought to my attention my a recent PBS bio of Ramanujan entitled "The
Man Who Loved Numbers", which I recommend. More or less by chance, I have a
copy of that monograph in my personal library and spent a stimulating
couple of hours over it last week. 

The formula R. discovered is not an asymptotic approximation, as one might 
expect from the "formula" for the number of primes < n, but is a rapidly 
converging series approximation that produces an exact value (i.e. error<1) 
in a reasonable number of terms. For example, the *first* term of R's
series produces about 10 significant figures for p(200) and 20 terms
suffice for an error of about .004, beyond which everything else is dust. 

I have some hope of gaining enough understanding of R's formula to be able 
to reduce it to a MAPLE program. If I can I will make it available.

Lynn Yarbrough