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
0answers
4 views

Algorithm: Integer vectors with equal inproduct with a constant vector

Given vector $\vec{a} \in \mathbb{Z}^{n}$ and constants $D, e \in \mathbb{Z}$, I need to find all vectors $\vec{x}\in \mathbb{Z}^{n}$ such that $e \geq x_{i} \geq -e$ and $\vec{x} \cdot \vec{a} = D$ ...
0
votes
0answers
15 views

Determing sequence from its Dirichlet series

Suppose I know the Dirchlet series $$\sum_{n=1}^{\infty} \frac{f(n)}{n^s} = \frac{\zeta(s)}{\zeta(3s)},$$ where $\zeta(s)$ is the usual Riemann zeta function. My question is - is there a way to ...
1
vote
0answers
11 views

Number of all labeled, unordered rooted trees with $n$ vertices and $k$ leaves.

I've been trying to do the following exercise: The problem Find the number of all labeled, unordered rooted trees with $n$ vertices and $k$ leaves. I know that I should try to write an ...
2
votes
3answers
88 views

A Problem of Combinatorics

In how many ways can three distinct numbers be chosen from the set {1,2,3,4....2n} such that the numbers are in increasing arithmetic progression?
1
vote
1answer
26 views

Interesting combinatorics problem

How can u solve this problem relatively quickly using combinatorics? I found it really interesting Let A be the set of all 4 digit numbers $a_1a_2a_3a_4$ (these are the digits) where $a_1< ...
0
votes
0answers
18 views

Combinations and Permutations. integer solutions

(a) How many integer solutions are there to the equation $x + y + z = 15$ if (i) $x$, $y$, $z$ are non-negative? (ii) $x$, $y$, $z$ are positive? (iii) $x$, $y$, $z$ are non-negative and $z \leq 5$? ...
0
votes
1answer
13 views

permutations and combination

How many different strings of lights can be created by placing 40 coloured lights on a horizontal string if 12 of them are red, 6 are blue, 14 are green and 8 are yellow? Assume that lights of the same ...
2
votes
3answers
83 views

Sum of binomial coefficients with three variables

What's the sum of coefficients of $(a+b+c)^8$? Thanks in advance!
0
votes
1answer
9 views

Bridge hand Combination/Permutation

A Bridge hand consists of 13 cards from a deck of 52 cards. In how many ways can a (bridge) hand consisting of 5 spades(♠), 4 hearts(♥), 4 diamonds(♦) and 0 clubs(♣) be selected?
1
vote
1answer
17 views

Two combinatorics questions

I would like help on these questions please: 1). How many numbers between 1 and 99999 have a digit sum of 7? 2). How many numbers between 1 and 100 are prime? In 1 I thought of representing all ...
0
votes
1answer
18 views

Probability Discrete Math

{1,2,3,4,5,6,7,8,9} What is the probability that the sum of any of these three numbers is odd? I know that I should use $ n \choose k $ somehow and I know that my professor used this as his equation: ...
0
votes
2answers
23 views

Preliminaries: Combinatorial Analysis [on hold]

There are 5 women and 7 men, how many different committees consisting of 2 women and 3 men can be formed? What if 2 of the men are feuding and refuse to be on the committee together?
1
vote
1answer
54 views

combinatorial proof $\sum_{i=0}^m x^i=\frac{x^{m+1}-1}{{x-1}}$

I would like a proof by counting two ways that for positive integers $x,m $ we have $\sum_{i=0}^m x^i=\frac{x^{m+1}-1}{{x-1}}$
1
vote
0answers
31 views

Deriving the formula for derangements: $\text{Round}\left[\frac{n!}{e}\right]$ [duplicate]

I saw on wikipedia that a formula for derangements is $\text{Round}\left[\frac{n!}{e}\right]$ However, how did they arrive at this elegant formula? Does it have to do with $ !n=n! \sum _{k=0}^n ...
2
votes
1answer
19 views

In how many ways can letters in mathematics be ordered with restrictions?

I've been stuck on these for a while. Please guide me through all the steps because I actually want to understand this. I've got an exam coming up. Consider the letters in the word "MATHEMATICS". In ...
0
votes
0answers
13 views

Probability of no consecutive numbers

There are $n$ balls in a bag, and they are numbered from $1$ to $n$. Take $k$ balls out of the bag. What is the probability of that there are not two consecutive numbers? I have looked for a solution ...
0
votes
1answer
22 views

Special types of derangements?

I have the numbers {1, 2, 3, 4}. How would you find the number of arrangements in which only 3 of the numbers are in their original positions? What about only 2 in their original positions? Only 1? ...
0
votes
4answers
63 views

How to calculate $f(n)=1\binom{n}{1}+2\binom{n}{2}+3\binom{n}{3}…n\binom{n}{n}$

$$f(n)=1\binom{n}{1}+2\binom{n}{2}+3\binom{n}{3}.....n\binom{n}{n}$$ Is there a formula for this?
0
votes
1answer
25 views

Number of necessary stickers to complete a sticker album

I have the following problem, and I was hoping you guys could help me solve it: Consider a set of $t$ unique, collectable stickers (that accounts for the universe of collectable stickers, i.e., ...
0
votes
1answer
17 views

Exponential generating function for number of 10 length sequences built from the alphabet, with some restrictions

I've got the following homework question. If anybody could possibly point me in the right direction, that would be great: Suppose X is a sequence with 10 terms built from 26 letters {a, b, c, ..., ...
0
votes
1answer
20 views

Combinations and Permutations

What is the probability that a poker hand has five cards each with a different rank? P(5 cards different rank)= P(No pair)+ P(Straight)+ P(Flush) $.50118+.00197+.00392= .50707 =50.7$ percent This ...
0
votes
2answers
27 views

How many square based pyramids are in a bigger pyramids?

The biggest challenge to solve the problem is that I can't really picture a pyramid. And it is hard to make a model. The pyramids I am trying to find include those on all tiers.
0
votes
1answer
19 views

Permutations and Combinations

In a group of 30 ball bearings, 5 are defective. If 10 ball bearings are chosen at random, a) what is the probability that none of them are defective? b) what is the probability that two or more ...
1
vote
3answers
60 views

Product of “reversed” numbers

Consider any 2 binary numbers, e.g.: 10101011 ; 11111101 and their product, say P. "Reverse" (mirror image) all the digits of the 2 numbers, e.g.: ...
4
votes
3answers
45 views

Stars and bars (combinatorics) with multiple bounds

Count the number of solutions to the following: $$x_1+x_2+\cdots+x_5=45$$ when: $1$. $x_1+x_2>0$, $x_2+x_3>0$, $x_3+x_4>0$ $2$. $x_1+x_2>0$, $x_2+x_3>0$, $x_4+x_5>1$ ...
0
votes
0answers
13 views

The lower bound of Cheeger Inequality as the degree goes to infinity

Consider an undirected graph $G(V,E)$ with adjacency matrix $A$ and define the graph Laplacian as \begin{equation} L = D - A \end{equation} where $D$ is a diagonal matrix such that $D(i,i) = d_i$. ...
1
vote
2answers
25 views

Permutations and Combinations

Show that $\binom{n}{0} - \binom{n}{1} + \binom{n}{2} - ...+(-1)^k * \binom{n}{k} = (-1)^k * \binom{n-1}{k}$. I know this has to do with permutations and combination problems, but I'm not sure how ...
0
votes
2answers
59 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
13 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
53 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
20 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
27 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
23 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
21 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
47 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
22 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
59 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
30 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
47 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
24 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
52 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
73 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
28 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
19 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
44 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 ...