Tagged Questions

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
1answer
468 views

combinatorics - partitions of sets

The question is this: In how many partitions of $\{1,2,\ldots,n\}$ into three disjoint sets, $A$, $B$, and $C$, are there no two consecutive numbers in the set $A$? thanks!
2
votes
2answers
338 views

Stirling numbers of the second kind with max cardinality

We know that Stirling numbers of the second kind is the number of ways to partition a set of $n$ elements into $m$ nonempty sets. My question is what's the number ways if the max cardinality of all ...
1
vote
2answers
2k views

Number of equivalence relations on a set

If a set has $n$ elements then what are maximum number of equivalence classes and equivalence relations possible on it?
4
votes
1answer
148 views

A number theoretic function to characterize midpoint free subsets

Recently, I was going over a curious recreational math paper titled "On the Diagonal Queens Domination Problem". The main result of the paper is establishing the minimum value $diag(n)$ of number of ...
2
votes
1answer
297 views

Applications of Helly's theorem to problem solving

Helly's Theorem states the following: Suppose that $X_1,X_2,...,X_n$ are convex sets in $\mathbb{R}^d$, such that for any $|I|\leq d+1$, $\cap_{i\in I}X_i \neq \emptyset$. Then $\cap_{i=1}^{n}X_i ...
5
votes
1answer
441 views

Explanation/Intuition behind why $C_n$ counts the number of triangulations of a convex $n+2$-gon?

I was reading about the Catalan numbers on wikipedia, because it seems like they show up quite a bit. I'm reading some of the examples in the applications to combinatorics section. Some of them make ...
29
votes
3answers
3k views

The Hexagonal Property of Pascal's Triangle

Any hexagon in Pascal's triangle, whose vertices are 6 binomial coefficients surrounding any entry, has the property that: the product of non-adjacent vertices is constant. the greatest common ...
10
votes
6answers
5k views

Proving Pascal's Rule : ${{n} \choose {r}}={{n-1} \choose {r-1}}+{{n-1} \choose r}$ when $1\leq r\leq n$

I'm trying to prove that ${n \choose r}$ is equal to ${{n-1} \choose {r-1}}+{{n-1} \choose r}$ when $1\leq r\leq n$. I suppose I could use the counting rules in probability, perhaps combination= ...
2
votes
2answers
86 views

what is some polynomial bound of the following expression?

