In combinatorics, double counting, also called counting in two ways, is a combinatorial proof technique for showing that two expressions are equal by demonstrating that they are two ways of counting the size of one set. In this technique, which van Lint & Wilson (2001) call “one of the most important tools in combinatorics,” one describes a finite set X from two perspectives leading to two distinct expressions for the size of the set. Since both expressions equal the size of the same set, they equal each other.
Famous quotes containing the words double and/or counting:
“I grew up confidently expecting to have a profession and earn my own living, and also confidently expecting to be married and have children. It was fifty-fifty with me. I was just as passionately determined to have children as I was to have a career. And my mother was the triumphant answer to all doubts as to the success of this double role. From my earliest memory she had more than half supported the family and yet she was supremely a mother.”
—Crystal Eastman (1881–1928)
“If all power is in the people, if there is no higher law than their will, and if by counting their votes, their will may be ascertained—then the people may entrust all their power to anyone, and the power of the pretender and the usurper is then legitimate. It is not to be challenged since it came originally from the sovereign people.”
—Walter Lippmann (1889–1974)