For 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 (4)

1
vote
0answers
29 views

What is the terminology of the collection of all possible combinations of the element of a set?

Let me explain my question better: Suppose I have a set $(1,2,3)$. Clearly, I have 6 ways to choose some elements from it: $$ (1),(2),(3),(1,2),(1,3),(2,3) $$ and I can make a collection to ...
4
votes
2answers
1k views

Probability of Posting a Quad and Trip on 4chan

Important Pre-Requisite Knowledge On the image board 4chan, every time you post your post gets a 9 digit post ID. An example of this post ID would be $586794945$. A Quad is a post ID which ends with ...
-1
votes
0answers
39 views

Number of possibilities of a dataset

I have objects defined by $20$ dimensions rated from $1$ to $10$ with no decimal. How many distinct objects can I have ? Ok it's $10^{20}$. But how many distinct objects Can I have considering that ...
0
votes
0answers
18 views

Proving a combinatorics identity (permutations and combinations) [duplicate]

Prove the following identity by interpreting their meaning combinatorially. $$\left( \begin{array}{c} n \\ r \\ \end{array} \right)=\left( \begin{array}{c} n-1 \\ r-1 \\ ...
3
votes
2answers
62 views

Number of unique binary strings containing at least m sequential 1s

Let $Z\left(n,m\right)$ be the number of unique binary strings of length $m$ containing at least one instance of $n$ consecutive 1's. I am trying to come up with an expression for $Z$, preferably ...
0
votes
1answer
29 views

Lower bound on circuit size of a Boolean function

I'm currently reading a proof of the following claim from the notes http://www.cs.berkeley.edu/~sinclair/cs271/n5.pdf which can be found on the bottom of page 6. I'd like to point out i'm interested ...
11
votes
1answer
120 views

Asymptotic Behavior of a Sum with Binomial Coefficients

The Problem: Find the asymptotic behavior (with respect to $n$) of the following sum $$\sum\limits_{j = 3}^n \binom{n}{j} \frac{(j - 1)!}{2\cdot n^j}. $$ Where the Problem Comes From: If we ...
5
votes
1answer
138 views

The locker puzzle - predetermined strategy

The question is related to the famous locker puzzle: The director of a prison offers 100 prisoners on death row, which are numbered from 1 to 100, a last chance. In a room there is a cupboard with ...
3
votes
4answers
449 views

Pólya's urn scheme, proof using conditional probability and induction

Problem An urn contains $B$ blue balls and $R$ red balls. Suppose that one extracts successively $n$ balls at random such that when a ball is chosen, it is returned to the urn again along with $c$ ...
1
vote
2answers
57 views

Ordered pairs of permutations in symmetric group

How many ordered pairs $\left(\alpha_1,\alpha_2\right)$ of permutations in symmetric group $S_n$ that commute: $$\alpha _1 \circ \alpha _2 = \alpha _2 \circ \alpha _1\,,$$ where $\alpha _1, \alpha _2 ...
8
votes
3answers
727 views

How many different dice exist? That is, how many ways can you make distinct dice that cannot be rotated to show they are the same?

Dice are cubes with pips (small dots) on their sides, representing numbers 1 through 6. Two dice are considered the same if they can be rotated and placed in such a way that they present ...
5
votes
0answers
103 views

Maximal Hamming distance

Here is a combinatorial problem: let $\Sigma=\{\alpha_1,\ldots,\alpha_n\}$ be an alphabet and we consider any words over $\Sigma$ of length $n$. We also define over the set of such words the Hamming ...
2
votes
3answers
95 views

Coin toss - winning by tossing $k$ heads first

Two players A and B take turns throwing a fair coin. The players that tosses $k$ heads first wins. Let player A begin. What is the likelihood p that players A wins? For a given $k$ the solution is ...
0
votes
3answers
131 views

Counting Number of even and distinct digits

The Question was: The number of even four-digit decimal numbers with no digit repeated. So the first digit cannot be 0 so there are 9 ways to choose a digit. Then for the 3rd, 2nd and 1st digits ...
2
votes
2answers
148 views

2011 AIME Problem 12, probability round table

Nine delegates, three each from three different countries, randomly select chairs at a round table that seats nine people. Let the probability that each delegate sits next to at least one delegate ...
3
votes
4answers
95 views

Application of Pigeon-Hole Principle to balls in bins.

Given $n$ balls placed in $m$ boxes, prove that if $n < \frac{m(m-1)}{2}$ then at least two boxes have same number of balls in them.
6
votes
2answers
67 views

selection of balls of three colors with restrictions

I have asked a similar question here and answers were very helpful. I tried doing similar questions and could solve them comfortably. However, I myself came up with a question like this and wondering ...
1
vote
1answer
28 views

3Finding minimum $f(k)$ ($n$: fixed natural number and $k=0,1,2,\cdots,n-1$

I would appreciate if somebody could help me with the following problem Q. Finding minimum $f(k)$ where $n \in \mathbb N$ and $k = 0,1,...,n-1$. $$f(k)={2k+1 \choose k} \times {2n-2k-1\choose n-k}$$ ...
-2
votes
1answer
51 views

Proof: A matrix with $m$ rows and $n$ colums has $nm$ entries.

How to prove rigorously the following statement: A matrix (a collection of numbers $a_{ij}:1\leq i \leq m, 1\leq j \leq n)$ with $m$ rows and $n$ colums has $nm$ entries. By rigorously I mean ...
2
votes
2answers
85 views

A combinatorial identity No. 2

I have no idea how to simplify ( if possible at all ) this sum $$\sum_{k=0}^{n}(-1)^k\binom{x}{n-k}\binom{y-2x}{k}2^k$$ It would be fine if a 1-binomial expression formula would result.
1
vote
0answers
46 views

Countably many projections on more than continuos vector space with trivial commutant?

Is there such an example? An $\mathbb{F}_2$-vector space $V$ of dimension strictly more than the continuos $c=|2^{\mathbb{N}}|$, and a numerable set of commuting $\mathbb{F}_2$ projections ...
3
votes
2answers
170 views

Find three $10\times10$ orthogonal Latin squares.

Can one find three $10\times 10$ mutually orthogonal Latin squares? Does anyone know if there is a mathematical "trick" in finding mutually orthogonal Latin squares? Or is it basically trial and ...
3
votes
2answers
67 views

Probability to draw two particular cards from a deck.

Given is a deck of 52 cards and the question is, what is the probability to draw an 8 and a Q (drawn without replacement). Here is what I did: The sample space should be $52 \choose 2$. Since for ...
1
vote
3answers
987 views

Number of equivalence relations

How many different equivalence relations can be defined on a set of five elements?
-1
votes
4answers
58 views

How many ways can we arrange 7 books, including 2 math books and 1 physics book, with the math books next to each other and left of the physics book?

I have 7 books I want to arrange on a shelf. Two of them are math books, and one is a physics book. How many ways are there for me to arrange the books if I want to put the math books next to each ...
27
votes
7answers
2k views

Beautiful identity: $\sum_{k=m}^n (-1)^{k-m} \binom{k}{m} \binom{n}{k} = \delta_{mn}$

Let $m,n\ge 0$ be two integers. Prove that $$\sum_{k=m}^n (-1)^{k-m} \binom{k}{m} \binom{n}{k} = \delta_{mn}$$ where $\delta_{mn}$ stands for the Kronecker's delta (defined by $\delta_{mn} = ...
1
vote
1answer
40 views

Binary tree of splitting that separates point over every set?

Is the following true? Let I be any set. For me a binary tree of splitting of I will be the following: start with $I_0=I$, at the step $n+1$ take the set of step $n$ and split each of them in two ...
1
vote
1answer
39 views

Distinguishability in Round Table Combinatorics

I have stumbled upon many questions, and one of the weaknesses is the ability to test if the concept is distinguishable or not. For example this: Nine delegates, three each from three different ...
-1
votes
1answer
33 views

Combinatoric meaning of multinomial coefficients

$$\binom{n}{k}$$ means how many ways there are to choose $k$ objects from $n$ total objects. What is the combinatoric meaning of: $$\binom{n}{k_1, k_2, ... , k_n}$$ ??
3
votes
1answer
52 views

Cutting a paper with the smallest number of cuts

You want to cut a piece of paper of length $N$ to $N$ pieces of length 1. It is not allowed to fold the paper, but if two or more previously-cut pieces of paper have the same length, it is allowed to ...
-3
votes
3answers
41 views

The number of one to one functions [closed]

If $A=\{1, 3, 5, 7\}$ and $ B=\{1, 2, 3, 4, 5, 6, 7, 8\}$ then the number of one to one functions from $A$ into $B$ is $ A)1340$ $B)1860$ $C)1430$ $D)1880$ $E)1680$
-1
votes
1answer
345 views

