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
1answer
26 views

A question about the elementary symmetric polynomial

I have asked this question and have come up with a possible answer $$ \frac{d^j}{dx^j}[\frac{(x)_c}{j!}] = e_{c-j}(x,x-1, \cdots ,x-c+1) $$ My first question is, how can I prove this? It seems trivial ...
1
vote
2answers
39 views

Cartesian product sets

I'm preparing a lesson on the Cartesian product of two sets and I have run into the following confusion: I understand that the Cartesian product is not a commutative operation. Generally speaking, ...
2
votes
2answers
52 views

Task about dice - combinatorics

We have $27$ dice. We throw them all. What is the probability to have eight $6$s, nine $5$s and four $4s$ after throwing them? ($6$s means side of the die, which has$ 6$ dots; $5$s - same but $5$ ...
-1
votes
1answer
42 views

Average number of tries to reach 5 successes.

So, I have a somewhat non-trivial probability question. The situation is as follows: You start off with 5 blank spots in order. In order to fill this spot, you flip a coin/any other event with a ...
2
votes
3answers
56 views

Find all possible combinations of $A, A, A, B, B$

10 year old daughter has this problem. She knows that all possible combinations of $A,B,C,D$ are $4! = 24 $ She figured it like this: If I write down $A$ first, it has $4$ possible places. If I ...
-2
votes
1answer
27 views

Permutations and image of numbers [closed]

How can I solve this? How many is permutations of the numbers 1,...,10 in which no even number maps to itself. Thanks
0
votes
1answer
9 views

One more recurrence relation degree 3 problem.

If you can answer one I would be forever thankful. I'm doing them right now and I just want to check my work on here. I know you start with getting the characteristic equation x^3=6x^2-12x+8 for the ...
0
votes
1answer
31 views

How to solve this recurrence relation of degree 3?

I'm just wondering how to do this problem. I know I have to make the characteristic equation. Thanks
1
vote
1answer
38 views

Strategy for number of non-negative integers solutions such that $x_1+x_2+\frac{\enspace\enspace\enspace}{}+x_5 = 50$

I'm trying to figure out the number of solutions to the following problems, although I'm not entirely sure what strategy I should use to solve these. Combinations of non-negative integers ...
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
28 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
98 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
53 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
20 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
8 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
77 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
22 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
24 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
53 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
28 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
47 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
26 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 ...