Seating Arrangement Bug: Circular vs Linear Overbooking

import math

def linear_arrangements(total_people):
    """
    Count arrangements of 'total_people' in a straight row.
    Every position is unique, so full permutation applies.
    Formula: N!
    """
    return math.factorial(total_people)

def circular_arrangements(total_people):
    """
    Count arrangements around a round table.
    We fix one person to eliminate rotational duplicates,
    then arrange the remaining (total_people - 1) freely.
    Formula: (N-1)!
    """
    if total_people < 1:
        return 0
    return math.factorial(total_people - 1)

def circular_necklace_arrangements(total_people):
    """
    For a necklace / identical chairs where flipping = same arrangement.
    Divide circular count by 2 to eliminate mirror duplicates.
    Formula: (N-1)! / 2
    """
    if total_people < 1:
        return 0
    return math.factorial(total_people - 1) // 2

# --- Demo ---
people = 6

print(f"People: {people}")
print(f"Linear (straight row):          {linear_arrangements(people):>6}")
print(f"Circular (round table):         {circular_arrangements(people):>6}")
print(f"Necklace (flip = same):         {circular_necklace_arrangements(people):>6}")

# Step-by-step breakdown
print("\n--- Why the numbers differ ---")
print(f"Linear  = {people}!  = {math.factorial(people)}")
print(f"Circular = ({people}-1)! = {people-1}! = {math.factorial(people-1)}")
print(f"Necklace = ({people}-1)!/2 = {math.factorial(people-1)//2}")
print(f"\nRatio Linear/Circular = {linear_arrangements(people)//circular_arrangements(people)}")
print(f"That ratio equals N ({people}) — exactly the rotational duplicates we removed.")

import math

def circular_with_bundle(total_people, bundle_size):
    """
    Circular arrangements where a specific group of 'bundle_size' people
    must all sit together.
    Steps:
    1. Bundle group = 1 unit
    2. Units to arrange = total_people - bundle_size + 1
    3. Circular of units = (units - 1)!
    4. Multiply by internal arrangements inside bundle: bundle_size!
    """
    units = total_people - bundle_size + 1
    if units <= 0:
        return 0
    circular_units = math.factorial(units - 1)
    internal = math.factorial(bundle_size)
    return circular_units * internal

def circular_with_two_bundles(total_people, b1_size, b2_size):
    """
    Two distinct groups must each sit together (group members within each group).
    Groups are treated as separate bundles.
    """
    units = total_people - b1_size - b2_size + 2
    circular_units = math.factorial(units - 1)
    internal1 = math.factorial(b1_size)
    internal2 = math.factorial(b2_size)
    return circular_units * internal1 * internal2, circular_units, internal1, internal2, units

# --- Problem 1: 6 people, 3 must sit together ---
total1 = 6
bundle1 = 3
total_ways1 = circular_with_bundle(total1, bundle1)
baseline_circ = math.factorial(total1 - 1)

print(f"=== SINGLE BUNDLE: {total1} people, {bundle1} must sit together ===")
print(f"Units to arrange: {total1 - bundle1 + 1} (bundle + {total1 - bundle1} individuals)")
print(f"Circular of {total1 - bundle1 + 1} units: ({total1 - bundle1 + 1}-1)! = {math.factorial(total1 - bundle1)}")
print(f"Internal bundle: {bundle1}! = {math.factorial(bundle1)}")
print(f"Total: {math.factorial(total1 - bundle1)} x {math.factorial(bundle1)} = {total_ways1}")
print(f"Baseline (no restriction): {baseline_circ}")
print(f"Reduction factor: {baseline_circ / total_ways1:.2f}x\n")

# --- Problem 2: 7 people, (A,B) together AND (C,D) together ---
total2 = 7
b1, b2 = 2, 2
total_ways2, circ2, int1, int2, units2 = circular_with_two_bundles(total2, b1, b2)

print(f"=== TWO BUNDLES: {total2} people, two pairs must each sit together ===")
print(f"Units to arrange: {units2}")
print(f"Circular of {units2} units: ({units2}-1)! = {circ2}")
print(f"Internal bundle 1: {b1}! = {int1}")
print(f"Internal bundle 2: {b2}! = {int2}")
print(f"Total: {circ2} x {int1} x {int2} = {total_ways2}")

import math
from itertools import permutations