Find sum of all permutations

We call two arrays A and B with length n almost equal if for every i (1 <= i <= n) ...
0
votes
0answers
24 views

functional equation from a recurrence relation

Hoe can we get a functional equation from a recurrence relation? Lets say I have a recurrence relation $P_n(x)=a\cdot P_{n-1}(x)-b\cdot P_{n-1}(x)$. We let $\sum P_m(x) t^n=P(x,t)$ and now we have to ...
1
vote
2answers
343 views

Gram Determinant equals volume?

I have been trying to solve this problem of finding the 'n-volume' of a paralleletope spanned by m vectors, where clearly m =< n. In general, for computational purposes, what I have managed to do ...
3
votes
1answer
111 views

composition of an integer number

Given two positive integers $m$ and $n$. I would like one special non-negative solution to the following system (which is related to a composition of an integer number): $$\begin{cases} \sum a_i = m ...
2
votes
3answers
145 views

Permutations of the elements of $\mathbb Z_p$

Let $p$ be prime. Describe all permutations $\sigma$ of the elements of $\mathbb Z_p$, having the property that $\{\sigma(i)-i: i\in\mathbb Z_p\}=\mathbb Z_p$ (Added by Robert Lewis in an attempt ...
2
votes
4answers
67 views

Number of Interesting Quadruples

Define an ordered quadruple of integers $(a, b, c, d)$ as interesting if $1 \le a<b<c<d \le 10$, and a+d>b+c. How many interesting ordered quadruples are there? This is a bit of trouble ...
4
votes
3answers
884 views

Number of spanning trees in a ladder graph

Let $L_n$ be the ladder graph formed from two $n$-vertex paths by joining corresponding vertices. For example $L_4$ is the following I have to find a recurrence $\langle t\rangle$ where $t_n$ is ...
0
votes
4answers
47 views

selection of balls

A jar contains 17 red balls and 22 blue balls. How many ways are there to choose, without replacement, 8 balls from this jar. This question is already answered here . Answer for this is 39C8 But ...
4
votes
0answers
46 views

Ramsey number $R(K_4,K_4,K_4)$.

I've done a bit of googling, but I can't seem to locate any bounds for $R(4,4,4)$. Here, $R(n_1,n_2,n_3)$ is the generalized Ramsey number where $n_1,n_2,n_3$ are orders of complete graphs. So, in ...
0
votes
2answers
69 views

Can this binomial polynomial sum be simplified?

$$\sum_{k=0}^{n} \binom{n}{k} k^d$$ where $d$ is some fixed positive integer. Is this a well known sum that has a faster-than-$O(n)$ evaluation? It looks similar to Faulhaber's formula, except with ...
0
votes
1answer
50 views

Sum of digits of permutations and combinations of a given set of digits [closed]

What is the sum of all $5$-digit numbers formed from $\{2,3,4,4,6,0\}$ without allowing repetition? What is the sum with repetition allowed?
0
votes
0answers
32 views

How to count the number of unique combination of numbers in a set N, whose products equal to K?

Let K be the number 32, and N be the set of its factors. K = 32 N = {2, 4, 8, 16} How many unique combination of numbers are there in N, whose product is equal to K ? The answer is 6, ...
17
votes
4answers
4k views

Number of ways to partition a rectangle into n sub-rectangles

How many ways can a rectangle be partitioned by either vertical or horizontal lines into n sub-rectangles? At first I thought it would be: ...
2
votes
2answers
147 views

2014 iberoamerican olympiad Problem 3

2014 points are placed on a circumference. On each of the segments with end points on two of the $2014$ points is written a non-negative real number. For any convex polygon with vertices on some of ...
2
votes
1answer
13 views

Partition lattice-maximal chains

Show that the number of maximal chains in the partition lattice $\prod _n$ is equal to $\dfrac{(n-1)!n!}{2^{n-1}}$. I showed that $\prod _n$ is graded lattice, so all maximal chains has the same ...
0
votes
2answers
89 views

The probability that each delegate sits next to at least one delegate from another country

Nine delegates, three each from three different countries, randomly select chairs at a round table that seats nine people. Let the probability that each delegate sits next to at least one delegate ...
15
votes
1answer
171 views

Prove a matrix of binomial coefficients over $\mathbb{F}_p$ satisfies $A^3 = I$.

(This problem is problem $1.16$ in Stanley's Enumerative Combinatorics Vol. 1). Let $p$ be a prime, and let $A$ be the matrix $A = \left[\binom{j+k}{k} \right]_{j,k = 0}^{p-1}$, taken over the ...
0
votes
2answers
103 views

Sum of roots of binary search trees of height $\le H$ with $N$ nodes

Consider all Binary Search Trees of height $\le H$ that can be created using the first $N$ natural numbers. Find the sum of the roots of those Binary Search Trees. For example, for $N$ = 3, $H$ = 3: ...
0
votes
0answers
25 views

How to calculate sum of LCMs [duplicate]

How to solve this problem? Given n, calculate the sum LCM(1,n) + LCM(2,n) + .. + LCM(n,n). Is there any way to solve it by math?