double_counting

Name: double_counting
Availability: InStock
Author: bneb

Prove combinatorial identities by counting incidences in finite bipartite relations.

1|Updated Mar 14, 2026

Search Tags:#combinatorics #lean #proof #double-counting #finite-sets #identities

Ready to run

npx skills add https://github.com/bneb/perqed --skill double-counting

💬 Prompt for ChatGPT / Claude Chat▼

Please help me install this Agent Skill.
Skill: double_counting
Source: https://github.com/bneb/perqed/tree/main/.agents/skills/double_counting
Command: npx skills add https://github.com/bneb/perqed --skill double-counting

SYSTEM DOCUMENTATION & REQUIREMENTS

What problem does it solve?

Double counting (also: counting in two ways, Fubini for finite sets) establishes an algebraic identity by considering a bipartite relationship R ⊆ A × B. Counting the total number of "incidences" |R| by summing over the A-side gives one expression; summing over the B-side gives another. Equating them yields the identity.

Core Features & Use Cases

Formalizes proofs by counting incidences in bipartite relations to derive equalities.
Proves classic lemmas like the handshaking lemma, Vandermonde convolution, and binomial identities.
Educational: useful for teaching combinatorics and for constructing Lean-based proofs.

Quick Start

Provide a double-counting proof of a chosen identity by counting incidences in a finite bipartite relation.

Frequently Asked Questions about double_counting

High-intent search queries and answers about installing and using this skill.

FAQPage Schema

How does double counting prove combinatorial identities?▼

Double counting proves combinatorial identities by counting incidences in a finite bipartite relation R ⊆ A × B. Summing over the A-side and B-side yields two expressions for the total count, and equating them establishes the identity.

How do I prove the handshaking lemma and Vandermonde convolution in Lean?▼

Prove the handshaking lemma and Vandermonde convolution in Lean by structuring the proof around Finset-like sums and incidence counts. This Skill formalizes the bipartite relation decomposition to equate sums over both sides.

What basic set theory knowledge is needed for counting in two ways?▼

Counting in two ways requires basic set theory and finite counts. You need to understand finite sets, bipartite relations R ⊆ A × B, and how to compute Finset-like sums over both sides to apply the technique correctly.

What is the best way to equate sums over finite sets for binomial identities?▼

The best way to equate sums over finite sets for binomial identities is double counting. Define a finite bipartite relation, count total incidences by summing over each side separately, and equate the resulting expressions to derive the identity.

When should I not use double counting for finite set proofs?▼

You should not use double counting for finite set proofs when your problem cannot be modeled as a finite bipartite relation R ⊆ A × B. The technique requires that both sides admit natural decompositions yielding meaningful Finset-like incidence sums.