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)

2
votes
3answers
110 views

Are these lines going to meet in exactly 2002 points?

There is a plane P.100 lines are on P.Is it possible to arrange them in a way such that they intersect in exactly 2002 points given that no three of them are concurrent? Any help is highly ...
-8
votes
0answers
44 views

mathematics question [closed]

QST: Class VIII has $58$ students. From this group a group of $8$ boys and $6$ girls was formed. From this small group in how many ways a group of $5$ can be chosen as to include at least $1$ girl?? ...
0
votes
1answer
21 views

Making all row sums and column sums non-negative by a sequence of moves

Real numbers are written on an $m\times n$ board. At each step, you are allowed to change the sign of every number of a row or of a column. Prove that by a sequence of such steps, you can always ...
1
vote
0answers
17 views

Understanding ILP formulations of combinatorial optimisation problems

I am having trouble understanding and producing integer linear programming formulations for combinatorial optimisation problems. I can understand basic ones like the knapsack problem: $min \quad ...
6
votes
3answers
93 views

Proving $\binom{n}{m}+2\binom{n-1}{m}+…+(n-m+1)\binom{m}{m} = \binom{n+2}{m+2}$

For $m,n\in\mathbb{N},\;n\geq m$, prove the following: $$ \tag{i}\binom{n}{m}+\binom{n-1}{m}+\binom{n-2}{m}+......+\binom{m}{m} = \binom{n+1}{m+1} $$ $$ ...
0
votes
1answer
13 views

Number of ways to sample a specific number of objects from a collection with several types of objects.

I'm trying to figure out the following combinatoric problem: Simple case: Suppose I have $N$ objects of two types with sizes $i_{1},i_{2}$ . I sample $n\leq N$ objects without returning, how many ...
1
vote
0answers
44 views

Finite partitions of $\mathbb{N}$ and relations betweens sets of natural numbers

Suppose that $R\subseteq \mathcal{P}(\mathbb{N})\times\mathcal{P}(\mathbb{N})$ is a relation such that $(x,y)\in R$ only if $|x|=|y|$. Say that a partition $P$ divides a set $x$ if $x$ is the union ...
0
votes
1answer
45 views

Combinatorics & Cupcakes

There are $10$ cupcakes left over after a birthday party: $3$ vanilla, $2$ red velvet, and $5$ chocolate. Each of the $8$ guests can take home as many of the cupcakes as they want. How many ways can ...
0
votes
0answers
20 views

Number of Crossing Cycles of length $3$ in a complete graph if we put $m$ edges on one side?

Alice and Bob don't play games anymore. Now they study properties of all sorts of graphs together. Alice invented the following task: she takes a complete undirected graph with $n$ vertices, ...
0
votes
1answer
101 views

Is there a term called 'GRAIL'?

I've been a talk with a PhD student about some graph issue and told me about GRAIL graph and have drawn it for me as you see in the picture, however, I try to generalize so-called "Grail graph" to ...
1
vote
1answer
39 views

A strange scheduling for $K_{24}$.

This question came from a question asked earlier today linked here The question implicitly asked how to make a schedule with his/her class of 24 students such that: 1) Everyday will consist of the ...
0
votes
0answers
17 views

Affine Weyl group as coxeter group

How do you write the affine Weyl group corresponding to type $A_n$ as a Coxeter group ?The generators are $s_0,s_1,s_2,\cdots ,s_n$ where $s_0$ corresponds to the highest root. What are all the ...
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 ...
3
votes
3answers
54 views

Grouping kids in Groups of $4$

How many different groups of $4$ can I create using $24$ students? I want to break my class of $24$ students into groups of $4$. I would like to create different groups each day until each student ...
0
votes
0answers
19 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 \\ ...
-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 ...
1
vote
2answers
55 views

Combination of $n$ objects taken $p$ at a time where $n$ contains $r$, $s$, and $t$ identical objects.

I am talking about something like this: $ N = \{2, 3, 3, 3, 5, 5, 7\}$ $ n = 7$ $ s=3 $ $t=2$ In my case specifically, those numbers in $N$ are the prime factors of a number $Z$ repeated the number ...
0
votes
1answer
51 views

Question regarding Application of Combinations and Permutations (HW Problem)

I have a midterm I am studying for and I don't have the solutions to this homework problem. Can anyone please explain how to do it? I would really appreciate it. Here is the problem: I googled the ...
3
votes
2answers
52 views

Sum over two binomials identity

So while trying to count the number of configurations in a statistical mechanics research problem I come across this lovely sum: $$\sum_{i=0}^k \binom{i+r}{r} \binom{k-i+r}{r}$$ I scoured the ...
1
vote
3answers
125 views

Why do we subtract [Combinatorics]

I asked Here This question and I am still confused. I got that, for at least one group together there are: $$3 \cdot 9 \cdot \binom{6}{3, 3}$$ But why do we subtract: $3 \cdot 9 \cdot 4$. Lets ...
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 ...
-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 ...
3
votes
4answers
96 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.
13
votes
3answers
226 views

What is $\sum_{r=0}^n \frac{(-1)^r}{\binom{n}{r}}$?

Find a closed form expression for $$\sum_{r=0}^n \dfrac{(-1)^r}{\dbinom{n}{r}}$$ where $n$ is an even positive integer. I tried using binomial identities, but since the binomial ...
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
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 ...
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 ...
-1
votes
4answers
60 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 ...
3
votes
2answers
68 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 ...
-2
votes
2answers
76 views

In how many ways can 4 red, 3 blue and 2 green balls be arranged? [closed]

In how many unique ways can 4 red, 3 blue and 2 green balls be arranged if they are indistinguishable aside from color?
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 ...
2
votes
3answers
96 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 ...
8
votes
3answers
728 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 ...
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
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}$$ ??
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 ...
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
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 ...
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 ...
2
votes
1answer
38 views

Paths starting from a given node that touch each node a given number of times

How many paths starting from a given node touch each node a given number of times? We have a complete graph with vertices $1,2,3…j$. We want to know the number of paths of length $N$, starting from ...
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 ...
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
0answers
33 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, ...
4
votes
0answers
47 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
1answer
51 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?
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
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?
1
vote
2answers
49 views

Find all Functions so that $f(1) = 1$ and $f(2) = 2$

Let $F$ denote the set of all functions from $A=\{1, 2, 3, 4\}$ to $B=\{1, 2, 3, ..., 10\}$. Find and simplify the number of functions $f \in F$ so that $f(1) = 1$ and $f(2) = 2.$ My attempt to ...
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 ...