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)

0
votes
0answers
7 views

Finding a ratio from a set of discrete values

For x = p/q, where x is a known value between 0.000 and 1.000 rounded to the thousandths place, p is an integer value between 0 and 127, and q is an integer value between 0 and 255: what is p and q? ...
2
votes
1answer
41 views

Powers of adjacency matrix doesn't seem to correspond to observed number of paths on graph

I would really appreciate some help on this! $A^n$ represents $n^{th}$ power of the adjacency matrix of a graph. I keep reading that the $A^n_{ij}$ entry equals "the number of paths of length n ...
1
vote
2answers
40 views

What is the probability of sinking ships in a simplified game of battleship?

Consider a a simplified game of battleship. We are given a 4x4 board on which we can place 2 pieces. One destroyer which is a 1 × 2 squares and a submarine that is 1 × 3 squares . The pieces are ...
0
votes
1answer
33 views

Combinatorial techniques, methods, and ideas in (“undergraduate”) real analysis

This question is dual to Probabilistic techniques, methods, and ideas in ("undergraduate") real analysis: I would like to collect some examples of combinatorial arguments to undergraduate ...
3
votes
3answers
122 views

Examples of combinatorial/probabilistic proofs of theorems in linear algebra

Are there any examples of combinatorial/probabilistic proofs of theorems in linear algebra? Motivation: I see here, the inverse is true.
2
votes
1answer
29 views

What is a simple proof that something is np complete that does not use np completeness of something else?

What is a simple proof that something is NP complete that does not use NP completeness of something else? Every proof seems to reduce to something else being NP complete.
0
votes
2answers
38 views

Calculating interaction beween 100 objects with each other.

The other day I was thinking about how many interactions 100 objects would have with each other. By that I mean if we are using a computer to draw the scene with 100 point lights, the total result ...
3
votes
1answer
57 views

A combinatorial proof of Wilson's Theorem

I am looking for a combinatorial proof of Wilson's Theorem. Something along the lines of this kind of proof. $\textbf{Combinatorial proof of Fermat's Little Theorem}$ First consider a $p$ -tuple and ...
3
votes
0answers
56 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 ...
0
votes
3answers
51 views

Combinatorics Question (discrete math) [on hold]

In how many ways can one mark 6 blocks on a grid of 5 columns and 3 rows such that in every row at least one block will be marked? An explanation will be appreciated! Thanks a lot
1
vote
1answer
41 views

Proof regarding notations

I tried to solve the following question: Let $f,g$ be non-negative functions such that $f(n)=g(n)\left[1+o(1)\right]$. Prove that $f(n)=\Theta(g(n))$. I looked on two cases: ...
1
vote
2answers
28 views

Deciding $\displaystyle o,\omega,\Theta$ notations

I have a question which I couldn't solve for about two hours. It goes like this: Let $\displaystyle f(n)=\left(\frac{n+3\ln(n)}{n}\right)^n \ ; \ g(n)=27^{\ln(n)}$. Fill the blank box with ...
0
votes
1answer
40 views

If $k, m, n$, are natural numbers and $k \leq n$ What is the final answer of this :

If $k, m, n$, are natural numbers and $k \leq n$ What is the final answer of this: $$\sum_{r=0}^{m}\frac{k\binom{m}{r}\binom{n}{k}}{(r+k)\binom{m+n}{r+k}}$$
1
vote
1answer
23 views

Generalized Dyck words with alphabet of size $k$

It is known (e.g., here) that the Catalan number $C_n$ is the number of Dyck words of length $2n$, where a Dyck word is a string consisting of $n$ $X$'s and $n$ $Y$'s such that no initial segment of ...
1
vote
2answers
44 views

Binomial-coefficients if, k, m, n natural numbers and k \leq n the result of

If $k, m, n$, are natural numbers and $k \leq n$ What is: $$\sum_{r=0}^{m}\frac{k\binom{m}{r}\binom{n}{k}}{(r+k)\binom{m+n}{r+k}}$$
0
votes
2answers
16 views

combinations which way way is correct?

The problem How many ways are there to select 5 persons: 2 men and 2 women from a group of 20 people: 12 men and 8 women. So far I've found 2 solutions: We select 3 men and 2 women or 2 men ...
-2
votes
0answers
24 views

circles and points on a grid [on hold]

An infinite number of points are marked on the coordinate grid such that there is no circle that passes by 1000 of them. Is there necessarily a circle of radius 20 that does not contain any of those ...
0
votes
1answer
32 views

Miklos Schweitzer 2014 - sum of reciprocal of lengths of intervals

We let there be $k$ intervals within $[0,1]$. Prove that the sum of the reciprocals of the lengths of the intervals plus twice the sum of the reciprocals of the lengths of the nonempty intersection of ...
2
votes
2answers
40 views

