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

0
votes
2answers
13 views

Discrete math: probability of picking certain hands with a preset condition

In 5-card draw poker, a player receives an initial hand of 5 cards, and is then allowed to replace up to three of her cards with the remaining cards in the deck. (b) Suppose that, among the initial 5 ...
0
votes
1answer
12 views

Permutations and Combinations

What is the probability that a 3-element subset selected at random from the set {1,2,3, … , 10} a) contains the integer 7? b) has 7 as its largest element? I know this deals with permutation and ...
0
votes
1answer
51 views

Are all uncountable infinities greater than all countable infinities? Are some uncountable infinities greater than other uncountable infinities? [duplicate]

I recently finished a discrete mathematics class, and near the end of the semester, the prof (very superficially) touched on countable and uncountable infinities. His explanation of countable ...
0
votes
1answer
18 views

How to find how many rectangular prisms ( including cubes) are in a n by n by n cube?

I somehow got the answer to be [(n+1)!/2!(n+1-2)!]^2 *n Each part of the equation represents the height, length, and width of the possible rectangular prism in the big cube. You can multiply the ...
1
vote
2answers
26 views

Counting pairs of subsets

Let A be a finite set. Show that there are $3^n - 2^n$ tuples (X,Y) where $X \subset Y \subseteq A$ and $n = \#A$. I tried to count the possibilities to build such tuples. There are ...
0
votes
2answers
22 views

How many chords of a circle with n points on it?

So, there are n points on a circle line all connected with each other building k chords. The question is, how many chords are there and how many intersection points are there. The goal is to find a ...
2
votes
1answer
18 views

building truth-functional connectives

It is known that $NAND$ and $XOR$ are the only one $2$-argument truth-functional connectives that can be used alone to create every $n$-argument truth-functional connective for all positive integer ...
1
vote
1answer
42 views

How to find how many cubes are in a n by n by n cube?

I tried finding the answer using combinatoric by determining how many different length and width ans height are there for a cube, given the size of the bigger cube. But the formula I got turns out not ...
2
votes
1answer
21 views

Given an undirected connected graph, how many orientations would maintain acyclicity

Given an undirected connected simple graph $G=(V,E)$ there are $2^{|E|}$ orientations. How many of these orientations are acyclic?
2
votes
2answers
52 views

number of solutions to $x_1 + x_2 + x_3 + x_4 + x_5 = 31$ via generating function?

I will be very happy to understand how to solve this problem with generating function: How many solutions are there to the equation $$x_1 + x_2 + x_3 + x_4 + x_5 = 31$$ where $x_i$ is a nonnegative ...
0
votes
0answers
27 views

Burnside's Lemma and Stirling Numbers of the First Kind

I've seen that $n!=\displaystyle\sum_{p=0}^n s(n, p)n^p$, where $s(n, p)$ are the signed Stirling Numbers of the First Kind, whose absolute values count the number of permutations in $S_n$ which have ...
2
votes
4answers
44 views

Count the divisors of n with particular property

Take $n = \prod_{i=1}^r {p_i}^{\alpha_i}$, where each $p_i$ is a prime and $\alpha_i\geq 1$. How many divisors of $n$, not equal to $n$, contain at least one $p_i$ with the corresponding multiplicity ...
0
votes
0answers
23 views

Introductory material on discrepancy theory

I'm interested in learning about discrepancy theory. By this I mean material such as http://math.mit.edu/classes/18.095/lect6/notes.pdf . However, I've been unable to get much from "Chazelle, ...
1
vote
1answer
44 views

The biggest number of possible sets created by $\setminus,\cup$ [on hold]

How many atmost sets can be created by $n$ sets by operations $\setminus, \cup$ .
0
votes
1answer
17 views

Tiling an $m\times n$ grid.

For natural numbers $m$ and $n$, an $m\times n$ grid of squares can be tiled with tiles of the form completely filling the grid, without overlapping, if and only if $m,n\geq2$ and $6\mid mn$. It ...
1
vote
0answers
50 views

How prove this $|S_{1}|-|S_{2}|\le 2^{2n}\binom{2n}{n}$

