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)

5
votes
1answer
93 views

How to evaluate this double infinite sum (Catalan number)

Let $C_n = \dfrac{1}{n+1}\binom{2n}{n}$. Is it possible to find the exact value of this infinite sum ? $$\sum_{n=1}^\infty \sum_{k=n}^\infty ...
2
votes
2answers
70 views

How to solve “ways of seating around a circular table”

Recently I asked a question about seating, here it is again: The Annual Interplanetary Mathematics Examination (AIME) is written by a committee of five Martians, five Venusians, and five ...
0
votes
0answers
98 views

Permutation equivalence classes with kendall-tau distance

Consider a set $A=\{a_1,...,a_m\}\subset \{1,...,n\}$ for which $a_i<a_{i+1}$ for all $i = 1,\ldots,m-1$. Take any two distinct permutations $\sigma, \tau$ of $\{1,...,n\}$ such that $ ...
3
votes
0answers
78 views

A sequence of polynomials [duplicate]

I posted this question a while back, and I think I may not have made myself clear or shown what I got so far. So let me post this question again with more information and clarification. I have a ...
1
vote
1answer
50 views

How many binomials are divisible by $p$?

Let $N$ be a interger (maybe $10^{15}$) and $p$ be a prime number less than $N$. How many binomials ${n}\choose{k}$, where $n<N$, divisible by $p$? we already know that ${pm}\choose{pn}$ $\equiv$ ...
1
vote
2answers
75 views

How many ways to arrange the seating?

The Annual Interplanetary Mathematics Examination (AIME) is written by a committee of five Martians, five Venusians, and five Earthlings. At meetings, committee members sit at a round table with ...
2
votes
0answers
48 views

inclusion-exclusion principle working

We have $n$ non-negative integers $a_1, a_2, \dots, a_n$. We will call a sequence of indexes $i_1, i_2, \dots, i_k$ such that $1\le i_1 < i_2 < \dots< i_k\le n$ a group of size $k$. How many ...
4
votes
0answers
34 views

How many ways I can put $k$ bishops on $n\times n$ chessboard?

Is there a formula how to count in how many ways I can put $k$ bishops on $n\times n$ chessboard such that no two bishops threaten each other?
2
votes
1answer
22 views

Number of square matrices of order $n$ where each row and each column has at most one $1$

What is the number of square matrices of order $n$ with the property that each row and each column has at most one $1$, and $0$s elsewhere? For example, when $n=2$, there are $7$ such matrices: ...
1
vote
2answers
33 views

Reduce Combination Formula

Hey i have to write a code for this: You can refer here: Picking Same Color Probability For the entire question. $\Pr(Success)=$$\sum\limits_{k=1}^{\min(m,n)}\frac{{m\choose k}\cdot{nm-m\choose ...
3
votes
0answers
32 views

Which graph with an automorphism group isomorphic to the quaternion group $Q_8$ minimizes $|V|+3|E|$?

In Symmetries of partial Latin squares, it is shown that for any graph $\Gamma=(V,E)$ with automorphism group $G$, there is a partial Latin square with $|V|+3|E|+49$ filled cells whose autotopism ...
1
vote
1answer
15 views

Recurrence Relations for Sequence Counting Hamming Weights

Define $a(n,k)=|\{x \in \mathbb{F}^{2n}_2 : Hx=0, ||x||=k\}|$ and $b(n,k)=|\{x \in \mathbb{F}^{2n}_2 : Hx=1, ||x||=k\}|$ where $||\cdot||$ denotes the Hamming weight of $x$ (i.e. number of non-zero ...
2
votes
2answers
24 views

Sunflower Lemma - Allow Duplicates?

The sunflower lemma states that if we have a family of sets $S_1, S_2, \cdots, S_m$ such that $|S_i| \leq l$ for each $i$, then $m > (p-1)^{l+1}l!$ implies that the family contains a sunflower with ...
2
votes
2answers
104 views

Prove $\sum\limits_{i=0}^{n}\binom{n+i}{i}=\binom{2n+1}{n+1}$ [duplicate]

I'm trying to prove this algebraically: $$\sum\limits_{i=0}^{n}\dbinom{n+i}{i}=\dbinom{2n+1}{n+1}$$ Unfortunately I've been stuck for quite a while. Here's what I've tried so far: Turning ...
1
vote
0answers
46 views

Calabi-Yau Toric Varieties

This is a rather naive question, but, from what I understand, we begin with a some reflexive polytope $P$. From the basic theory of toric varieties, we can construct a toric variety corresponding to ...
0
votes
2answers
54 views

How to calculate combinations count for this problem

I will explain my question using simple example, cause I don't know to descrive it properly. If we have 2 numbers $\{a,b\}$, by comparing them, we get 3 possible combinations: $$a>b, \hspace{3pt} ...
1
vote
1answer
45 views

Free idempotent semigroup with 3 generators

On Finite free objects I asked examples of finite free objects. I got answer "The free idempotent semigroup satisfies $x^2=x$ for each element $x$. And I confirm it is finite if it is finitely ...
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
4answers
97 views

When will Andrea arrive before Bert?

The question was as follows- on any given day, Andrea is equally likely to clock in at work any time from 8:50am to 9:06am. Similarly, Bert is equally likely to to clock in at work at any time ...
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
32 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 ...
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 ...
4
votes
1answer
89 views

Ordering $2n$ numbers

In how many different ways can you order $2n$ different numbers with alternating $<,>$ signs? An example for the case where $2n=6$ is $$1<3>2<6>4<5>1$$ ...
3
votes
3answers
75 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
votes
1answer
60 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) ...
0
votes
1answer
34 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 ...
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 ...
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 ...
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
44 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 ...
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 ...
5
votes
6answers
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 ...
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 ...
6
votes
1answer
120 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 ...
1
vote
0answers
62 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 ...
3
votes
1answer
56 views

find a group of lowest N numbers so that no 2 pairs have the same bitwise or

I am trying to find the lowest group of N numbers (i.e. N=1000) so that no 2 pairs from the group have the same bit-wise or. more specific need to find a group $A = \{a_1,a_2,a_3,..,a_N\} $ such ...
2
votes
1answer
60 views

sample variance of regular polygon upon superimposition of vertices

Given, the vertices of a regular polygon, the centroid here would be the sample mean of the vertices and we assume it to be at the origin. The distance from each vertex to centroid is ...
2
votes
0answers
45 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
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.
10
votes
4answers
177 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 ...
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 ...
2
votes
2answers
47 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 ...
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 ...
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
2answers
38 views

(Fast way to) Get a combination given its position in (reverse-)lexicographic order

This question is the inverse of the Fast way to get a position of combination (without repetitions). Given all $\left(\!\!\binom{n}{k}\!\!\right)$ combinations without repetitions (in either ...
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 ...