If given $\sum_{r=1}^{m-1}\binom r3$, how does the summation evaluate when $n<r$ in $\binom nr$?

Correct me if I'm running the summation correctly - $$\sum_{r=1}^{m-1}\binom r3=\binom 13+\sum_{r=2}^{m-1}\binom r3$$ $$\sum_{r=1}^{m-1}\binom r3=\binom 13+\binom 23+\sum_{r=3}^{m-1}\binom r3$$ ...
4
votes
2answers
29 views

Number of teams and matches

This question has two parts. Given n players, how many different teams can be created with at least one and at most n-1 players? For example, given the four players A, B, C, and D, the following ...
2
votes
1answer
30 views

Combinatorics calc

I'm trying to make an application that's based on bets system. Until now i was able to calc the number of combination of the inserted events, in particular, i've used this formula: ...
2
votes
1answer
47 views

Calculating sum of all permutations

Given a number n. If we generate all the permutation from 1 to n, for a permutation $P_i, F(P_i)$ is defined as $\sum(|P_i - i|)$ for i = 1 to n. So if n = 3, for the permutation 1 3 2 F = |1-1| + ...
0
votes
1answer
37 views

What happens from $\displaystyle (1+(x+x^2))^n$ to $\displaystyle \sum_k {n \choose k} (x+x^2)^n$?

I'm reading Harris/Hirst/Mossinghoff's: Combinatorics and Graph Theory. I don't understand what happens from $\displaystyle \bbox[1px,border:1px solid black]{(1+(x+x^2))^n} $ to $\displaystyle ...
2
votes
1answer
41 views

Counting in other bases [duplicate]

While this could be considered opinionated to a certain degree, by setting the requirement as ease of use, is there a base that is better for performing simple math functions (+-×÷) than base ten. I ...
2
votes
1answer
34 views

Adjacent dominos in a train

Definition of a domino -- a domino contains two squares separated by a line. In both of the squares, there are some numbers of dots (can be 0). Definition of "double-n" domino set: It contains one of ...
3
votes
1answer
47 views

Minimum number of bags to buy to allocate equally

It is from a programming contest but I feel it pertains more to the mathematics realm ( I once asked it in stackoverflow but they closed the problem saying I should go here ) The problem goes like ...
1
vote
1answer
41 views

Expected number of matching “cards”. Why is $\sum_{m=0}^n D_{n,m} = \sum_{m=0}^n m \cdot D_{n,m}$?

Each of n ≥ 2 people puts his or her name on a slip of paper (no two have the same name). The slips of paper are shuffled in a hat, and then each person draws one (uni- formly at random at each ...
2
votes
1answer
54 views

Maximization problem related to set of common representatives

We are given set $\{1, \dots n\}$ and requested to construct $A = \{A_1 \dots A_s\}$, where $|A_i|=k$, $|A| = s$, $A_i \subset \{1, \dots n\}$. We say that $S$ is a minimal set of common ...
2
votes
2answers
33 views

Number of Terms in a Polynomial (4th Degree)

Find the number of terms of $(x^3+5x^2-x+2)^4$, when like terms are added. My approach to this uses stars and bars to get $****|||$, since there are $4$ groups. $\binom{7}{3} = ...
2
votes
1answer
36 views

Set of common representatives and pigeonhole principle in one problem

We are given set $\{1, \dots n\}$ and $A = \{A_1 \dots A_s\}$ such as $|A_i|=k$, $|A| = s = \binom n k$, namely $A$ contists of all possible subsets of size $k$. We say that $S$ is a set of common ...
1
vote
2answers
26 views

Permutation/Combination question on dice

Question: Three dice (six faces: each face -> number 1 to 6) are rolled. What is the number of possible outcomes such that at least one die shows number 2? My attempt: One die has to show two. ...
1
vote
0answers
52 views

Traveling salesman neighborhood

I am solving some TSP problems and i got this one and i am not pretty sure about my answer. By seeing TSP as a formal combinatorial problem, i have that the Feasible solutions $F$ is the set defined ...
6
votes
0answers
57 views

Game to maintain distinct number of balls in glasses

There are $n$ glasses, containing $n+1,n+2,\ldots,2n$ balls, respectively. Two players $A$ and $B$ play a game, alternately taking turns with $A$ going first. In each move, the player must choose some ...
2
votes
2answers
34 views

Probability in dice, Feller exercise

I am stuck with exercise 2 of Chapter 4 Feller vol 1 "an introduction to probability theory and its application". Here I report the exercise text: Five dice are thrown. Find the probability that at ...
1
vote
1answer
28 views

Find a probability of $n$ event happening from $m$ types

The question is: to find a sum $$ S=\sum\limits_{n_1+n_2+\ldots+n_m = n,\ n_i=0,1,\ldots,n} p_1^{n_1}p_2^{n_2}\cdots p_m^{n_m}, $$ where $p_i\in[0,1]$. UPDATE. This issue has no probabalistic ...
5
votes
2answers
43 views

Distributing candies

Suppose ther are B boys and G girls in a classroom.Teacher wants to distribute candies among B boys and G girls such that: 1.Each student gets atleast one candy and atmost N candies. 2.sum of ...
-2
votes
0answers
38 views

Modifying recursion matching result

Let $f_0=\frac{1}{4}$ and $f_i=\dfrac{3f_{i-1}}{4}+\dfrac{2^{-i}}{2}$ and this gives $f_n>\frac{3^{n}}{4^{n+1}}$. This problem came as I was trying to solve a complexity theory problem. ...
0
votes
2answers
47 views

Exclusion-Inclusion principle.

I have this problem in discrete maths (combinatorics) which nags me. We have a computer system, where a password is of length of at least 3 signs and at most 100 signs. The premitted signs to use ...
5
votes
1answer
47 views

Erasing numbers from circle and writing down sum

There are $50$ copies of the number $1$, and $50$ copies of the number $-1$, written alternately in a circle. In each step, we pick an arbitrary number, write down the sum of the number and its two ...
1
vote
1answer
54 views

How find the smallest $m$ such this $|A|=n,|B|=m,A\subseteq B$

Question: Let $n \geq 5$ be a positive integer and let $A$ and $B$ be sets of integers satisfying the following conditions: i) $|A| = n$, $|B| = m$ and $A$ is a subset of $B$ ii) For any ...
0
votes
2answers
29 views