Question: let $n\in N^{+}$,and define set $S=\{1,2,\cdots,4n\}$, for any$ a<b\in R^{+}$,defind $$S_{1}=\{X|X\subseteq S,a\le S(X)\le b,S(X)\equiv 1\pmod 2\}$$ $$S_{2}=\{X|X\subseteq S,a\le ...
1
vote
1answer
64 views

Kind of basic combinatorical problems and (exponential) generating functions

I have a pretty straightforward combinatorical problem which is an exercise to one paper about generating functions. How many ways are there to get a sum of 14 when 4 distinguishable dice are ...
1
vote
2answers
35 views

Counting problem involving sets

Let $S$ be a set of size $37$, and let $x$,$y$, and $z$ be three distinct elements of $S$. How many subsets of $S$ are there that contain x and $y$, but do not contain $z$? How many subsets of $S$ ...
0
votes
1answer
14 views

Get number of occurences containing a specific number in combinations of N digits?

If I have all the combinations of 3 digits (000 to 999) I want to count how many results contain the digit 4: 456 104 404 ... For 4XX there are 100, for X4X it ...
0
votes
1answer
19 views

Probablity nCr problem days of week 3 chosen.

Straight from my daughter's math book :) You work 3 evenings. Your boss assigns you 3 evenings at random from 7. What's the probability of Friday being chosen. We did this long hand (drew out all ...
0
votes
2answers
24 views

Different ways of arranging a group of 10 people

In how many ways can a photographer arrange $8$ people in a row from a family of $10$ people, if (a) the bride and groom are in the photo. This would be $9*8*7*6*5*4*3*2*1=362880$, correct? (b) the ...
0
votes
2answers
18 views

Probability of weather on consecutive days.

Probability of a cloudy day is .55 Probability of a sunny day is .45 A)What is the probability of three consecutive cloudy days, followed by a sunny day? B)What is the probability that exactly 1 out ...
1
vote
2answers
43 views

Probability, chose two skittles, out of 2 skittles left from a bag of skittles with 5 colors.

so me and my friend are studying statistics but we are just stuck on this stupid skittle question we made up ourselves when we tried to guess the colors of the two last skittles so we can see who will ...
1
vote
1answer
29 views

Show that there exists a satisfactory assignment for the unstandard language of arithmetic $\{\textbf{0}, ', <_1\}$

Consider: $A1: \textbf{0} \not = x'$ $A2: x'=y' \rightarrow x = y$ $A3: \neg x < \textbf{0}$ $A4: x < y' \leftrightarrow (x < y \vee x = y)$ $A5: \textbf{0} < y ...
-1
votes
0answers
11 views

Using BCR experiment [on hold]

consider a random experiment of observing a mechanical or electrical unit consisting of five components and determining which components are working and which have failed. Use the BCR to find the ...
0
votes
0answers
31 views

A conjecture relating Multiple Zeta Values and the Polya Enumeration Theorem

Let me state my motivation. I believe that the Polya Enumeration Theorem and Multiple Zeta Values (the classic being the Basel problem and the values of the Riemann zeta function at the even ...
-1
votes
2answers
39 views

In tossing 5 6-sided fair dice, what is the probability of at least one 2 if the dice are indistinguishable?

I know that the answer is .4 because it is given. I just do not know how to get there. The answer would be .598 if the dice were distinguishable (ordered).
0
votes
2answers
20 views

probability, need help to differentiate distinct or non-distinct

I am having trouble to understand the problems based on combinatorics. In particular, I don't understand when to think in terms of disctinct object or non-disctinct object. Here is one question: ...
2
votes
1answer
54 views

How to find $\sum_{d\mid n}(w(d)w(\frac{n}{d}))$?

i) $w(n)$ is the prime divisor count function. For example $w(6)=2$ ii) Let prime factorization of $n=p_{1}^{a_{1}}p_{2}^{a_{2}}.....p_{w(n)}^{a_{w(n)}}$ iii) Lets define this function. ...
1
vote
2answers
39 views

Probability of number formed from dice rolls being multiple of 8

A fair 6-sided die is tossed 8 times. The sequence of 8 results is recorded to form an 8-digit number. For example if the tosses give {3, 5, 4, 2, 1, 1, 6, 5}, the resultant number is $35421165$. ...
0
votes
2answers
24 views

How many strings of 8 digits end with an even digit?

So there are $10$ combinations for each digit except the last which has 5 possibilities ($0,2,4,6,8$). Thus $10*10*10*10*10*10*10*5=50000000$ combinations right? As a follow up, how many strings of 8 ...
2
votes
3answers
26 views

Find the formula for the given sum of series

Find the sum of the series: $$\sum_{i=2}^{n}\binom{i}{2}= \,^{2}C_{2}+\cdots+\,^{n}C_{2}$$ I did try expanding it and see if I could simplify it further.I am unable to find a formula for it? Can ...
1
vote
2answers
18 views

Stirling Numbers of the First Kind and $S_n$.

