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
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
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
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
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
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 ...
4
votes
2answers
43 views

Prove that a sequence of degrees can be the degrees of a simple graph

Hi there I need to show that the sequence $s(n) = \{1,1,2,2,3,3,4,4,...,n,n\}$ can be the degrees of the vertices of a simple graph, $\forall n\geq 1$. So far I have tryied to prove this by induction ...
2
votes
4answers
93 views

Number of positive unordered integral solutions

What are the number of positive unordered integral solutions for $a+b+c=36$ Solution given is $108.$.But I am getting $91$ as $$\frac{\binom{35}2-3\times16-1}{3!}.$$ $3\times16($ for $a=b$ cases and ...
0
votes
0answers
10 views

Graph properties of Bruhat order for the general linear Lie algebra $\mathfrak{gl}$ on $\mathbb{Z}^n$

Let $P = \oplus_{i\in \mathbb{Z}}\mathbb{Z}\epsilon_i$ the free abelian group of infinite rank. Then we have a natural partial order $\leq'$ on $P$, that is, $a \leq' b $ if and only if $b \in a+\sum_{...
1
vote
0answers
61 views

Using Burnside's Lemma in GAP to handle special variations of the Rubik's Cube?

If you want to count the number of distinct positions of a standard 2x2x2 Rubik's Cube simple counting arguments will suffice: There are 8 corners, all distinct The 8 corners can be in any ...
3
votes
2answers
65 views

Multiples Problem

Question: Anna writes the first 1000 positive integers. She then circles the even ones with a green pen. Bob circles the multiples of three in red. Cindy circles the multiples of five in blue. How ...
2
votes
1answer
38 views

Combinatorics: Color a wall such that not two neighbored slots have the same color

We have a wall with $7$ slots. We can color the wall either with blue or red. How many combinations do we have to color the wall if two red slots cannot be neighbors? I thought, in a very intuitive ...
-1
votes
0answers
35 views

Ways to select $6$ integers with no two consecutive integers [duplicate]

Given the set of integers from $1$ to $49$, find the number of ways we can select $6$ integers from the set such that no two consecutive integers are selected.
2
votes
2answers
26 views

Nr. of combinations given K stars and N borders

I am given K stars(X's) and N inner borders, in how many unique ways can I arrange them ? empty spaces between borders is allowed. Some examples: 0 inner borders and 3 stars => 1 combination (if no ...
2
votes
2answers
64 views

The expansion of $(a+b+c+d)^{20}$ [closed]

Let us consider the expansion of $$(a+b+c+d)^{20}.$$ Find: The coefficients of $a^{11}b^6c^2d$ and $a^{11}b^9$, The total number of terms of this expansion, The sum of all the coefficients. Thank ...
1
vote
0answers
28 views

What do attendance figures tell me about regularity? What does the average tell me about individual attendance?

Suppose I have a group of $N$ people, attending a series of $M$ events, and (for simplicity) let's assume the overall attendance happens to be the same at each event, say $A$ people (ranging between 1 ...
3
votes
3answers
114 views

How many permutations of {1,2,3,…,n} there are with no 2 consecutive numbers?

How many permutations of $\{1,2,3,...,n\}$ there there are with no 2 consecutive numbers? For example: $n=4$, $2143$, $3214$, $1324$ are the permutations we look for and $1234$, $1243$, $2134$ are ...
4
votes
1answer
52 views

In how many ways can you select a committee of 3 persons, so that no two are from the same department?

The problem asks the following: A certain company has 4 departments, with 100, 200, 300, and 400 employees respectively. In how many ways can you select: (a) a committee of 4 persons, so that ...
3
votes
1answer
44 views

Filling an NxN table with N numbers

I have been confronted with the following homework question: Let $M$ be a table of size $N \times N$. A legal filling of $M$ with the numbers $\{1,\dots,N\}$ is one such that each cell of the ...
0
votes
6answers
85 views

Combinations of Permutations - Is the solution $5^7$ or $7^5$?

An example from my textbook says the following: Five persons entered the lift cabin on the ground floor of an 8 floor house. Suppose each of them can leave the cabin independently at any floor ...