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 (5)

0
votes
0answers
17 views

Generating Functions and Power Series

The question is Use partial fractions and the generalised binomial theorem to write $R(x)$ as a power series where $R(x)$=$-1+5x\over{1-x-2x^2}$ I found the partial fractions to be ...
1
vote
1answer
26 views

Why is this an example of n choose k? Confusion about combination

I am learning about combinations & I am not understanding how one example of nCk applies, since it is conceptually a bit different from example problems. I have come to understand nCk as the ...
1
vote
1answer
35 views

Listing all k-element subsets of an n-element set where consecutive sets differ by 2 elements

Let $S$ be the set of all $k$-element subsets of some given universe $M$. My question is as follows: Is it possible to enumerate (without repetition) the elements of $S$ such that each pair of ...
0
votes
1answer
87 views
+50

Find the number of ways giving name tags such that there exist a student who don't exit the table after 4 operations.

Question: There are $n$ students sitting at a round table. You collect all $ n $ name tags and give them back arbitrarily. Each student gets one of the $n$ name tags. Now the $n$ students repeat ...
1
vote
2answers
59 views

Number of ways to distribute 100 identical chairs among 4 different rooms

In how many ways can 100 identical chairs be divided among 4 different rooms so that each room will have 10,20,30,40 or 50 chairs? I'm having problems coming up with the generating function for this ...
0
votes
0answers
37 views

Mathematical proof to find the length of each side of a square filled with Regular Hexagons

I have to prove or disprove that in a square box if there are full regular hexagons( whose distance from center to every corner is r) inside it, then the centers of those hexagons should lie inside ...
0
votes
1answer
52 views

Number of arrangement of six LEGO bricks

I came across a very interesting question on how many different combinations there are when you have six eight-stud LEGO bricks (with the same color). I found this article saying that there are 915 ...
1
vote
1answer
16 views

Dirichlet's principle- task.

Given is set $S$ where $|S| = n > 1 $ and his subsets $M_1, ..., M_{n+1}$ such that $M_i \neq M_j, i \neq j $ Using Dirichlet's principle prove that exists $A, B$ where $A,B \subset \{1,...,n+1\} $ ...
3
votes
1answer
29 views

Stars and Bars problem involving odd restriction, and equal or greater than restriction.

I just had this question in an exam and was unsure how to complete some parts using the Stars and Bars method. Problem as follows: How many solutions has the equation: $x_1 + x_2 + x_3 + x_4 + x_5 ...
0
votes
2answers
38 views

Is this proposition posible? [duplicate]

In a board, you have $13$ White round pieces, $15$ Black round pieces, and $17$ Red round pieces. In each round you can choose two different color pieces and change them with two other pieces of ...
0
votes
0answers
21 views

Taking derivative of a partial bell polynomial?

I am trying to prove a statement that involves me taking the derivative of a bell polynomial. Is there an elementary way to express: $$ \frac{d}{dx}[ B_{n,k}(x_1,x_2,....,x_{n-k+1})] $$ Where you ...
1
vote
0answers
39 views

A list of numbers and

I have a real life problem that math may be able to solve. I am no mathematician so if you have any insight please use the simplified version. This problem is way beyond me. My gut tells me there is ...
3
votes
0answers
38 views

How many ways to place 3 non-attacking bishops given the following conditions

How many ways are they to place 3 non-attacking bishops on an $n \times n$ board such that $2$ of these bishops are placed within the $(n-1) \times (n-1)$ board and the other 1 is placed outside of ...
1
vote
1answer
31 views

How many different ways are there from $(0,0,0)$ to the point $(4,3,5)$?

I had an exam in my introduction to combinatorics lectures today, there was a question like this: In the $3D$ space, consider the points of integer coordinates. Using only moviments corresponding ...
0
votes
0answers
19 views

Find a recurrence relation for the number $a_{n,m,k}$ of distributions of $n$ identical objects into $k$ distinct

Find a recurrence relation for the number $a_{n,m,k}$ of distributions of $n$ identical objects into $k$ distinct boxes with at most four objects in a box and with exactly $m$ boxes having four ...
0
votes
0answers
7 views

Split Question: Bergelson multiplicative density of evens and powers of 2

This post splits the post: Questions about Bergelson multiplicative upper density into one more concentrated series of questions. It is largely copied directly. Let $\mathbb{P} \subset \mathbb{N}$ ...
0
votes
0answers
23 views

Find a recurrence relation for the number of regions created by n mutually intersecting circles on a piece of paper.

