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
5answers
94 views

Help needed to solve combinatorics problem.

I have been revisiting my old probability courses and I found a problem, which I can't figure out how to solve or at least what I get differs from the answer in the book. The problem reads as ...
1
vote
1answer
164 views

On the probability that $\sum\pm b_i=0$ for some given $(b_i)$

Let $b_i, i=1,\ldots,m$ be real numbers. Let $r_i, i=1,\ldots,m$ be random variables with $P(r_i=1)=P(r_i=-1)=1/2$. Consider group $\Pi_m$ of all permutations of the set $\{1,\ldots,m\}$. On the ...
1
vote
3answers
126 views

Combination sum .

I want to evaluate the following sum : $$S(k,k')=\sum_{i} C_{i+k}^k C_{k'-i}^{k}$$ = $$S(k,k')=\sum_{i} \binom{i+k}{k} \binom{k'-i}{k}$$ I tried some steps but couldnt get further than : ...
1
vote
4answers
34 views

Question on Permutations Please advise

Among all seven digit decimal numbers,how many of then contain exactly three 9's? My Approach: 3 places contains only 9's---> 1*1*1 (No. of Ways to Choose out of 0 to 9) other 4 places: since first ...
1
vote
0answers
23 views

How to calculate the $k$-dimension of a subspace of a polynomial ring?

Let $k$ be an infinite field and $R:=k[x_1,...,x_n]$ the polynomial ring in $n$ indeterminates. Why is the $k$-dimension of $U$ given by $\begin{pmatrix} n+m-1 \\ m\end{pmatrix}$, when $U$ is the ...
2
votes
2answers
40 views

Size of a maximum matching of a complete multipartite graph?

Let $G=(V,E)$ be a complete multipartite graph on even number of vertices, with $V(G) = X_1\cup X_2\cup\ldots\cup X_k$, let $n_i := |X_i|$, and suppose $n_1\le n_2\le \ldots\le n_k$. The problem I am ...
1
vote
1answer
1k views

what is maximum number of points of intersection between the diagonals of a convex octgon?

What is the maximum number of points of intersection between the diagonals of a convex octagon (8-vertex planar polygon)? Note that a polygon is said to be convex if the line segment joining any two ...
3
votes
2answers
75 views

How to prove ${{pm} \choose {pn}}\equiv{m \choose n} \pmod{p}$.

Question:(1) if p is a prime and m,n $\in$ N,prove that ${{pm} \choose {pn}}\equiv{m \choose n} \pmod p$ (the book gives me a hint: think about $(1+x)^{pm}$ and $(1+x^m)^p$ in $F_{p}(x)$. (2) Prove ...
0
votes
0answers
80 views

combinatorics (check top cards of deck, if same color set aside and repeat, else stop)

Lets say you have a deck of $z$ cards. $x_1$ are white, $x_2$ are black and $y$ are blanks. $n>0$ is given. Now you do Check top $n$ cards, if they all have the same color, put them aside and ...
3
votes
1answer
31 views

Representation-theoretical reasons for positivity of product of two Schubert polynomials?

In the Wikipedia article on Schubert polynomials there is a claim that there are representation-theoretical reasons for the product of two Schubert polynomials to have nonnegative coefficients when ...
6
votes
0answers
70 views

Has this subset-sum game been studied?

Consider the following game: two players, Yolanda (who always goes first) and Zachary, take turns selecting (not yet chosen) numbers between $1$ and $9$. The first player who can make three of their ...
3
votes
1answer
137 views

If I randomly generate a string of length N from an alphabet {A, B, C}, what's the likelihood that k characters will be the same OR BETTER?

This is an addendum to a previous question found here. I have an alphabet: {A, B, C}. I'm randomly generating strings of length N from that alphabet. Examples: Examples: N=5, AACBC, AAAAA, BBCAA ...
-1
votes
1answer
59 views

how many ziplines between two buildings? [closed]

There are two buildings facing each other, each 5 stories high. How many ways can Kevin string ziplines between the buildings so that: (a) each zipline starts and ends in the middle of a floor. (b) ...
3
votes
3answers
73 views

The number of positive integral solutions to the system of equations.

The number of positive integral solutions to the system of equations $$\begin{align} & a_{1}+a_{2}+a_{3}+a_{4}+a_{5}=47\\ &a_{1}+a_{2}=37,\ \ \{a_{1},a_{2},a_{3},a_{4},a_{5}\} \in ...
1
vote
2answers
302 views

Probability of picking specific balls

Suppose I have $20$ red balls in one box and $20$ blue balls in another box. There $12$ red balls and $7$ blue balls have stars on them. I randomly take out one red ball and one blue ball at each ...
5
votes
5answers
5k views

If I buy 2 lottery tickets do I double my chance of winning?

There's a lottery. There are 6 balls chosen randomly from 49 and you have to match all the balls to win. I buy one ticket. If I buy two tickets with different numbers for the same draw, do I ...
0
votes
1answer
33 views

Amy's grandmother gave her 3 identical chocolate chip cookies and 4 identical sugar cookies.

Amy's grandmother gave her 3 identical chocolate chip cookies and 4 identical sugar cookies. In how many different orders can Amy eat the cookies such that either she eats a chocolate chip cookie ...
6
votes
1answer
119 views

If I randomly generate a string of length N from an alphabet {A, B, C}, what's the likelihood that exactly k characters will be the same?

I have an alphabet: {A, B, C}. I'm randomly generating strings of length N from that alphabet. Examples: Examples: N=5, AACBC, AAAAA, BBCAA What is the likelihood that exactly k characters of that ...
2
votes
1answer
55 views

A problem about chance

I can't really think of a more definitive title. I have a problem about chances or probably combinations (I'm not very good at math). The problem is: If there is an event that occurs 2 times in a ...
1
vote
2answers
2k views

