Unique Codes

[BMAD]

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.

[dgreening]

My guess is that it is a pretty big number!

[sorry I couldn't pass that up]

[BMAD]

[Rob_G]

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

[BMAD]

because?

[Dr XP]

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

[m00li]

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 + .....

= ⁿC₀f(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

[Rob_G]

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! )

[carefreekaran]

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!)

[m00li]

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 + .....

= ⁿC₀f(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

[plasmid]

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!.

Code 2 cannot have "456", removing another 8! possibilities but with some double-counting of cases. First, consider the number of cases where both "123" and "456" appear. If you write out pairs of (x, y) such that one triplet starts at position x and the other triplet starts at position y, then you get (1,4) (1,5) (1,6) (1,7) (1,8) ; (2,5) (2,6) (2,7) (2,8) ; (3,6) (3,7) (3,8) ; (4,7) (4,8) ; (5,8) for a total of 15, and accounting for the fact that either "123" or "456" could appear as the first of those triplets (ie you can reverse the order of x and y) there are a total of 30 ways of placing those two triplets in the code. For each of those 30 cases, the four other numbers "7890" could be arranged in any of 4! ways, so the total number of codes with both "123" and "456" that we would need to add back because they were already removed by considering cases where "123" appears is 30 * 4!. It just so happens that 30 = 6 * 5, so 30 * 4! = 6!. (If you were to think of "123" and "456" as single digits that you were adding back into a 6-digit code, that would make sense). Now for the next step, consider all cases that contain "345" and "456". As in the previous case, we know that if a code contains both "234" and "456" then it must contain "23456" and therefore also contain both "345" and "456", so we can just consider adding back the "345" "456" cases that would have been double-counted. As was shown two paragraphs ago, there are 7! cases that contain four consecutive numbers like "3456". But we also have to consider that some of those 7! cases were already negated from being double-counted because they contain both "123" and "456" -- specifically, any sequences containing not only "3456" but "123456" would have already been removed in the first part of this paragraph. So while adding back the 7! cases where "3456" appears, we must not doubly-add-back the 5! cases where "123456" appears. So at the end of all that, the first part of this paragraph has us adding back 6! cases where both "123" and "456" appear, and the second part has us adding back 7! cases where "345" and "456" appear but excluding 5! of those 7! cases that were already added back by the first part of the paragraph. So at this point, we're at (10! - 3 * 8! + 2 * 7!) (from where the previous paragraph left off) - 8! + 6! + 7! - 5! which simplifies to 10! - 4 * 8! + 3 * 7! + 6! - 5!.

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.

[m00li]

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

[m00li]

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

[plasmid]

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.