Find a recurrence relation for the number of regions created by n mutually intersecting circles on a piece of paper (no three circles have a common intersection point).
1
vote
2answers
76 views

A) Find a recurrence relation for the number of n-digit binary sequences with no pair of consecutive 1s.

A) Find a recurrence relation for the number of n-digit binary sequences with no pair of consecutive 1s. (A binary sequence only uses the numbers 0 and 1 for those who don't know) B) Repeat for ...
2
votes
0answers
21 views

Split Question: Bergelson Multiplicative Density of “Even-like” sets

This post splits the post: Questions about Bergelson multiplicative upper density into one more concentrated series of questions. It is largely copied directly. Let $\mathbb{P} \subset \mathbb{N}$ ...
2
votes
1answer
32 views

A specific group lacking Følner sequences

How does one go about proving that the free group $<a,b,a^{-1},b^{-1}>$ lacks any Følner sequence?
0
votes
0answers
15 views

Questions about Bergelson multiplicative upper density

Let $\mathbb{P} \subset \mathbb{N}$ be the set of all primes. Let $\forall n \in \mathbb{N}, F_n = \{a_n \prod_{i=1}^n (p_i^{r_i}): a_n \in \mathbb{N}, p_i \in \mathbb{P}, r_i \in [0, N_i(n)] \cap ...
5
votes
5answers
1k views

How many even 3 digit numbers contain at least one 7.

How many even 3 digit numbers contain at least one 7. I got 126, but it was not an answer choice for the problem. Can anyone help?
0
votes
0answers
7 views

Question about a possible relationship between additive and Bergelson multiplicative upper densities

Let $A \subseteq \mathbb{N}$; let $\mathbb{P} \subset \mathbb{N}$ be the set of all primes. Let $\forall n \in \mathbb{N}, F_n = \{a_n \prod_{i=1}^n (p_i^{r_i}): a_n \in \mathbb{N}, p_i \in ...
0
votes
1answer
48 views

How to show a number is not a sum of squares

I've been tasked with the following: Let $m$ and $n$ be positive integers, prove that $4^{n}(8m+7)$ cannot be written as the sum of three squares. I've already gotten the idea that I should do ...
-4
votes
0answers
37 views

Probability in The Senate

Each of the 50 states has two senators. In order for a bill to pass, it must have at least 50 votes. Suppose a bill passes with the minimum number of votes. Compare the probability that at least one ...
1
vote
2answers
41 views

Flipping a coin until 4 heads occur, or until flipped 7 times. How many combinations are possible?

Question: A coin is tossed until either 4 heads occur or until the coin has been tossed 7 times. How many heads/tails sequence are possible? For example, HTHTTHT, HHHH, THHTHH, and TTTTTTT are all ...
-3
votes
2answers
21 views

Permutations and combinations - how many ways to select? [closed]

From eight persons A, B, C, D, E, F, G, H, four has to be selected such that if A is selected, B also has to be selected. How many this can be done?
1
vote
2answers
23 views

Probability of selecting three of the same thing from a collection

Question: A collection of 6 items is to be randomly drawn from a bin containing 100 good items and 8 defective items. What is the probability that exactly 3 of the items chosen are defective? My ...
1
vote
1answer
40 views

How often do I need to draw until all balls in an Urn are of the same color?

Suppose there is an Urn with $n$ balls, $m$ being white and $(n-m)$ being black. Now we draw $c, c < n$ balls - any white ball drawn will be colored black - then we put all balls back into the Urn ...
1
vote
2answers
28 views

How many non-decreasing sequences of finite length do exist?

Given a finite set of numbers $A=\{1,2,\dots,k\}$. How many sequences $a_{1} a_{2}...a_{n}$ of length $n$ with $a_i\in A$ and $a_i \le a_{i+1} $ for $i\in \{1,\dots,n-1\} $ do exist? Obviously, if ...
0
votes
0answers
30 views

Find a strong orientation such that $G$ can reach $D$ within $7$ steps.

Find a strong orientation such that $G$ can reach $D$ within $7$ steps. I found the following strong orientation. Can it be counted as an answer since I can reach from G to D in 1 step? EDIT: ...
2
votes
3answers
52 views

Proving a Binomial Sum

How do I prove that $$\sum_{r=0}^{n-1}\left[ r \binom{n}{r} \binom{n}{r+1}\right]=n \binom{2n-1}{n-2}$$ without induction? I've tried manipulating $(1+x)^n$ and the binomial coefficients, but to no ...
1
vote
0answers
24 views

Counting binary strings that have atmost k consecutive 0's

I know how to count how many binary strings with length n and having exactly k 0's are there but i am not able to find a way to count the number of binary strings that have exactly x 0's and y 1's and ...
0
votes
0answers
30 views

number of pairs of equal elements in the sample

Version 1: let $P$ be a discrete probability distribution with support over whole $\mathbb{N}$. What is the probability of having exactly $m$ pairs of equal items in a sample of size $n$ drawn from ...
1
vote
1answer
46 views

Queens on a chessboard

What is the smallest number of queens that can be placed on a chessboard so that every square is either occupied or can be reached in one move?
1
vote
1answer
25 views

Obtuse triangles in a regular polygon

How many triangles formed by three vertices of a regular $17$-gon are obtuse? As an extension, how many triangles formed by three vertices of a regular $n$-gon are obtuse?
0
votes
1answer
24 views

solving a inclusion-exclusion problem

Given N positive integers, not necessarily distinct, how many ways you can take 4 integers from the N numbers such that their GCD is 1. For example,N=10 and the positive integers are ...
0
votes
1answer
29 views

proof of a formula

I need combinatorial approach to prove the following formula.I read books and internet articles but I didn't find a satisfactory explanation.Here is the formula to calculate ordered bell numbers. I ...
3
votes
3answers
99 views

What's the probability of a straight in $5$ card poker given $5$ and $7$ of hearts?

Using a standard $52$ card deck, if you are given the $5$ and $7$ of hearts from it, what is the probability that you end up with a straight if $3$ additional cards from that same deck are given to ...
1
vote
2answers
103 views

Permutations / Combinations - suppose a word is a string of 8 letters of the alphabet with repeated letters allowed

1.) How many words are there? Not sure how to solve this since repeated letters are allowed. $n^r$ is the formula we are told to use for permutations with repeated objects, but $26^8$ seems like too ...
1
vote
1answer
22 views

Combinatorics problem

I am trying to solve this question, my solution involves solving a combinatorial problem as follows : Number of arrangements of exactly k distinct elements in n slots such that each one of the ...
0
votes
0answers
40 views

Approximation for fewest incompatibilities in a task scheduling selection algorithm

Suppose you have a task selection algorithm to select the largest subset of tasks that do no overlap. The greedy algorithm that selects tasks based on their finish time will always produce an optimal ...
0
votes
1answer
37 views

Making reccurence relation

I have trouble in understanding how to make recurrence relations. I read some of the questions on stack exchange but this stuff is not intuitive to me. For example, when we want to find a number of ...
1
vote
2answers
69 views

Proving a combinatorics equality

How to prove the following? Should I use induction or something else? Let n and r be positive integers with n ≥ r. Prove that $${\binom{r}{r}} + {\binom{r+1}{r}} + · · · + {\binom{n}{r}} = ...
2
votes
2answers
39 views

Total possible combinations of primes

I have been working on a problem as follows: Do there exist 100 consecutive natural numbers none of which is prime? I know that the answer is 'yes', by considering 101!, and noting the sequence 101! + ...
1
vote
1answer
17 views

Trying to find polynomial-time algorithms for knapsack-like problems

Consider two related problems: You have $n$ cannisters that must go into $m$ trucks that can each carry $k$ cannisters. You require that no truck becomes overloaded, and for each cannister, there is ...
0
votes
0answers
19 views

How can we show that 3-dimensional matching $\le_p$ exact cover?

In exact cover, we're given some universe of objects and subsets on those objects, and we want to know if a set of the subsets can cover the whole universe such that all selected subsets are pairwise ...
1
vote
0answers
25 views

möbius function on poset

Let $P$ be the poset of all subsets of $\{1,2,\ldots, n\}$ with av even number of elements, ordered by inclusion. There is a recursive formula for the Möbius function on a poset: $$ \mu(x,y) = ...
2
votes
1answer
95 views

Fight against the Hydra - Graph Theory

The following problem is supposed to be a nice application of the basic knowledge of graph theory. I consider it however as difficult and I would be happy if someone could help me find a solution. ...
0
votes
0answers
27 views

inverse element in incidence algebra of a poset

This question is from Stanley's Enumerative combinatorics vol 1, excercise 3.90. Let $P$ be a finite graded poset. Let $m(s,t)$ denote the number of maximal chains from $s$ to $t$, and $l(s,t)$ the ...