This tag is for basic questions about the study of finite or countable discrete structures — specifically how to count or enumerate elements in a set (perhaps of all possibilities) or any subset. It includes questions on permutations, combinations, bijective proofs, and generating functions. ...

learn more… | top users | synonyms (5)

2
votes
4answers
3k views

Algorithm for generating integer partitions

I'm looking for a fast algorithm for generating all the partitions of an integer up to a certain maximum length; ideally, I don't want to have to generate all of them and then discard the ones that ...
5
votes
2answers
264 views

What's the name of this problem?

Problem: count the number of distinct ways to write number X as the sum of numbers {a, b, c...} with replacement. For instance, there are 3 ways to write 11: 2+2+7 2+2+2+2+3 2+3+3+3 And if I ...
8
votes
0answers
481 views

Combinatorial reasoning for the identity $\left ( \sum_{i=1}^n i \right )^2 = \left ( \sum_{i=1}^n i^3 \right ) $ [duplicate]

Possible Duplicate: Intuitive explanation for the identity $\sum\limits_{k=1}^n {k^3} = \left(\sum\limits_{k=1}^n k\right)^2$ There is the interesting identity: $$\left ( \sum_{i=1}^n i ...
4
votes
3answers
803 views

How many bytes contain exactly two 1's?

I know that the answer is C(8,2), but I don't get, why. Can anyone, please, explain it?
3
votes
2answers
2k views

Maximum number of regions formed by points on a circle

The question is : 6 points are located on a circle and lines are drawn connecting these points, each pair of points connected by a single line. What can be the maximum number of regions into which ...
16
votes
3answers
2k views

Consecutive birthdays probability

Let $n$ be a number of people. At least two of them may be born on the same day of the year with probability: $$1-\prod_{i=0}^{n-1} \frac{365-i}{365}$$ But what is the probability that at least two ...
5
votes
2answers
112 views

Do bounded permutations of N leave an initial segment invariant?

Let $p$ be a permutation of $\mathbb{N}$. We say that $p$ is bounded if there exists $k$ so that $|p(i)-i| \le k$ for all $i$. If $p$ is bounded, must there exist $M>0$ such that $p(\{1,2,\ldots, ...
6
votes
1answer
473 views

Guessing a hidden number on a cube

You are and your friend are given a list of N distinct integers and are told this: Six distinct integers from the list are selected at random and placed one at each side of a cube. The cube is placed ...
2
votes
3answers
256 views

Combinatorial proof of $\Big|\prod\limits_{0 \leq i < j < N} (\zeta^j -\zeta^i)\Big| = \sqrt {N^N}$ for $\zeta \equiv \exp({2\pi i \over N})$

I've been playing with Fourier transform a little and discovered the identity quoted in the title. More precisely, writing the matrix for the Fourier transform in ${\mathbb Z} / N {\mathbb Z}$ as $$A ...
18
votes
1answer
726 views

Why is a general formula for Kostka numbers “unlikely” to exist?

In reference to Stanley's Enumerative Combinatorics Vol. 2: right after he has defined Kostka numbers (section 7.10), he mentions that it is unlikely that a general formula for $K_{\lambda\mu}$ ...
5
votes
1answer
646 views

Using one stack to find number of permutations

Suppose I have a stack and I want to find the permutations of numbers 1,2,3,...n. I can push and pop. e.g. if n=2: push,pop,push,pop 1,2 and push,push,pop,pop 2,1 if n=4 I can only get 14 from the ...
4
votes
1answer
327 views

Is there a combinatorial proof of this congruence identity?

Prove that $$\binom{2p}{p} \equiv 2\pmod{p^3},$$ where $p\ge 5$ is a prime number.
3
votes
1answer
338 views

Thue-Morse sequence cube-freeness proof from the Book

I'm TA-ing an intro class on theoretical CS, and this week class only covered the simplest concepts, such as words and languages. I wanted to take this chance to present some combinatorics on words, ...
3
votes
1answer
148 views

How many possible solutions for 6 wires?

Imagine 2 sets of 6 wires. How would I find how many possible connections there are? Every wire must be used to be considered a connection. ...
0
votes
2answers
842 views

How to create a graycode of N bits with a code-agnostic iteration function

I'm posting this as more of a theory/mathematic how-to followup to a stackoverflow question. The non-iterative method for calculating graycode depends on Log2N bytes, to store position information ...
2
votes
0answers
297 views

how many ways to construct a number

I am thinking about following problem, but am not able to find answer. In how many ways can a number be formed only using 3 digits (0, 1, 2) given following constraints with K and D:- 1) Each digit ...
5
votes
2answers
1k views

Derivation of the Partial Derangement (Rencontres numbers) formula

I'm looking for the method by which the partial derangement formula $D_{n,k}$ was derived. I can determine the values for small values of N empirically, but how the general case formula arose still ...
4
votes
1answer
199 views

“On the consequences of an exact de Bruijn Function”, or “If Ramanujan had more time…”

In this question on Math.SE, I asked about Ramanujan's (ridiculously close) approximation for counting the number of 3-smooth integers less than or equal to a given positive integer $N$, namely, ...
2
votes
1answer
241 views

Maximal number of vectors with (pairwise) negative scalar product

Consider $\mathbb{R}^n$ equipped with the standard scalar product. Let $f(n)$ denote the maximal cardinality of a set of vectors in $\mathbb{R}^n$ with a pairwise negative scalar product. What is ...
12
votes
2answers
235 views

Distinctness is maintained after adding some element to all sets

Let $S=\{S_1,S_2,\ldots,S_n\}$ be a set of $n$ distinct subsets with $S_i \subseteq \{1,\ldots,n\}$ for $i=1,\ldots, n$ then $k \in \{1,\ldots,n\}$ exists with $S_i \cup \{k\}$ is distinct for ...
5
votes
4answers
512 views

How to find unique multisets of n naturals of a given domain and their numbers?

Let's say I have numbers each taken in a set $A$ of $n$ consecutive naturals, I ask myself : how can I found what are all the unique multisets, which could be created with $k$ elements of this set ...
4
votes
1answer
145 views

Fixed points in a sequence of permutations

Let $S_3$ be the symmetric group on the three objects $x_1, x_2, x_3$. We are given a (countably infinite) sequence of permutations in $S_3$: $\sigma_1 \ , \ \sigma_2 \ , \ \sigma_3 \ , \ \ldots \ , ...
4
votes
1answer
525 views

Generating a Eulerian circuit of a complete graph with constant memory

(this question is about trying to use some combinatorics to simplify an algorithm and save memory) Let $K_{2n+1}$ be a complete undirected graph on $2n+1$ vertices. I would like to generate a Eulerian ...
1
vote
0answers
262 views

Interesting uses of Burnside's lemma? [duplicate]

Possible Duplicate: Nice application of the Cauchy?-Frobenius?-Burnside?-Pólya? formula Burnside's lemma states that the number of orbits in a group action is equal to the average ...
4
votes
3answers
439 views

Stirling numbers of the second kind on Multiset

Stirling numbers of the second kind S(n, k) count the number of ways to partition a set of n elements into k nonempty subsets.What if there were duplicate elements in the set?That is,the set is a ...
4
votes
2answers
393 views

Choosing seats for guests

You have a circular table with $N$ seats.$K$ bellicose guests are going visit your house of-course you don't want them to sit beside each other.As the host, you want to find out how many ways there ...
10
votes
3answers
629 views

Evaluation of the sum $\sum_{k = 0}^{\lfloor a/b \rfloor} \left \lfloor \frac{a - kb}{c} \right \rfloor$

Let $a, b$ and $c$ be positive integers. Recall that the greatest common divisor (gcd) function has the following representation: \begin{eqnarray} \textbf{gcd}(b,c) = 2 \sum_{k = 1}^{c- 1} \left ...
1
vote
0answers
102 views

Complexity of Counting the number of inducing $n$-gons

Definition: A $n$-gon is simple if it has no self intersection and is in general position if no pair of its edges are parallel. It is clear that by extending the edges of each simple $n$-gon in ...
2
votes
1answer
339 views

Total no. of balanced parenthesis with maximum nesting of d

Cn(the nth catalan number) counts the number of expressions containing n pairs of parentheses which are correctly matched How to count the possibilities if the maximum nesting level is fixed to d?
3
votes
0answers
189 views

Numbers generated from combination of 3's and 5's [duplicate]

Possible Duplicate: When do the multiples of two primes span all large enough natural numbers? We have to generate a number by using only 3's and 5's. For ex : ...
11
votes
3answers
1k views

Nice application of the Cauchy?-Frobenius?-Burnside?-Pólya? formula

Burnside's Lemma, whose list of names is longer than the proof, says that the number of orbits of a permutation group is the average number of fixed points of its elements. It's a very elegant result, ...
4
votes
2answers
527 views

How to find $\sum_{k=1}^n 2^kC(n,k)$?

How to find the sum of series, $$\sum_{k=1}^n 2^kC(n,k)$$
4
votes
2answers
399 views

Minimum number of X-subsets needed to cover all K-subsets

Assume I have a universe of N elements. The question is: How many sets of size $X$ are needed to assure that every set of K elements is a subset of (at least) one of these sets (where $K \ll X \lt ...
3
votes
1answer
206 views

Complexity of counting the number of Good-perfect matching in bipartite graph

Let's $G=(U, V, E)$ be a balanced bipartite graph which $|U|=|V|=n$ and $|E|=n*(n-1)$; All nodes in $U$ are connected to all nodes in $V$ except $u_i$ to $v_i$ for $1\leq i \leq n$. Definition1: ...
3
votes
1answer
321 views

What is a convenient way to convert a string of balanced parentheses to a corresponding “multiplication ordering” or rooted binary tree?

In an article by Tom Davis on Catalan numbers, Davis mentions several problems that are shown to be equivalent. One of them is the problem of determining the number of strings of $n$ pairs of balanced ...
7
votes
1answer
450 views

Parity of Perfect Matchings

Source: Lovasz, Plummer - Matching Theory I had a question related to the number of perfect matchings in a graph. While going through the 8th Chapter on Determinant and Matchings in the text I ...
5
votes
3answers
357 views

Prove that $\sum_{i=0}^n2^{3i} \binom {2n+1}{2i+1}$ is never divisible by 5

Question : Prove that the number is never divisible by 5.
24
votes
3answers
1k views

An example of a real-world map that is not 4-colourable?

The four-colour mapping theorem states that all maps can be four-coloured (adjacent regions receive distinct colours, and four different colours are used in total). However, the technical definition ...
4
votes
1answer
449 views

Calculating Total Amount of Money Based on Weight

Dealing with US Dollars... Assuming we know the weights of half-dollars, quarters, dimes, nickels, and pennies. Also assuming the weights remain constant (don't change from one quarter to another ...
11
votes
1answer
727 views

combinatorics olympiad problem - sort out a schedule

Interesting problem from a 2000 St. Petersburg school olympiad. There are 109 soldiers in a camp. Every night three of them go on watch patrol. Prove that it can be arranged so that after a while, ...
8
votes
2answers
906 views

Chess Master Problem

From Introductory Combinatorics by Richard Brualdi We have a chess master. He has 11 weeks to prepare for a competition so he decides that he will practice everyday by playing at least 1 game a day. ...
6
votes
1answer
975 views

Permutation with Duplicates

I could swear I had a formula for this years ago in school, but I'm having trouble tracking it down. The problem: I have 3 red balls and 3 black balls in a basket. I draw them out one at a time. How ...
1
vote
3answers
270 views

Probability of finding $m$ or more cells empty

I asked I question here trying to obtain clarification about how to follow a hint. In spite of the fine answers I received there, the hint doesn't look very helpful. I'd like to know a hint for the ...
1
vote
1answer
347 views

Lucas Numbers and Tilings

Show that $f_{n-1} + L_n = 2f_{n}$. So we need to find a $2$ to $1$ correspondence. Set 1: Tilings an $n$-board. Set 2: Tiling of an $n-1$-board or tiling of an $n$-bracelet. So we need to ...
4
votes
2answers
3k views

Number of even and odd subsets [duplicate]

Suppose we have the following two identities: $\displaystyle \sum_{k=0}^{n} \binom{n}{k} = 2^n$ $\displaystyle \sum_{k=0}^{n} (-1)^{k} \binom{n}{k} = 0$ The first says that the number of subsets ...
5
votes
1answer
203 views

Permutation Identity and Sum

Show that $\displaystyle 1+ \sum\limits_{k=1}^{n} k \cdot k! = (n+1)!$ RHS: This is the number of permutations of an $n+1$ element set. We can rewrite this as $n!(n+1)$. LHS: It seems that the $k ...
7
votes
1answer
450 views

Mathematics related to the card game SET

Last month, I was introduced to the card game SET. The game raises several interesting questions eg what's the probability that n randomly drawn cards contain k sets, is it possible to end with 12 (or ...
14
votes
7answers
5k views

Making Change for a Dollar (and other number partitioning problems)

I was trying to solve a problem similar to the "how many ways are there to make change for a dollar" problem. I ran across a site that said I could use a generating function similar to the one quoted ...
2
votes
2answers
161 views

Combinatorial Identity and Counting

Show that $\binom{2n}{2} = 2 \binom{n}{2}+n^2$. LHS: This is the number of pairs of $2n$ distinct elements. RHS: We can rewrite this as $2 \binom{n}{2}+ \binom{n}{1} \binom{n}{1}$. So you can ...
33
votes
3answers
2k views

What is the shortest string that contains all permutations of an alphabet?

What is the shortest string $S$ over an alphabet of size $n$, such that every permutation of the alphabet is a substring of $S$? I thought of this problem while reading a open problem on shortest ...