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

1
vote
3answers
60 views

How many ways to arrange $6$ children in $4$ bedrooms if at most $2$ kids per room

If I have $6$ children and $4$ bedrooms, how many ways can I arrange the children if I want a maximum of $2$ kids per room? The problem is that there are two empty slots, and these empty slots are ...
1
vote
2answers
72 views

Find $R$ such that $\sum\limits_{n=2k}^{3k}\binom{3k}{n}\cdot{(R)}^n\cdot{(1-R)}^{3k-n}$ is constant for all $k\in\mathbb{N}$

Given $A_k = \sum\limits_{n=2k}^{3k}\binom{3k}{n}\cdot{(R)}^n\cdot{(1-R)}^{3k-n}$ with $0<R<1$. The sequence $A_k$ seems to be decreasing for $R\leq0.6$ and increasing for $R\geq0.8$. How can ...
3
votes
2answers
82 views

Prove by induction that $A_k = \sum\limits_{n=2k}^{3k}\binom{3k}{n}\cdot{(\frac{60}{100})}^n\cdot{(\frac{40}{100})}^{3k-n}$ is decreasing

I want to prove that the following sequence is monotonously decreasing: $A_k = \sum\limits_{n=2k}^{3k}\binom{3k}{n}\cdot{(\frac{60}{100})}^n\cdot{(\frac{40}{100})}^{3k-n}$ I think it should be ...
2
votes
0answers
48 views

Number of faces of a polytopal subdivision

Let $\mathcal{P}$ be a (bounded) polytope in $\mathbb{R}^d$ and let $\mathcal{C}$ be a polytopal subdivision of $\mathcal{P}$ [1]. Is there a known tight upper bound in the number of polytopes in ...
6
votes
4answers
68 views

$k$-th number in $N \times M$ Table

Given an array $A$ , where $A[i][j] = i\times j$ and $1 \leq i \leq N, 1 \leq j \leq M$ , then what is the best way to find the $k$-th number in this array , if we order them into a single array in ...
1
vote
1answer
26 views

Writing $n$ as the sum of $m$ positive integers (without order)

Let $p(n,m)$ denote the number of ways of writing the integer $n$ as a sum of $m$ positive integers, regardless of any ordering. Prove that $p(n,m)=0$ if $m>n$ Prove that $p(n,1)=1$ ...
0
votes
1answer
30 views

Permutation problem - How many permutations are there such that no two numbers are immediately adjecent? [duplicate]

Consider the set of numbers 1,1,2,2,3,3,4,4. How many permutations are there such that no two identical numbers are immediately adjacent?
1
vote
0answers
26 views

Finding an array of numbers knowing the distribution and possible values

There is an array of 16 unknown numbers, which I need to find. I know that numbers are whole and can take values from 0 to 7. I also know what values the numbers can take in the array. I will give an ...
2
votes
0answers
45 views

hat matching problem (Ross, p.41)

I'm studying Ross's probability book, and kind of got stuck on the matching problem. Suppose that each of N men at a party throws his hat into the center of the room. The hats are first mixed up, and ...
0
votes
0answers
42 views

An equation on Catalan number [closed]

Catalan numbers have the form $C_n=\frac{1}{n+1}\binom{2n}{n}$ prove: $C_{n+1}=\sum_{m+k=n}C_mC_k$ I tried to expand $C_n$ but soon get confused..
1
vote
1answer
38 views

Number of subsets intersecting certain sets

I've puzzling this for a while, and I'm starting to doubt that there is a reasonable-looking closed form; and if you could give me some pointers towards which sorts of techniques I might want to look ...
0
votes
1answer
37 views

Expected Value Intermediate Counting Problem

