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
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.
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 ...
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 ...
2
votes
2answers
170 views

Making sense of combinatorics-based marketing hyperboles

Diablo 3 has 97 billion possible skill/trait builds. Per class. LessPop_MoreFizz, emphasis is mine. I used base two logarithm to claim "97 billion" configurations only are roughly 37 binary ...
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
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 ...
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) ...
3
votes
0answers
130 views

Derangement bijection

This is a generalization of this question. An $(n,k)$ partial permutation is an injection from $[k]$ to $[n]$. It can be thought of as word of length $k$ in symbols in $[n]$ without duplications. ...
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
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 ...
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$ ...
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 ...
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?
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 ...
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?
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
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 ...
2
votes
4answers
77 views

How to approach this type of combinatorics problems

Say we have a $16$ letter long word consisting only of $\{a,b,c\}$. How many possible words are there in which the letter $c$ appears $4$ times but there are no $2$ $c$'s next to one another? For ...
12
votes
5answers
502 views

Combinatorially showing $\lim_{n\to \infty}{\frac{2n\choose n}{4^n}}=0$

I am trying to show that $\lim_{n\to \infty}{\frac{2n\choose n}{4^n}}=0$. I found that using stirling's approximation, I can get: $$ \lim_{n\to \infty}{\frac{2n\choose n}{4^n}}= \lim_{n\to ...
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 ...
2
votes
0answers
24 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 ...
2
votes
2answers
397 views

How many 90 ball bingo cards are there?

In the UK there are 90 bingo balls. A bingo card consists of 9 columns and 3 rows. A row contains exactly five numbers and four blanks. A column consists of one, two or three numbers and never three ...
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 ...
1
vote
1answer
228 views

What is a relationship between sets and Trinomial Coefficient?

We know that the relationship between set with n Cardinality named A and Binomial Coefficient is all about subsets of the set A. Binomial Coefficients describes Cardinality of subsets for A set. But ...
2
votes
2answers
54 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 ...
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 ...
3
votes
3answers
440 views

Probability of having at least $K$ consecutive zeros in a sequence of $0$s and $1$s

I have a sequence of length $N$ consisting of $M$ ones and $N-M$ zeros. I am trying to find the number of possible arrangements that produce a sequence in which there exist at least K consecutive ...
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 ...
0
votes
2answers
75 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 ...
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 ...
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 ...
2
votes
2answers
96 views

Factorials of Non-Natural

$$n!=\int_{0}^{\infty}{e^{-x}x^{n}\:dx}$$ (a) I want to find a formula for the above and then prove it by induction. The answer according to Wolfram is $n!$, however I have no idea how to get there. ...
0
votes
1answer
240 views

Grasshopper in a tropical forest

There is a Grasshopper in a tropical forest. The grasshopper can jump only vertically and horizontally, and the length of the jump is always equal to x centimeters. A Grassshopper has found herself at ...
2
votes
2answers
3k views

How many ways can 10 teachers be divided among 5 schools?

In how many ways can ten teachers be divided among five schools? One answer is that each teacher can go to any of the five schools so there are $10^5$ possibilities. However, if you treat each ...
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 ...
1
vote
1answer
410 views

How to find different number of distinct integers from given set of number

How many different integers can be expressed as the sum of $3$ distinct numbers from the set $\{3, 10, 17, 24, 31, 38, 45, 52\}$? Could someone help me with this problem?
6
votes
1answer
251 views

Proving that G contains a cycle with at least $k+1$ edges

Let $k\geq 2$. Prove that if $G$ is $k$-regular, then $G$ contains a cycle with at least $k+1$ edges. The way I did it was to prove that the longest path in $G$ must have at least $k$ edges, and that ...
5
votes
2answers
123 views

How to count different card combinations with isomorphism?

Let's consider a standard deck of cards and say that two sets of cards are isomorphic if there exists permutation of colors that makes one set into another. For example: ...
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)
1
vote
1answer
70 views

Expected value over many trials

I am a poker player and was talking to my friend about expected value. He claimed that if you play far enough above your bankroll, expected value can be negative, even if you have a skill edge. I ...
0
votes
0answers
28 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
votes
2answers
27 views

common multiple polynominal time

Given $n$ rational numbers. Is there a polynominal time algorithm to compute a common denominator? My idea was for each number search for $k_i$ so that $k_i \cdot n_i$ is integer. Then the solution ...
6
votes
1answer
47 views

Does $K_{15,15}$ decompose into $K_{5,5}-C_{10}$ and $K_{5,5}-(C_6 \cup C_4)$ subgraphs?

Following on from this question: Q: Does $K_{15,15}$ decompose into $K_{5,5}-C_{10}$ and $K_{5,5}-(C_6 \cup C_4)$ subgraphs? or equivalently Q: Does there exist a $15 \times 15$ matrix ...
1
vote
1answer
78 views

How can I divide 30 people into 6 different groups of 5 people in 6 ways so that no two groups share two people?

I have a group of 30 people that I need to divide into 6 groups of 5 people in 6 different ways, however I do not want the same people to be together twice. I already have 5 ways written down, but I ...
0
votes
1answer
132 views

Prove that $\lambda(v-1) = r(k-1)$

This is to do with balanced incomplete block design. Some homework exercise wants me to prove the relation $$\lambda(v-1) = r(k-1)$$ $v$ is the number of elements in your ground set. $r$ is the ...