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)

7
votes
2answers
108 views

Number of integer triplets $(a,b,c)$ such that $a<b<c$ and $a+b+c=n$

What is an equivalent combinatorial presentation for the problem? Can I use the stars and bars approach to find the number of integral solutions of $a+b+c=n$ where $a,b,c\geq 0$? If in addition $a+b&...
0
votes
0answers
21 views

Homotopy type of some lattices with top and bottom removed

There was an interesting question on MO which OP removed by some reason. Here is a (more or less) equivalent form. Take a finite cartesian product of finite linear orders, and remove top and bottom. ...
4
votes
3answers
108 views

Books for maths olympiad

I want to prepare for the maths olympiad and I was wondering if you can recommend me some books about combinatorics, number theory and geometry at a beginner and intermediate level. I would appreciate ...
0
votes
1answer
33 views

counting number of steps using permutation-combination

We need to climb 10 stairs. At each support, we can walk one stair or you can jump two stairs. In what number alternative ways we'll climb ten stairs? How to solve this problem easily using less ...
1
vote
2answers
46 views

How many attending puppy school are brown and have long hair but are not small?

Of the 24 dogs attending puppy school -6 are small -12 are brown -15 have long hair -1 is small and brown and has long hair -2 are small and brown but their hair is not long -2 are small and have long ...
1
vote
1answer
40 views

What is the probability that a majority vote gives the correct answer, given that we know the accuracy of each of the voters?

Let's say that we have 7 voters who are voting on a decision. Furthermore, we know that voter A makes the right decision with 10% probability. voter B makes the right decision with 20% probability. ...
2
votes
2answers
52 views

How many length-$k$ strictly decreasing sequences where sum is $N$?

How many strictly decreasing sequences of length $k$ in positive integers can I find where the sum of elements is $N$? The problem can be described this way too, I have a number $N$ . Now I want ...
2
votes
0answers
22 views

Inclusion-exclusion principle for multisets

Lets say I want to count the number of monic polynomials of degree $d$ in $\mathbb{F}_p[X]$ that have no roots in $\mathbb{F}_p$. Fix a $1 \leq k \leq d$ and choose $k$ distinct elements of $\mathbb{F}...
2
votes
3answers
57 views

Number of binary strings of length $n$ satisfying specific (ad-hoc) conditions

Count the number of binary strings of length $n$ that satisfy the following additional conditions: a) Two zeroes in a row are not allowed b) Three ones in a row are not allowed c) The ...
1
vote
0answers
54 views

Combinatorics problem involving binomial coefficient

I found this interesting problem in a Romanian mathematical magazine while preparing for the USAMO. Let $k$ be a non-zero natural number. Determine $x,y,z \in \Bbb N$ such that $$\binom {z+k}{x+y} - \...
1
vote
3answers
35 views

How to prove by induction(do not use differential) $(1-x)^{-n}=\sum^{\infty}_{k=0}\binom{n-1+k}{k}x^k$

I would appreciate if somebody could help me with the following problem. Q: How to prove by induction(do not use differential) $$(1-x)^{-n}=\sum^{\infty}_{k=0}\binom{n-1+k}{k}x^k$$ I tried to solve ...
0
votes
0answers
16 views

Combinations over tree nodes

Assuming to have a generic tree, how can I calculate all the possible combinations of 1,2,3...n nodes (with n that represents the number of nodes at a certain level of the tree) that can be generated ...
1
vote
1answer
41 views

Find number $n(A)$? $A=\{(x,y,z)|x+2y+4z=n, x,y,z\in\{0,1,2,3,4,\cdots\} \}$

I would appreciate if somebody could help me with the following problem. Q: Find number $n(A)$? $$A=\{(x,y,z)|x+2y+4z=n, x,y,z\in\{0,1,2,3,4,\cdots\} \}$$ I tried to solve by $z=0,1,2,3,\cdots$ ...
2
votes
2answers
89 views

A 3-valued mathematical logic?

Classical propositional logic is consistent and in conformity with human language. A formal statement is true or not true and it is possible to develope rules with which it is possible decide which ...
1
vote
2answers
31 views

Distinct digits in a combination of 6 digits

How many 6-digit numbers contain exactly 4 different digits? My approach is: For any 3 digis same and the remaining 3 different(aaabcd) 4*9*8*7*6 For any 2 duplicate digits(aabb) and the remaining ...
2
votes
1answer
61 views

Simplify this equation.

Can I simplify or approximate this equation without sigma and combination? \begin{align} \sum_{i = 0}^n (-1)^i {n \choose i} \frac{{d+1}}{d(di + 1)} \end{align}
1
vote
2answers
76 views

Is there a closed form for this binomial sum?

I am looking for a closed form of this sum:$\sum\limits_{j=k}^n\binom{j}{k}(-1)^j$ I know that this sum has a closed form: $\sum\limits_{j=k}^n\binom{j}{k}=\binom{n+1}{k+1}$ I can get this closed ...
1
vote
2answers
47 views