def circular_never_together(total_people):
    """
    One specific PAIR must NEVER sit together at a round table.
    Complement: Total - arrangements where pair IS together.
    """
    total_circular = math.factorial(total_people - 1)
    units_with_bundle = total_people - 2 + 1
    bundle_circular = math.factorial(units_with_bundle - 1)
    bundle_internal = math.factorial(2)
    arrangements_together = bundle_circular * bundle_internal
    valid = total_circular - arrangements_together
    return total_circular, arrangements_together, valid

def circular_two_pairs_never_together(total_people):
    """
    Two pairs (A,B) and (C,D) must each NEVER sit together.
    Uses inclusion-exclusion to avoid double-subtraction.
    """
    total_circular = math.factorial(total_people - 1)

    # Pair 1 (A,B) together
    units_ab = total_people - 2 + 1
    ab_together = math.factorial(units_ab - 1) * math.factorial(2)

    # Pair 2 (C,D) together
    units_cd = total_people - 2 + 1
    cd_together = math.factorial(units_cd - 1) * math.factorial(2)

    # BOTH pairs together (two bundles)
    units_both = total_people - 4 + 2
    both_together = math.factorial(units_both - 1) * math.factorial(2) * math.factorial(2)

    # Inclusion-Exclusion
    valid = total_circular - ab_together - cd_together + both_together
    return total_circular, ab_together, cd_together, both_together, valid

# --- Single pair: 5 people, D and E never adjacent ---
total = 5
total_circ, together, valid = circular_never_together(total)
print(f"=== SINGLE RESTRICTED PAIR: {total} people ===")
print(f"Total circular: ({total}-1)! = {total_circ}")
print(f"Together (bundle): {together}")
print(f"Never together: {total_circ} - {together} = {valid}")

# Brute-force verification
people = ['A', 'B', 'C', 'D', 'E']
def are_adjacent_circular(arr, p1, p2):
    n = len(arr)
    i1, i2 = arr.index(p1), arr.index(p2)
    return abs(i1 - i2) == 1 or abs(i1 - i2) == n - 1

fixed = [('A',) + perm for perm in permutations(['B', 'C', 'D', 'E'])]
valid_brute = [a for a in fixed if not are_adjacent_circular(list(a), 'D', 'E')]
print(f"Brute-force: {len(valid_brute)} — Match: {valid == len(valid_brute)}")

print()

# --- Two restricted pairs: 7 people ---
total2 = 7
total2_circ, ab2, cd2, both2, valid2 = circular_two_pairs_never_together(total2)
print(f"=== TWO RESTRICTED PAIRS: {total2} people ===")
print(f"Total circular: {total2_circ}")
print(f"A,B together: {ab2}")
print(f"C,D together: {cd2}")
print(f"Both together: {both2}")
print(f"Never together (inclusion-exclusion): {total2_circ} - {ab2} - {cd2} + {both2} = {valid2}")
print(f"\nWRONG approach (no inclusion-exclusion): {total2_circ} - {ab2} - {cd2} = {total2_circ - ab2 - cd2}")
print(f"Difference: {valid2 - (total2_circ - ab2 - cd2)} cases were double-subtracted")

import math

def linear_alternating(total_group1, total_group2):
    """
    Linear row: no two members of group2 adjacent.
    Place group1 first (larger group), creating gaps.
    Gaps = total_group1 + 1 (extra gap at each end).
    """
    if total_group2 > total_group1 + 1:
        return 0, 0, 0, 0
    ways_group1 = math.factorial(total_group1)
    gaps = total_group1 + 1
    ways_group2 = math.perm(gaps, total_group2)
    total = ways_group1 * ways_group2
    return total, ways_group1, gaps, ways_group2

def circular_alternating(total_group1, total_group2):
    """
    Circular table: no two members of group2 adjacent.
    Fix one from group1, arrange rest.
    Gaps = total_group1 (no end gaps in a circle).
    """
    if total_group2 > total_group1:
        return 0, 0, 0, 0
    ways_group1 = math.factorial(total_group1 - 1)
    gaps = total_group1
    ways_group2 = math.perm(gaps, total_group2)
    total = ways_group1 * ways_group2
    return total, ways_group1, gaps, ways_group2