Playing roulette

Suppose we have a roulette wheel with $38$ total slots ($18$ black/red, $2$ neither). The ball lands in one slot selected uniformly at random, independent of all previous spins. An $\$x$ bet on ...
1
vote
2answers
42 views

A general formula to calculate sum of product of all combinations of size r from given n numbers?

I came across a quesion - https://www.hackerrank.com/contests/ode-to-code-finals/challenges/pingu-and-pinglings The question basically asks to generate all combinations of size k and sum up the ...
0
votes
1answer
30 views

Comparing the password strength of random characters to random words.

Passwords with any ASCII printable character and passwords containing only words in the English dictionary are attacked equally using a guessing program that cycles between random words and random ...
0
votes
1answer
19 views

Combinatoric for number of ways to have monotone-increasing sequence

I hope I am using the right term. By monotone-increasing I mean to imply that it is a non-decreasing sequence. So for example a sequence $1, 1, 2, 5, 6, 10, 10, 11$, etc. Anyhow, consider a ...
10
votes
4answers
174 views

A circle with $500$ points in its interior

Given any $1000$ points in the plane, show that there is a circle which contains exactly $500$ of the points in its interior, and none on its circumference. How do I approach this problem? I feel ...
4
votes
1answer
559 views

Calculating the Shapley value in a weighted voting game.

Given a special case of WVG (Weighted Voting Game) of $a$ 1s and $b$ 2s and a quota q, $ [q:1,1,1,1..1,2,2,..2] $. I need help with calculating the Shapley value of a player with a weight of $2$ and a ...
1
vote
0answers
61 views

Graph Theory number of handshakes of couples

This is an Olympiad question which I now know the answer to, but I am a bit unsatisfied with it. So maybe someone can shed some light: Question: $5$ couples go to a party. Each person shakes the ...
7
votes
2answers
165 views

Expand $\binom{xy}{n}$ in terms of $\binom{x}{k}$'s and $\binom{y}{k}$'s

Motivated by this question, I want to find a complete set of relations for the ring of integer-valued polynomials, where the generators are the polynomials $\binom{x}{n}$ for $n\in \mathbb{N}$. The ...
2
votes
0answers
44 views

Sum taken over the specified set of integer: $\sum_{3 \mid n} a_n$

Let's consider a sum $$S_{m}=\sum_{ 3 | n}^{m} {a_{n}}$$ where the sum is taken over all the integers $3t$, where $0 \leq 3t \leq m$. Assume that $G(z)$ is a generating function of the sequence ...
0
votes
1answer
51 views

Counting possible passwords

Stephanie changes her password using letters and numbers to create a $6$ character code. There is no restriction on the number of times these can be used, how many combinations are possible? The ...
1
vote
1answer
61 views

Construction of Rauzy Fractals with substitutions without a fixed point

The formal definition of a Rauzy fractal can be found at the beginning of this paper Using Sage-math-cloud, I can generate Rauzy fractals of substitutions that I choose. Should I choose the ...
2
votes
3answers
94 views

How to prove that $(\frac{n}{k})^k\leq{{n}\choose{k}}\leq\frac{n^k}{k!}$?

How to prove that $(\frac{n}{k})^k\leq{{n}\choose{k}}\leq\frac{n^k}{k!}$? I can only manage to see the second inequality, could any one give a hint about the first one?
0
votes
3answers
3k views

No husband can sit next to his wife in this probability question

