Enumerative Combinatorics · Binomial and multinomial coefficients, identities, and lattice paths

Let a,b ≥ 0 and h ≥ 1 be integers with b-a<h

Problem

Let $a,b\ge 0$ and $h\ge 1$ be integers with $b-a<h$. Count northeast paths from $(0,0)$ to $(a,b)$ that never visit a vertex with $y-x\ge h$. Prove the count by reflecting the prefix through the first visit to $y-x=h$, and give the inverse map explicitly. Use the convention that an out-of-range binomial coefficient is zero. Specialize to paths from $(0,0)$ to $(7,4)$ that stay on or below $y=x$. Explain what happens if $b<h$.

Hint

Count all paths and remove those that first reach the forbidden line.

Check your work

Work the problem yourself first. Then open it in Training to check your answer and read the full worked solution.

Check your answer See the full solution

The answer check and full solution for this problem come with ProofAnvil Practice membership ($19 USD monthly). See membership. Or start with the free Enumerative Combinatorics sample problem: Try the free sample problem.

More Enumerative Combinatorics practice problems

A group has six distinct volunteersCounting principles, bijections, and the pigeonhole principle
Among n distinct volunteers, a specified set of r volunteers is qualified to serve as…Counting principles, bijections, and the pigeonhole principle
Let a,b ≥ 0 and let k be an integerBinomial and multinomial coefficients, identities, and lattice paths
For n ≥ 1, a positive composition of n is an ordered list of positive integers summing…Compositions, multisets, and distributing objects into boxes
Among thirty labeled projects, eighteen use method A, fourteen use method B, and twelve…Inclusion-exclusion, derangements, and surjections
Let S(n,k) count partitions of [n] into k nonempty unordered blocksSet partitions, Stirling numbers, and the cycle structure of permutations
An integer partition of n is a finite weakly decreasing sequence of positive integers…Integer partitions and Ferrers diagrams
Let a₀=2, a₁=5, and aₙ=5aₙ₋₁-6aₙ₋₂ for n ≥ 2Ordinary generating functions, recurrences, and Catalan numbers
If aₙ counts structures on a specified set of n distinct labels, its exponential…Exponential generating functions and labeled structures