# --- Linear: 5 boys, 4 girls — no two girls adjacent ---
boys, girls = 5, 4
total_lin, ways_b, gaps_lin, ways_g = linear_alternating(boys, girls)
print(f"=== LINEAR: {boys} boys, {girls} girls, no two girls adjacent ===")
print(f"Arrange boys: {boys}! = {ways_b}")
print(f"Gaps created: {gaps_lin} (since {boys} people in a row create {boys+1} gaps)")
print(f"Place {girls} girls in {gaps_lin} gaps: P({gaps_lin},{girls}) = {ways_g}")
print(f"Total: {ways_b} × {ways_g} = {total_lin}")

# --- Circular: 5 boys, 4 girls ---
total_circ, ways_b_circ, gaps_circ, ways_g_circ = circular_alternating(boys, girls)
print(f"\n=== CIRCULAR: {boys} boys, {girls} girls, no two girls adjacent ===")
print(f"Arrange boys in a circle: ({boys}-1)! = {ways_b_circ}")
print(f"Gaps created: {gaps_circ} (since {boys} people in a circle create exactly {boys} gaps)")
print(f"Place {girls} girls in {gaps_circ} gaps: P({gaps_circ},{girls}) = {ways_g_circ}")
print(f"Total: {ways_b_circ} × {ways_g_circ} = {total_circ}")

# --- Why order matters: compare with placing girls first ---
print(f"\n=== Why larger group first? ===")
print(f"If we placed {girls} girls first in a circle:")
print(f"  Gaps created: {girls} (since {girls} people in a circle create {girls} gaps)")
print(f"  Need to place {boys} boys in {girls} gaps: P({girls},{boys}) = {math.perm(girls, boys)}")
print(f"  That's {math.perm(girls, boys)} arrangements — which is zero because {boys} > {girls}, impossible!")
print(f"Always arrange the larger group first to create enough gaps.")

import math
from collections import Counter

def distinct_arrangements(word):
    """
    Count distinct arrangements of a word's letters.
    Accounts for repeated letters by dividing out duplicate permutations.
    Formula: N! / (n1! x n2! x ... x nk!)
    """
    total_letters = len(word)
    letter_counts = Counter(word)
    numerator = math.factorial(total_letters)
    denominator = 1
    for letter, count in letter_counts.items():
        denominator *= math.factorial(count)
    return numerator // denominator, total_letters, letter_counts

def word_with_letters_never_together(word, restricted_letter):
    """
    Count arrangements where specific repeated letters never appear adjacent.
    Uses complement: Total - arrangements where they ARE together.
    """
    total_distinct, total_letters, letter_counts = distinct_arrangements(word)

    # Bundle the restricted letters as one unit
    bundled_word_length = total_letters - 2 + 1
    bundled_counts = dict(letter_counts)
    bundled_counts[restricted_letter] -= 2
    if bundled_counts[restricted_letter] == 0:
        del bundled_counts[restricted_letter]
    bundled_counts[restricted_letter*2] = 1  # marker for the bundle

    # Recalculate denominator for bundled word
    denom_bundled = 1
    for cnt in bundled_counts.values():
        denom_bundled *= math.factorial(cnt)

    arrangements_together = math.factorial(bundled_word_length) // denom_bundled
    valid = total_distinct - arrangements_together
    return total_distinct, arrangements_together, valid

# --- ARRANGE example ---
word = "ARRANGE"
total, length, counts = distinct_arrangements(word)
print(f"=== Word: {word} (length {length}) ===")
print(f"Letter counts: {dict(counts)}")
print(f"Total distinct arrangements: {length}! / (2! × 2!) = {total}")

# Complement for two R's never together
total_arr, together_arr, valid_arr = word_with_letters_never_together(word, 'R')
print(f"\n=== Two R's NEVER together in {word} ===")
print(f"Total arrangements: {total_arr}")
print(f"Arrangements with R's together (treat RR as unit): {together_arr}")
print(f"Valid arrangements: {total_arr} - {together_arr} = {valid_arr}")

# --- Identical objects example ---
print("\n=== Identical objects: 3 red balls (R), 2 blue balls (B) in a row ===")
total_balls = 5
red, blue = 3, 2
identical_arrangements = math.factorial(total_balls) // (math.factorial(red) * math.factorial(blue))
print(f"Total arrangements: 5! / (3! × 2!) = {identical_arrangements}")

# --- Sanity check: sum of permutations equals total? ---
print("\n=== Sanity check: total = together + never-together ===")
print(f"Together: {together_arr} + Never: {valid_arr} = {together_arr + valid_arr}")
print(f"Should equal total: {total_arr} → {together_arr + valid_arr == total_arr}")