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
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
26 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
92 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
27 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*...
2
votes
1answer
48 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
81 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
50 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
30 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
54 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
42 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
40 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
23 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
41 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 ...
-1
votes
2answers
48 views

How to determine the number of integer solutions to this particular case?

Consider the equation $$z_1 + z_2 + z_3 + z_4 + z_5 + z_6 = k$$ For: $i = 1, \dotsc,6$ $z_i$ is a positive natural number and they must satisfy the following: \begin{align} z_1 & \ge 4 \\ z_2 ...
3
votes
2answers
30 views

How many bit strings of length $N$ are there such that the all ones lie within a window of length $K$?

Out of all bit strings of length $N$, we need to count how many of them are there in which all the ones are present in a window of length $K$. For this, my initial thought was: The starting point of ...
0
votes
0answers
19 views

Efficient algorithm to list all sequences that sum up to a constant value

We are given A set of T numbers S1, S2,....ST An integer called Range This means 1st number can take on (2*Range+1) values (S1-Range,S1-Range+1,...S1, S1+1,....S1+Range) Similarly 2nd, ...Tth can ...
8
votes
3answers
199 views

Determine the largest natural number $r$ with the property that among any five subsets with $500$ elements of the set $\{1,2,\ldots,1000\}$

Question: Determine the largest natural number $r$ with the property that among any five subsets with $500$ elements of the set $\{1,2,\ldots,1000\}$ there exist two of them which share at least $r$ ...
1
vote
2answers
58 views

number of subsets of the positive integers that whose members sum to n

What is the number of subsets of the positive integers that whose members sum to n. Example, subsets of the positive integers that whose members sum to 5. These are the subsets: {5},{4,1},{3,2},{3,1,...
0
votes
1answer
31 views

Find the number of ways of choosing three initials from the alphabet if none of the letters can be repeated

This question is from Marcel Finan A Probability Course for the Actuaries A Preparation for Exam P/1 4.8 Find the number of ways of choosing three initials from the alphabet if none of the letters ...
0
votes
2answers
65 views

How to pick $10$ people from $13$ such that at least $1$ is a woman

Problem 10c from here. Thirteen people on a softball team show up for a game. Of the $13$ people who show up, $3$ are women. How many ways are there to choose $10$ players to take the field if at ...
0
votes
2answers
44 views

How many ways can we put $m$ people in the circle with $m+r$ identical seats?

There are $m$ different people and a circle that has $m+r$ identical seats. How many ways can we put those people in the circle? If the seats were not identical then the solution was: $ \frac{1*(m+r-...
2
votes
0answers
32 views

Factorization of Schur polynomials

For a weakly decreasing sequence of non negative integers $\lambda = (\lambda_1, ... , \lambda_n)$ the Schur polynomial $S_\lambda$ is defined as $S_\lambda(x_1,x_2,...x_n) = \sum_T x_1^{t_1}x_2^{...
-1
votes
1answer
47 views

Iterate through integers solutions of linear inqualities [closed]

Say we have a set of integers value $x_1,\ldots x_n$ such that $$ \left\{ \begin{array}{l} a_{1,1} x_1 + \ldots a_{1,n}x_n \leq b_1 \\ \vdots \\ a_{m,1} x_1 + \ldots a_{m,n} x_n \leq b_m \\ x_1, \...
1
vote
1answer
46 views

Could someone help decode what this combinatoric problem is asking me?

The problem: There are $10$ professors at a certain CS department. According the tentative course schedule, there are $7$ distinct courses that should be taught next semester. Please count in how ...
1
vote
5answers
85 views

How many ways can we put $n+2$ different balls into $n$ different cells?

There are n different cells and $n+2$ different balls. Each cell can not be empty. ($n>0$). How many ways can we put those balls into those cells? My solution: Let's start with putting one ...