Best Answer m00li, 27 April 2014 - 01:05 PM

Spoiler for Still struggling with it but

EDIT: the last term for F(n) should read ^{n-[n/2]}C[n/2]f(n-[n/2]) where [k] is the max integer <=k

Welcome to BrainDen.com - Brain Teasers Forum. Like most online communities you must register to post in our community, but don't worry this is a simple free process. To be a part of BrainDen Forums you may create a new account or sign in if you already have an account. As a member you could start new topics, reply to others, subscribe to topics/forums to get automatic updates, get your own profile and make new friends. Of course, you can also enjoy our collection of amazing optical illusions and cool math games. If you like our site, you may support us by simply clicking Google "+1" or Facebook "Like" buttons at the top. If you have a website, we would appreciate a little link to BrainDen. Thanks and enjoy the Den :-) |

Guest Message by DevFuse

Started by BMAD, Apr 22 2014 03:12 AM

Best Answer m00li, 27 April 2014 - 01:05 PM

Spoiler for Still struggling with it but

EDIT: the last term for F(n) should read ^{n-[n/2]}C[n/2]f(n-[n/2]) where [k] is the max integer <=k

13 replies to this topic

Posted 27 April 2014 - 04:21 PM

Spoiler for partial solution

It looks like it's heading towards DrXP's solution, but I can't tell for sure.
Posted 29 April 2014 - 11:12 PM

I still think the correct answer for n digit string is given by

= nC0f(n) + n-1C1f(n-1) + n-2C2f(n-2) + n-3C3f(n-3) + ...... + n-[n/2]C[n/2]f(n-[n/2])

putting n = 10, we get F(10) = **3349507**;

where f(n) = (subfactorial(n+1))/n

I wrote a vba code to do the simulation and it confirms the answer too. The values for first few n's are:

n
F(n)
3
5
4
21
5
106
6
720
7
4547
8
36696
9
332769
10
3349507

Here's the vba code:

Dim arrlen As Integer

Dim counter As Long

Sub randomd()

j = 1

position = 1

counter = 0

Dim i_arr As Variant

i_arr = Array(1, 3, 7, 4, 10, 6, 8, 2, 9, 5)

arrlen = UBound(i_arr) + 1

ReDim Preserve i_arr(1 To arrlen)

Call perm(ByVal i_arr, j, ByVal position)

Sheet2.Cells(1, arrlen + 1) = counter

End Sub

Sub perm(ByVal i_arr, ByRef j, ByVal position)

For i = position To arrlen

temp = i_arr(position)

i_arr(position) = i_arr(i)

i_arr(i) = temp

If position = arrlen Then

'For k = 1 To position: Sheet2.Cells(j, k) = i_arr(k): Next k

satisfies = True

k = 3

While satisfies And k <= arrlen

If i_arr(k) - i_arr(k - 1) = 1 And i_arr(k - 1) - i_arr(k - 2) = 1 And satisfies Then satisfies = False

k = k + 1

Wend

If satisfies Then counter = counter + 1

j = j + 1

End If

Call perm(ByVal i_arr, j, ByVal position + 1)

Next i

End Sub

Posted 30 April 2014 - 06:06 AM

I still think the correct answer for n digit string is given by

= nC0f(n) + n-1C1f(n-1) + n-2C2f(n-2) + n-3C3f(n-3) + ...... + n-[n/2]C[n/2]f(n-[n/2])putting n = 10, we get F(10) =3349507;where f(n) = (subfactorial(n+1))/nI wrote a vba code to do the simulation and it confirms the answer too. The values for first few n's are:n F(n)3 54 215 1066 6437 45478 366969 33276910 3349507Here's the vba code:Dim arrlen As IntegerDim counter As LongSub randomd()j = 1position = 1counter = 0Dim i_arr As Varianti_arr = Array(1, 3, 7, 4, 10, 6, 8, 2, 9, 5)arrlen = UBound(i_arr) + 1ReDim Preserve i_arr(1 To arrlen)Call perm(ByVal i_arr, j, ByVal position)Sheet2.Cells(1, arrlen + 1) = counterEnd SubSub perm(ByVal i_arr, ByRef j, ByVal position)For i = position To arrlentemp = i_arr(position)i_arr(position) = i_arr(i)i_arr(i) = tempIf position = arrlen Then'For k = 1 To position: Sheet2.Cells(j, k) = i_arr(k): Next ksatisfies = Truek = 3While satisfies And k <= arrlenIf i_arr(k) - i_arr(k - 1) = 1 And i_arr(k - 1) - i_arr(k - 2) = 1 And satisfies Then satisfies = Falsek = k + 1WendIf satisfies Then counter = counter + 1j = j + 1End IfCall perm(ByVal i_arr, j, ByVal position + 1)Next iEnd Sub

EDIT: corrected the n:F(n) table above

Posted 30 April 2014 - 03:30 PM

m00li's answer of 3349507 seems correct. I couldn't follow the VB code's logic for making permutations (a subroutine seems to be calling itself?) and I don't have MS Office, so I wrote a perl script to calculate it, and it gave the same answer.

#!/usr/bin/perl use strict; use warnings; # The "implicit" starting permutation for this program to # avoid copying any triplets from is # 0 1 2 3 4 5 6 7 8 9 # since that makes programming easier. # This will generate permuatations, see if any # triplets appear in the permutation, and if not then # print the permutation and increase the counter my $counter = 0; # This uses List::Permutor to generate permutations # If you don't already have it installed, from the command # prompt, run "cpan List::Permutor" # (or run "cpan App::cpanminus" then "cpanm List::Permutor") use List::Permutor; my $permutor = List::Permutor -> new(0..9); while (my @perm = $permutor -> next()) { # For each permutation, check for consecutive triplets # If there are no triplets, increase the counter and print # the permutation my $notriplets = 1; TRIPLETLOOP: for(my $triplet=0; $triplet<8; $triplet++) { if(($perm[$triplet] == $perm[$triplet+1]-1) && ($perm[$triplet] == $perm[$triplet+2]-2)) { $notriplets = 0; last TRIPLETLOOP; } } if($notriplets) { print "Permutation " . ++$counter . ": @perm\n"; } } print "Found $counter permutations with no triplets\n";I also couldn't understand post 10 at first, but now it seems to make sense.

0 members, 0 guests, 0 anonymous users