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)

0
votes
1answer
18 views

Finding algorithm to design combinatorics formulae per input data

Problem: calculate how many unique "words" can be made using the letters of your a) name (Kateryna - 8 letters, letter 'a' used twice) b) lastname (Atamanchuk - 10 letters, letter 'a' used 3 times) ...
1
vote
2answers
24 views

Trying to find polynomial-time algorithms for knapsack-like problems

Consider two related problems: You have $n$ cannisters that must go into $m$ trucks that can each carry $k$ cannisters. You require that no truck becomes overloaded, and for each cannister, there is ...
10
votes
1answer
103 views
+50

In how many ways can $1000000$ be expressed as a product of five distinct positive integers?

I'm trying to solve the following problem: "In how many ways can the number $1000000$ be expressed as a product of five distinct positive integers?" Here is my attempt: Since $1000000 = 2^6 \cdot ...
2
votes
1answer
55 views

Combinatorics - Integer sided triangles with integer median

The original problem states: "Given a number N, how many integer-sided triangles $(a,b,c)$ with an integer median $m_{c}$ exist, provided that $a \leq b \leq c \leq N$?". I've managed to get it down ...
0
votes
1answer
24 views

Probability of choosing a combination [on hold]

A person has $8$ red pills and $8$ blue pills. He chooses $8$ pills at random. What is the probability that the chosen pills are $4$ red and $4$ blue?
3
votes
2answers
59 views

Problem in deducing the number of onto functions

Let $A, B$ have $m, n$ elements ($m > n$). Therefore, the number of onto functions from $A$ to $B$ is: $$\sum_{k = 0}^n (-1)^k \binom{n}{k} (n - k)^m.$$ How can one use the IE (Inclusion/Exclusion) ...
1
vote
1answer
27 views

Shortest grid walks which

On a grid, $G = (0,0)$, $E = (3,3)$, $F = (6,9)$, $ H = (9,6)$, $ J = (10,12)$. What is the number of shortest grid walks form G to J which: a) go through H but not E b) go through neither E nor F ...
0
votes
1answer
26 views

Question about counting cards

A standard deck of cards contains $52$ cards divided into four suits: the red suits, hearts and diamonds, and the black suits, clubs and spades. Each suit, in turn, is divided in 13 ordered ranks: ace ...
2
votes
1answer
24 views

Tower of Hanoi variation from Concrete Mathematics - possible arrangements

From Concrete Mathematics, there is a problem that describes a variation of the Towers of Hanoi, where the disks can not move directly from peg $A$ to peg $B$, but must go through a middle peg. ...
0
votes
1answer
16 views

Binomial distribution tail inequality

Let $X \sim \mathrm{Bin}(n,p)$ does there exist $l$ ideally $l=f(n)$ such that $P(X<l)=o(1)$ in the limit $n\rightarrow \infty$? I'd be looking for the largest possible $l$.
0
votes
0answers
25 views

At a step, we either increment or decrement $t$. If $|t| = x$, the program halts. What is the chance of the program still running after $n$ steps? [on hold]

We start with $t = 0$. At each step, we either increment $t$ with probability $p$ or decrement $t$ with probability $1-p$. If $|t| = x$, the program halts. What is the chance of the program still ...
34
votes
7answers
5k views

How many scientists can survive?

Yesterday the aliens took 100 scientists from Earth as prisoners. They want to test how smart the humans are. The aliens made 101 headbands, numbered from 1 to 101. On the contest day, they throw ...
3
votes
2answers
158 views

Counting permutations that respect a partial order

Suppose you have three kinds of coins, say: pennies, nickels, and dimes. Each penny has a unique date, likewise for nickels and dimes. (A penny and a nickel may have the same date, etc.) How many ways ...
0
votes
1answer
26 views

How many ways to assign 10 digits to 6 containers.

So if we had 6 containers eg (a,b,c,d,e,f) how many ways could we assign the digits 0-9 to these containers. For example one way might be: a = 4 b = 5 c = 0 d = 3 e = 8 f = 7 Is there a ...
4
votes
2answers
390 views

No closed form for the partial sum of ${n\choose k}$ for $k \le K$?