in urn A white balls and B black balls. what would be the probability of taking the 5th ball being white

the problem goes like that "in urn $A$ white balls, $B$ black balls. we take out without returning 5 balls. (we assume $A,B\gt4$) what would be the probability that at the 5th ball removal, there was ...
2
votes
2answers
66 views

How many 6-digit numbers contain exactly 4 different digits? [duplicate]

my solution is----> NUMBER can be 777210 this i denote by aaabcd ------ this can be done in ---> 10*1*1*9*8*7*[6!/3!] {1 for a thrice} NUMBER can be 772210 this i ...
0
votes
0answers
30 views

Transforming generating functions into algorithms that generate combinatorial objects

I've stumbled upon this paper where they write about random sampling of combinatorial objects. For sampling to be proper one has to know some core numbers (probabilities). However, I'm not interested ...
3
votes
2answers
45 views

Help me understanding what actually i counted with inclusion-exclusion

I tried to solve following task: Count number of $8$-permutations from $2$ letters $A$, $2$ letters $B$, $2$ letters $C$ and $2$ letters $D$ where exactly one pair of same letters are adjacent in ...
0
votes
6answers
34 views

Arrangement of 12 boys and 2 girls in a row.

12 boys and 2 girls in a row are to be seated in such a way that at least 3 boys are present between the 2 girls. My result: Total number of arrangements = 14! P1 = number of ways girls can sit ...
4
votes
1answer
35 views

When is a recurrence the sum of the powers of the roots of a polynomial?

Newton's formula allows one to calculate the sum $S_n(P)$ of the $n$th powers of the roots of a given monic polynomial $P$ without finding the roots explicitly. (This works even when the roots ...
1
vote
1answer
68 views

Parity of $\sum_{i=1}^{n}\lfloor \log_2(i) \rfloor$

Let, $L=\sum_{i=1}^{n}\lfloor \log_2(i) \rfloor $. Problem: Find $n$ for which $L$ is odd. In other words, find a closed form expression (function) $f(n)$of variable $n$ such that $L$ is odd/even if ...
0
votes
1answer
56 views

Isi B.Math Fibonacci problem.

Let $\dbinom{n}{k}$ denote the binomial coefficient $\frac{n!}{k!(n-k)!}$ , and $F_m$ be the $m^{th}$ Fibonacci number given by $F_1=F_2=1$ and $F_{m+2}=F_m+F_{m+1}$ for all $m\geq 1$. Show that $\...
3
votes
1answer
51 views

Each $2\times 5$ rectangle contains $1\times 3$ rectangle

A $60\times 60$ board is partitioned into rectangles of size $2\times 5$ (or $5\times 2$). Is it true that there always exist another partition into rectangles of size $1\times 3$ (or $3\times 1$) ...
1
vote
1answer
62 views

Need to prove that there is a continuous sequence which contains 100 cup of coffee , i.e. a man drinks one cup of coffee at the day.

A man can drink at least one cup of coffee at the day. After one year he drinks 500 cup of coffee. Need to prove that there is a continuous sequence which contains 100 cup of coffee, i.e. a man drinks ...
2
votes
0answers
28 views

Number of zigzag permutations of first $n$ natural numbers given start and end value

Given $n$ and $1\le s,e\le n$, how to compute the number of zigzag permutations of first $n$ positive integers starting with $s$ and ending with $e$? I tried formulating a recurrence relation but can'...
3
votes
2answers
72 views

Rewriting product to a binomial

I'm currently researching Wigner matrices. I wanted to calculate the moments of its spectral density. The probability density is $$\frac{1}{2\pi} \sqrt{4-x^2} \text{ for } x \in [-2,2] $$ I have ...
1
vote
0answers
96 views

Joint probability with constraint [closed]

Let's say that one is conducting an experiment with 8 units and 4 units have to be assigned to treatment. Assuming all units' respective treatment assignment probabilities are greater than 0 and less ...
0
votes
1answer
50 views

Closed formula for ${r \choose 1}+{r \choose 2}\cdots{r \choose w}$ where $w < r$ [on hold]

Let $r,w \in \mathbb{N}$. Are there some formula for the next sum? $${r \choose 1}+{r \choose 2}\cdots{r \choose w}$$ where $w<r$?
0
votes
2answers
42 views

How to correctly count the probability for a computer game situation? [closed]