I have a probability question that reads: Question: If 4 married couples are arranged in a row, find the probability that no husband sits next to his wife. My attempt: ...
2
votes
3answers
105 views

Fast way to get a position of combination (without repetitions)

This question has an inverse: (Fast way to) Get a combination given its position in (reverse-)lexicographic order What would be the most efficient way to ...
-1
votes
1answer
30 views

Multi stage probability events [closed]

Three students are selected at random from a group of $6$ boys and $4$ girls. How many combinations are possible that contain exactly $2$ boys? The answer is $120$. I'm not sure where to begin.
2
votes
2answers
46 views

Counting points of intersection

There are 9 points on the circumference of a circle. The points are not evenly spaced. Line segments are drawn connecting each pair of points. What is the largest number of different points inside ...
3
votes
1answer
18 views

Get amount of submatrixes from $a \times b $matrix

I was trying to do the following exercise Given a grid of size $a \times b$, write a formula able t calculate the total number of rectangles contained in this rectangle. All integer sizes and ...
1
vote
1answer
45 views

Probability of not making a shoe pair.

Ten adults enter a room, remove their shoes, and toss their shoes into a pile. Later, a child randomly pairs each left shoe with a right shoe without regard to which shoes belong together. The ...
3
votes
1answer
65 views

Why doesnt this Combinatoric work two ways?

There are two distinguishable flagpoles, and there are $19$ flags, of which $10$ are identical blue flags, and $9$ are identical green flags. Let $N$ be the number of distinguishable arrangements ...
1
vote
0answers
27 views

Is the proposed a different version of the stable marriage problem and a valid Gale-Shapley solution?

my problem is the following. I've two sets A and B with the same numbe of elements. The elements in A can match only with some elements of B. The elements of B have no preferences. Elements have no ...
8
votes
2answers
306 views

Reorder adjacency matrices of regular graphs so they are the same

Given a matrix A of a strongly $k$ regular graph G(srg($n,k,\lambda,\mu$);$\lambda ,\mu >0;k>3$). The matrix A can be divided into 4 sub matrices based on adjacency of vertex $x \in G$. $A_x$ ...
5
votes
1answer
122 views

Stirling transform of $(k-1)!$

While reading about combinatorial mathematics, I found this article about the Stirling transform which caught my attention. So, if I wanted to find the Stirling transform of, for instance, $(k-1)!$, ...
5
votes
0answers
100 views

Puzzle - In how many pairings can 25 married couples dance when exactly 7 men dance with their own wives?

Each married couple as well as each dancing pair consists of a man and a woman. How many possible pairings are there? Here is the same question with a different amount of couples. I read the answers ...
3
votes
2answers
85 views

Picking Same Color Probability

So i recently came across this question, Marla has m bottles of marbles. Each bottle has n marbles of n different colours. Marla mixes all the marbles from all the bottles together. Now, she picks up ...
0
votes
0answers
18 views

Combinatorial nature of discrete-valued variables

Can I ask what this statement means? An example would be preferred. Due to the combinatorial nature of discrete-valued variables, rare values are more acutely felt than in numeric variables.
4
votes
2answers
61 views

Minimal edge cut

Suppose that $C$ is a minimal edge cut of a graph $G=(V,E)$ is it possible that the removal of $C$ can split $G$ into three components? I ask this because i'm reading a proof which states that it's ...
2
votes
0answers
35 views

Limit probability of winning a card game [duplicate]

As mentioned in this question, the probability of winning, with an $n$-card per $k$ suit deck, a counting-up match card game (where you count through each of $n$ cards in order $k$ times and lose if ...
6
votes
1answer
63 views

Is it possible to choose $10$ distinct numbers from the set $\{0, 1, 2, . . . , 14\}$ so that various differences are all distinct?

From the 1991 Canada National Olympiad: Can ten distinct numbers $a_1, a_2, b_1, b_2, b_3, c_1, c_2, d_1, d_2, d_3$ be chosen from $\{0, 1, 2, \dotsc, 14\}$ so that the $14$ differences $$ ...
4
votes
1answer
97 views

What tactics could help with this probability questions

I'm not too sure if this question is solvable (I sort of just thought of it yesterday) but when I brute force numerical answers on my computer they seem to show a pattern, so I believe it to be ...
1
vote
1answer
60 views

movement of knight in a game of chess

This question arose in my brain while playing a game of chess. We all know how a knight moves in a game of chess. I wanted to calculate the minimum no. of moves required by a knight to cover all the ...
1
vote
1answer
61 views

Counting lattice ponts

A lattice point is a point with integer coordinates such as $(2,3)$. There are two parts of this problem. [a] In how many ways can we pick 3 lattice points such that both coordinates of all three ...