In Concrete Mathematics, the authors state that there is no closed form for $$\sum_{k\le K}{n\choose k}.$$ This is stated shortly after the statement of (5.17) in section 5.1 (2nd edition of the ...
0
votes
4answers
5k views

Math Riddle in Combinatorics.

A blind man is on a strange island and he has 2 red pills and 2 white pills, completely identical and has kept in his pockets, he needs to take 1 red pill and 1 white pill order doesn't matter. If he ...
1
vote
3answers
2k views

How to use stars and bars(combinatorics)

How to use the stars and bars method? Say I want to find number of combinations I can get with $x_1+x_2+x_3+x_4=22$ Where $x_i\in\mathbb{N}$ Is this the correct time to apply the method?
0
votes
0answers
32 views

Forbidden Positions [on hold]

How would you go about doing forbidden positions on a rectangular chessboard? For example, we have a chessboard with $9$ rows and $3$ columns. The first column has $2$ forbidden positions ($X$) in ...
2
votes
2answers
37 views

Trying to understand the formula for counting multiset permutations

In how many ways can we plant $5$ red, $3$ yellow and $2$ white flowers in a row? The answer is $\frac {10!}{(5! \cdot 3! \cdot 2!)}$. So it looks like we are dividing out the redundant ...
0
votes
0answers
16 views

How to count the number ways to place `k` identical balls in `n` bags when order matters?

I understand that to count the number of s selections from r possibilities, disregarding order, we can use the formula ...
1
vote
1answer
16 views

Use induction to figure out the number of handshakes in a party

Every arriving guest shakes hand with everybody else at a party. If there are n guests in the party, how many handshakes were there? Proof by using induction. My approach to this problem was to write ...
2
votes
0answers
22 views

computing characteristic polynomial of hyperplane arrangement

The following problem comes from Richard Stanley's $\textit{Enumerative Combinatorics}$ vol. 1, 2nd ed. It is problem 114 (c) in Chapter 3. Let $\mathcal{A}$ be a hyperplane arrangement in ...
2
votes
1answer
64 views

composition of an integer number

Given two positive integers $m$ and $n$. I would like one special non-negative solution to the following system (which is related to a composition of an integer number): $$\begin{cases} \sum a_i = m ...
1
vote
2answers
35 views

How would you go through this combination/ permutation problem

A market has 30 different pants and 12 different hats. You want to to get 3 different pants and 2 different hats. How many ways can you make this purchase? I assume this is a combination, but stuck ...
0
votes
3answers
423 views

How would I prove this strange combinatorial identity?

I came across a combinatorial identity today but have no idea how to handle the $\frac{1}{i+1}$ term: $$\sum_{i=0}^m {m \choose i} (-1)^i \frac{1}{i+1} = \frac{1}{m+1}$$ How would I prove it?
-4
votes
0answers
28 views

Finding the modulo of 801 [on hold]

If $d_{k}(m)$ is the number of divisor of m that are congruent to $k$ modulo $4$. How can I find $d_{1}(801)$ and $d_{3}(801)$ .
0
votes
0answers
11 views

Help needed for statistical analysis of pitch class sets

Within Music Analysis, there is a quite mathematical type of analysis which looks at pitch class sets ($pcs$), not surprisingly known as pitch class set analysis. See ...
0
votes
2answers
37 views

Probability to get from point A to point B.

In the photo each dot is a city and each blue segment a road. Each road is blocked with probability 1/3 and free with probability 2/3 (independence among all roads). What is the probability that it is ...
0
votes
0answers
11 views

Self-Avoiding Walk incorporating diagonals

How many paths are there between $(0,0)$ and $(n,n)$ if you include all eight common cardinal directions: North, East, South, West, Northeast, Northwest, Southeast, and Southwest. The only condition ...
2
votes
2answers
19 views

Proving cycles in graph

I have the problem: Let $d>1$ be an integer. Prove that if every vertex of a graph $G$ has degree at least d, then G contains a cycle of length at least $d + 1$. I'm pretty sure this can be done ...
2
votes
2answers
20 views

Number of Partitions in which the Two Largest Parts are Equal

Show that for any positive integer $n$, the number of partitions of $n$ in which the two largest parts are equal is $p(n) − p(n − 1)$. What I have so far: We can construct a bijection from the set ...
4
votes
1answer
42 views

Permutations and Combinations exam question

Before I proceed with my queries I think it's best to present the question at hand. A class consisting of 4 males and 12 females in randomly divided into 4 groups of 4. What is the probability ...
0
votes
1answer
12 views

Applying multiplication principle to counting subsets

In my textbook MP is strictly reserved to counting lists. Does what I do below to count subsets work? Consider $3$ men(Ace, Bob, Corry) and $3$ women(Ann, Beth, Candace). Suppose we need to choose a ...
0
votes
0answers
20 views

Lower bound for the chromatic number of $\mathbb{R}^n$

I'm going through a proof that of the following lower bound for the chromatic number of $\mathbb{R}^n$: $$\chi(\mathbb{R}^n) \geq (1.2 + o(1))^n$$ At some point in the proof we get that ...
3
votes
3answers
125 views

Find the number of ways to form 15 teams out of 15 men and 15 women.

In how many ways can 15 teams be formed, each consisting of a man and a woman, from 15 men and 15 women. This looks like the same problem as finding the number of bijective functions from a set $A$ ...
3
votes
1answer
19 views

Selecting “either representative” Permutation

A Chess club consisting of $14$ Math majors, $11$ EE majors and $11$ CS majors. In how many ways can the club select a president and vice president if either the president or the vice president must ...
-6
votes
2answers
152 views

Pixel Permutations

How many possible arrangements of pixels can a 1024x768 pixel screen display if the color of a pixel is determined by mixing 3 values: red, green, and blue, ranging from an intensity of 0 to 255? The ...
0
votes
1answer
20 views

Representing a positive $x$ with a generating function

If we want to find the integer solutions of $x_1+x_2+x_3=n$ such that $x_1$ is positive using a generating function. We would first make the parentheses for each $x_i$, for $x_{2,3}$ it would be the ...
2
votes
1answer
28 views

How to deduce the formula “distribution” in groups? What is the difference between “distribution” & “arrangement”?

The number of ways in which $n$ different things can be distributed into $r$ different groups is $$r^n - \binom{r}{1} (r - 1)^n + \binom{r}{2} (r - 2)^n + \ldots + (- 1)^{r - 1} \binom{r}{r - 1}$$. ...
0
votes
3answers
168 views

In a bit string of length 11, how do you find the probability of even number of zeros?

I thought about doing the complement but I wasn't sure if that was correct. Or add up the different cases that there is an even number of 0's as the probability?
2
votes
2answers
31 views

binomial sum binomial (a + k , a)

Anyone know a way to compute such a sum : $$S = \sum_{k=0}^{n}\binom{a+k}{a} $$ I encountered this sum in a problem in which $a=7, n=7$. In this case the sum can be computed by hand, but I was ...
2
votes
1answer
39 views

$2n+1$ real numbers with equal sums [duplicate]

Suppose we have $2n+1$ real numbers. If we remove any of these numbers we can separate the remaining $2n$ numbers in two groups of $n$ numbers with equal sums. Show that all these numbers are equal.
0
votes
1answer
38 views

Recurrence relation for a mortgage

Find a recurrence relation for the amount of money outstanding on a \$40,000 mortgage after n years. The interest rate on the mortgage is 10% and the yearly payment is \$2,000( the yearly payment is ...
5
votes
2answers
101 views

Optimal scheduling dilemma (A textbook math problem IRL)?

I am trying to solve a scheduling problem for a boys camp. I have 12 teams(A through L), 6 sports for them to play, and 6 periods for them to play in(P1 through P6). ...
1
vote
2answers
267 views

Proof of recursive formula for Catalan numbers, and their interpretation as the number of paths

If $C_n$ is the $n$th Catalan number, then show that they satisfy the following recurrence: $$C_0 = 1,\quad C_{n+1} = C_0C_n + C_1C_{n−1}+ \cdots + C_kC_{n−k} + \cdots + C_nC_0\text{ ?}$$ I tried ...
2
votes
1answer
28 views

How to deduce the formula for arrangement in groups?

The number of ways in which $n$ different things can be arranged into $r$ different groups is $$n! \cdot \dbinom{n - 1}{r - 1} $$. This is the quote from my book. However, it didn't offer any ...
2
votes
3answers
34 views

Steiner Triple System

A Steiner Triple System, denoted by $STS(v),$ is a pair $(S,T)$ consisting of a set $S$ with $v$ elements, and a set $T$ consisting of triples of $S$ such that every pair of elements of $S$ appear ...
1
vote
1answer
654 views

Given n girls and boys how many ways are there to arrange them such that any two boys have atleast 'k' girls between them.

Professor X wants to position $1 \leq N \leq 100,000$ girls and boys in a single row to present at the annual fair. Professor has observed that the boys have been quite pugnacious lately; if two ...
2
votes
1answer
98 views
+100

Minimizing over partitions $f(\lambda) = \sum \limits_{i = 1}^N |\lambda_i|^4/(\sum \limits_{i = 1}^N |\lambda_i|^2)^2$

I'm trying to characterize the behavior of the the quantity: $$A = \frac{\sum \limits_{i = 1}^N x_i^4}{(\sum \limits_{i = 1}^N x_i^2)^2},$$ subject to the constraints that $$ \sum \limits_{i = 1}^N ...
2
votes
1answer
46 views

How many odd numbers can be formed using the digits $0, 4, 5, 7$?

How many odd numbers can be formed using digits $0,4,5,7$. I am getting answer $12$ but the actual answer is $14$.