BrainDen.com - Brain Teasers
• 0

# Unique Codes

## Question

Make a 10 digit code using the digits 0-9 each once. Make another 10-digit code without any three adjacent code sequences repeating. How many unique codes can be made following these two rules?

For example:

code 1: 0,1,2,3,4,5,6,7,8,9

code 2 cannot contain 0,1,2 or 1,2,3 or 2,3,4 or ,3,4,5, etc. anywhere in its code.

## Recommended Posts

• 0

Let f(n) denote the number of n-permutations of n-string where none of the two adjacent bits are in succession.

Then, f(n) = (except for the first bit, arrange remaining such that no two adjacent are in succession. This can be done in f(n-1) ways.Then insert the first bit in the n available spaces. Subtract 1 as in one of these spaces, the first two bits will be in the same order) + (except for the first bit, arrange remaining such that ONLY any '2 adjacent bits' are in succession. This can be done in f(n-2) ways. Then insert the first bit in between the '2 adjacent bits'. This single set of 2 adjacent bits can be selected from n-1 string in n-2 ways)

therefore f(n) = (n-1)*f(n-1) + (n-2)*f(n-2)

Calculating f(10) = 1468457, f(9) = 148329, ...

Now, Let F(n) number of n-permutations of n-string where 3 successive bits are not allowed together again

= (no 2 successive allowed) + only 1 2-successive bit allowed + only 2 successive bits allowed + .....

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

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

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

##### Share on other sites

• 0

My guess is that it is a pretty big number!

[sorry I couldn't pass that up]

• 0
##### Share on other sites

• 0

there are 3,346,559 ways to write the second code and not repeat a triplet.

• 0

because?

##### Share on other sites

• 0

I'm sure I missed something but here is my best effort:

10! - 8*8! + 7*7! + 15(6! - 5!) + 5! or 3,350,640

##### Share on other sites

• 0

Let f(n) denote the number of n-permutations of n-string where none of the two adjacent bits are in succession.

Then, f(n) = (except for the first bit, arrange remaining such that no two adjacent are in succession. This can be done in f(n-1) ways.Then insert the first bit in the n available spaces. Subtract 1 as in one of these spaces, the first two bits will be in the same order) + (except for the first bit, arrange remaining such that ONLY any '2 adjacent bits' are in succession. This can be done in f(n-2) ways. Then insert the first bit in between the '2 adjacent bits'. This single set of 2 adjacent bits can be selected from n-1 string in n-2 ways)

therefore f(n) = (n-1)*f(n-1) + (n-2)*f(n-2)

Calculating f(10) = 1468457, f(9) = 148329, ...

Now, Let F(n) number of n-permutations of n-string where 3 successive bits are not allowed together again

= (no 2 successive allowed) + only 1 2-successive bit allowed + only 2 successive bits allowed + .....

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

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

##### Share on other sites

• 0

there are 3,346,559 ways to write the second code and not repeat a triplet.

because?

10! - ( 8*8! - 7*7! - 6*6! - 5*5! - 4*4! - 3*3! - 2*2! - 1*1! )

##### Share on other sites

• 0

Total cases = 10!.

Considering case when one block( 3 digits) is same as 1st code sequence= 8!..

Multiply by 2 because 3 digits can be reversed in a block and they'll still be adjacent..

Total blocks= 8. Hence total cases=8*2*8!..

[Above expression also contains cases when more than 3 digits are same w.r.t 1st code..]

Therefore ans= 10!-(2*8*8!)

##### Share on other sites

• 0

Without loss of generality, call the first code

1234567890

If there were no restrictions on the second code, it could have any of 10! values -- all of the different permutations of the 10 digits.

Code 2 cannot have "123" in the first position, so that removes 7! possibilities (all codes starting with "123" and having any of the 7! permutations of the numbers 4 through 0 in the other positions). Code 2 also cannot have "123" in the second, third, fourth ... eighth position (not ninth or tenth because we need to fit all three of the "123" digits in the 10-digit code), so that removes another 7! possibilities for each of those positions, and overall this eliminates 8 * 7! = 8! possibilities. So we're now down to 10! - 8!.

Code 2 cannot have "234" in the second position, or any of the eight positions that a triplet could fall in, so that eliminates more possibilities. One might think that this would eliminate another 8! possibilities, however, some of the possibilities where "234" appears would also contain "123", so we cannot simply subtract another 8! because then we would be double-counting a sequence like 8761234950 which contains both "123" and "234". Cases that have both "123" and "234" must contain the sequence "1234". There are 7 positions where "1234" could appear within a code and 6! codes that contain "1234" for each of those positions, so there are a total of 7 * 6! = 7! codes that would be double-counted by considering "123" and "234" independently. So at this point, we're down to 10! - 8! - 8! + 7! possible codes.

Code 2 cannot have "345" in any of the eight positions where a triplet could be, removing another 8! possible codes, but double-counting some cases with both "123" and "345" or "234" and "345". If a code contains both "123" and "345", then it must contain "12345", and therefore must also contain both "234" and "345", so we can account for all of the double-counted cases simply by considering all cases where both "234" and "345" appear. As in the previous paragraph, this implies that the code contains "2345", and there are 7! such cases. So at this point, we're at 10! - 3 * 8! + 2 * 7!.

This appears to only get more complex as you go along, so I'm stopping here and keeping what's left of my sanity.

It looks like it's heading towards DrXP's solution, but I can't tell for sure.

##### Share on other sites

• 0

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
##### Share on other sites

• 0

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 643
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

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

##### Share on other sites

• 0

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.

## Join the conversation

You can post now and register later. If you have an account, sign in now to post with your account.

×   Pasted as rich text.   Paste as plain text instead

Only 75 emoji are allowed.

×   Your previous content has been restored.   Clear editor

×   You cannot paste images directly. Upload or insert images from URL.