Show that the number of subsets of $S_1 \cup \dots \cup S_t$ that contain at most one element from each $S_i$ is $(a_1 + 1)(a_2 + 1) \dots (a_t + 1)$.

I found this problems on Aigner's: A course in enumeration: 1.1 We are given $t$ disjoint sets $S_i$ with $|Si| = a_i$. Show that the number of subsets of $S_1 \cup \dots \cup S_t$ that contain ...
2
votes
3answers
37 views

Probability of winning a rigged coin-flipping game

Betsy and Katie are playing a game with an unfair coin. The coin is rigged to come up heads with probability $\frac35$ and tails with probability $\frac25$. Betsy goes first. The two take turns. The ...
3
votes
1answer
49 views

Number of ways to arrange items

Given a list of $n$ distinct items, where a smaller item behind a larger item is obscured, if you can see $x$ items from one end, and $y$ from the other, how many ways can the items be arranged? ...
2
votes
4answers
67 views

How to find the number of possible outcomes of 10 games between 20 teams?

Hi I am looking for an equation to find possible combinations in a non repeating format with a twist. Here is the example: There are 10 games between 20 teams. I have to chose 5 winners but ...
-1
votes
4answers
46 views

How many ways are there to prepare one of 400 varieties of coffee in one of 7 ways?

I'm hoping someone can check my thinking: I have 400 distinct varieties of coffee. Each can be prepared in 7 ways (black, cream and sugar, etc.). How many possible combinations are there? I'm thinking ...
0
votes
0answers
45 views

Put a set of triangles into proper mathematical equations / objects

I have a set of $n$ points $\{A_1,A_2,...,A_n\}$ of the plane. Three points $A$ should never form a line (so we can still draw a proper triangle). I draw every triangle formed with $3$ points $A$. I ...
1
vote
1answer
60 views

How to solve this kind of problem?

I've just found the following problem: $\quad\quad$ $\quad\quad$ $\quad\,$ And I believe that it could be done with something in combinatorics, my feeling is that generating functions would ...
-10
votes
0answers
34 views

Showing $M(n,k,q)=\sum_{i=0}^{q}(-1)^{q+i}\binom{q}{i}\begin{pmatrix}0&n\\k&i\end{pmatrix}$. [on hold]

How do I show $$M(n,k,q)=\sum_{i=0}^{q}(-1)^{q+i}\binom{q}{i}\begin{pmatrix}0&n\\k&i\end{pmatrix}$$ for $q>1?$
3
votes
3answers
54 views

How many different (circular) garlands can be made using $3$ white flowers and $6m$ red flowers?

This is my first question here. I'm given $3$ white flowers and $6m$ red flowers, for some $m \in \mathbb{N}$. I want to make a circular garland using all of the flowers. Two garlands are considered ...
0
votes
0answers
44 views

A combinatorial game theory problem

In details, Let, there are four bishops on a chessboard where every two bishops are in pair ( as there are 4 bishops that means 2 pairs and in each pair they sit in vicinal squares). How many ...