I know that, on the one hand, if $s(n, p)$ denotes the unsigned Stirling Numbers of the First Kind, then $(x)_n=\displaystyle\sum_{p=0}^n s(n, p)x^p$, where $(x)_n=x(x-1)\cdots(x-n+1)$. It follows ...
0
votes
2answers
28 views
0
votes
2answers
36 views

permutation problem: cycle representation

Let $n$ be an odd number. Let $C_n$ be the set of permutations $\pi$ of $[n]$ whose cycle representation has only one cycle. Let $\pi,\sigma\in C_n$. Prove that their composition $\pi\sigma$ has an ...
2
votes
1answer
32 views

Probability of drawing 4 green balls from an urn when you're the last person to draw

An urn contains 24 balls, 8 of them being white, 8 green and 8 black. There are 6 people sequentially drawing these balls out of the urn (without replacement), with every person drawing 4 balls, and ...
1
vote
1answer
35 views

Algorithm to find all feasible partition of a set

By feasible I mean all the sets of the partition belongs to a predefined feasible sets. For example, I what to find a partition of {1,2,3}, and only sets in S = {{1,2}, {1,3}, {1}, {2}, {3,4,5}} is ...
1
vote
0answers
67 views

How many ways move n pies to m distances?

A table size $1\times (m+n)$ squares. Give $n$ pies on the $n$ first squares. Now, I want move $n$ pies to the end of table by $m.n$ steps ($m$ steps for each pie), satify conditions one pie only move ...
0
votes
1answer
29 views

Exercises in combinatorics

I'm always having problem with this type of question : 1). Can the set ${1,2,...,2010}$ be expressed as the disjoint union of $A_{1},A_{2},...,A_{n}$ such that a). Each $A_{i}$ contains the same ...
4
votes
2answers
92 views

Fraction Problem. 3rd grader question got parents thinking

So our nine year old son comes home from 3rd grade and tells us an amazing thing happened in school today. He was playing a math game with his friend and they got the same score two times in a row! ...
1
vote
0answers
17 views

Counting bit string with fixed values

I would like to run this questions with stack: How many bit strings of length 33 are there that start with 1010, end with 0101, and contain exactly 11 zeros. The amount of fixed bits are 8. ...
1
vote
1answer
35 views

Balls. Combinations.

A jar contains 17 red balls and 22 blue balls. How many ways are there to choose, without replacement, 8 balls from this jar. I have two answers, but they both seem right to me. Could some explain ...
0
votes
2answers
26 views

How many bit strings of length $7$ either begin with two $1's$ or end with three $1's$?

So for the first case (beginning with 2 $1's$) there are: $2*2*2*2*2=32$ ways Second case (end with three $1's$): $2*2*2*2=16$ And then we can just sum it $32+16=48$ different bit string of length 7 ...
0
votes
2answers
12 views

Combinations questions

a. How many different 4 letter codes can there be? b. What if letters cannot be repeated? c. What if, in addition, 2 of the letters are x and y? For a, it would simply be $26*26*26*26=456976$ For ...
1
vote
1answer
15 views

Question over combinations

A t-shirt is being sold in 8 colors, 4 sizes, collared or tee, and long sleeve or short sleeve. a. How many different shirts are being sold? b. What if collared shirts only come in 5 colors and 2 ...
0
votes
0answers
7 views

How many partitions of $N$ are there into $n$ non-negative parts $c_k$ such that $\sum_{k=1}^n c_k = N$ and $\sum_{k=1}^n kc_k = M$??

So when coming up with a recursive solution to a counting problem of placing 1's into an $N \times N$ matrix ($N$ even) so that every row and every column has exactly $N/2$ 1's, my recursive ...
0
votes
2answers
22 views

permutation with four fixed numbers [on hold]

My problem appeared to be part of permutation but not sure. I have a fixed length of 4 digits with 2 variable digits. say i have ...
0
votes
1answer
59 views

Number of surjective functions from $\{1,2,…,n\}$ to $\{a,b,c\}$

Ok so following questions are given in my text book Let $A = \{1, 2, 3,...., n\}$ and $B =\{a, b, c\}$ then the number of functions form $A$ to $B$ that are onto is. I have no idea how to find ...
3
votes
0answers
29 views

A question on combinations of a set of numbers

I have the set of the first $n$ primes $\{2,3,5,\ldots,p_n\}$. There are $n^n$ ways of selecting $n$ numbers from this set. Each combination has a number ($C_k$) associated with it and it is the ...
1
vote
3answers
42 views

Error solving “stars and bars” type problem

I have what I thought is a fairly simple problem: Count non-negative integer solutions to the equation $$x_1 + x_2 + x_3 + x_4 + x_5 = 23$$ such that $0 \leq x_1 \leq 9$. Not too hard, right? ...