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)

0
votes
1answer
35 views

Combinations and Probability with Cards

I don't really understand the following problem, so if someone could set up the process for me it would be appreciated. Suppose that I draw two cards out of a set of $52$. If I know that these $2$ ...
2
votes
2answers
124 views

Binomial theorem.

I first saw this thing (admittedly much to late in life) in a third year class entitled non-linear dynamics and chaos theory. There if i am remembering correctly we used to look for non-zero terms to ...
0
votes
1answer
130 views

Number of ways to arrange people in two rows, so that nobody stands behind or to the right of someone taller [closed]

How many ways are there to arrange $2n$ people (no two of them being the same height) in 2 rows of $n$ people, so that: the people in each row are ordered by height, with the shortest on the left ...
3
votes
1answer
48 views

Equal number of black and white neighbors in circle

There are $n\geq 12$ points on a circle, each colored black or white. When we consider the $5$ neighbors to the left of any point and $5$ to the right, then among the $10$ points, exactly $5$ are ...
-1
votes
2answers
76 views

Size of prime products

How many primes are there that are $n$ bits long? How many primes are there that are atmost $n$ bits long? What is the number of bits in product of all primes that are $n$ bits long (with carry ...
2
votes
2answers
111 views

Counting Set Partitions with Constraints

I'm trying to count set partitions under the following constraints: The number of partitions on $n$ elements where the largest cell(s) have exactly $k$ elements All cells have at least two elements ...
11
votes
1answer
72 views

Coloring $\mathbb R^n$ with $n$ colors always gives us a color with all distances.

I wanted to share a really cool but simple problem. Consider a coloring of the points of $\mathbb R^n$ with $n$ colors. Prove that there is a color $c$ such that for any $r>0$ there are two points ...
5
votes
1answer
118 views

Intersection of Random Subsets

Consider $n$ independently drawn $q$-subsets $e_1,...,e_n$ from a finite set $P$. What is the probability that the intersection of the $n$ subsets is non-empty, in terms of $n$, $q$, and $|P|$? ...
0
votes
1answer
87 views

Given a set of integers and operators, find if number is obtainable

Let's say I have a set of sequential integers $(x_1,x_2,x_3,x_4,\ldots,x_n)$ and operators $(+,-,\times,/,(,))$ (arithmetic operators and parenthesis). Now say we can have any $t$ numbers from the ...
0
votes
1answer
70 views

Combination sports odds question

There are 10 games between 20 teams being played. I want to know how many combinations of 5 I can make from those 20 teams. Order doesn't matter. I only want to pick winners so only 1 team per game ...
2
votes
0answers
36 views

Structure of skew $0,\pm1$ matrix

Let $S$ be a skew symmetric matrix with entries from $\{-1,0,+1\}$. We know that there is a unitary matrix $U$ that diagonalizes $S$. There are only $3^{\frac{n^2-n}{2}}$ such matrices and still lower ...
7
votes
3answers
463 views

Conditionally combining vanilla and chocolate ice cream scoops

Suppose I have a plate that fits $n$ number of ice cream scoops. I can choose between vanilla and chocolate flavors. The only condition is that I cannot scoop for chocolate twice in a row, e.g. if ...
2
votes
3answers
50 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? ...
9
votes
1answer
730 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
119 views

What is the probability of sinking all 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 ...
1
vote
1answer
118 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
189 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
55 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
54 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 ...
5
votes
1answer
94 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 ...
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
vote
1answer
80 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
42 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 ...
-2
votes
0answers
94 views

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

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}}$$
2
votes
1answer
93 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 ...
-3
votes
3answers
163 views

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

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
24 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 ...
1
vote
1answer
60 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
49 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
53 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
43 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: ...
3
votes
1answer
276 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
47 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
55 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
49 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
56 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
3answers
152 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
76 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
39 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
51 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
66 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. ...
2
votes
0answers
94 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 ...
14
votes
2answers
248 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
77 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
40 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
55 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 ...
0
votes
2answers
91 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
59 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
56 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
36 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 ...