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)

2
votes
1answer
40 views

Number of combinations of selecting $r$ numbers from first $n$ natural numbers of which exactly $m$ are consective.

Number of combinations of selecting $r$ numbers from first $n$ natural numbers of which exactly $m$ are consective. Say $g(n,r,m)$ is the number of such combinations. The two cases of $m=r$ and $m=1$ ...
11
votes
2answers
90 views

Let $x$ be an irrational number. Prove that there exist infinitely many rational numbers $\dfrac pq$ that satisfy the following

$$\bigg|\,x-\dfrac pq\,\bigg|<\dfrac 1{q^2+q}$$ My idea would be to solve the inequality for $\frac pq$ and then somehow use the pigeonhole principle. Is this heading in the right direction? Any ...
2
votes
2answers
79 views

Messaging probabilities

New to site! I'm a near-retirement cellist who likes to mess with math, but I have a probability problem beyond me. I'm part of a large family - we have twenty-four people who send texts back and ...
1
vote
2answers
27 views

Probability of getting same configuration in 2 throws with R dices

EDIT: There's same question already: Probability of throwing the same multiset twice in a row with six dice I'm trying to find general solution for a problem from Feller's book (p. 56): What ...
3
votes
2answers
79 views

Graph theory-related problem, unit distance graph, pairs of people with restraining orders

This problem is for my own exploration, not for class. The problem goes as follows: There are $n$ pairs of people with restraining orders against one another. However, all $2n$ people are friends ...
3
votes
5answers
88 views

How many $5$ element sets can be made?

Let $m$ be the number of five-element subsets that can be chosen from the set of the first $14$ natural numbers so that at least two of the five numbers are consecutive. Find the remainder when $m$ ...
0
votes
1answer
50 views

Mountain of coins

Let a mountain of coins be an arrangement coins in rows such that the coins in each row form a single block, and that in all rows (except the bottom row) each coin touches exactly two coins from the ...
1
vote
1answer
48 views

Special Palindromic String

A string of length $N$ can be made from $6$ characters $a$, $b$, $c$, $d$, $e$ and $f$. There are some rules to make such a string: 1) $b$ can not come directly after $a$. 2) $d$ can not come ...
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 ...
3
votes
3answers
1k views

Place maximum Rooks on a chessboard

I am given a chessboard of size $8*8$. In this chessboard there are two holes at positions $(X1,Y1)$ and $(X2,Y2)$. Now I need to find the maximum number of rooks that can be placed on this chessboard ...
2
votes
1answer
53 views

Easiest way to find the 'area of a Venn diagram,' given certain information.

We have a bunch of intersecting regions: $$X_1,\dots, X_n,$$ all with non-negative volume, and we know $V(X_i)$ and $V\left((\cup_{a\in A}X_a)\cap (\cup_{b\in B}X_b)\right)$ for any disjoint ...
2
votes
2answers
60 views

Generate all De Bruijn sequences

There are several methods to generate a De Bruijn sequence. Is there a general algorithm to create all unique (rotations are counted as the same) De Bruijn sequences for a binary alphabet of length ...
1
vote
1answer
22 views

Writing a Sum of Partition Items in Combinatorial Form

