This is a classic combinatorics problem: number of ways to place 3 non-adjacent 1s in 8 positions.

["# The Classic Combinatorics Problem: Counting Ways to Place 3 Non-Adjacent 1s in 8 Positions", "In combinatorics, one of the most intriguing yet foundational problems is determining the number of ways to place non-adjacent objects in a sequence—particularly, how many ways can we place 3 non-adjacent 1s in 8 positions? This seemingly simple exercise unlocks deeper understanding of combinatorial reasoning, constraints, and the power of clever counting techniques.", "## What Is the Problem?", "Imagine we have 8 equally spaced positions in a row labeled from 1 to 8. We want to count how many distinct ways we can place exactly three "1s" such that no two 1s are adjacent—meaning there is at least one "0" separating any two 1s.", "For example, placing 1s in positions {1, 3, 5} is valid. But placing them in {1, 2, 4} is not, because positions 1 and 2 are adjacent.", "## Why Is This a Classic Problem?", "This problem exemplifies a common theme in combinatorics: imposing adjacency restrictions on selections from a linear sequence. It appears in various settings—from scheduling problems and resource allocation to algorithm design and probability. Solving it teaches essential tools like the stars and bars method, gap counting, and combinatorial reasoning under constraints.", "---", "## The Combinatorial Solution", "### Step 1: Transform the Problem", "To count placements where 3 ones are non-adjacent in 8 positions, we use a space-filling transformation. Since no two 1s can be adjacent, each selected position needs at least one unselected position (a “gap”) to its right—except possibly the last one.", "Rather than directly counting valid arrangements, we map the configuration to a simpler counting problem.", "Let’s define:", "- We place 3 ones (1s) in some order in 8 positions.\n- To enforce non-adjacency, think of placing the 3 ones with gaps of at least one zero between each.", "Instead of counting forbidden adjacents directly, we transform the positions to remove constraints.", "### Step 2: Use Gap Method – Transform Positions", "Imagine placing 3 non-adjacent 1s. Between each pair of 1s, there must be at least one 0. So:", "- Place 3 ones: • • + gaps\n- Between each pair, insert 1 mandatory zero. This uses up 2 zeros (between pos 1–2 and 2–3).\n- So, we start by reserving 2 mandatory zeros to enforce non-adjacency.", "That leaves:\n8 – 3 (for ones) – 2 (mandatory zeros) = 3 remaining zeros\nThese 3 zeros are free to distribute as gaps: before the first 1, between the 1s (beyond the mandatory one already placed), and after the last 1.", "But to model this cleanly, we use a standard combinatorics trick.", "Let the positions of the 1s be $ p_1 < p_2 < p_3 $, satisfying $ p_{i+1} \geq p_i + 2 $ (non-adjacent).", "Define new variables to represent gaps:", "Let\n- $ x_1 $: number of zeros before position 1 (before first 1)\n- $ x_2 $: number of zeros between 1st and 2nd (at least 1)\n- $ x_3 $: number of zeros between 2nd and 3rd (at least 1)\n- $ x_4 $: number of zeros after 3rd 1", "The total length is:", "$$\nx_1 + 1 + x_2 + 1 + x_3 + 1 + x_4 = 8\n\Rightarrow x_1 + x_2 + x_3 + x_4 = 8 - 3 - 2 = 3\n$$", "Where $ x_2 \geq 1 $, $ x_3 \geq 1 $, and $ x_1, x_4 \geq 0 $.", "Let:", "- $ y_2 = x_2 - 1 \geq 0 $\n- $ y_3 = x_3 - 1 \geq 0 $", "Then:", "$$\nx_1 + y_2 + y_3 + x_4 = 3 - 2 = 1\n$$", "We now count the number of non-negative integer solutions to:\n$$\nx_1 + y_2 + y_3 + x_4 = 1\n$$", "This is a classic stars and bars problem: number of ways to distribute 1 identical item (zeros) into 4 non-negative bins.", "$$\n\ ext{Number of solutions} = \binom{1 + 4 - 1}{4 - 1} = \binom{4}{3} = 4\n$$", "But wait—this gives only 4? That seems too small. Let’s double-check.", "Wait—actually, the total remaining zeros is 3, after reserving 2 mandatory ones, so yes, $ x_1 + x_2 + x_3 + x_4 = 3 $, with $ x_2 \geq 1 $, $ x_3 \geq 1 $.", "So define $ x_2' = x_2 - 1 \geq 0 $, $ x_3' = x_3 - 1 \geq 0 $, then:", "$$\nx_1 + x_2' + x_3' + x_4 = 3 - 2 = 1\n$$", "Number of non-negative integer solutions: $ \binom{1 + 4 - 1}{3} = \binom{4}{3} = 4 $? No—standard formula: number of solutions is $ \binom{n + k - 1}{k - 1} $, where $ n = 1 $, $ k = 4 $, so:", "$$\n\binom{1 + 4 - 1}{4 - 1} = \binom{4}{3} = 4\n$$", "But this counts only 4 placements? Let’s list them manually.", "### Step 3: List All Valid Arrangements for Verification", "Let positions be $ p_1, p_2, p_3 $, with $ p_{i+1} \geq p_i + 2 $.", "Start with $ p_1 = 1 $:\n- $ p_2 \geq 3 $: try 4 → $ p_3 \geq 6 $ → 1,3,6; 1,3,7; 1,3,8 → 3\n- $ p_2 = 5 $ → $ p_3 \geq 7 $: 1,5,7; 1,5,8 → 2\n- $ p_2 = 6 $ → $ p_3 \geq 8 $: 1,6,8 → 1\nTotal for $ p_1 = 1 $: 3 + 2 + 1 = 6", "Now $ p_1 = 2 $:\n- $ p_2 \geq 4 $: try 5 → $ p_3 \geq 7 $: 2,5,7; 2,5,8 → 2\n- $ p_2 = 6 $ → $ p_3 \geq 8 $: 2,6,8 → 1\nTotal: 2 + 1 = 3", "$ p_1 = 3 $:\n- $ p_2 \geq 5 $: 7 or 8 → $ p_3 \geq 9 $ invalid\n→ only 3,7,— too far\nWait: 3,5,7 → $ p_3 = 7 $ (OK), 3,5,8 → valid\n→ 3,5,7; 3,5,8 → 2", "So total:\n- $ p_1=1 $: 6\n- $ p_1=2 $: 3\n- $ p_1=3 $: 2\n- $ p_1=4 $? $ p_2 \geq 6 $, $ p_3 \geq 8 $: 4,6,8 → valid → 1\nTotal: 6 + 3 + 2"]