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)

1
vote
3answers
45 views

Simplify $\sum_{i,j}\left[{n}\atop{i+j}\right]\binom{i+j}{i}$

I have to simplify $\sum_{i,j}\left[{n}\atop{i+j}\right]\binom{i+j}{i}$. I looks like we have $n$ children and we have to answer how many times we can arrange them into circles and color some of ...
0
votes
1answer
13 views

Gallai's theorem on independent edges

In a simple graph of $n$ vertices let $\alpha(G)$: the maximal number of independent vertices (no two of them have a common edge) vertices $\beta(G)$: the minimal number of covering vertices (edges ...
3
votes
1answer
55 views

how many ways to fill the room

How many ways are there to fill a $3\times10$ room with $1\times2$ tiles? I tried to solve this problem $\binom{30}{2}\times\binom{28}{2}\times\cdots$ but then I noticed that they may not be next to ...
4
votes
2answers
36 views

Stirling number equality

How to prove that $\left\{{n}\atop{k}\right\} = \sum_{i_1,\ldots,i_{n-k}}i_1\cdot i_2\dots i_{n-k} \cdot [1\le i_1\le i_2 \le \ldots \le i_{n-k}\le k]\ $ and $\left[{n}\atop{k}\right] = \sum_{i_1,\...
1
vote
1answer
34 views

Number of n-permutations with repetition

Let $a_n(k)$ be number of n-permutations with repetition on set $\{1,\dots,k\}$ in which $k$ occurs odd numbers of times. I have to find formula of $a_n(k)$ for $k > 1$. Let $b_n(k)$ be number of n-...
0
votes
0answers
93 views

Binomial-like distribution with shifting probability

Suppose a student answers a question from a teacher, his probability of getting the question right is p, for each successive answer he gets right, p is reduced by r because the teacher decides to make ...
1
vote
2answers
79 views

A combinatorics problem I can't quite understand

A pizzeria offers 777 types of pizza and 3 types of soda. Mary goes there everyday for lunch, always buying one slice of pizza and one soda. However, she never gets exactly the same thing on two ...
1
vote
1answer
41 views

Graph theory: The average degree of G is at least k

Let $G=(V,E)$ be a simple graph with at least $k+1$ vertices, Suppose that for every two vertices that are not adjacent $u,v$ : $d(u)+d(v) \ge 2k$. Prove or disprove: The average degree of G is at ...
1
vote
1answer
37 views

Probability of picking balls with same color with replacement and without replacement

This is one of our probability exercise: We have an urn with m green balls and n yellow balls. Two balls are drawn at random. What is the probability that the two balls have the same color? (...
2
votes
2answers
78 views

Find $\mathbb P (X_1 + \cdots + X_n = 6n-3)$

A fair die is tossed n times (for large n). Assume tosses are independent. What is the probability that the sum of the face showing is $6n-3$? Is there a way to do this without random variables ...
5
votes
3answers
76 views

Find $2^k$ elements from the set ${0,1,\cdots,3^k-1}$ such that none of these element is the average of two other elements of $T$.

The problem is: Consider the set $S = \{0, 1, 2, \ldots, 3^k-1\}$. Prove that one can choose $T$ to be a $2^k$-element subset of $S$ such that none of the elements of $T$ can be represented as the ...
0
votes
1answer
24 views

Find $i^{\text{th}}k-\text{combination}$ in lexicographic order

I would like to obtain the $i^{\text{th}}k-\text{combination}$ in lexicographic order. For instance, for $comb(10,5)$: $i=0: [0,1,2,3,4]$ $i=1: [0,1,2,3,5]$ $i=2: [0,1,2,3,6]$ $\dots$ $i=10: [0,1,2,...
3
votes
3answers
91 views

Number of solutions of: $3x+y=5702$

Find the number of ordered pairs $(x,y)$ satisfying $3x+y=5702$ in natural numbers restricted by: $x+y\le2003$ I don't know any method for counting number of solutions of such equations...
1
vote
1answer
43 views

Shuffles a deck of r ranks and k suits; looks for m cards of the same rank dealt in a row

This is a question that has arisen in my work. Game the First: the dice game. Suppose I have a fair die with r faces. Given some k, I roll the die r*k times; call that sequence of rolls a game. ...
0
votes
0answers
21 views

Probability of getting a “full house” by rolling dice [duplicate]

In poker, full house means getting three cards with the same rank, and another two cards with the same rank (not the same as other three cards). I can understand how to use combination to solve this ...
1
vote
4answers
121 views

What is the probability that a person wearing a blue t-shirt will sit next to one wearing red?

9 people sit in a row linearly. 2 dressed in Red, 3 blue and 4 in yellow. What is the probability that a person in blue will sit next to a person in red? Why? RRBBBYYYY this sequence from what I ...
-1
votes
2answers
60 views

Billy has 5 books and 6 novels, in how many way can he pack 5 books so that at least 2 are novels?

So you'd work out in how many ways he can take 5 books with him $11 \choose 5$ Then what? :/
0
votes
1answer
40 views

What is the probability that at least 2 people in class have the same birthday?

The title states the full question I was provided with. Am I able to just assume the class contains more than 12 students? If so, would we just do: (n choose 2?); where n = number of students in ...
0
votes
1answer
26 views

How many six digit integers contain zero exactly twice.

I can't seem to figure this out. We're provided with the answer (65610) but no matter what I do , I can't seem to find the mathematically. My idea was to let A = the number of six digit integers = $9*...
1
vote
0answers
40 views

What is the Probability came from the same machine

Machine A produced 65 of the day’s output of Product X and machine B produced the other 55. If three products are selected with replacement at random from the day’s output, the probability that, My ...
5
votes
2answers
79 views

Inclusion–exclusion: Matrices

Let $A$ be an $n\times n$ matrix that contains all the numbers $1,2,\ldots,n^2$ (each one appears one time). Count the number of $n \times n$ matrices $B$ that contain all the numbers $1,2,\ldots,n^2$ ...
1
vote
1answer
44 views

Do you have a better chance of getting hit by lightning or winning the lottery?

The actual problem is stated as follows: The chance of getting hit by lightning is 1 in 600,000. In the lottery you will play, you'll chose 6 numbers out of the first 30. Do you have a better chance ...
0
votes
2answers
40 views

Permutations of n numbers with no odd numbers next to each other

What is the number of $\{1, 2, \dots, n\}$ permutations, in which neither two neighbouring numbers are odd? Could somebody show me the reasoning that leads to the answer?
0
votes
3answers
50 views

How many combinations are there for the interior angles of a triangle?

Suppose the interior angles of a triangle are all Natural numbers. How many combinations of angles are there without repeating similar triangles? So for instance, {1,1,178}, {1,2,177},...But without ...
2
votes
1answer
48 views

How many transitive relations on a set of four elements are functions?

How many functions $f:\left \{ a,b,c,d \right \}\rightarrow \left \{ a,b,c,d \right \}$ are also transitive relations? Sorry if I have mistakes in my English. I understand that $f$ is supposed to ...
0
votes
0answers
29 views

Which of the twelvefold way?

Sorry - basic question. Which of the twelvefold way does the following scenario correspond with? I have two buckets. The first bucket comprises 3 unique balls and the second bucket comprises 5 ...
0
votes
2answers
29 views

Rolling a loaded die and the probability of getting the third six on the 7th roll

A die is loaded in such a way that the probability of the face with j dots turning up is proportional to $j^2$ for j = 1,2,3,4,5,6. What is the probability of getting the third six on the 7th roll of ...
4
votes
0answers
34 views

Optimal strategy in an idealized dating scenario

The question I have is in some ways a variation on the stable marriage problem adapted to the situation of dating. Suppose there are $n$ boys and $n$ girls, where every boy ranks the girls from $1$ ...
0
votes
1answer
23 views

Number of intersecting subsets

Suppose that we have a universe $U= \{1,\dots,n\}$ for some integer $n$. How many subsets $S_1,S_2,\dots\subseteq U $ are there such that $S_i \nsubseteq S_j$ but $S_i \cap S_j \neq \emptyset$ for all ...
3
votes
0answers
29 views

Coupon collection with trading of doubles

I've been answering old unanswered coupon collection questions recently, and in thinking what other variations might be interesting I came up with this: There are $n$ coupon types. You ...
2
votes
3answers
53 views

How many bit strings of length $5$ do not have consecutive $1$'s?

How many bit strings of length 5 do not have consecutive 1's? I'm trying to think of a way to calculate how many ways we can arrange a string of length 5 starting with the first position (or index). ...
1
vote
4answers
49 views

Why is this a permutation instead of a combination?

Textbook question: (apologies for the "baby math" question) A new company with just two employees, Sanchez and Patel, rents a floor of a building with 12 offices. How many ways are there to assign ...
0
votes
0answers
22 views

How do I calculate the degrees of freedom for this odds ratio?

I don't have a math background so I'm kinda improvising right now. I have a feeling the regular n-1 or n1+n2-2 rule doesn't apply here. These are the conditions. 522 people with diabetes 346 ...
0
votes
1answer
26 views

Probability that a set of uniformly distributed random variables is 'greater' than another such set.

Suppose we generate several uniformly distributed random variables (between 0 and 1), and arrange them in descending order to form a set [A1, B1, C1...]. We then do the same process to form a second ...
3
votes
1answer
64 views

How many sets correspond to connected graphs

I'm trying to solve this project euler problem. I don't want to get too much help, since that would defeat the purpose, but I'm hitting a wall, so I'm asking a related problem here, from which I'll ...
11
votes
4answers
1k views

How many bit strings of length 8 start with “1” or end with “01”?

A bit string is a finite sequence of the numbers $0$ and $1$. Suppose we have a bit string of length $8$ that starts with a $1$ or ends with an $01$, how many total possible bit strings do we have? I ...
1
vote
0answers
41 views

List of positive integers from $1$ to $N$ that is NOT divisible by a list of prime numbers.

Give a list from $1$ to $N$ where $N$ is a positive non-zero integer and a list of prime numbers $p$, $q$, $r$, etc. What are the number of cases left from the $N$ list that are not a divisible by any ...
0
votes
1answer
39 views

How many different ways are possible

Twenty students, including John, Casey and Michelle, are candidates to serve on a committee of six. (a) How many different ways of committees are possible if contain three of them? My attempt(Not ...
2
votes
1answer
22 views

Ordered Integral solutions

If $a\times b\times c = 12 \times \gcd(a,b,c)$, how many ordered triplets $(a,b,c)$ are possible? Assuming $a=hx,b=hy,c=hz$ where $h=\gcd(a,b,c)$ .I am getting $h^2xyz=12$. Solving this I am getting ...
5
votes
0answers
64 views

Show that $\sum_{d\mid f} \varphi(f/d) a^{|d|} \equiv 0 \pmod f$

This equation is correct when $f$ and $a$ are any integers. I want to show that this holds for $f,a\in K[x]$ where $K$ is any finite field. In the equation $\varphi(f)$ is defined as $|(K[x]/(f))^\...
0
votes
3answers
50 views

Equality with binomial coefficient

I don't understand a step of a solution: Let $m,n\in\mathbb{N}$ and $r\in\{1,\dots,m+n\}$ then $$(1+x)^{n+m}=\left(\sum\limits_{i=0}^m \binom{m}{i}x^i\right)\left(\sum\limits_{j=0}^n \binom{n}{j}x^j\...
2
votes
3answers
49 views

Closed form for this series involving multiple binomial coefficients

The series is: $$\sum_{k=1}^m k {n-1 \choose n-k}{m \choose k}$$ where $m \leq n$. Is there a better form for this series? Perhaps, can we clean up the binomial coefficients somehow to make the ...
1
vote
1answer
25 views

2 variables “variable weighting” function

I have two variables $X,Y \in [0,1]$ and want to output some kind of weighted indicator based on these two. X is a raw indicator value where a low value indicates good health, and Y measures ...
3
votes
4answers
105 views

How many words of length $n$ can we make from $0, 1, 2$ if $2$'s cannot be consecutive?

How many words we can make from $0,1,2$? The restriction is we can't put the digit $2$ after the digit $2$. My solution: I tried to solve it with Inclusion-Exclusion Principle. Count the number of ...
2
votes
1answer
21 views

Expected number of buckets

Suppose you have three buckets A, B and C. Every ball goes into a bucket according to a uniform distribution (same likelihood for every bucket). Every ball also has a number. During a time window of ...
0
votes
1answer
41 views

Summation involving factorial

It is known that $\sum_{k = 0}^{n } {n \choose k}(k!) = \lfloor e \cdot n! \rfloor $ But is it known what $\sum_{k = 0}^{n} {n \choose k} (k! \cdot (n-k)!)$ is equal to?
2
votes
2answers
40 views

first card club and second card ace?

Larsen and Marx Suppose that two cards are drawn—in order— from a standard 52-card poker deck. In how many ways can the first card be a club and the second card be an ace? I think there are ...
0
votes
3answers
34 views

A boat is to be manned by 8 men,of whom 2 can only row on bow side & 1 can only row on stroke side;in how many ways can the crew be arranged?

I tried it by selecting 2 men out of 8 for bow side,and then arrange them in 2! ways.This can be done in$ \binom{8}{2}$*2! ways,and the stroke side can be crewed in 6 ways.So the required no. of ways ...