I have the expression (for some $k$ and $r$ natural numbers): $\sum_{l=0}^r {l \choose k}$. Is there a way to bound this expression using a polynomial of degree which is linear in $k$ (or polynomial ...
11
votes
1answer
3k views

6-letter permutations in MISSISSIPPI

How many 6-letter permutations can be formed using only the letters of the word, MISSISSIPPI? I understand the trivial case where there are no repeating letters in the word (for arranging smaller ...
2
votes
3answers
463 views

Probability of Sum of Different Sized Dice

I am working on a project that needs to be able to calculate the probability of rolling a given value $k$ given a set of dice, not necessarily all the same size. So for instance, what is the ...
2
votes
1answer
757 views

Figuring out possible combinations with restrictions

OK, so I am choosing 4 letters/numbers out of 10 possible letters. These letters are X,Y,LT,LB,RT,RB,U,D,L,R. The first three letters can be any one of these, but must contain at least one X or Y. The ...
4
votes
2answers
1k views

How many ways can $r$ nonconsecutive integers be chosen from the first $n$ integers?

During self-study, I ran across the question of how many ways six numbers can be chosen from the numbers 1 - 49 without replacement, stipulating that no two of the numbers be consecutive. I can ...
3
votes
0answers
369 views

Multinomial Coefficients ! [closed]

I have come across a paper that has suggested a formula for "NUMBER OF MULTINOMIAL COEFFICIENTS NOT DIVISIBLE BY A PRIME"; but I don't understand the notation.Please help. The formula is: $ G(n,l,p)= ...
1
vote
3answers
213 views

Limit to Unique Combinations

Suppose you have a deck of cards. Each card has n images on it. Any two cards will have exactly one matching image. What would be the formula for the maximum number of unique images and the maximum ...
10
votes
3answers
469 views

On a combinatorial identity

I'm trying to prove that if we have the elementary symmetric polynomials that the following identity holds:(where $x = (x_1,..,x_n)$ is a vector of n variables) $$\sum_{k=0}^n e_k(x)^2 = x_1\cdots x_n ...
4
votes
1answer
201 views

Random permutations of Z_n

In http://www.springerlink.com/content/y19u81675243r237/fulltext.pdf, the author states the following without proof (equation 3.1): Consider a random permutation $\pi$ of $\mathbb{Z}_n$. What is the ...
2
votes
4answers
283 views

Combinatorial interpretations of elementary symmetric polynomials?

I have some questions as to some good combinatorial interpretations for the sum of elementary symmetric polynomials. I know that for example, for n =2 we have that: $e_0 = 1$ $e_1 = x_1+x_2$ $e_2 ...
1
vote
3answers
203 views

Counting matrices based on determinant and trace

Let $p$ be an odd prime number and $T_p$ is the following set of $2 \times 2$ matrices: $$ T_p = \left\{ A = \begin{bmatrix} a & b \\ c & a \end{bmatrix}\ \Biggm|a,b,c \in ...
8
votes
2answers
265 views

What is the most frequent number of edges of Voronoi cells of a large set of random points?

Consider a large set of points with coordinates that are uniformly distributed within a unit-length segment. Consider a Voronoi diagram built on these points. If we consider only non-infinite cells, ...
2
votes
1answer
789 views

How many eight digit numbers are there that contain both a 5 and a 6

So I'm revising my counting, and I looked at this problem and after a little bit of brainstorming I came up with the following solution. Number of 8 digit numbers containing both a 5 and a 6 = Number ...
4
votes
1answer
697 views

Stirling numbers of the second kind $S (r,k)$ - does one ever sum over $r$?

A Stirling number of the second kind, $S (r,k)$, is defined to be the number of ways one can partition an $r$-element set into $k$ subsets. Consider the following problem: You have $r$ ...
1
vote
1answer
192 views

Combinatorial Optimization Problem (can I/how do I solve this with integer programming?)

Inputs: 1) A set of M x N matrices, {A,B,C...N} containing only integers. 2) A single 1 x N matrix of floats, W (weights). I need to pull one row from each input matrix and sum values for each ...
4
votes
1answer
170 views

Number of permutations

Is there some easy way to compute number of particular permutations? Namely let $S_i$ be the number of permutations $(a_1,...,a_n)$, $\{a_1,\ldots,a_n\}=\{1,...,n\}$, satisfying the following ...
4
votes
1answer
174 views

Sort of Combination with repetitions

How many string exist of length 2M with 9 characters and without repeating a character more than M times? You can suppose that M is greater than 4. I know that my english is really bad so i'll give ...
25
votes
9answers
2k views

why is $\sum\limits_{k=1}^{n} k^m$ a polynomial with degree $m+1$ in $n$

why is $\sum\limits_{k=1}^{n} k^m$ a polynomial with degree $m+1$ in $n$? I know this is well-known. But how to prove it rigorously? Even mathematical induction does not seem so straight-forward. ...
3
votes
2answers
275 views

13 integers with each set of 12 integers

Take 13 integers. Prove that if any 12 of them can be partitioned into two sets of six each with equal sums, then all the integers are the same. Does anyone know if the general case with 2n+1 ...
3
votes
1answer
110 views

Software for proving sum identites

Summations can really get complicated - esp. when you have convoluted n-fold summations with all kinds of different indices. My question: Is there some software (or add-on) with which you can find ...
3
votes
2answers
315 views

For teaching: Combinatorial Construction Riddles

Can you give examples of combinatorial construction riddles, approachable by gifted high school students? Examples: Find a finite set $A$ and $B \subset 2^A$ such that any element of $A$ is covered ...
12
votes
4answers
1k views

Algebraic Proof that $\sum\limits_{i=0}^n \binom{n}{i}=2^n$

I'm well aware of the combinatorial variant of the proof, i.e. noting that each formula is a different representation for the number of subsets of a set of $n$ elements. I'm curious if there's a ...
5
votes
6answers
1k views

Proof of a combination identity:$\sum \limits_{j=0}^n{(-1)^j{{n}\choose{j}}\left(1-\frac{j}{n}\right)^n}=\frac{n!}{n^n}$

I want to ask if there is a slick way to prove: $$\sum_{j=0}^n{(-1)^j{{n}\choose{j}}\left(1-\frac{j}{n}\right)^n}=\frac{n!}{n^n}$$ Edit: I know Yuval has given a proof, but that one is not direct. ...
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
480 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
799 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
472 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
645 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
840 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
296 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
240 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 ...