Imagine we have the following situation in a computer game: One player has two minions with 30 and 6 hitpoints correspondingly. Another player casts a spell which does 12 times 1 damage (for each of ...
0
votes
0answers
26 views

Distribution for playing n scratcher lottery tickets

If I know the prize distribution for a scratcher lottery ticket (i.e. the various prize amounts and the probability associated with each prize) is there a way to form a distribution for playing, say, ...
1
vote
0answers
42 views

Given N blocks, find the number of unique shapes in a NxN block

Constraints: The blocks must be adjacent to each other. i.e. A pair of blocks must have a common edge or vertex. Any shapes that are formed by flipping or rotating or mirroring should be considered to ...
2
votes
1answer
23 views

double summation of conditional variable depending on sum of integer

I am having trouble with taking a certain summation and finding an explicit value for the summation. The summation is: $$ S = \sum_{w=3}^a \lambda_w \sum_{m=w}^a \lambda_m $$ The only information ...
8
votes
0answers
95 views

How many ways can I arrange the numbers $1$ to $N$ with this divisibility condition?

For the numbers $1, \ldots, N$, how many ways can I arrange them such that either: The number at $i$ is evenly divisible by $i$, or $i$ is evenly divisible by the number at $i$. Example: for N = 2$...
1
vote
3answers
154 views

Find general solution for the equation $1 + 2 + \cdots + (n − 1) = (n + 1) + (n + 2) + \cdots + (n + r) $

A positive integer $n$ is called a balancing number if $$1 + 2 + \cdots + (n − 1) = (n + 1) + (n + 2) + \cdots + (n + r) \tag{1}$$ for some positive integer $r$. Problem: Find the general ...
2
votes
1answer
33 views

Binomial identity for bijection $\mathbb N\times\mathbb N\to\mathbb N$

In a book I'm currently reading it is said (without proof) that, for an enumeration $d$ of $\mathbb N\times\mathbb N$ defined by $$d(0)=(0,0),\ d(1)=(0,1),\ d(2)=(1,0),\ d(3)=(0,2),\ d(4)=(1,1),\ d(5)=...
4
votes
0answers
58 views

How many subsets of $n$ linearly independent binary strings of length $n$?

Let's consider binary words of length $n$ with elements {-1,1}. There are $2^n$ binary words of length $n$. Now let's consider a subset of $n$ such binary words. All possible subsets are $\binom{2^n}{...
0
votes
0answers
14 views

Noetherian Rings Definition, countability?

In my book (Jantzen, Algebra, 2014), Noetherian rings are defined by three equivalent conditions. I wonder how the first two can be equivalent: Every ascending chain of ideals $(a_1) \subset (a_2) \...
2
votes
3answers
57 views

Doubt in finding number of integral solutions

Problem : writing $5$ as a sum of at least $2$ positive integers. Approach : I am trying to find the coefficient of $x^5$ in the expansion of $(x+x^2+x^3\cdots)^2\cdot(1+x+x^2+x^3+\cdots)^3$ . ...
1
vote
2answers
35 views

Half from any $2n$ but not $2n+2$

Let $n$ be a positive integer. What is the length of the longest possible sequence of $0$'s and $1$'s such that among any $2n$ consecutive numbers, exactly half are $0$'s, but among any $2n+2$ ...
1
vote
3answers
40 views

Expected Value for Heads for Unknown Weighted Coin Given Head First Flip

This is a combinatorics problem, and I think it involves expected values and conditional probability, but I don't know how to use them: "A bag contains an infinite number of coins whose probabilities ...
0
votes
1answer
39 views

distributing numbered balls with duplicates into 4 boxes [closed]

How many ways are there to distribute 52 balls, numbered 1 to 13 with 4 duplicates for each number, into 4 distinguishable boxes.
2
votes
0answers
18 views

Finitely many steps to $n$-stone pile.

I have a combinatoric problem still unsolved: $2n$ ($n$ is a positive integer) stones are divided into $3$ piles. In each step, we pick half of a pile which has even number of stones and move those ...
0
votes
3answers
31 views

code to calculate all combinations [closed]

I have the follwing problem: I have an array u of length d. The sum of every integer of this array u should be k, and integers are from 0 to k. I want now all possible combination that suffice this ...
1
vote
4answers
50 views

Bayesian probability problem?

Problem: In a city there are three types of taxis which drive towards the airport. 30% are blue, 20% green, 50% yellow. They take there customers too late with probabilities 0.1,0.2,0.3 respectively. ...
7
votes
4answers
149 views

Maximum area of triangle inside a convex polygon

Prove that within any convex polygon of area $A$, there exists a triangle with area at least $cA$, where $c=\tfrac{3}{8}$. Are there any better constants $c$? I'm not sure how to approach this ...
0
votes
3answers
36 views

Prove that if a collection of subsets of {1,..,n} that each pair of subsets has at least one element in common, there are at most $2^{n-1}$ subsets

Full question: Prove that if a collection of subsets of {1,2,...,n} has the property that each pair of subsets has at least one element in common, then there are at most $2^{n-1}$ subsets in the ...
0
votes
2answers
57 views

In AB + BC + AC = N, how can I find all possibilities for A, B and C in less than n³ computational time?

The problem is the one on the title. Given a N, find all possibilies for A, B and C that make this true: $AB+BC+AC = N$when $A \ge B \ge C$. This code in C do the job: ...