A palindrome is chosen at random from the list of all 6-digit palindromes, with all entries equally likely to be chosen. (Recall that a palindrome is a number that reads the same forward and ...
2
votes
1answer
42 views

Partition of graph with maximal score

Let $G=(V,E)$ be an undirected graph. Suppose that we partition the nodes into groups $C_1,C_2,\ldots,C_k$. The score of group $C_i$ is $E(C_i)/n(C_i)$, where $E(C_i)$ is the number of edges within ...
5
votes
1answer
110 views

Combinations mod $n$ property

So after some "fooling around" I came across this property in Pascal's triangle (which seems to repeat, and makes a lot of sense): $\begin{pmatrix} n \\ k \end{pmatrix} \mod n = \begin{cases} n ...
1
vote
0answers
34 views

A Vandermonde like identity for binomial coefficients

The Vandermonde identity is given by $ \left(\begin{matrix} m + n \\ j \end{matrix}\right) = \displaystyle\sum_{j=0}^k \left(\begin{matrix} m \\ j \end{matrix}\right)\left(\begin{matrix} n \\ k-j ...
1
vote
2answers
48 views

4 pairs of identical pens.

Say I have 4 pairs of identical pens (say red, blue, green and black). How many ways can I arrange them such that no two identical pens are next to each other? Inclusion/Exclusion works (I get 864) ...
2
votes
1answer
28 views

Arrangements of the word ISOMORPHISM

Say I want to arrange the letters of the word ISOMORPHISM, such that no two vowels are next to each other but the vowels are in alphabetical order. What I'd do is firstly consider the consonants ...
1
vote
0answers
23 views

Weak compositions with bounded partial sums

Is there an easy way to count the number of weak m-compositions of n whose partial sums are lower bounded by some function? Example: Let K be a weak 3-composition of 4 K = (k1, k2, k3) Let s(t) be ...
0
votes
1answer
79 views

How many squares can be formed from n equidistant points in a circle?

I am trying to find a general formula for finding the number of squares that can be formed from n points that are equidistant from each other and placed on the circumference of a circle, I started ...
0
votes
2answers
57 views

How many positive integer solutions are there to the inequality $x_1+x_2+…+x_r\le n$?

The original problem is there are $r$ identical boxes and $n$ identical balls. Every box is nonempty. Then how many ways of putting balls in boxes? It is equivalent to the problem of finding ...
0
votes
1answer
47 views

How do 3 points define a plane?

I was solving a combinatorics problem which asked me to find the number of planes that can be constructed from a set of 25 points such that no 4 points in the set of 25 points are co-planar and then I ...
-1
votes
3answers
85 views

Trailing zeroes on factorial? [closed]

How many zeroes are at the end of the product (100!)(200!)(300!) when you multiply it all out? Thank you for your help in advance.
0
votes
0answers
20 views

Probability of x pocket pairs at a table of n people (NLHE)?

With n people at a table, what is the probability that x of them are dealt pocket pairs? There are several easy ways to approximate this but I was wondering there was an elegant solution. Any takers?
1
vote
0answers
67 views

Geometrical application of generation function for permutation

It is quite well known that the generation function for permutations is represented as $$(1+x)(1+x+x^2)\dots(1+x+x^2+x^3...+x^{nāˆ’1})$$ (See, e.g., question The generating function for permutations ...
0
votes
1answer
41 views

Intermediate to Advanced level Counting Problem [closed]

In how many ways can we fill a 3 by 3 grid with 0s and/or 1s, so that every row and every column has an odd total?
-1
votes
1answer
177 views

Number of ways to win chocolate game

Alice and Bob are playing a game. They have N containers each having one or more chocolates. Containers are numbered from 1 to N, where ith container has A[i] number of chocolates. The game goes like ...
0
votes
1answer
63 views

Is this solution correct? 4

There are $3$ black balls and $18$ white balls. In how many ways the balls can be arranged such that no two black balls are together? Solution: The number of ways of arranging all the balls ...
0
votes
0answers
45 views

generating function combinatorics solution

I am studying generating functions in combinatorics, and came across a problem that has already been posted here: Generating function and combinatorics =x^10(1-x^6)^10 * (1+x+x^2....)^10 I ...
1
vote
3answers
32 views

Number of ways of walking up stairs and Recurrence relation

Suppose you want to walk up a staircase of $6$ steps, and can take $1, 2$ or $3$ steps at a time. How many ways are there to walk the $6$ steps? It seems hard to count the number of ways of walking ...
2
votes
0answers
25 views

Ehrhart polynomial of lattice tetrahedrons in $\Bbb{R}^4$

Let $\lbrace v_1 , v_2, v_3 , v_4 \rbrace \subset \Bbb{Z}^4$ be linearly independent, and denote by $P$ the convex hull of this set. Now, $P$ is a 3-polytope residing in four-dimensional space. What's ...
1
vote
3answers
52 views

Question regarding permutations and combinations?

Hi, I was just wondering on how you are supposed to approach this question. I keep getting 114 as an answer, but the answers say it is 174. How would anyone do this question, because I feel like I'm ...
1
vote
1answer
132 views

What is the count of the strict partitions of n in k parts not exceeding m?

Lets say we had a $k,m,n \in \mathbb{N}$ where $k < m \le n$. How many different sets $X_1,..,X_m$ with $|X_i|=k$ for $i=1,..,m$, where the sets do not include duplicates, for which the sum of ...
15
votes
1answer
2k views

Why are there only a few known Ramsey numbers?

Can someone explain in a simple way, why there are so few known exact Ramsey Numbers? I guess it's because there are no efficient algorithms for this task, but are there so many combinations to test? ...
9
votes
1answer
86 views
+150

Blocking lines of length $5$ in a $7 \times 8$ matrix; how can we know the solutions have a specific form?

A friend shared with me the following puzzle he encountered in a Chinese math competition: In a $7 \times 8$ matrix, we place tokens so that any straight line of length $5$ (horizontal, vertical, ...
7
votes
1answer
80 views

The rows continue to be different to each other

In each position of an $n \times n$ matrix there is a number. We know that all the rows of the matrix are different from each other. Show that we can delete a column so that the rows of the matrix ...
2
votes
1answer
93 views

Tough combinatorics problem

We have an urn containing $n_a$ tiles labelled "A", $n_b$ ones labelled "B", and $n_c$ tiles labelled "C". We also have a string of letters consisting of $s_a$ occurrences of the letter "A", $s_b$ ...
3
votes
1answer
68 views

Counting possible combinations to open a lock( 2006 ACM ICPC)

I was working on a problem in a coding competition and I began to wonder about the analytical (mathematical) solution to this problem. I am not even sure how to go about counting this. Any ideas will ...
1
vote
1answer
39 views

How many combinations can be made with these rules? (game of Dobble) [duplicate]

The game called Dobble consists of a deck of cards; each card contains 8 symbols from a set of 50. The deck is made so that any two cards have exactly one symbol in common. (The idea of the game is ...
0
votes
2answers
76 views

please help me ( probabilities )

please let me know if my answer true or false Three numbers are chosen at random without replacement from the set {0, 1, 2, 3, ... , 10}. Calculate the probabilities that for the three numbers drawn ...
0
votes
1answer
26 views

Linear Constraints Solution Existence

how can one decide if $$A*t\ge b$$ $A$ is a Matrix with integer Entries and $t$ is a Vector with integer Entries, $b$ is a fixed Vector with integer Entries exists?
1
vote
2answers
33 views

Counting exercises - Solution verification.

i'm studying some combinatorics and i came up in the following exercises. Suppose we are given a set $U$ of $n$ elements. Suppose $A \subset U$ has $k$ elements. Determine the number of subsets ...
0
votes
1answer
26 views

Finite sum equaling Kronecker Delta

could anyone help understand how $$\sum_{j=0}^{n-r}\binom{n-r}{j}*(-1)^{j} = [1 + (-1)]^{n-r}$$ I see that if $j=0$, i get $1=1^{n-r}$, and if $j=n-r$, i get $(-1)^{n-r},$ but what about the rest of ...
0
votes
1answer
72 views

How to find out the number of ways to solve Instant Insanity

Problem : We are given 4 cubes. The 6 faces of every cube are variously colored - Blue, Green, Red or White. Stack the cubes on top of another in such a way that no color appears twice on any of the ...
0
votes
1answer
26 views

Small remarkable matroids

I'm working on a problem involving matroids $M=(E,\mathfrak{C})$ (here $E$ is the ground set, $\mathfrak{C}$ the set of circuits) with a "small" ground set $E,$ in the sense that $\sharp(E)\leq7$ I ...
3
votes
0answers
27 views

Does there exist Latin square critical sets for which deleting any entry results in arbitrarily many completions?

For those familiar with Latin squares terminology, I'll get straight to the point: Q: For all $N \geq 2$, does there exists a critical set $C$ (for a Latin square of any finite order) such that ...
5
votes
2answers
54 views

Putting objects in a line.

I'm working on a project outside of school, and I've run into a bit a problem. I thought, maybe there are some problem solvers on the internet who would enjoy this. I have 8 balls, 3 red cubes, and ...
2
votes
2answers
55 views

The Weyl group of A_3

Could someone please list all elements of the Weyl group of the root system $A_3$ in terms of simple reflections. In this case the Weyl group is $S_4$. Its strange that GAP failed to list all elements ...
0
votes
0answers
29 views

Inversion and permutations

Let call two arrays A and B with length n almost equal if for every i (1 <= i <= n) CA(A[i]) = CB(B[i]). CX[x] equal to number of index j (1 <=j <= n) such that X[j] < x. For two ...
1
vote
1answer
39 views

Examples of Matroids

Preparing an exam, I'm looking for examples of matroids and maybe hints or references on proves that they are. (what I already know are representable matroids and graphic matroids)
4
votes
1answer
37 views

Chromatic number of generalized hypercube

It's clear that the chromatic number of $Q_n$ is $2$. But what about the graph $G$ with vertex set ${n}^{(r)}$ where two vertices are adjacent if and only if their coordiantes differ by one? Can't ...