For each partition $\lambda$ we can define \begin{equation} n(\lambda) = \sum_{i \geq 1}(i-1)\lambda_i. \end{equation} According to my book this is equivalent to \begin{equation} n(\lambda)=\sum_{i ...
0
votes
0answers
45 views

Question on how to manipulate terms in this expression

sorry for the vague title, i dont know how else to express what i mean with this question. But what i need to do is find out which terms on the RHS of the expression are constants. It is clear that it ...
5
votes
2answers
53 views

Floor Function Equation

How many positive integers $ N$ less than $ 1000$ are there such that the equation $ x^{\lfloor x\rfloor} = N$ has a solution for $ x$? (The notation $ \lfloor x\rfloor$ denotes the greatest ...
21
votes
1answer
377 views

What is the intuition behind generating functions? What makes them valuable?

I'm sorry if this question makes no sense. I have been reading generatingfunctionology and I have been able to solve the problems in the first chapters and I understand the mechanism I have to follow ...
0
votes
1answer
21 views

Representing a combinatorial sum with an equation

I am trying to represent a situation with an equation that is fairly conceptually simple, but I am not sure what is the proper way to represent it as a formal mathematical equation. I have a set of n ...
1
vote
1answer
16 views

Maximal number of subsets with 3 elements and small intersection - special Constant Weight Codes

in the middle of some proof I encountered a combinatorial problem and tracked it back to the theory of Constant Weight Codes. Those problems seem hard to solve, but my question is rather specific, so ...
0
votes
0answers
30 views

Calculating the minimum number of players required for a system to operate

Players wish to find other players to play games against, games are 1 v 1. Games are played in discrete time periods of 1 hr on the hour for one week (i.e. starting Monday 00:00 and ending Sunday ...
3
votes
2answers
57 views

Maximum and minimum Expected values when taking colored balls

We have a sack with $60$ balls. From them $15$ balls are red, $15$ green, $15$ blue and $15$ yellow. We take $30$ balls from the sack. What's the expected number of balls of the color from which ...
0
votes
4answers
48 views

Choosing a ball randomly from each urn

I am stucked at this combinatorics/probability problem: There are 10 urns, each contains 8 balls numbered 1,2,...,8 If we randomly choose 1 ball from each urn, what is the probability that the ...
1
vote
1answer
43 views

Find the Sum using bijection

Find the sum of $S=\displaystyle\sum_{i,j,k \ge 0, i+j+k=17} ijk$. I am looking for a solution that uses some bijection. I couldn't find any bijection. I am able to do the problem by other method by ...
8
votes
3answers
153 views

Non combinatorial proof of formula for $n^n$?

I came across the below identity: $$ n^n=\sum_{k=1}^n\frac{n!}{(n-k)!}\cdot k\cdot n^{n-k-1} $$ A combinatorial proof of this fact is as follows. Consider the collection of lists of length $n$, where ...
1
vote
2answers
49 views

Number of finite-state machines with $n$ states, output alphabet size $a$, and binary input

How many FSMs are there where the machine has $n$ states, reads a binary symbol at each time-step, and may or may not output a symbol from an alphabet of size $a$ after each transition?
0
votes
2answers
69 views

Find the coefficient of $x^{17}$

Find the coefficient of $x^{17}$ in:$$ (1 + x^5 + x^7)^{20}$$ $x^{17} = x^{5} x^5 x^{7}$ I would say: $$\frac{17!}{5!5!7!} $$ But this isnt the correct answer. I know I need to use ...
2
votes
1answer
53 views

Homomorphism of Free Groups

I am reading the theorem of homomorphism of free group from Fraleigh's text in $\S$36 and could only get a fuzzy idea at best: Let $G$ be generated by $A = \{a_i \mid i \in I \}$ and let $G'$ be ...
1
vote
1answer
38 views

TCP Connection, 6 Packets, Probability of certain arrival orders

So I have a very hard time with statistics and probability. This comes from not being able to extract what I need to do from the given information. I don't get why I can't solve such easy stuff... :( ...
2
votes
2answers
47 views

Ways to make change

Given unlimited coins with values $1^2$, $2^2$, $3^2$, $4^2$,..., $17^2$ Now given an amount X, in how many ways can we exchange it using these coins? Example for $X=24$ answer is $16$. It means ...
3
votes
1answer
32 views

Equality of unions of subsets of finite set

For $n \in \mathbb{N}$, let $\alpha_n$ be the biggest number such that there exist $\alpha_n$ subsets $M_1, \dots, M_{\alpha_n} \subseteq \{1, \dots, n\}$ with the property \begin{equation*} M_{i_1} ...
10
votes
1answer
487 views

A polynomial sequence

I have a sequence of polynomials $Q_k(x, y)$, $k\geq 1$ defined recursively as follows: $Q_1=x$. There is a sequence of polynomials $p_j(y)$ of degree $j$ such that $Q_{2m}$ is of the form ...
-3
votes
0answers
36 views

12- In a standard deck of 52 cards, how many ways can you deal out 4 cards that are all black or all not face cards? [duplicate]

I did the sad mistake of taking math in summer school to boost my average. I am stuck on a few questions. In a standard deck of $52$ cards, how many ways can you deal out $4$ cards that are all ...
2
votes
2answers
54 views

Simplifying a Triple Summation

I have the summation: $$ \sum_{c=1}^{n-1} \sum_{k=c}^n \sum_j \frac{\rho(n,k)}{j!(k-c-j)!(c-j)!} $$ Where the sum $j$ goes from $0$ to $k-c$ if $k-c \leq c$, but if $k-c \geq c$ then the sum goes from ...
0
votes
0answers
11 views

Is this a Combinatorial Optimization problem with Multiple Constraint Satisfaction?

Given n-dimensional data consisting of over 20000 samples with 200 dimensions, using this as an example: ...
1
vote
1answer
61 views

“At least” type probability question.

Recently, I asked a question: Team A has more Points than team B Though I ultimately got the right answer, it took extreme casework, and long computations. My question is: suppose the question was ...
1
vote
1answer
53 views

Graph where every vertex has degree 3, perfect matching?

Suppose $G$ is a graph where every vertex has degree $3$. There is no single edge which separates the graph. My question is, must $G$ necessarily have a perfect matching? I tried drawing some graphs ...
13
votes
1answer
134 views

“Binomiable” numbers

Is there a nice criterion to determine whether a given natural $m$ can be written as a binomial number $\binom{n}{k}$ with $1 < k < n-1$? I've been thinking on this problem with a friend and ...
0
votes
0answers
70 views

Reference request for well known theorem in combinatorics

From where, I can find the proof of the following theorem. I have to to cite it, in my research article. Theorem: The combination $ {n} C {r}$ is the number of possibilities for ...
2
votes
1answer
34 views

Algorithm for generating restricted integer composition of N in k parts from interval [a,b] given the lexicographic number.

Consider the restricted compositions of $6$ in four parts from integers $\{1, 2, 3\}$. ...
2
votes
1answer
23 views

A construction of a Hadamard matrix

Let $H_n$ be a $2^n \times 2^n$ matrix indexed by all subsets of $[n] = \{1,\ldots,n\}$ and let the entry at the intersection of the row and column indexed by the sets $X$ and $Y$ be $$(-1)^{ |X \cap ...
1
vote
0answers
29 views

Predicate logic a game where player goes first?

What kind of predicate logic statement describes a game that the person who goes first can always win? Write you answer in terms of successive moves by two players. I am lost here I tried initially ...
1
vote
2answers
26 views

Number of edges Upper Bound

Given a simple graph with $n$ vertices and $m$ edges, then show: $m \le \binom{n}{2}$. Obviously the equality holds when the graph is complete, and if you have less edges, then the inequality would ...
2
votes
4answers
88 views

Probability that team $A$ has more points than team $B$

Seven teams play a soccer tournament in which each team plays every other team exactly once. No ties occur, each team has a $50\%$ chance of winning each game it plays, and the outcomes of the ...
0
votes
0answers
37 views

What will be Terms after repeating this step(Differentiation and multiplication) F times.

I was solving a probability problem and got stuck on the following situation, where each x_i is independent of others: $$f=(x_1+x_2+..x_k)^N$$ I'm interested in the expression obtained after ...
2
votes
1answer
53 views

Finding the number of ways to pick ${n}$ marbles from a jar

Problem: А jar contains 8 blue marbles, 6 green marbles, and 4 red marbles. Five marbles are selected at random, all at once. In how many ways can: A.) two red and three blue marbles be obtained? ...
7
votes
0answers
80 views

A matrix with a dense submatrix - application of Chernoff’s Inequality

I am trying to solve an exercise from this book, which I will post here for convenience. I have a bit of a problem understanding how the hint of using Chernoff's bound implies the claim. Specifically ...
2
votes
0answers
22 views

Prove for $ \forall n \in \mathbb{N}, \exists x,y,z$ ( $0 \leq x < y < z$ ) such that $ n = \binom{x}{1} + \binom{y}{2} + \binom{z}{3}$ [duplicate]

I'm trying to solve a problem from the combinatorics book. Prove or disprove for $ \forall n \in \mathbb{N}, \exists x,y,z \in \mathbb{N} $ ($0 \leq x < y < z$) such that $$ n = \binom{x}{1} + ...
7
votes
1answer
81 views

Is the set $\phi(\mathbb{N})$ syndetic?

A set $A \subset \mathbb{N}$ is said to be syndetic if the gaps in $A$ are bounded. Is the set $\phi(\mathbb{N})$ syndetic? (where $\phi$ denotes de Euler totient function) I've thought quite a ...
1
vote
1answer
33 views

Finding the number of combinations

A teacher distributes 7 books to 7 children (each student a books), on the next day she collects the books back and redistributes in such a way that each students get a new book. In how many ways can ...
2
votes
2answers
85 views

Verify input is the sum of other numbers

I have a relationship: 4000k + 2500j + 400g = n, k >= 0, 0 <= j <= k, 0 <= g <= j I have to, given n, verify ...
9
votes
0answers
170 views

Maximum integer not in $\{ ax+by : \gcd(a,b) = 1 \land a,b \ge 0 \}$

Ryan asked about a variation of the coin problem, which was whether for any coprime natural numbers $x,y$ every sufficiently large natural number is $ax+by$ for some coprime natural numbers $a,b$. ...